計算機操作系統(tǒng)啟發(fā)式教學研究

1、計算機操作系統(tǒng)啟發(fā)式教學研究計算機操作系統(tǒng)啟發(fā)式教學研究操作系統(tǒng)是計算機相關專業(yè)的一門核心專業(yè)課，而實時調度算法是操作系統(tǒng)課程中的一個重要內容，在多數的操作系統(tǒng)教科書中主要介紹了兩種實時調度算法，即最早截止時間優(yōu)先算法EarliestDeadlineFirst，EDF和最低松弛度優(yōu)先算法LeastLaxityFirst，LLF。這兩個算法看上去并不難理解，然而問題往往并不像看起來那樣簡單。事實上，在操作系統(tǒng)的教學中有一個很大的困難，即操作系統(tǒng)的教學不易落到實處，即原理容易講，但要讓學生體驗這些原理卻并不容易。操作系統(tǒng)課程中涉及大量算法，如進程調度算法、死鎖防止算法、頁面置換算法等。外表上這些算

2、法看起來比擬容易，但要讓學生理解算法后面蘊含的深化道理，并從這些算法中發(fā)現一些問題就絕非易事了。對于這個困難，我們希望通過一些啟發(fā)式的教學設計，引導學生從程序員、從算法設計者的角度去分析和考慮算法中的一些問題，從而將抽象的原理轉化為詳細的問題和解決方案，加深對這些原理的理解。下面結合實時調度算法的例子來闡述對于啟發(fā)式教學設計的考慮。1實時調度算法的啟發(fā)式教學設計1.1調度算法問題定義很多操作系統(tǒng)教科書中都介紹了兩個重要的實時調度算法，一個是EDF，另一個是LLF。這兩個實時調度算法的調度準那么都很簡單，課堂講授時本文由論文聯盟.Ll.搜集整理學生并不難理解。然而，這兩個不同的調度算法在應用中的

3、效果如何，教科書中并沒有給出進一步的分析和討論。事實上，這是一個很好的啟發(fā)式教學的切入點，我們就從這里出發(fā)來設計問題。首先來看一看EDF算法和LLF算法的思想。EDF算法是根據任務的開場截止時間來確定任務的優(yōu)先級。截止時間愈早，其優(yōu)先級愈高。該算法要求在系統(tǒng)中保持一個實時任務就緒隊列，該隊列按各任務截止時間的早晚排序；當然，具有最早截止時間的任務排在隊列的最前面。調度程序在選擇任務時，總是選擇就緒隊列中的第一個任務，為之分配處理機，使之投入運行。截止時間可以是開場截止時間，也可以是完成截止時間。一般來說，完成截止時間等于開場截止時間加上任務處理時間。LLF算法是根據任務緊急或松弛的程度，來確定

4、任務的優(yōu)先級。任務的緊急程度越高，越優(yōu)先執(zhí)行。例如，一個任務在200s時必須完成，而它本身所需的運行時間就有100s，因此，該任務的緊急程度松弛程度為100s。又如，另一任務在400s時必須完成，它本身需要運行150s，那么其松弛程度為250s。調度程序總是選擇就緒隊列中松弛度最小的任務執(zhí)行。LLF算法主要采用搶占調度方式。1.2發(fā)現問題按照教科書的描繪和給出的例如，在LLF算法中，當有新任務到達時，并不馬上比擬當前所有任務的松弛度包括正在執(zhí)行的任務，而是等到某個在等待的任務的松弛度降為零才進展切換，即選擇這個松弛度已經降為零的任務運行。按照這個原那么，我們在啟發(fā)式教學設計中提出的第一個問題。

5、第一個問題：按照教科書給出的LLF算法調度原那么，是否會存在不可調度的情況？經過分析，很容易找出問題，如圖1中給出的例如。通過上面的例如可知，在某些情況下，當某個任務在執(zhí)行過程中，假設某個或某些正在等待的任務的松弛度減至0s，那么可能會導致任務無法成功調度，而實際上系統(tǒng)才能是允許成功調度的。1.3提出改良針對前面提出的問題，可以引導學生對LLF算法的調度準那么進展改良。通常比擬容易想到的改良是，修正松弛度的計算和任務切換時機，即松弛度不需要隨時計算，而在如下兩種情況時進展計算：1當前任務正在執(zhí)行時新任務到達，可能會引起搶占和任務切換，此時需要計算并比擬松弛度；2當前任務完成時可能會引起新的任務

6、調度和切換，此時計算松弛度。進程在執(zhí)行時松弛度會不斷變化，但是不用進展跟蹤計算和比擬。修正后，可以對學生提出第二個問題。第二個問題：修正后的LLF算法，是否存在著不可調度的情況？答復仍然是存在問題，可以看一看圖2中給出的另一個例如。1.4證明猜測假設發(fā)現改良后的LLF算法還是存在問題，這時可以引導學生再作改良，并進展討論。事實上，無論如何改良LLF的調度和切換時機，都無法解決問題。那么我們可以引導學生逐步轉到EDF算法上來，即EDF算法也會存在類似問題嗎？因此我們提出的第三個問題如下。第三個問題：按照完成截至時間調度的EDF算法，是否存在不可調度的情況？通過啟發(fā)學生尋找反例會發(fā)現無法找到反例，

7、這時學生也許會想到，EDF是一個最優(yōu)的算法，即可以得出以下的猜測。猜測：給定一系列的任務，只要這些任務是可調度的，即存在某種序列使得所有任務都在完成截至時間之前完成，那么使用EDF算法一定能成功調度這些任務。有了猜測，如何證明呢？這顯然要比設計反例困難得多。我們可以引導學生深化研究這個問題，這逐步進人了這個實驗的關鍵局部，即發(fā)現問題，以及問題背后的問題，給出猜測，并分析和證明自己的猜測。對此，我們也給出了這個猜測的一個證明。證明：1假設一系列任務是可調度的，并且安排出來的任務調度順序不等同于EDF算法所安排的序列。2那么，此安排順序中至少有兩個任務A、B，其中A的截止時間比B的早，但A安排在B

8、后面如圖3a所示。那么只需將B移至A后面一位即可如圖3b所示。3在之前的序列中A沒有超時，那么移走B，A更不會超時；而B的新位置的完成時刻等于原來序列時A的完成時刻；而A的截止時刻小于B的截止時刻，所以B肯定不會超時。4重復以上過程，可以得到一個符合EDF規(guī)那么的任務序列。所以EDF一定能找到成功序列。證明了按完成截止時間調度的EDF算法的最優(yōu)性之后，還可以啟發(fā)學生進一步考慮，假設是按開場截止時間調度的EDF算法，會有什么不同嗎？另外，EDF算法和LLF算法之間有什么聯絡嗎？通過進一步分析和比擬可以得到下面的結論。EDF算法和LLF算法的比擬結論：按開場截止時間調度的EDF算法并不能像按完成截

9、止時間調度的EDF算法那樣得到最優(yōu)的結果。事實上，按開場截止時間調度的EDF算法的調度結果和按LLF算法的調度結果是一樣的。也就是說，給定一個任務序列，按開場截止時間排序的結果和按松弛度排序的結果是一樣的。證明：因為開場截止時間和松弛度分別滿足如下關系。開場截止時間=完成截止時間-運行時間松弛度=完成截止時間-當前時間-運行時間比擬式和式可得：松弛度=開場截止時間-當前時間注意到對所有任務來說，其當前時間都是一樣的，因此將任務按開場截止時間排序和按松弛度排序得到的結果是一樣的。這同時也就說明了，假設按松弛度優(yōu)先進展調度無法得到最優(yōu)的結果，那么按開場截止時間調度的EDF算法也無法得到最優(yōu)結果。1

10、.5新的問題通過上面的證明可知，假設給出的一系列任務是可調度的，那么使用按完成截止時間調度的EDF算法一定可以成功調度這些任務，在這種意義下EDF是一個最優(yōu)的算法。但是我們還可以再啟發(fā)學生作進一步的考慮。假設給出的一系列任務是不可能全部調度成功的，那么EDF還是最優(yōu)的嗎？當然，需要重新定義最優(yōu)的標準。這自然就得出下面這個新的問題。第四個問題：假設當前存在n個任務，用i表示1in，下同，每個任務包含三個參數，一是任務的運行時間ti，第二個是任務的完成截止時間di，第三個是成功安排該任務可以獲得的收益ri。請問按EDF進展調度能獲得最大收益嗎？假設不能，請設計一個調度算法使得最終的調度能獲得最大收

11、益。對于這個問題可以引導學生進展討論。事實上，這個問題要困難得多，運用一些直觀、樸素的原那么很難得到理想的解決方案。對此，可引導學生進一步運用算法和最優(yōu)化方法中的一些技巧來分析該問題。下面是運用動態(tài)規(guī)劃來求解該問題的一個方案。第四個問題的動態(tài)規(guī)劃分析：1首先可以考慮的是，我們的目的是在n個任務中選取假設干個任務來獲得最大收益，假設選出了這些任務即這些被選中的任務是可以安排好的，那么可以按照EDF的規(guī)那么來安排執(zhí)行，即把被選出的任務按各自的完成截止時間排序，那么這些任務一定都可以在各自的完成截止時間之內完成，這就是前面的猜測證明的結論。所以我們可以考慮將所有的n個任務按完成截止時間排序。假設按完

12、成截止時間排好序后的n個任務用1，2，n表示。2其次考慮，在n個任務中選取假設干個任務來獲得最大收益，與在n-1個任務中選取假設干個任務來獲得最大收益之間有什么關系？可以看出，按完成截止時間排序后的第n個任務n假設不在最終選定的假設干個任務之列，那么問題可以轉化為在n-1個任務，即1，2，n-1中選取最優(yōu)的任務序列；假設任務n在最終選定的假設干個任務之列，那么問題可以轉化為在截止時間T-tn之前，從1，2，n-1。中選取最優(yōu)的任務序列。假設用fn，dn表示在截止時間dn前，從n個任務中選取滿足條件的最優(yōu)序列所獲得的最大收益，那么可以得到如下的遞歸表達式：3根據遞歸式可以很容易地寫出一個自底向上的動態(tài)規(guī)劃算法，其時間復雜度為nT。其實，遞歸式與0/1背包問題動態(tài)規(guī)劃求解的遞歸式極其相似，求解的時間復雜度也類似。所以提出的第四個問題是一個NP完全問題。2結語從前面的啟發(fā)式教學設計中可以看出，通過精心的教學設計，安排一些具有啟發(fā)性的問題，可以有效地引導學生深化