摘要:在教學(xué)實(shí)踐中“操作系統(tǒng)”的教學(xué)不易落到實(shí)處,即原理容易講,但要讓學(xué)生“體驗(yàn)”這些原理卻并不容易。文章通過一個(gè)啟發(fā)式教學(xué)設(shè)計(jì)的實(shí)例,闡述對(duì)于該問題的一些思考。
關(guān)鍵詞:?jiǎn)l(fā)式教學(xué);實(shí)時(shí)調(diào)度;操作系統(tǒng);最早截至?xí)r間優(yōu)先;最低松弛度優(yōu)先
文章編號(hào):1672-5913(2013)03-0062-04
中圖分類號(hào):G642
“操作系統(tǒng)”是計(jì)算機(jī)相關(guān)專業(yè)的一門核心專業(yè)課,而實(shí)時(shí)調(diào)度算法是“操作系統(tǒng)”課程中的一個(gè)重要內(nèi)容,在多數(shù)的“操作系統(tǒng)”教科書中主要介紹了兩種實(shí)時(shí)調(diào)度算法,即最早截止時(shí)間優(yōu)先算法(Earliest Deadline First,EDF)和最低松弛度優(yōu)先算法(Least Laxity First,LLF)。這兩個(gè)算法看上去并不難理解,然而問題往往并不像看起來(lái)那樣簡(jiǎn)單。事實(shí)上,在操作系統(tǒng)的教學(xué)中有一個(gè)很大的困難,即操作系統(tǒng)的教學(xué)不易落到實(shí)處,即原理容易講,但要讓學(xué)生“體驗(yàn)”這些原理卻并不容易。操作系統(tǒng)課程中涉及大量算法,如進(jìn)程調(diào)度算法、死鎖避免算法、頁(yè)面置換算法等。表面上這些算法看起來(lái)比較容易,但要讓學(xué)生理解算法后面蘊(yùn)含的深刻道理,并從這些算法中發(fā)現(xiàn)一些問題就絕非易事了。
對(duì)于這個(gè)困難,我們希望通過一些啟發(fā)式的教學(xué)設(shè)計(jì),引導(dǎo)學(xué)生從程序員、從算法設(shè)計(jì)者的角度去分析和思考算法中的一些問題,從而將抽象的原理轉(zhuǎn)化為具體的問題和解決方案,加深對(duì)這些原理的理解。下面結(jié)合實(shí)時(shí)調(diào)度算法的例子來(lái)闡述對(duì)于啟發(fā)式教學(xué)設(shè)計(jì)的思考。
1 實(shí)時(shí)調(diào)度算法的啟發(fā)式教學(xué)設(shè)計(jì)
1.1調(diào)度算法問題定義
很多“操作系統(tǒng)”教科書中都介紹了兩個(gè)重要的實(shí)時(shí)調(diào)度算法,一個(gè)是EDF,另一個(gè)是LLF。這兩個(gè)實(shí)時(shí)調(diào)度算法的調(diào)度準(zhǔn)則都很簡(jiǎn)單,課堂講授時(shí)學(xué)生并不難理解。然而,這兩個(gè)不同的調(diào)度算法在應(yīng)用中的效果如何,教科書中并沒有給出進(jìn)一步的分析和討論。事實(shí)上,這是一個(gè)很好的啟發(fā)式教學(xué)的切入點(diǎn),我們就從這里出發(fā)來(lái)設(shè)計(jì)問題。首先來(lái)看一看EDF算法和LLF算法的思想。
EDF算法是根據(jù)任務(wù)的開始截止時(shí)間來(lái)確定任務(wù)的優(yōu)先級(jí)。截止時(shí)間愈早,其優(yōu)先級(jí)愈高。該算法要求在系統(tǒng)中保持一個(gè)實(shí)時(shí)任務(wù)就緒隊(duì)列,該隊(duì)列按各任務(wù)截止時(shí)間的早晚排序;當(dāng)然,具有最早截止時(shí)間的任務(wù)排在隊(duì)列的最前面。調(diào)度程序在選擇任務(wù)時(shí),總是選擇就緒隊(duì)列中的第一個(gè)任務(wù),為之分配處理機(jī),使之投入運(yùn)行。截止時(shí)間可以是開始截止時(shí)間,也可以是完成截止時(shí)間。一般來(lái)說(shuō),完成截止時(shí)間等于開始截止時(shí)間加上任務(wù)處理時(shí)間。
LLF算法是根據(jù)任務(wù)緊急(或松弛)的程度,來(lái)確定任務(wù)的優(yōu)先級(jí)。任務(wù)的緊急程度越高,越優(yōu)先執(zhí)行。例如,一個(gè)任務(wù)在200ms時(shí)必須完成,而它本身所需的運(yùn)行時(shí)間就有100ms,因此,該任務(wù)的緊急程度(松弛程度)為100ms。又如,另一任務(wù)在400ms時(shí)必須完成,它本身需要運(yùn)行150ms,則其松弛程度為250ms。調(diào)度程序總是選擇就緒隊(duì)列中松弛度最小的任務(wù)執(zhí)行。LLF算法主要采用搶占調(diào)度方式。
1.2發(fā)現(xiàn)問題
按照教科書的描述和給出的示例,在LLF算法中,當(dāng)有新任務(wù)到達(dá)時(shí),并不馬上比較當(dāng)前所有任務(wù)的松弛度(包括正在執(zhí)行的任務(wù)),而是等到某個(gè)在等待的任務(wù)的松弛度降為零才進(jìn)行切換,即選擇這個(gè)松弛度已經(jīng)降為零的任務(wù)運(yùn)行。按照這個(gè)原則,我們?cè)趩l(fā)式教學(xué)設(shè)計(jì)中提出的第一個(gè)問題。
第一個(gè)問題:按照教科書給出的LLF算法調(diào)度原則,是否會(huì)存在不可調(diào)度的情況?
經(jīng)過分析,很容易找出問題,如圖1中給出的示例。
通過上面的示例可知,在某些情況下,當(dāng)某個(gè)任務(wù)在執(zhí)行過程中,若某個(gè)(或某些)正在等待的任務(wù)的松弛度減至0s,則可能會(huì)導(dǎo)致任務(wù)無(wú)法成功調(diào)度,而實(shí)際上系統(tǒng)能力是允許成功調(diào)度的。
1.3提出改進(jìn)
針對(duì)前面提出的問題,可以引導(dǎo)學(xué)生對(duì)LLF算法的調(diào)度準(zhǔn)則進(jìn)行改進(jìn)。通常比較容易想到的改進(jìn)是,修正松弛度的計(jì)算和任務(wù)切換時(shí)機(jī),即松弛度不需要隨時(shí)計(jì)算,而在如下兩種情況時(shí)進(jìn)行計(jì)算:
1)當(dāng)前任務(wù)正在執(zhí)行時(shí)新任務(wù)到達(dá),可能會(huì)引起搶占和任務(wù)切換,此時(shí)需要計(jì)算并比較松弛度;
2)當(dāng)前任務(wù)完成時(shí)可能會(huì)引起新的任務(wù)調(diào)度和切換,此時(shí)計(jì)算松弛度。
進(jìn)程在執(zhí)行時(shí)松弛度會(huì)不斷變化,但是不用進(jìn)行跟蹤計(jì)算和比較。
修正后,可以對(duì)學(xué)生提出第二個(gè)問題。
第二個(gè)問題:修正后的LLF算法,是否存在著不可調(diào)度的情況?
回答依然是存在問題,可以看一看圖2中給出的另一個(gè)示例。
1.4證明猜想
若發(fā)現(xiàn)改進(jìn)后的LLF算法還是存在問題,這時(shí)可以引導(dǎo)學(xué)生再作改進(jìn),并進(jìn)行討論。事實(shí)上,無(wú)論如何改進(jìn)LLF的調(diào)度和切換時(shí)機(jī),都無(wú)法解決問題。那么我們可以引導(dǎo)學(xué)生逐步轉(zhuǎn)到EDF算法上來(lái),即EDF算法也會(huì)存在類似問題嗎?因此我們提出的第三個(gè)問題如下。
第三個(gè)問題:按照完成截至?xí)r間調(diào)度的EDF算法,是否存在不可調(diào)度的情況?
通過啟發(fā)學(xué)生尋找反例會(huì)發(fā)現(xiàn)無(wú)法找到反例,這時(shí)學(xué)生也許會(huì)想到,EDF是一個(gè)最優(yōu)的算法,即可以得出以下的猜想。
猜想:給定一系列的任務(wù),只要這些任務(wù)是可調(diào)度的,即存在某種序列使得所有任務(wù)都在完成截至?xí)r間之前完成,則使用EDF算法一定能成功調(diào)度這些任務(wù)。
有了猜想,如何證明呢?這顯然要比設(shè)計(jì)反例困難得多。我們可以引導(dǎo)學(xué)生深入研究這個(gè)問題,這逐步進(jìn)人了這個(gè)實(shí)驗(yàn)的關(guān)鍵部分,即發(fā)現(xiàn)問題,以及問題背后的問題,給出猜想,并分析和證明自己的猜想。
對(duì)此,我們也給出了這個(gè)猜想的一個(gè)證明。
證明:
1)假設(shè)一系列任務(wù)是可調(diào)度的,并且安排出來(lái)的任務(wù)調(diào)度順序不等同于EDF算法所安排的序列。
2)那么,此安排順序中至少有兩個(gè)任務(wù)A、B,其中A的截止時(shí)間比B的早,但A安排在B后面(如圖3(a)所示)。則只需將B移至A后面一位即可(如圖3(b)所示)。
3)在之前的序列中A沒有超時(shí),則移走B,A更不會(huì)超時(shí);而B的新位置的完成時(shí)刻等于原來(lái)序列時(shí)A的完成時(shí)刻;而A的截止時(shí)刻小于B的截止時(shí)刻,所以B肯定不會(huì)超時(shí)。
4)重復(fù)以上過程,可以得到一個(gè)符合EDF規(guī)則的任務(wù)序列。所以EDF一定能找到成功序列。
證明了按完成截止時(shí)間調(diào)度的EDF算法的最優(yōu)性之后,還可以啟發(fā)學(xué)生進(jìn)一步思考,若是按開始截止時(shí)間調(diào)度的EDF算法,會(huì)有什么不同嗎?另外,EDF算法和LLF算法之間有什么聯(lián)系嗎?
通過進(jìn)一步分析和比較可以得到下面的結(jié)論。
EDF算法和LLF算法的比較結(jié)論:按開始截止時(shí)間調(diào)度的EDF算法并不能像按完成截止時(shí)間調(diào)度的EDF算法那樣得到最優(yōu)的結(jié)果。事實(shí)上,按開始截止時(shí)間調(diào)度的EDF算法的調(diào)度結(jié)果和按LLF算法的調(diào)度結(jié)果是一樣的。也就是說(shuō),給定一個(gè)任務(wù)序列,按開始截止時(shí)間排序的結(jié)果和按松弛度排序的結(jié)果是一樣的。
證明:因?yàn)殚_始截止時(shí)間和松弛度分別滿足如下關(guān)系。
開始截止時(shí)間=完成截止時(shí)間-運(yùn)行時(shí)間①松弛度=完成截止時(shí)間-當(dāng)前時(shí)間-運(yùn)行時(shí)間②
比較式①和式②可得:
松弛度=開始截止時(shí)間-當(dāng)前時(shí)間
注意到對(duì)所有任務(wù)來(lái)說(shuō),其“當(dāng)前時(shí)間”都是一樣的,因此將任務(wù)按開始截止時(shí)間排序和按松弛度排序得到的結(jié)果是一樣的。這同時(shí)也就說(shuō)明了,若按松弛度優(yōu)先進(jìn)行調(diào)度無(wú)法得到最優(yōu)的結(jié)果,那么按開始截止時(shí)間調(diào)度的EDF算法也無(wú)法得到最優(yōu)結(jié)果。
1.5新的問題
通過上面的證明可知,若給出的一系列任務(wù)是可調(diào)度的,則使用按完成截止時(shí)間調(diào)度的EDF算法一定可以成功調(diào)度這些任務(wù),在這種意義下EDF是一個(gè)最優(yōu)的算法。但是我們還可以再啟發(fā)學(xué)生作進(jìn)一步的思考。若給出的一系列任務(wù)是不可能全部調(diào)度成功的,那么EDF還是“最優(yōu)”的嗎?當(dāng)然,需要重新定義“最優(yōu)”的標(biāo)準(zhǔn)。這自然就得出下面這個(gè)新的問題。
第四個(gè)問題:假設(shè)當(dāng)前存在n個(gè)任務(wù),用m表示(1≤i≤n,下同),每個(gè)任務(wù)包含三個(gè)參數(shù),一是任務(wù)的運(yùn)行時(shí)間t,第二個(gè)是任務(wù)的完成截止時(shí)間d,第三個(gè)是成功安排該任務(wù)可以獲得的收益r。請(qǐng)問按EDF進(jìn)行調(diào)度能獲得最大收益嗎?若不能,請(qǐng)?jiān)O(shè)計(jì)一個(gè)調(diào)度算法使得最終的調(diào)度能獲得最大收益。
對(duì)于這個(gè)問題可以引導(dǎo)學(xué)生進(jìn)行討論。事實(shí)上,這個(gè)問題要困難得多,運(yùn)用一些直觀、樸素的原則很難得到理想的解決方案。對(duì)此,可引導(dǎo)學(xué)生進(jìn)一步運(yùn)用算法和最優(yōu)化方法中的一些技巧來(lái)分析該問題。下面是運(yùn)用動(dòng)態(tài)規(guī)劃來(lái)求解該問題的一個(gè)方案。
第四個(gè)問題的動(dòng)態(tài)規(guī)劃分析:
1)首先可以考慮的是,我們的目標(biāo)是在n個(gè)任務(wù)中選取若干個(gè)任務(wù)來(lái)獲得最大收益,若選出了這些任務(wù)(即這些被選中的任務(wù)是可以安排好的),則可以按照EDF的規(guī)則來(lái)安排執(zhí)行,即把被選出的任務(wù)按各自的完成截止時(shí)間排序,則這些任務(wù)一定都可以在各自的完成截止時(shí)間之內(nèi)完成,這就是前面的猜想證明的結(jié)論。所以我們可以考慮將所有的n個(gè)任務(wù)按完成截止時(shí)間排序。假設(shè)按完成截止時(shí)間排好序后的n個(gè)任務(wù)用m,m,…,m表示。
2)其次考慮,在n個(gè)任務(wù)中選取若干個(gè)任務(wù)來(lái)獲得最大收益,與在n-1個(gè)任務(wù)中選取若干個(gè)任務(wù)來(lái)獲得最大收益之間有什么關(guān)系?可以看出,按完成截止時(shí)間排序后的第n個(gè)任務(wù)m若不在最終選定的若干個(gè)任務(wù)之列,則問題可以轉(zhuǎn)化為在n-1個(gè)任務(wù),即m,m,…,m中選取最優(yōu)的任務(wù)序列;若任務(wù)m在最終選定的若干個(gè)任務(wù)之列,則問題可以轉(zhuǎn)化為在截止時(shí)間T-t之前,從m,m,…,m。中選取最優(yōu)的任務(wù)序列。若用f(n,d)表示在截止時(shí)間d前,從n個(gè)任務(wù)中選取滿足條件的最優(yōu)序列所獲得的最大收益,則可以得到如下的遞歸表達(dá)式:
3)依據(jù)遞歸式③可以很容易地寫出一個(gè)自底向上的動(dòng)態(tài)規(guī)劃算法,其時(shí)間復(fù)雜度為O(n×T)。其實(shí),遞歸式③與0/1背包問題動(dòng)態(tài)規(guī)劃求解的遞歸式極其相似,求解的時(shí)間復(fù)雜度也類似。所以提出的第四個(gè)問題是一個(gè)NP完全問題。
2 結(jié)語(yǔ)
從前面的啟發(fā)式教學(xué)設(shè)計(jì)中可以看出,通過精心的教學(xué)設(shè)計(jì),安排一些具有啟發(fā)性的問題,可以有效地引導(dǎo)學(xué)生深入思考問題背后的問題,從而加深對(duì)一些原理的理解,把握其中的本質(zhì)。通過提出問題和猜想,引導(dǎo)學(xué)生深入研究。啟發(fā)式的教學(xué)不僅可以讓學(xué)生更深刻地理解系統(tǒng)原理,同時(shí)對(duì)于培養(yǎng)學(xué)生的邏輯思維能力,培養(yǎng)獨(dú)立思考的習(xí)慣都有著重要的意義。在某些問題的設(shè)計(jì)上,適當(dāng)引入一些研究性的思路,對(duì)學(xué)生提出更高的要求,而不僅僅局限在教材上,有利于培養(yǎng)學(xué)生的鉆研精神和探索精神,為今后的學(xué)習(xí)和工作打下堅(jiān)實(shí)的基礎(chǔ),培養(yǎng)良好的習(xí)慣。
(見習(xí)編輯:劉麗麗;編輯:白杰)