摘要：在教學實踐中“操作系統(tǒng)”的教學不易落到實處，即原理容易講，但要讓學生“體驗”這些原理卻并不容易。文章通過一個啟發(fā)式教學設(shè)計的實例，闡述對于該問題的一些思考。

關(guān)鍵詞：啟發(fā)式教學；實時調(diào)度；操作系統(tǒng)；最早截至時間優(yōu)先；最低松弛度優(yōu)先

文章編號：1672-5913（2013）03-0062-04

中圖分類號：G642

“操作系統(tǒng)”是計算機相關(guān)專業(yè)的一門核心專業(yè)課，而實時調(diào)度算法是“操作系統(tǒng)”課程中的一個重要內(nèi)容，在多數(shù)的“操作系統(tǒng)”教科書中主要介紹了兩種實時調(diào)度算法，即最早截止時間優(yōu)先算法（Earliest Deadline First，EDF）和最低松弛度優(yōu)先算法（Least Laxity First，LLF）。這兩個算法看上去并不難理解，然而問題往往并不像看起來那樣簡單。事實上，在操作系統(tǒng)的教學中有一個很大的困難，即操作系統(tǒng)的教學不易落到實處，即原理容易講，但要讓學生“體驗”這些原理卻并不容易。操作系統(tǒng)課程中涉及大量算法，如進程調(diào)度算法、死鎖避免算法、頁面置換算法等。表面上這些算法看起來比較容易，但要讓學生理解算法后面蘊含的深刻道理，并從這些算法中發(fā)現(xiàn)一些問題就絕非易事了。

對于這個困難，我們希望通過一些啟發(fā)式的教學設(shè)計，引導(dǎo)學生從程序員、從算法設(shè)計者的角度去分析和思考算法中的一些問題，從而將抽象的原理轉(zhuǎn)化為具體的問題和解決方案，加深對這些原理的理解。下面結(jié)合實時調(diào)度算法的例子來闡述對于啟發(fā)式教學設(shè)計的思考。

1 實時調(diào)度算法的啟發(fā)式教學設(shè)計

1.1調(diào)度算法問題定義

很多“操作系統(tǒng)”教科書中都介紹了兩個重要的實時調(diào)度算法，一個是EDF，另一個是LLF。這兩個實時調(diào)度算法的調(diào)度準則都很簡單，課堂講授時學生并不難理解。然而，這兩個不同的調(diào)度算法在應(yīng)用中的效果如何，教科書中并沒有給出進一步的分析和討論。事實上，這是一個很好的啟發(fā)式教學的切入點，我們就從這里出發(fā)來設(shè)計問題。首先來看一看EDF算法和LLF算法的思想。

EDF算法是根據(jù)任務(wù)的開始截止時間來確定任務(wù)的優(yōu)先級。截止時間愈早，其優(yōu)先級愈高。該算法要求在系統(tǒng)中保持一個實時任務(wù)就緒隊列，該隊列按各任務(wù)截止時間的早晚排序；當然，具有最早截止時間的任務(wù)排在隊列的最前面。調(diào)度程序在選擇任務(wù)時，總是選擇就緒隊列中的第一個任務(wù)，為之分配處理機，使之投入運行。截止時間可以是開始截止時間，也可以是完成截止時間。一般來說，完成截止時間等于開始截止時間加上任務(wù)處理時間。

LLF算法是根據(jù)任務(wù)緊急（或松弛）的程度，來確定任務(wù)的優(yōu)先級。任務(wù)的緊急程度越高，越優(yōu)先執(zhí)行。例如，一個任務(wù)在200ms時必須完成，而它本身所需的運行時間就有100ms，因此，該任務(wù)的緊急程度（松弛程度）為100ms。又如，另一任務(wù)在400ms時必須完成，它本身需要運行150ms，則其松弛程度為250ms。調(diào)度程序總是選擇就緒隊列中松弛度最小的任務(wù)執(zhí)行。LLF算法主要采用搶占調(diào)度方式。

1.2發(fā)現(xiàn)問題

按照教科書的描述和給出的示例，在LLF算法中，當有新任務(wù)到達時，并不馬上比較當前所有任務(wù)的松弛度（包括正在執(zhí)行的任務(wù)），而是等到某個在等待的任務(wù)的松弛度降為零才進行切換，即選擇這個松弛度已經(jīng)降為零的任務(wù)運行。按照這個原則，我們在啟發(fā)式教學設(shè)計中提出的第一個問題。

第一個問題：按照教科書給出的LLF算法調(diào)度原則，是否會存在不可調(diào)度的情況？

經(jīng)過分析，很容易找出問題，如圖1中給出的示例。

通過上面的示例可知，在某些情況下，當某個任務(wù)在執(zhí)行過程中，若某個（或某些）正在等待的任務(wù)的松弛度減至0s，則可能會導(dǎo)致任務(wù)無法成功調(diào)度，而實際上系統(tǒng)能力是允許成功調(diào)度的。

1.3提出改進

針對前面提出的問題，可以引導(dǎo)學生對LLF算法的調(diào)度準則進行改進。通常比較容易想到的改進是，修正松弛度的計算和任務(wù)切換時機，即松弛度不需要隨時計算，而在如下兩種情況時進行計算：

1）當前任務(wù)正在執(zhí)行時新任務(wù)到達，可能會引起搶占和任務(wù)切換，此時需要計算并比較松弛度；

2）當前任務(wù)完成時可能會引起新的任務(wù)調(diào)度和切換，此時計算松弛度。

進程在執(zhí)行時松弛度會不斷變化，但是不用進行跟蹤計算和比較。

修正后，可以對學生提出第二個問題。

第二個問題：修正后的LLF算法，是否存在著不可調(diào)度的情況？

回答依然是存在問題，可以看一看圖2中給出的另一個示例。

1.4證明猜想

若發(fā)現(xiàn)改進后的LLF算法還是存在問題，這時可以引導(dǎo)學生再作改進，并進行討論。事實上，無論如何改進LLF的調(diào)度和切換時機，都無法解決問題。那么我們可以引導(dǎo)學生逐步轉(zhuǎn)到EDF算法上來，即EDF算法也會存在類似問題嗎？因此我們提出的第三個問題如下。

第三個問題：按照完成截至時間調(diào)度的EDF算法，是否存在不可調(diào)度的情況？

通過啟發(fā)學生尋找反例會發(fā)現(xiàn)無法找到反例，這時學生也許會想到，EDF是一個最優(yōu)的算法，即可以得出以下的猜想。

猜想：給定一系列的任務(wù)，只要這些任務(wù)是可調(diào)度的，即存在某種序列使得所有任務(wù)都在完成截至時間之前完成，則使用EDF算法一定能成功調(diào)度這些任務(wù)。

有了猜想，如何證明呢？這顯然要比設(shè)計反例困難得多。我們可以引導(dǎo)學生深入研究這個問題，這逐步進人了這個實驗的關(guān)鍵部分，即發(fā)現(xiàn)問題，以及問題背后的問題，給出猜想，并分析和證明自己的猜想。

對此，我們也給出了這個猜想的一個證明。

證明：

1）假設(shè)一系列任務(wù)是可調(diào)度的，并且安排出來的任務(wù)調(diào)度順序不等同于EDF算法所安排的序列。

2）那么，此安排順序中至少有兩個任務(wù)A、B，其中A的截止時間比B的早，但A安排在B后面（如圖3（a）所示）。則只需將B移至A后面一位即可（如圖3（b）所示）。

3）在之前的序列中A沒有超時，則移走B，A更不會超時；而B的新位置的完成時刻等于原來序列時A的完成時刻；而A的截止時刻小于B的截止時刻，所以B肯定不會超時。

4）重復(fù)以上過程，可以得到一個符合EDF規(guī)則的任務(wù)序列。所以EDF一定能找到成功序列。

證明了按完成截止時間調(diào)度的EDF算法的最優(yōu)性之后，還可以啟發(fā)學生進一步思考，若是按開始截止時間調(diào)度的EDF算法，會有什么不同嗎？另外，EDF算法和LLF算法之間有什么聯(lián)系嗎？

通過進一步分析和比較可以得到下面的結(jié)論。

EDF算法和LLF算法的比較結(jié)論：按開始截止時間調(diào)度的EDF算法并不能像按完成截止時間調(diào)度的EDF算法那樣得到最優(yōu)的結(jié)果。事實上，按開始截止時間調(diào)度的EDF算法的調(diào)度結(jié)果和按LLF算法的調(diào)度結(jié)果是一樣的。也就是說，給定一個任務(wù)序列，按開始截止時間排序的結(jié)果和按松弛度排序的結(jié)果是一樣的。

證明：因為開始截止時間和松弛度分別滿足如下關(guān)系。

開始截止時間=完成截止時間-運行時間①松弛度=完成截止時間-當前時間-運行時間②

比較式①和式②可得：

松弛度=開始截止時間-當前時間

注意到對所有任務(wù)來說，其“當前時間”都是一樣的，因此將任務(wù)按開始截止時間排序和按松弛度排序得到的結(jié)果是一樣的。這同時也就說明了，若按松弛度優(yōu)先進行調(diào)度無法得到最優(yōu)的結(jié)果，那么按開始截止時間調(diào)度的EDF算法也無法得到最優(yōu)結(jié)果。

1.5新的問題

通過上面的證明可知，若給出的一系列任務(wù)是可調(diào)度的，則使用按完成截止時間調(diào)度的EDF算法一定可以成功調(diào)度這些任務(wù)，在這種意義下EDF是一個最優(yōu)的算法。但是我們還可以再啟發(fā)學生作進一步的思考。若給出的一系列任務(wù)是不可能全部調(diào)度成功的，那么EDF還是“最優(yōu)”的嗎？當然，需要重新定義“最優(yōu)”的標準。這自然就得出下面這個新的問題。

第四個問題：假設(shè)當前存在n個任務(wù)，用m表示（1≤i≤n，下同），每個任務(wù)包含三個參數(shù)，一是任務(wù)的運行時間t，第二個是任務(wù)的完成截止時間d，第三個是成功安排該任務(wù)可以獲得的收益r。請問按EDF進行調(diào)度能獲得最大收益嗎？若不能，請設(shè)計一個調(diào)度算法使得最終的調(diào)度能獲得最大收益。

對于這個問題可以引導(dǎo)學生進行討論。事實上，這個問題要困難得多，運用一些直觀、樸素的原則很難得到理想的解決方案。對此，可引導(dǎo)學生進一步運用算法和最優(yōu)化方法中的一些技巧來分析該問題。下面是運用動態(tài)規(guī)劃來求解該問題的一個方案。

第四個問題的動態(tài)規(guī)劃分析：

1）首先可以考慮的是，我們的目標是在n個任務(wù)中選取若干個任務(wù)來獲得最大收益，若選出了這些任務(wù)（即這些被選中的任務(wù)是可以安排好的），則可以按照EDF的規(guī)則來安排執(zhí)行，即把被選出的任務(wù)按各自的完成截止時間排序，則這些任務(wù)一定都可以在各自的完成截止時間之內(nèi)完成，這就是前面的猜想證明的結(jié)論。所以我們可以考慮將所有的n個任務(wù)按完成截止時間排序。假設(shè)按完成截止時間排好序后的n個任務(wù)用m，m，…，m表示。

2）其次考慮，在n個任務(wù)中選取若干個任務(wù)來獲得最大收益，與在n-1個任務(wù)中選取若干個任務(wù)來獲得最大收益之間有什么關(guān)系？可以看出，按完成截止時間排序后的第n個任務(wù)m若不在最終選定的若干個任務(wù)之列，則問題可以轉(zhuǎn)化為在n-1個任務(wù)，即m，m，…，m中選取最優(yōu)的任務(wù)序列；若任務(wù)m在最終選定的若干個任務(wù)之列，則問題可以轉(zhuǎn)化為在截止時間T-t之前，從m，m，…，m。中選取最優(yōu)的任務(wù)序列。若用f（n，d）表示在截止時間d前，從n個任務(wù)中選取滿足條件的最優(yōu)序列所獲得的最大收益，則可以得到如下的遞歸表達式：

3）依據(jù)遞歸式③可以很容易地寫出一個自底向上的動態(tài)規(guī)劃算法，其時間復(fù)雜度為O（n×T）。其實，遞歸式③與0/1背包問題動態(tài)規(guī)劃求解的遞歸式極其相似，求解的時間復(fù)雜度也類似。所以提出的第四個問題是一個NP完全問題。

2 結(jié)語

從前面的啟發(fā)式教學設(shè)計中可以看出，通過精心的教學設(shè)計，安排一些具有啟發(fā)性的問題，可以有效地引導(dǎo)學生深入思考問題背后的問題，從而加深對一些原理的理解，把握其中的本質(zhì)。通過提出問題和猜想，引導(dǎo)學生深入研究。啟發(fā)式的教學不僅可以讓學生更深刻地理解系統(tǒng)原理，同時對于培養(yǎng)學生的邏輯思維能力，培養(yǎng)獨立思考的習慣都有著重要的意義。在某些問題的設(shè)計上，適當引入一些研究性的思路，對學生提出更高的要求，而不僅僅局限在教材上，有利于培養(yǎng)學生的鉆研精神和探索精神，為今后的學習和工作打下堅實的基礎(chǔ)，培養(yǎng)良好的習慣。

（見習編輯：劉麗麗；編輯：白杰）