操作系統(tǒng)課后習(xí)題答案

1、5.1 為什么對調(diào)度程序而言，區(qū)分CPU約束程序和I/O約束程序很重要？答：在運行I/O操作前，I/0限制的程序只運行很少數(shù)量的計算機操作。而CPU約束程序一般來說不會使用很多的CPU另一方面，CPU約束程序會利用整個時間片，且不做任何阻礙I/O操作的工作。因此，通過給I/O約束程序優(yōu)先權(quán)和允許在CPU約束程序之前運行，可以很好的利用計算機資源。5.3 考慮用于預(yù)測下一個CPU區(qū)間長度的指數(shù)平均公式。將下面的值賦給算法中的參數(shù)的含義是什么？A.a=0且t0=100msB.a=0.99且t0=10ms答：當(dāng)a=0且t0=100ms時，公式總是會預(yù)測下一次的CPU區(qū)間為100毫秒。當(dāng)a=0.99且

2、t0=10毫秒時，進(jìn)程將給予更高的重量以便能和過去相比。因此，調(diào)度算法幾乎是無記憶的，且簡單預(yù)測未來區(qū)間的長度為下一次的CPU執(zhí)行的時間片。5.4 考慮下面一組進(jìn)程，進(jìn)程占用的CPU區(qū)間長度以毫秒來計算：進(jìn)程區(qū)間時間優(yōu)先級Pi103P211P323P414P552假設(shè)在0時刻進(jìn)程以P1、P2、P3、P4、P5的順序到達(dá)。a.畫出4個Gantt圖分別演示用FCFSSJF非搶占優(yōu)先級（數(shù)字小代表優(yōu)先級高）和RR（時間片=1）算法調(diào)度時進(jìn)程的執(zhí)行過程。b.每個進(jìn)程在每種調(diào)度算法下的周轉(zhuǎn)時間是多少？c.每個進(jìn)程在每種調(diào)度算法下的等待時間是多少？d.哪一種調(diào)度算法的平均等待時間最?。看餫.FCFSP1P

3、2P3P4P501011131419P2P4P3P5P1SJF2199401P2P5P1P3P4非搶占優(yōu)先級:616181901RRP1P2P3P4P5P1P3P5P1P5P1P5P1P5P10123456789101112131419b.周轉(zhuǎn)時間:FCFSSJF非搶占優(yōu)先級RRP110191619P211112P3134187P4142194P5199614c.等待時間:FCFSSJF非搶占優(yōu)先級RRP10969P210001P3112165P4131183P514429d.從上表中可以看出SJFW等待時間最小。5.5 下面哪種調(diào)度算法能導(dǎo)致饑餓a.先到先服務(wù)b.最短作業(yè)優(yōu)先c.輪轉(zhuǎn)法d.優(yōu)

4、先級答：最短作業(yè)優(yōu)先和優(yōu)先級調(diào)度算法能導(dǎo)致饑餓。因為對于優(yōu)先級較低的作業(yè)來說，最短作業(yè)優(yōu)先和優(yōu)先級調(diào)度算法會使其無窮等待CPU,長期得不到調(diào)用，這就導(dǎo)致了饑餓問題，也叫無窮阻塞。5.9考慮下面的動態(tài)改變優(yōu)先級的搶占式優(yōu)先級調(diào)度算法。大的優(yōu)先級數(shù)代表高優(yōu)先級。當(dāng)一個進(jìn)程在等待CPU時（在就緒隊列中，但未執(zhí)行），優(yōu)先級以“速率改變；當(dāng)它運行時，優(yōu)先級以3速率改變。所有的進(jìn)程在進(jìn)入等待隊列時被給定優(yōu)先級為0。參數(shù)a和3可以進(jìn)行設(shè)定得到許多不同的調(diào)度算法。a. 3>a>0是什么算法？b. a<3<0時是什么算法？答：a.FCFSB到先服務(wù)調(diào)度算法。當(dāng)進(jìn)程進(jìn)入到就緒隊列時，其PC

5、B鏈接到隊列的尾部，優(yōu)先級以a速率改變；當(dāng)CPU空閑時，CPU分配給位于隊列頭的進(jìn)程，優(yōu)先級加快，以3速率改變，接著該運行進(jìn)程從隊列中刪除。b.LIFO后進(jìn)先服務(wù)調(diào)度算法。同上，當(dāng)進(jìn)程進(jìn)入到就緒隊列時，優(yōu)先級以a速率改變，等待后進(jìn)的進(jìn)程先調(diào)度，之后輪到該進(jìn)程時，優(yōu)先級加快，以3速率改變，完成調(diào)度。2.1 第一個著名的正確解決兩個進(jìn)程的臨界區(qū)問題的軟件方法是Dekker設(shè)計的。兩個進(jìn)程P0和P1共享以下變量：booleanflag2;/*initiallyfalse*/intturn;進(jìn)程Pi（i=0或1）的結(jié)構(gòu)見6.25,另一個進(jìn)程為Pj（j=0或1）。證明這個算法滿足臨界區(qū)問題的所有三個要求

6、。doflagi=TRUE;while（flagj）if(turn=j)flagi=false;while(turn=j);/donothingflagi=TRUE;/criticalsectionturn=j;flagi=FALSE;/remaindersectionwhile(TRUE);圖6.25Dekker算法中的進(jìn)程pi結(jié)構(gòu)答：這個算法滿足臨界區(qū)問題的三個要求：(1) 在標(biāo)記和返回變量的使用中，互斥條件是保證的。如果兩個進(jìn)程將它們的標(biāo)識設(shè)為真，那么只有一個進(jìn)程會成功進(jìn)行，即輪到的那個進(jìn)程。當(dāng)另一個進(jìn)程更新它的返回變量時，等待的那個進(jìn)程只能進(jìn)入它的臨界區(qū)域。(2) 就緒的進(jìn)程，通過標(biāo)志

7、，返回變量。這個算法沒有提供嚴(yán)格的交替。如果一個進(jìn)程想要進(jìn)入它們的臨界區(qū)域，它可以將它的標(biāo)識設(shè)為真，然后進(jìn)入它們的臨界區(qū)域。當(dāng)退出它的臨界區(qū)域，它可以設(shè)置轉(zhuǎn)向其他進(jìn)程的值。如果這個進(jìn)程想要在其他進(jìn)程之前再次進(jìn)入它的臨界區(qū)域，它會重復(fù)這樣的進(jìn)程：進(jìn)入它的臨界區(qū)域，在退出時轉(zhuǎn)向另一個進(jìn)程。(3) 在雙T返回變量的使用過程中，臨界等待受阻。假設(shè)兩個進(jìn)程想要進(jìn)入它們的責(zé)任所在的臨界區(qū)域。它們都將它們的標(biāo)志的值設(shè)為真；而只有輪到的那個線程可以執(zhí)行；其他的線程處于等待狀態(tài)。如果臨界等待沒有受阻，當(dāng)?shù)谝粋€進(jìn)程重復(fù)“進(jìn)入-退出”它的臨界區(qū)域這一過程。Dekker算法在一個進(jìn)程中設(shè)置一個轉(zhuǎn)向另一個進(jìn)程的值，從而

8、保證另一個進(jìn)程接下來進(jìn)入它的臨界區(qū)域。2.2 第一個將等待次數(shù)降低到n-1范圍內(nèi)的正確解決n個進(jìn)程臨界區(qū)問題的軟件解決方法是由日senberg和Mcguire設(shè)計的。這些進(jìn)程共享以下變量：enumpstateidle,wantin,incs;pstateflagn;intturn;flag的所有成員被初始化為idle;turn的初始值無關(guān)緊要(在0和n-1之間)。進(jìn)程pi的結(jié)構(gòu)見圖6.26。試證明這個算法滿足臨界區(qū)問題的所有三個要求。dowhile(TRUE)flagi=wantin;j=turn;while(j!=i)if(flagj!=idle)j=turn;elsej=(j+1)%n;f

9、lagi=incs;j=0;while(j<n)&&(j=I|flagj!=incs)j+;if(j>=n)&&(turn=I|flagturn=idle)break;/criticalsectionj=(turn+1)%n;while(flagj=idle)j=(j+1)%n;turn=j;flagi=idle;/remaindersectionwhile(TRUE);圖6.26Eisenberg和McGuire算法中的進(jìn)程pi結(jié)構(gòu)答：(1)互斥：注意到一個進(jìn)程只有在下列條件滿足時才能進(jìn)入臨界區(qū)域：沒有其他進(jìn)程在CS中有設(shè)置的標(biāo)識變量。保證沒有兩個

10、進(jìn)程同時進(jìn)入臨界區(qū)域。(2)有空讓進(jìn)：當(dāng)多進(jìn)程同時在CS中設(shè)置它們的標(biāo)識變量時，檢查是否有其他進(jìn)程在cs中設(shè)置標(biāo)識變量。這種情況發(fā)生時，所有的進(jìn)程意識到這里存在進(jìn)程競爭，在外層while(1)的循環(huán)下進(jìn)入下一次迭代，重置它們的標(biāo)識變量到want中。這個進(jìn)程僅能進(jìn)入臨界區(qū)域。(3)有限等待：當(dāng)進(jìn)程k在打算進(jìn)入臨界區(qū)域時，它的標(biāo)識不再置為空閑。任何序號不在輪次和k之間的進(jìn)程不能進(jìn)入臨界區(qū)域。與此同時，所有序號落在輪次和k之間且又想要進(jìn)入臨界區(qū)域的進(jìn)程能夠進(jìn)入臨界區(qū)域(這是基于系統(tǒng)一直在進(jìn)步的事實)，這個輪次值變得越來越接近ko最后，要么輪次變?yōu)閗,要么沒有哪些序號在輪次和k之間的進(jìn)程，這樣進(jìn)程k就

11、進(jìn)入臨界區(qū)域了。6.9試說明如果wait()和signal()操作不再是原子化操作，那么互斥可能是不穩(wěn)定的。答：買賣操作自動遞減和信號量有關(guān)的值。如果兩個買賣操作在信號量的值為1的信號量上執(zhí)行，而且這兩種操作不是自動執(zhí)行的，那么這兩個操作在進(jìn)展中會遞減信號量的值，從而干擾互斥。6.11理發(fā)店問題。一家理發(fā)店有一間有n把椅子的等待室和一間有一把理發(fā)椅的理發(fā)室。如果沒有顧客，理發(fā)師就去睡覺。如果顧客來時所有的椅子都有人，那么顧客就會離去。如果理發(fā)師在忙，而又有空閑的椅子，那么顧客會坐在其中一個空閑的椅子上。如果理發(fā)師在睡覺，顧客會搖醒他。編寫一個程序來協(xié)調(diào)理發(fā)師和顧客。答：當(dāng)系統(tǒng)中某一進(jìn)程使用某一

12、資源時，可以看作是消耗，且該進(jìn)程稱為消費者。而當(dāng)某個進(jìn)程釋放資源時，則它就相當(dāng)一個生產(chǎn)者。因此此題可看作是n個生產(chǎn)者和1個消費者問題。顧客作為生產(chǎn)者，每到來一個就使計數(shù)器count增加1,以便讓理發(fā)師理發(fā)(相當(dāng)于消費)至最后一個顧客(相當(dāng)于產(chǎn)品)。并且，第1個到來的顧客應(yīng)負(fù)責(zé)喚醒理發(fā)師；如果不是第1個到達(dá)的顧客，則在有空椅子的情況下坐下等待，否則離開理發(fā)店(該消息可由計數(shù)器count獲得)，所以可以通過一個有界緩沖區(qū)把理發(fā)師和顧客聯(lián)系起來通過對信號進(jìn)行P、V操作來實現(xiàn)有關(guān)問題和相關(guān)描述?？刂谱兞縲aiting用來記錄正在等候顧客的理發(fā)師數(shù)；信號量customers用來記錄等候理發(fā)的顧客數(shù)，并用

13、作阻塞理發(fā)師進(jìn)程；信號量barbers用來記錄正在等候顧客的理發(fā)師數(shù)，并用作阻塞顧客進(jìn)程。信號量mutex用于互斥。初始化：intlongwaiting(0);/正在等待的顧客的數(shù)目customers,barbers,mutex:semaphore;customers:0;barbers:=1;waiting:=0;mutex:=NULL;理發(fā)師進(jìn)程：barber()begindoP(customers)，若無顧客，理發(fā)師睡眠p(mutex);/進(jìn)程互斥waiting-;/等候顧客減1V(barbes);/理發(fā)師為下一個顧客理發(fā)V(mutex);/開放臨界區(qū)cut-hair();/正在理發(fā)while(TURE)是否還有顧客顧客進(jìn)程：customer()begindoP(mutex);/進(jìn)程互斥if(waiting)waiting+;/等待顧客數(shù)加1V(customers);/喚醒理發(fā)師V(mutex);/開放臨界區(qū)P(barbers);/理發(fā)師沒空，顧客等候get-haircut;/顧客準(zhǔn)備理發(fā))elseV(utex);/無空閑位，顧客離開while(TRUE)6.1