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

1、計(jì)算機(jī)操作系統(tǒng)啟發(fā)式教學(xué)研究計(jì)算機(jī)操作系統(tǒng)啟發(fā)式教學(xué)研究操作系統(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)先算法EarliestDeadlineFirst，EDF和最低松弛度優(yōu)先算法LeastLaxityFirst，LLF。這兩個(gè)算法看上去并不難理解，然而問題往往并不像看起來那樣簡(jiǎn)單。事實(shí)上，在操作系統(tǒng)的教學(xué)中有一個(gè)很大的困難，即操作系統(tǒng)的教學(xué)不易落到實(shí)處，即原理容易講，但要讓學(xué)生體驗(yàn)這些原理卻并不容易。操作系統(tǒng)課程中涉及大量算法，如進(jìn)程調(diào)度算法、死鎖防止算法、頁面置換算法等。外表上這些算

2、法看起來比擬容易，但要讓學(xué)生理解算法后面蘊(yùn)含的深化道理，并從這些算法中發(fā)現(xiàn)一些問題就絕非易事了。對(duì)于這個(gè)困難，我們希望通過一些啟發(fā)式的教學(xué)設(shè)計(jì)，引導(dǎo)學(xué)生從程序員、從算法設(shè)計(jì)者的角度去分析和考慮算法中的一些問題，從而將抽象的原理轉(zhuǎn)化為詳細(xì)的問題和解決方案，加深對(duì)這些原理的理解。下面結(jié)合實(shí)時(shí)調(diào)度算法的例子來闡述對(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í)本文由論文聯(lián)盟.Ll.搜集整理學(xué)生并不難理解。然而，這兩個(gè)不同的調(diào)度算法在應(yīng)用中的

3、效果如何，教科書中并沒有給出進(jìn)一步的分析和討論。事實(shí)上，這是一個(gè)很好的啟發(fā)式教學(xué)的切入點(diǎn)，我們就從這里出發(fā)來設(shè)計(jì)問題。首先來看一看EDF算法和LLF算法的思想。EDF算法是根據(jù)任務(wù)的開場(chǎng)截止時(shí)間來確定任務(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í)間可以是開場(chǎng)截止時(shí)間，也可以是完成截止時(shí)間。一般來說，完成截止時(shí)間等于開場(chǎng)截止時(shí)間加上任務(wù)處理時(shí)間。LLF算法是根據(jù)任務(wù)緊急或松弛的程度，來確定

4、任務(wù)的優(yōu)先級(jí)。任務(wù)的緊急程度越高，越優(yōu)先執(zhí)行。例如，一個(gè)任務(wù)在200s時(shí)必須完成，而它本身所需的運(yùn)行時(shí)間就有100s，因此，該任務(wù)的緊急程度松弛程度為100s。又如，另一任務(wù)在400s時(shí)必須完成，它本身需要運(yùn)行150s，那么其松弛程度為250s。調(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è)問題。

5、第一個(gè)問題：按照教科書給出的LLF算法調(diào)度原那么，是否會(huì)存在不可調(diào)度的情況？經(jīng)過分析，很容易找出問題，如圖1中給出的例如。通過上面的例如可知，在某些情況下，當(dāng)某個(gè)任務(wù)在執(zhí)行過程中，假設(shè)某個(gè)或某些正在等待的任務(wù)的松弛度減至0s，那么可能會(huì)導(dǎo)致任務(wù)無法成功調(diào)度，而實(shí)際上系統(tǒng)才能是允許成功調(diào)度的。1.3提出改良針對(duì)前面提出的問題，可以引導(dǎo)學(xué)生對(duì)LLF算法的調(diào)度準(zhǔ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ù)

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

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

8、后面如圖3a所示。那么只需將B移至A后面一位即可如圖3b所示。3在之前的序列中A沒有超時(shí)，那么移走B，A更不會(huì)超時(shí)；而B的新位置的完成時(shí)刻等于原來序列時(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è)是按開場(chǎng)截止時(shí)間調(diào)度的EDF算法，會(huì)有什么不同嗎？另外，EDF算法和LLF算法之間有什么聯(lián)絡(luò)嗎？通過進(jìn)一步分析和比擬可以得到下面的結(jié)論。EDF算法和LLF算法的比擬結(jié)論：按開場(chǎng)截止時(shí)間調(diào)度的EDF算法并不能像按完成截

9、止時(shí)間調(diào)度的EDF算法那樣得到最優(yōu)的結(jié)果。事實(shí)上，按開場(chǎng)截止時(shí)間調(diào)度的EDF算法的調(diào)度結(jié)果和按LLF算法的調(diào)度結(jié)果是一樣的。也就是說，給定一個(gè)任務(wù)序列，按開場(chǎng)截止時(shí)間排序的結(jié)果和按松弛度排序的結(jié)果是一樣的。證明：因?yàn)殚_場(chǎng)截止時(shí)間和松弛度分別滿足如下關(guān)系。開場(chǎng)截止時(shí)間=完成截止時(shí)間-運(yùn)行時(shí)間松弛度=完成截止時(shí)間-當(dāng)前時(shí)間-運(yùn)行時(shí)間比擬式和式可得：松弛度=開場(chǎng)截止時(shí)間-當(dāng)前時(shí)間注意到對(duì)所有任務(wù)來說，其當(dāng)前時(shí)間都是一樣的，因此將任務(wù)按開場(chǎng)截止時(shí)間排序和按松弛度排序得到的結(jié)果是一樣的。這同時(shí)也就說明了，假設(shè)按松弛度優(yōu)先進(jìn)展調(diào)度無法得到最優(yōu)的結(jié)果，那么按開場(chǎng)截止時(shí)間調(diào)度的EDF算法也無法得到最優(yōu)結(jié)果。1

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

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

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