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

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

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

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

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

5、B鏈接到隊列的尾部，優(yōu)先級以a速率改變；當CPU空閑時，CPU分配給位于隊列頭的進程，優(yōu)先級加快，以3速率改變，接著該運行進程從隊列中刪除。b.LIFO后進先服務調(diào)度算法。同上，當進程進入到就緒隊列時，優(yōu)先級以a速率改變，等待后進的進程先調(diào)度，之后輪到該進程時，優(yōu)先級加快，以3速率改變，完成調(diào)度。2.1 第一個著名的正確解決兩個進程的臨界區(qū)問題的軟件方法是Dekker設計的。兩個進程P0和P1共享以下變量：booleanflag2;/*initiallyfalse*/intturn;進程Pi（i=0或1）的結(jié)構見6.25,另一個進程為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算法中的進程pi結(jié)構答：這個算法滿足臨界區(qū)問題的三個要求：(1) 在標記和返回變量的使用中，互斥條件是保證的。如果兩個進程將它們的標識設為真，那么只有一個進程會成功進行，即輪到的那個進程。當另一個進程更新它的返回變量時，等待的那個進程只能進入它的臨界區(qū)域。(2) 就緒的進程，通過標志

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

8、保證另一個進程接下來進入它的臨界區(qū)域。2.2 第一個將等待次數(shù)降低到n-1范圍內(nèi)的正確解決n個進程臨界區(qū)問題的軟件解決方法是由日senberg和Mcguire設計的。這些進程共享以下變量：enumpstateidle,wantin,incs;pstateflagn;intturn;flag的所有成員被初始化為idle;turn的初始值無關緊要(在0和n-1之間)。進程pi的結(jié)構見圖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算法中的進程pi結(jié)構答：(1)互斥：注意到一個進程只有在下列條件滿足時才能進入臨界區(qū)域：沒有其他進程在CS中有設置的標識變量。保證沒有兩個

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

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

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

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