操作系統(tǒng)精髓與設(shè)計(jì)原理第9章單處理器調(diào)度

1、第九章單處理器調(diào)度復(fù)習(xí)題9.1簡要描述三種類型的處理器調(diào)度。長程調(diào)度：決定加入到待執(zhí)行的進(jìn)程池中；中程調(diào)度：決定加入到部分或全部在主存中的進(jìn)程集合中；短程調(diào)度：決定哪一個(gè)可用進(jìn)程將被處理器執(zhí)行。9.2在交互式操作系統(tǒng)中，通常最重要的性能要求是什么？反應(yīng)時(shí)間9.3周轉(zhuǎn)時(shí)間和響應(yīng)時(shí)間有什么區(qū)別？周轉(zhuǎn)時(shí)間是一個(gè)要求花費(fèi)在系統(tǒng)上的包括等待時(shí)間和服務(wù)時(shí)間的總的時(shí)間。響應(yīng)時(shí)間對(duì)一個(gè)交互進(jìn)程，這是指從提交一個(gè)請(qǐng)求到開始接受響應(yīng)之間的時(shí)間間隔。通常進(jìn)程在處理該請(qǐng)求的同時(shí)，就開始給用戶產(chǎn)生一些輸出。9.4對(duì)進(jìn)程調(diào)度，較小的優(yōu)先級(jí)值表示較低的優(yōu)先級(jí)還是較高的優(yōu)先級(jí)？在UNIX和許多其他系統(tǒng)中，大的優(yōu)先級(jí)值表示低優(yōu)

2、先級(jí)進(jìn)程。許多系統(tǒng)，比如WINDOWS,剛好相反，大數(shù)值表示高優(yōu)先級(jí)。9.5搶占式和非搶占式調(diào)度有什么區(qū)別？非搶占：在這種情況下，一旦進(jìn)程處于運(yùn)行態(tài)，他就不斷執(zhí)行直到終止，或者為等待I/O或請(qǐng)求某些操作系統(tǒng)服務(wù)而阻塞自己。搶占：當(dāng)前正在運(yùn)行的進(jìn)程可能被操作系統(tǒng)中斷，并轉(zhuǎn)移到就緒態(tài)。關(guān)于搶占的決策可能是在一個(gè)新進(jìn)程到達(dá)時(shí)，或者在一個(gè)中斷發(fā)生后把一個(gè)被阻塞的進(jìn)程置為就緒態(tài)時(shí)，或者基于周期性的時(shí)間中斷。9.6簡單定義FCFS調(diào)度。當(dāng)每個(gè)進(jìn)程就緒后，它加入就緒隊(duì)列。當(dāng)當(dāng)前正在運(yùn)行的進(jìn)程停止執(zhí)行時(shí)，選擇在就緒隊(duì)列中存在時(shí)間最長的進(jìn)程運(yùn)行。9.7簡單定義輪轉(zhuǎn)調(diào)度以一個(gè)周期性間隔產(chǎn)生時(shí)鐘中斷，當(dāng)中斷產(chǎn)生時(shí)，

3、當(dāng)前正在運(yùn)行的的進(jìn)程被置于就緒隊(duì)列中，然后基于FCFS策略選擇下一個(gè)就緒作業(yè)運(yùn)行。9.8簡單定義最短進(jìn)程優(yōu)先調(diào)度。這是一個(gè)非搶占的策略，其原則是下一次選擇所需處理時(shí)間最短的進(jìn)程。9.9簡單定義最短剩余時(shí)間調(diào)度。最短剩余時(shí)間是針對(duì)SPN增加了搶占機(jī)制的版本。在這種情況下，調(diào)度器總是選擇預(yù)期剩余時(shí)間最短的進(jìn)程。當(dāng)一個(gè)新進(jìn)程加入到就緒隊(duì)列時(shí)，他可能比當(dāng)前運(yùn)行的進(jìn)程具有更短的剩余時(shí)間，因此，只有新進(jìn)程就緒，調(diào)度器就可能搶占當(dāng)前正在運(yùn)行的進(jìn)程。9.10簡單定義最高響應(yīng)比優(yōu)先調(diào)度。在當(dāng)前進(jìn)程完成或被阻塞時(shí)，選擇R值最大的就緒進(jìn)程。R=(w+s)/s,w等待處理器的時(shí)間，s期待的服務(wù)時(shí)間。9.11簡單定義反

4、饋調(diào)度。調(diào)度基于搶占原則并且使用動(dòng)態(tài)優(yōu)先級(jí)機(jī)制。當(dāng)一個(gè)進(jìn)程第一次進(jìn)入系統(tǒng)時(shí)，它被放置在RQ0。當(dāng)它第一次被搶占后并返回就緒狀態(tài)時(shí)，它被防止在RQ1。在隨后的時(shí)間里，每當(dāng)它被搶占時(shí)，它被降級(jí)到下一個(gè)低優(yōu)先級(jí)隊(duì)列中。一個(gè)短進(jìn)程很快會(huì)執(zhí)行完，不會(huì)在就緒隊(duì)列中降很多級(jí)。一個(gè)長進(jìn)程會(huì)逐級(jí)下降。因此，新到的進(jìn)程和短進(jìn)程優(yōu)先于老進(jìn)程和長進(jìn)程。在每個(gè)隊(duì)列中，除了在優(yōu)先級(jí)最低的隊(duì)列中，都使用簡單的FCFS機(jī)制。一旦一個(gè)進(jìn)程處于優(yōu)先級(jí)最低的隊(duì)列中，它就不可能再降低，但是會(huì)重復(fù)地返回該隊(duì)列，直到運(yùn)行結(jié)束。習(xí)題9.1考慮下面的進(jìn)程集合：進(jìn)程名到達(dá)時(shí)間處理時(shí)間A03B15C32D95E125對(duì)這個(gè)集合，給出類似于表9.

5、5和圖9.5的分析。每格代表一個(gè)時(shí)間單位，方框中的數(shù)表示當(dāng)前運(yùn)行的進(jìn)程第一到第八行依次是9.2對(duì)下面的集合重復(fù)習(xí)題9.1的要求進(jìn)程到達(dá)時(shí)處理時(shí)間A01B19C21D39ABCDTa0123Ts1919FCFSTf1.0010.0011.0020.00Tr1.009.009.0017.009.00Tr/Ts1.001.009.001.893.22RRq=1Tf1.0018.003.0020.00Tr1.0017.001.0017.009.00Tr/Ts1.001.891.001.891.44RRq=4Tf1.0015.006.0020.00Tr1.0014.004.0017.009.00Tr/T

6、s1.001.564.001.892.11SPNTf1.0010.0011.0020.00Tr1.009.009.0017.009.00Tr/Ts1.001.009.001.893.22SRTTf1.0011.003.0020.00Tr1.0010.001.0017.009.00Tr/Ts1.001.111.001.891.25HRRNTf1.0010.0011.0020.00Tr1.009.009.0017.009.00Tr/Ts1.001.009.001.893.22FBq=1Tf1.0019.003.0020.00Tr1.0018.001.0017.009.25Tr/Ts1.002.00

7、1.001.891.47FBTf1.0018.003.0020.00q=2iTr1.0017.001.0017.009.00Tr/Ts1.001.891.001.891.449.3證明在非搶占調(diào)度算法中，對(duì)于同時(shí)到達(dá)的批處理作業(yè)，SPN提供了最小平均等待時(shí)間。假設(shè)調(diào)度器只要有任務(wù)就必須執(zhí)行。我們能夠證明在一批n個(gè)作業(yè)同時(shí)到達(dá)且忽略以后到來的作業(yè)。試驗(yàn)會(huì)延伸包含以后的作業(yè)。假設(shè)各作業(yè)到來的順序是：tlv=t2v=v=tn.假設(shè)n個(gè)使用者必須等到工作1的完成:n-1個(gè)使用者必須等到工作2的完成，依次繼續(xù)。那么，平均反應(yīng)時(shí)間是n*t1+(n-1)*t2+tn/n。如果我們?cè)谶@個(gè)時(shí)間表中做些改變，例如

8、調(diào)換工作j和k(jvk),平均反應(yīng)時(shí)間增加,因?yàn)?k-j)*(tk-tj)/n=0。換句話說，如果SPN運(yùn)算法則沒被采用，平均反應(yīng)時(shí)間只會(huì)增加。9.4假設(shè)一個(gè)進(jìn)程的每一次瞬間執(zhí)行時(shí)間(burst-time模式)為6，4，6，4，13，13，13，假設(shè)最初的猜測值為10。請(qǐng)畫出類似于圖9.9的圖表。數(shù)據(jù)圖如下：平均觀察觀測值平均值apha=0.8alpha=0.5160.000.000.00243.004.803.00363.334.163.50444.005.634.755134.004.334.386135.5011.278.697136.5712.6510.849.5考慮下面的公式，它可以

9、替代Sn+1=aTn+(1-a)Sn,Xn+1=minUbound,maxLbound,(BSn+1)其中，Ubound和Lbound是預(yù)先選擇的估計(jì)值T的上限和下限。Xn+1的值用于最短進(jìn)程優(yōu)先的算法，并且可以代替Sn+1。a和B有什么功能，它們每個(gè)取最大值和最小值會(huì)產(chǎn)生什么影響？第一個(gè)等式等同于等式，所以參數(shù)使指數(shù)起平滑作用。參數(shù)B是延遲變化參數(shù)。一個(gè)較小的B值將會(huì)時(shí)在觀察次數(shù)里更快的適應(yīng)改變，但估計(jì)上會(huì)產(chǎn)生更多的波動(dòng)。一個(gè)詭辯的這種估計(jì)類型的程序收錄于。在圖下面的例子中，在控制權(quán)限轉(zhuǎn)移到之前，進(jìn)程運(yùn)行個(gè)時(shí)間單元，另外一個(gè)場景是在控制權(quán)限轉(zhuǎn)移到之前，進(jìn)程運(yùn)行個(gè)時(shí)間單元。在反饋調(diào)度算法中，這

10、兩種場景的策略有什么不同？關(guān)鍵要看進(jìn)程是否一開始就被放置在隊(duì)列中。如果是，它在被搶占前就被賦予個(gè)額外的時(shí)間單元。在一個(gè)非搶占的單處理器系統(tǒng)中，在剛剛完成一個(gè)作業(yè)后的時(shí)間，就緒隊(duì)列中包含三個(gè)作業(yè)。這些作業(yè)分別在時(shí)間，處到達(dá)，估計(jì)執(zhí)行時(shí)間分別為，。圖顯示了它們的響應(yīng)比隨著時(shí)間線形增加。使用這個(gè)例子，設(shè)計(jì)一種響應(yīng)比調(diào)度的變體，稱為極小極大響應(yīng)比調(diào)度算法，它可以使給定的一批作業(yè)的最大響應(yīng)比最小。首先，調(diào)度器計(jì)算時(shí)刻的響應(yīng)比，如果三個(gè)進(jìn)程都結(jié)束，此時(shí)，進(jìn)城就有最高響應(yīng)比，因此調(diào)度器就執(zhí)行該進(jìn)程，然后在時(shí)刻繼續(xù)執(zhí)行進(jìn)程和直到結(jié)束。因此，進(jìn)程1的響應(yīng)比最小，其次進(jìn)程，在，時(shí)間被選中執(zhí)行。這種算法在每個(gè)進(jìn)程結(jié)

11、束的時(shí)候重復(fù)一次并且考慮新加入的進(jìn)程。但注意這種算法和最高響應(yīng)比算法不完全相同。后者在，時(shí)刻會(huì)選擇進(jìn)程1。直覺上看，當(dāng)前算法通過不斷的推遲具有最少響應(yīng)比增值的進(jìn)程從而減小最咼響應(yīng)比9，證8明，對(duì)給定的一批作業(yè)，上一習(xí)題中的最大響應(yīng)比調(diào)度算法能夠使它們的最大響應(yīng)時(shí)間最小這個(gè)證明，來自于。考慮在時(shí)間時(shí)的隊(duì)列，僅僅在前一個(gè)進(jìn)程結(jié)束且忽略以后工作的到來。等待執(zhí)行的作業(yè)被編號(hào)從到：TOC o 1-5 h z作業(yè)：到達(dá)時(shí)間：t1t2tit：服務(wù)時(shí)間：r1r2rir：我們假設(shè)作業(yè)在完成前能達(dá)到最高的響應(yīng)時(shí)間比。當(dāng)作業(yè)至I都執(zhí)行結(jié)束，總時(shí)間為r作業(yè)的響應(yīng)比為()()執(zhí)行作業(yè)的原因是它的響應(yīng)比將是以下作業(yè)在時(shí)最

12、小的：考慮不同序列中同樣的個(gè)作業(yè)的排序結(jié)果：作業(yè)：到達(dá)時(shí)間：tatbtjtz服務(wù)時(shí)間：Rarbrjrz在新的序列中，我們選擇最小的后繼服務(wù)作業(yè)，從到，包括從到最初的后繼。當(dāng)作業(yè)至I被執(zhí)行結(jié)束，總時(shí)間為作業(yè)的響應(yīng)比是由于作業(yè)至I是作業(yè)至I的一個(gè)子集，那么總的服務(wù)時(shí)間一定小于等于總的服務(wù)時(shí)間又響應(yīng)比隨著時(shí)間增加而增加，意味人們還知道，作業(yè)J是其中的之一，作業(yè)j在時(shí)間Ti有最小的響應(yīng)比。上述不平等的，因此可以延長如下：Rj(Tj)=Rj(Ti)=Ri(Ti).換言之，在調(diào)度算法改變后，會(huì)有作業(yè)j達(dá)到響應(yīng)比Rj(Tj)，它會(huì)大于等于最高的響應(yīng)比Ri(Ti).這證明有效期一般為優(yōu)先考慮的都是非遞減函數(shù)的

13、時(shí)間。例如，在一個(gè)FIFO制度，優(yōu)先增加線性與等候時(shí)間，在同樣的速度，為所有作業(yè)機(jī)會(huì)。因此，目前的證據(jù)表明，該FIFO的算法最大限度地減少候車時(shí)間，對(duì)于給定了一批作業(yè)。9.9駐留時(shí)間Tr被定義成一個(gè)進(jìn)程花費(fèi)在等待和被服務(wù)上的總平均時(shí)間。說明對(duì)FIFO,若平均服務(wù)時(shí)間為Ts，則有Tr=Ts/(1-p)，其中p為使用率。在我們開始以前，有一個(gè)結(jié)果，這是必要的，具體情況如下。假設(shè)一個(gè)項(xiàng)目擁有T服務(wù)時(shí)間，而實(shí)際服務(wù)了時(shí)間h。那么，預(yù)期的殘留服務(wù)時(shí)間ET/Th=Ts。那就是，無論多久，一個(gè)項(xiàng)目服務(wù)，預(yù)計(jì)剩余服務(wù)時(shí)間，只是平均服務(wù)時(shí)間為項(xiàng)目。這一結(jié)果，雖然反以直覺是正確的，正如我們現(xiàn)在查看，考慮到指數(shù)的概

14、率分布函數(shù)：F(x)=PrXWx=1-e-ux，那么，我們有PrXx=e-uxo現(xiàn)在讓我們看看X多于X+h的條件概率：PrXsx+h/Xxl=l=PrXmh：|因此，概率分布為服務(wù)時(shí)間給予確已送達(dá)期限x是相同的概率分布，總服務(wù)時(shí)間。因此，預(yù)期價(jià)值的剩余服務(wù)時(shí)間是一樣的原來預(yù)期值的服務(wù)時(shí)間。與這一結(jié)果，我們現(xiàn)在可以著手將原問題。當(dāng)一個(gè)項(xiàng)目展開服務(wù)以來，總的響應(yīng)時(shí)間，該項(xiàng)目將包括它自己的服務(wù)時(shí)間，再加上服務(wù)的時(shí)候，所有的物品擺在它面前的，在排隊(duì)。預(yù)期總體響應(yīng)時(shí)間由三部分組成。預(yù)計(jì)到達(dá)進(jìn)程的服務(wù)時(shí)間=TSo預(yù)計(jì)所有目前正在等待服務(wù)的進(jìn)程程的服務(wù)時(shí)間。值為wxTs，w是平均等待服務(wù)時(shí)間。剩余等待服務(wù)時(shí)

15、間，如果現(xiàn)在有一個(gè)進(jìn)程正在執(zhí)行。這個(gè)值可以表示成為PxTs，p是利用，因此一個(gè)進(jìn)程正在服務(wù)的概率。Ts正如我們已證明是預(yù)計(jì)等待服務(wù)的時(shí)間。，因此，我們有/?-7x（J+lv+p）-7xjJ.+p-IJ-P丿J-P9.10一個(gè)處理器被就緒隊(duì)列中的所有進(jìn)程以無限的速度多路復(fù)用，且沒有任何額外的開銷（這是一個(gè)在就緒進(jìn)程中使用輪轉(zhuǎn)調(diào)度的理想模型，時(shí)間片相對(duì)于平均服務(wù)時(shí)間非常?。Ｕf明對(duì)來自一個(gè)無限源的泊松輸入和指數(shù)服務(wù)時(shí)間，一個(gè)進(jìn)程的平均響應(yīng)時(shí)間Rx和服務(wù)時(shí)間x由式Rx=x/（1-p）給出。讓我們把時(shí)間片在輪轉(zhuǎn)調(diào)度中記為D。在這個(gè)問題中，D相對(duì)于服務(wù)時(shí)間很小?，F(xiàn)在，考慮一個(gè)新來的進(jìn)程，它排在就緒隊(duì)列的

16、最后。我們假設(shè)這一特定的進(jìn)程的服務(wù)時(shí)間為X，是D的一些倍數(shù)：x=mU。首先，讓我們回答一個(gè)問題，多少時(shí)間花費(fèi)在進(jìn)程得到服務(wù)前的等待隊(duì)列中。它必須等待所有排在它之前的q個(gè)進(jìn)程結(jié)束服務(wù)后，從而初步等待時(shí)間=qU。Q則是等待隊(duì)列中的平均進(jìn)程數(shù)目?，F(xiàn)在，我們可以計(jì)算總時(shí)間花費(fèi)在收到x秒鐘的服務(wù)之前的等待時(shí)間。因?yàn)樗仨毥?jīng)過隊(duì)列m次，而每一次他們等待qU秒，其總等待時(shí)間分列如下：讓tiitrue=mq=紳）=恥然后，響應(yīng)時(shí)間是指等待時(shí)間和總服務(wù)時(shí)間Rx=waittime+servicetime=qx+x=（q+1）x。談到排隊(duì)的公式，在附錄A，是指物品的數(shù)量，該系統(tǒng)的Q可表示為：Q=pp貝Upppppp

17、9.1大1多數(shù)輪轉(zhuǎn)調(diào)度器使用大小固定的時(shí)間片。給定支持小時(shí)間片的參數(shù)。現(xiàn)在給定一個(gè)支持大的時(shí)間片的參數(shù)。比較并對(duì)比兩個(gè)參數(shù)所適用的系統(tǒng)和作業(yè)的類型。存在兩種參數(shù)都合理的情況嗎？一個(gè)論點(diǎn)主張一個(gè)小時(shí)間片：用一個(gè)小時(shí)間片會(huì)加強(qiáng)反應(yīng)能力，多次運(yùn)行的所有進(jìn)程進(jìn)行了短暫的時(shí)間片。當(dāng)就緒隊(duì)列有許多流程，這是互動(dòng)性，反應(yīng)能力是非常重要的如：一般用途的計(jì)算機(jī)系統(tǒng)。一個(gè)論點(diǎn)主張一個(gè)大的時(shí)間片：利用大型公司將提高吞吐量和CPU利用率測量方面的實(shí)際工作，因?yàn)槟抢锸遣蛔愕谋尘跋虑袚Q，從而減少開銷。一個(gè)系統(tǒng)，其中既可能是適當(dāng)?shù)模河幸恍┲贫?，即無論是中小企業(yè)還是大廣，是合理的。例如：很長的行業(yè)，需要在短短數(shù)用戶互動(dòng)。雖然

18、這種類型的工作可以被視為一個(gè)批處理工作，在某種意義上來說，它仍然需要與用戶手中。因此，在時(shí)代的時(shí)候，有沒有使用者之間的相互作用，時(shí)間片可能會(huì)增加優(yōu)化，并在整個(gè)過程中的互動(dòng)時(shí)間，時(shí)間片可能降至提供更好的應(yīng)變能力。9.12在排隊(duì)系統(tǒng)中，新作業(yè)在得到服務(wù)之前必須等待一會(huì)兒。當(dāng)一個(gè)作業(yè)等待時(shí)，它的優(yōu)先級(jí)從0開始以速度a線形增加。一個(gè)作業(yè)一直等待到它的優(yōu)先級(jí)達(dá)到正在運(yùn)行中的作業(yè)的優(yōu)先級(jí)，然后它開始與其他正在運(yùn)行的作業(yè)使用輪轉(zhuǎn)法平等地共享處理器，與此同時(shí)，它的優(yōu)先級(jí)繼續(xù)以比較慢的速度B增長。這個(gè)算法稱為自私輪轉(zhuǎn)法，因?yàn)樵谶\(yùn)行中的作業(yè)試圖通過不斷地增加它的優(yōu)先級(jí)來壟斷處理器。首先，我們需要厘清意義的參數(shù)Q。

19、速度在項(xiàng)目到達(dá)第一盒（“隊(duì)列專欄）是Q。兩個(gè)相鄰的來港人士，以第二個(gè)選項(xiàng)（服務(wù)的框），將得出一個(gè)稍微減慢，因?yàn)榈诙?xiàng)是延遲其追逐的第一個(gè)項(xiàng)目。我們可以計(jì)算出垂直偏移Y的數(shù)字，在兩種不同方式的基礎(chǔ)上，幾何形狀的圖表：9.13一個(gè)使用輪轉(zhuǎn)調(diào)度和交換的交互式系統(tǒng)，試圖按如下方式對(duì)普通的請(qǐng)求給出有保證的響應(yīng)：在所有就緒進(jìn)程中完成一次輪轉(zhuǎn)循環(huán)后，系統(tǒng)通過用最大響應(yīng)時(shí)間除以需要服務(wù)的進(jìn)程數(shù)目，確定在下一個(gè)循環(huán)中分配給每個(gè)就緒進(jìn)程的時(shí)間片。請(qǐng)問是否是合理的解釋？只是，只要有相對(duì)很少有用戶在該系統(tǒng)內(nèi)。當(dāng)時(shí)間片變小，以滿足更多用戶迅速兩件事情發(fā)生：（1）處理器利用率下降，以及（2）在某一個(gè)點(diǎn)，時(shí)間片變得太小，以

20、滿足最瑣碎的請(qǐng)求。用戶將經(jīng)歷一個(gè)突然增加的響應(yīng)時(shí)間，因?yàn)樗麄兊囊?，必須?jīng)過輪轉(zhuǎn)調(diào)度好幾次。9.14多級(jí)反饋排隊(duì)調(diào)度對(duì)哪種類型的進(jìn)程有利，是受處理器限制的進(jìn)程還是受I/O限制的進(jìn)程？請(qǐng)簡要說明原因。如果一個(gè)進(jìn)程占用過多處理器時(shí)間，它將會(huì)被移到一個(gè)低優(yōu)先級(jí)的隊(duì)列中。這會(huì)使受限制的進(jìn)程留在優(yōu)先級(jí)高的隊(duì)列中。9.1在5基于優(yōu)先級(jí)的進(jìn)程調(diào)度中，如果當(dāng)前沒有其他優(yōu)先級(jí)更高的進(jìn)程處于就緒狀態(tài)，調(diào)度器將把控制給一個(gè)特定的進(jìn)程。假設(shè)在進(jìn)行進(jìn)程調(diào)度決策時(shí)沒有使用其他信息，還假設(shè)進(jìn)程的優(yōu)先級(jí)是在進(jìn)程被創(chuàng)建是建立的，并且不會(huì)改變。在這樣的系統(tǒng)中，為什么使用方法解決互斥問題是非常“危險(xiǎn)”的？通過說明會(huì)發(fā)生什么和如何發(fā)生來解釋該問題。dekker的算法依靠的是對(duì)公平性的硬件和操作系統(tǒng)。使用的優(yōu)先次序的風(fēng)險(xiǎn)饑餓如下?？赡苡羞@樣的情況，如果出生是一種很快速的反復(fù)過程，因?yàn)樗粩嗟匕l(fā)現(xiàn)Flag1=虛假的，不斷進(jìn)入其關(guān)鍵路段，而在P1,離開內(nèi)部回路，它正在等待它反過來又可以不設(shè)置Flag1為真實(shí)，阻止這樣做出生的讀變量（記得進(jìn)入該變發(fā)生下相互排斥）9.165個(gè)批作業(yè)，從A到E，同時(shí)到達(dá)計(jì)算機(jī)中心。它們的