操作系統(tǒng)試題庫

1、200353. 某車站售票廳，任何時(shí)刻最多可容納20名購票者進(jìn)入，當(dāng)售票少于20名購票者時(shí)，則廳外的購票者可立即進(jìn)入，否則需在外面等待。若把一個(gè)購票者看作一個(gè)進(jìn)程，請回答下列問題：（1）用P、V操作管理這些并發(fā)進(jìn)程時(shí)，應(yīng)怎樣定義信號(hào)量？寫出信號(hào)量的初值以及信號(hào)量各種取值的含義。（2）根據(jù)所定義的信號(hào)量，把應(yīng)執(zhí)行的P、V操作填入下述程序中，以保證進(jìn)程能夠正確地并發(fā)執(zhí)行。   Cobegin PROCESS Pi(i=1,2,)       Begin      進(jìn)入售

2、票廳；購票；退出；End;   Coend(3)若欲購票者最多為n個(gè)人，寫出信號(hào)量可能的變化范圍（最大值和最小值）。此題答案為：售票廳問題解答如下：（1）定義一信號(hào)量S，初始值為20。    S>0  S的值表示可繼續(xù)進(jìn)入售票廳的人數(shù)；    S=0  表示售票廳中已有20名購票者；    S<0  |S|的值為等待進(jìn)入售票廳中的人數(shù)。（2）上框?yàn)镻(S)，下框?yàn)閂(S)。（3）S的最大值為20，S的最小值為20N，N為某一時(shí)刻需要進(jìn)入售票廳的

3、最多人數(shù)。  此題難度等級為：A200354. 已經(jīng)系統(tǒng)中有四個(gè)緩沖池M0，M1，M2，M3。其容量分別為3、2、3、2，現(xiàn)各緩沖區(qū)分別存在0、1、0、2個(gè)數(shù)據(jù)。現(xiàn)同時(shí)有四個(gè)進(jìn)程P0、P1、P2、P3分別在各緩沖區(qū)間不斷地移動(dòng)數(shù)據(jù)（見圖3.5）。例如，P0進(jìn)程從M0向M1移動(dòng)數(shù)據(jù)。試用信號(hào)量及其P、V（或signal，wait）操作及類Pasic/C語言描述各進(jìn)程之間的同步關(guān)系，并給出各信號(hào)量的含義和初值。 此題答案為：緩沖池各問題解答如下： （1）互斥信號(hào)量和初值M(0)=1，M(1)=1，M(2)=1，M(3)=1， （2）同步信號(hào)量  &

4、#160;   Full(i)表示buffer(i)是否有數(shù)據(jù)；      初值為full(0)=0，full(1)=1，full(2)=0，full(3)=2；      Empty(i)表示buffer(i)是否有空間；      初值為empty(0)=3，empty(1)=1，empty(2)=3，empty(3)=0（3）進(jìn)程i的程序     Process Proc(i)&#

5、160;          p(full(i);            p(empty(i+1) mod 5);            p(m(i);            move;

6、60;           v(m(i);            v(m(full(i+1) mod 5);            v(empty (i);          此題難度等級為：A200

7、356. 設(shè)有兩個(gè)優(yōu)先級相同的進(jìn)程P1和P2如下，信號(hào)量S1和S2的初值均為0。試問P1、P2并發(fā)執(zhí)行結(jié)束后，x=?,y=?,z=? <進(jìn)程P1>    Y:=1;    Y:=y+2;    V(S1);    Z:=y+1;    P(S2);    Y:=z+y;  進(jìn)程P2    X:=1;    X:=x+

8、1;    P(S1);    X:=x+y;    V(S2);    Z:=x+z;此題答案為：答：因?yàn)镻1和P2是兩個(gè)并發(fā)進(jìn)程，所以進(jìn)程調(diào)度程序調(diào)度P1 和P2的順序是不確定的。  這里不妨假設(shè)P1先執(zhí)行。進(jìn)程P1執(zhí)行到語句P(S2)時(shí)，S21，進(jìn)程P1阻塞。此時(shí)y=3,z=4。當(dāng)進(jìn)程調(diào)度程序調(diào)度到進(jìn)程P2時(shí)，由于進(jìn)程P1已執(zhí)行了V(S1)，進(jìn)程P2在執(zhí)行P(S1)時(shí)并未阻塞而繼續(xù)執(zhí)行，當(dāng)執(zhí)行到 V(S2)時(shí)，將P1喚醒，然后執(zhí)行最后一個(gè)語句z:=x+z，此時(shí)

9、x=5,z=9。當(dāng)進(jìn)程P1再次被調(diào)度時(shí)，繼續(xù)執(zhí)行P1的最后一個(gè)語句，此時(shí)y=12，最終結(jié)果是：x=5,y=12,z=9。   如果當(dāng)P2進(jìn)程執(zhí)行到 V(S2)時(shí)，將P1喚醒，然后P2進(jìn)程被中斷，此時(shí)x=5,y=3,z=4。P1進(jìn)程開始執(zhí)行然后執(zhí)行最后一個(gè)語句y:=z+y，此時(shí)x=5,y=3,z=7。然后P2進(jìn)程被調(diào)度，執(zhí)行z:=x+z，此時(shí)x=5,y=3,z=12。   如果P2先執(zhí)行，則執(zhí)行結(jié)果與上面相同。  此題難度等級為：D200362. 在批處理系統(tǒng)、分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)中，各采用哪幾個(gè)進(jìn)程（作業(yè)）調(diào)度算法？此題答案為：答：（1）批處理系

10、統(tǒng)中的作業(yè)調(diào)度算法有：先來先服務(wù)算法（FCFS）、短作業(yè)優(yōu)先算法（SJF）、優(yōu)先級調(diào)度算法（HPF）和高響應(yīng)比優(yōu)先算法（RF）。批處理系統(tǒng)的進(jìn)程調(diào)度算法有：先進(jìn)先出算法（FIFO）、短進(jìn)程優(yōu)先算法（SPF）、優(yōu)先級調(diào)度算法（HPF）和高響應(yīng)比優(yōu)先算法（RF）。（2）分時(shí)系統(tǒng)中只設(shè)有進(jìn)程調(diào)度（不設(shè)作業(yè)調(diào)度），其進(jìn)程調(diào)度算法只有輪轉(zhuǎn)法（RR）一種。（3）實(shí)時(shí)系統(tǒng)中只設(shè)有進(jìn)程（不設(shè)作業(yè)調(diào)度），其進(jìn)程調(diào)度算法調(diào)度有：輪轉(zhuǎn)法、優(yōu)先級調(diào)度算法。前者適用于時(shí)間要求不嚴(yán)格的實(shí)時(shí)系統(tǒng)；后者用于時(shí)間要求嚴(yán)格的實(shí)時(shí)系統(tǒng)。后者又可細(xì)分為：非搶占式優(yōu)先級調(diào)度、搶占式優(yōu)先級調(diào)度、基于時(shí)鐘中斷的搶占式優(yōu)先級調(diào)度。注意，一個(gè)

11、純粹的實(shí)時(shí)系統(tǒng)是針對特定應(yīng)用領(lǐng)域設(shè)計(jì)的專用系統(tǒng)。作業(yè)提交的數(shù)量不會(huì)超過系統(tǒng)規(guī)定的多道程序的道數(shù)，因而可全部進(jìn)入內(nèi)存。若將實(shí)時(shí)系統(tǒng)與批處理系統(tǒng)結(jié)合的話，就可以讓作業(yè)量超過多道程序道數(shù)，使優(yōu)先級低的作業(yè)呆在外存的后備隊(duì)列上。  此題難度等級為：A200372. 假設(shè)系統(tǒng)中有5個(gè)進(jìn)程，它們的到達(dá)時(shí)間和服務(wù)時(shí)間見下表1，忽略I/O以及其他開銷時(shí)間，若按先來先服務(wù)（FCFS）、非搶占的短作業(yè)優(yōu)先和搶占的短作業(yè)優(yōu)先三種調(diào)度算法進(jìn)行CPU調(diào)度，請給出各個(gè)進(jìn)程的完成時(shí)間、周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間、平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間，完成表2。     表1 進(jìn)程到達(dá)

12、和需要服務(wù)時(shí)間  進(jìn)程     到達(dá)時(shí)間     服務(wù)時(shí)間   A          0            3   B          2   

13、         6   C          4            4   D          6       

14、     5   E          8            2                      

15、0; 表2 進(jìn)程的完成時(shí)間和周轉(zhuǎn)時(shí)間             進(jìn)程       A      B        C       D      E    

16、;    平均FCFS        完成時(shí)間                       周轉(zhuǎn)時(shí)間                   帶

17、權(quán)周轉(zhuǎn)時(shí)間       SPF(非搶占) 完成時(shí)間                       周轉(zhuǎn)時(shí)間                   帶權(quán)周轉(zhuǎn)時(shí)間  &

18、#160;    SPF(搶占)   完成時(shí)間                       周轉(zhuǎn)時(shí)間                   帶權(quán)周轉(zhuǎn)時(shí)間   &#

19、160;  此題答案為：                        表2 進(jìn)程的完成時(shí)間和周轉(zhuǎn)時(shí)間                  進(jìn)程    

20、     A      B        C       D       E        平均  FCFS          完成時(shí)間 &

21、#160;     3      9       13      18       20                   周轉(zhuǎn)時(shí)間   

22、    3      7        9      12       12       8.6            帶權(quán)周轉(zhuǎn)時(shí)間   &

23、#160;   1.00   1.17    2.25    2.40    6.00      2.56  SPF(非搶占)   完成時(shí)間       3      9       15  

24、0;   20       11                   周轉(zhuǎn)時(shí)間       3      7       11    

25、60; 14       3        7.6            帶權(quán)周轉(zhuǎn)時(shí)間      1.00   1.17    1.75    2.80    1.50  

26、0;    1.84  SPF(搶占)     完成時(shí)間       3      15      8       20      10          &#

27、160;         周轉(zhuǎn)時(shí)間       3      13      4       14       2        7.2   

28、;         帶權(quán)周轉(zhuǎn)時(shí)間      1.00    2.16   1.00    2.80    1.00       1.59  此題難度等級為：A200377. 一個(gè)邏輯空間最多可有64個(gè)頁，每頁1KB字節(jié)。若把它映射到由32個(gè)物理塊組成的存儲(chǔ)器。問：（1）有效的邏輯地址由多少

29、位？（2）有效的物理地址由多少位？此題答案為：答：一個(gè)邏輯空間有64個(gè)頁，每頁1KB字節(jié)。若把它映射到由32個(gè)物理塊組成的存儲(chǔ)囂。6426，則：（1）邏輯地址有16位。（2）物理地址有15位。說明：解此題的關(guān)鍵是要知道在分頁管理中，"頁"和"塊"是一樣大小的，這樣才知道物理存儲(chǔ)器是32KB。  此題難度等級為：B200380. 在某分頁系統(tǒng)中，測得CPU和磁盤的利用率如下，試指出每種情況下的問題和措施。（1）CPU的利用率為15%，磁盤利用率為95%。（2）CPU的利用率為88%，磁盤利用率為3%。（3）CPU的利用率為13%，磁盤利用率為5%

30、。此題答案為：答：在某分頁虛存系統(tǒng)中，在題中的CPU和磁盤的利用率的情況下，出現(xiàn)的問題和應(yīng)采取的措施如下：（1）可能已出現(xiàn)了抖動(dòng)現(xiàn)象，應(yīng)減少系統(tǒng)的進(jìn)程數(shù)。（2）系統(tǒng)比較正常，可考慮適當(dāng)增加進(jìn)程數(shù)以提高資源利用率。（3）CPU和磁盤的利用率都較低，必須增加并發(fā)進(jìn)程數(shù)。  此題難度等級為：A200381. 對訪問串：1，2，3，4，1，2，5，1，2，3，4，5，指出在駐留集大小分別為3，4時(shí)，使用FIFO和LRU替換算法的缺頁次數(shù)。結(jié)果說明了什么？此題答案為：答：首先采用FIFO，當(dāng)m=3時(shí)，缺頁次數(shù)9，當(dāng)m=4時(shí)，缺頁次數(shù)10。采用LRU算法，當(dāng)m=3時(shí)，缺頁次數(shù)10；當(dāng)m=4時(shí)，缺

31、頁次數(shù)8。結(jié)果說明：FIFO有Belady奇異現(xiàn)象，即不滿足駐留集增大，缺頁次數(shù)一定減小的規(guī)律；另外在m=3時(shí)，LRU的缺頁次數(shù)比FIFO要多，所以LRU算法并不總優(yōu)于FIFO，還要看當(dāng)前訪問串的特點(diǎn)。  此題難度等級為：C200389. 一個(gè)分頁存儲(chǔ)器的頁表存放在內(nèi)存。（1）若內(nèi)存的存取周期為0.6ms，則CPU從內(nèi)存取一條指令（或一個(gè)操作數(shù)）需多少時(shí)間？（2）若使用快表且快表的命中率為75%，則內(nèi)存的平均存取周期為多少？此題答案為：答：一個(gè)分頁存儲(chǔ)器的頁表存放在內(nèi)存  （1）因?yàn)轫摫矸旁趦?nèi)存，故取一條指令（或一個(gè)操作數(shù)）須訪問兩次內(nèi)存，所以需0.6ms×2=1

32、.2ms的時(shí)間。  （2）這里家假設(shè)訪問快表的時(shí)間忽略不計(jì)，命中快表時(shí)，取數(shù)只要一次訪問，故此時(shí)的平均存取周期為0.6ms×0.75+1.2ms×(1-0.75)=0.75ms  此題難度等級為：A200392. 在一個(gè)請求分頁系統(tǒng)中，采用LRU頁面置換算法時(shí)，假如一個(gè)作業(yè)的頁面走向?yàn)?、3、2、1、4、3、5、4、3、2、1、5，當(dāng)分配給該作業(yè)的物理內(nèi)存塊數(shù)M分別為3和4時(shí)，分別計(jì)算在訪問過程中所發(fā)生的缺頁次數(shù)和缺頁率，并畫出頁面置換圖。此題答案為：解：   訪問過程中缺頁情況（M=3）    

33、;    頁面走向                   4   3   2   1   4   3   5   4   3   2   1   5  

34、 最近最長時(shí)間未使用的頁面                4   3   3   2   4   3   5   4   3   2           

35、60;                           4   3   2   1   4   3   5   4   3   2  

36、1   最近剛使用過的頁面              4   3   2   1   4   3   5   4   3   2   1   5       

37、缺頁                                                    當(dāng)M=3時(shí)，缺頁次數(shù)為10次，缺頁率為10/12=0.83=83%。 &

38、#160;       訪問過程中缺頁情況（M=4）        頁面走向                    4   3   2   1   4   3   5&#

39、160;  4   3   2   1   5   最近最長時(shí)間未使用的頁面                     4   3   2   1   1   1   5&

40、#160;  4   3                                            4  

41、3   2   1   4   3   5   4   3   2                                

42、          4   3   2   1   4   3   5   4   3   2   1   最近剛使用過的頁面             

43、0; 4   3   2   1   4   3   5   4   3   2   1   5        缺頁                &

44、#160;                                          當(dāng)M=4時(shí)，缺頁次數(shù)為8次，缺頁率為8/12=0.66=66%。   可見，增加分配給作業(yè)的內(nèi)存塊數(shù)可以減少缺頁次數(shù)，從而降低缺頁率。 

45、 此題難度等級為：A200394. 對于一個(gè)使用快表的頁式虛存，設(shè)快表的命中率為70%，內(nèi)存的存取周期為1ns；缺頁處理時(shí)，若內(nèi)存有可用空間或被置換的頁面在內(nèi)存未被修改過，則處理一個(gè)缺頁中斷需8000ns，否則需20000ns。假定被置換的頁面60%是屬于后一種情況，為了保證有效存取時(shí)間不超過2ns，問可接受的最大缺頁率是多少？此題答案為：答：設(shè)可接受的最大缺頁率位p，則有1ns×0.7+2ns×(1-0.7-p)+0.4p×8000ns+0.6p×20000ns=2ns即       0.7+

46、0.6-2p+3200p+12000p=2          15198p=0.7          P=0.000046  此題難度等級為：A200396. 在分頁存儲(chǔ)管理系統(tǒng)中，存取一次內(nèi)存的時(shí)間是8ns，查詢一次快表的時(shí)間是1ns，缺頁中斷的時(shí)間是20ns。假設(shè)頁表的查詢與快表的查詢同時(shí)進(jìn)行，當(dāng)查詢頁表時(shí)，如果該頁在內(nèi)存但快表中沒有頁表項(xiàng)，系統(tǒng)將自動(dòng)把該頁頁表項(xiàng)送入快表。一個(gè)作業(yè)最多可保留3個(gè)頁面在內(nèi)

47、存?，F(xiàn)在開始執(zhí)行一作業(yè)，系統(tǒng)連續(xù)對作業(yè)的2，4，5，2，7，6，4，8頁面的數(shù)據(jù)進(jìn)行一次存取，如分別采用FIFO算法和最優(yōu)頁面置換算法，求每種上存取這些數(shù)據(jù)需要的總時(shí)間。此題答案為：答：（1）FIFO         第2頁面：208×3         第4頁面：208×3         第5頁面：208×3 &#

48、160;       第2頁面：81         第7頁面：208×3         第6頁面：208×3         第4頁面：208×3         第8頁面：208

49、15;3   因此總的時(shí)間是（208×3）×7（81）ns(2) OPT         第2頁面：208×3         第4頁面：208×3         第5頁面：208×3         第2頁

50、面：81         第7頁面：208×3         第6頁面：208×3         第4頁面：81         第8頁面：81   因此總的時(shí)間是（208×3）×5（81）×3ns

51、0; 此題難度等級為：A200532. 在一個(gè)請求分頁系統(tǒng)中，采用LRU頁面置換算法時(shí)，假如一個(gè)作業(yè)的頁面走向?yàn)?、3、2、1、1、3、5、1、3、2、1、5，當(dāng)分配給該作業(yè)的物理內(nèi)存塊數(shù)M分別為3和4時(shí)，分別計(jì)算在訪問過程中所發(fā)生的缺頁次數(shù)和缺頁率，并畫出頁面置換圖。此題答案為：解：   訪問過程中缺頁情況（M=3）        頁面走向              

52、;     1   3   2   1   1   3   5   1   3   2   1   5   最近最長時(shí)間未使用的頁面                1&#

53、160;  3   3   2   1   3   5   1   3   2                             &#

54、160;         1   3   2   2   1   3   5   1   3   2   1   最近剛使用過的頁面              1

55、0;  3   2   1   1   3   5   1   3   2   1   5        缺頁                 

56、60;                                         當(dāng)M=3時(shí)，缺頁次數(shù)為6次，缺頁率為6/12=0.5=50%。         訪問過程中缺頁情況（M

57、=4）        頁面走向                    1   3   2   1   1   3   5   1   3   2 &#

58、160; 1   5   最近最長時(shí)間未使用的頁面                                 2   2   2   5   5 

59、;  3                                            1   3   3

60、60;  2   1   3   5   1   3   2                                    

61、;       1   3   2   2   1   3   5   1   3   2   1   最近剛使用過的頁面               1 &#

62、160; 3   2   1   1   3   5   1   3   2   1   5        缺頁                  &

63、#160;                             當(dāng)M=4時(shí)，缺頁次數(shù)為4次，缺頁率為4/12=0.33=33%。   可見，增加分配給作業(yè)的內(nèi)存塊數(shù)可以減少缺頁次數(shù)，從而降低缺頁率。   此題難度等級為：A200592. 在一個(gè)請求分頁系統(tǒng)中，采用OPT頁面置換算法時(shí)，假如一個(gè)作業(yè)的頁面走向?yàn)?、3

64、、2、1、4、3、5、4、3、2、1、5，當(dāng)分配給該作業(yè)的物理內(nèi)存塊數(shù)M分別為3和4時(shí)，分別計(jì)算在訪問過程中所發(fā)生的缺頁次數(shù)和缺頁率，并畫出頁面置換圖。此題答案為：解：   訪問過程中缺頁情況（M=3）        頁面走向              4   3   2   1   4 

65、  3   5   4   3   2   1   5   最近最長時(shí)間未使用的頁面           2   1   1   1   5   4  4/3 3/2 1/2     

66、60;                            3   3   3   4   3   3   5      最近剛使用過的頁面  &#

67、160;      4   4   4   4   3   4   4   3   5   5   5        缺頁             &

68、#160;                                     當(dāng)M=3時(shí)，缺頁次數(shù)為7次，缺頁率為7/12=0.583=58.3%。         訪問過程中缺頁情況（M=4）    &

69、#160;   頁面走向             4   3   2   1   4   3   5   4   3    2     1   5   最近最長時(shí)間未使用的頁面 &

70、#160;            1   1   1   5   4  4/3 4/3/2 1/3/2                         

71、;            2   2   2   2   2   5                            

72、60;      3   3   3   4   3   3   2   5       最近剛使用過的頁面        4   4   4   4   3   4 &

73、#160; 4   3   2    5     5           缺頁                              &

74、#160;                       當(dāng)M=4時(shí)，缺頁次數(shù)為8次，缺頁率為6/12=0.5=50%。   可見，增加分配給作業(yè)的內(nèi)存塊數(shù)可以減少缺頁次數(shù)，從而降低缺頁率。   此題難度等級為：A200593. 在一個(gè)請求分頁系統(tǒng)中，采用FIFO頁面置換算法時(shí)，假如一個(gè)作業(yè)的頁面走向?yàn)?、3、2、1、4、3、5、4、3、2、1、5，當(dāng)分配給該作業(yè)的物理

75、內(nèi)存塊數(shù)M分別為3和4時(shí)，分別計(jì)算在訪問過程中所發(fā)生的缺頁次數(shù)和缺頁率，并畫出頁面置換圖。此題答案為：解：   訪問過程中缺頁情況（M=3）        頁面走向                   4   3   2   1   4 &

76、#160; 3   5   4   3   2   1   5   最近最長時(shí)間未使用的頁面                4   3   2   1   4   4   4 &#

77、160; 3   5   5                                       4   3   2 &#

78、160; 1   4   3   3   3   5   2   2   最近剛使用過的頁面              4   3   2   1   4   3   5 

79、0; 5   5   2   1   1        缺頁                                      &#

80、160;            當(dāng)M=3時(shí)，缺頁次數(shù)為9次，缺頁率為9/12=0.75=75%。         訪問過程中缺頁情況（M=4）        頁面走向                  

81、;  4   3   2   1   4   3   5   4   3   2   1   5   最近最長時(shí)間未使用的頁面                  

82、0;  4   4   4   3   2   1   5   4   3                             

83、0;              4   3   3   3   2   1   5   4   3   2                &

84、#160;                         4   3   2   2   2   1   5   4   3   2   1 

85、60; 最近剛使用過的頁面               4   3   2   1   1   1   5   4   3   2   1   5        缺頁&#

86、160;                                                     當(dāng)M=4時(shí)，缺頁次數(shù)為10次，缺頁率為10/12=0.8

87、6=83%。   可見，增加分配給作業(yè)的內(nèi)存塊數(shù)并不能減少缺頁次數(shù)，降低缺頁率，這種現(xiàn)象叫抖動(dòng)現(xiàn)象（Belady）。  此題難度等級為：A200594. 利用信號(hào)量機(jī)制描述前趨關(guān)系：S=S1,S2,S3,S4,S5,S6,S7=(S1,S2),(S1,S3),(S2,S4),(S2,S5),(S3,S5),(S3,S6),(S4,S7),(S5,S7),(S6,S7)此題答案為：解：Var a,b,c,d,e,f,g,h,i,:semaphore:=0,0,0,0,0,0,0,0,0,0;      &#

88、160;      Begin     Parbegin       Begin S1;signal(a);signal(b);end;      Begin wait(a);S2;signal(c);signal(d);end;      Begin wait(b);S3;signal(e);signal(f);end;    

89、;  Begin wait(c);S4;signal(g);end;      Begin wait(d);wait(e);S5;signal(h);end;      Begin wait(f);S6;signal(i);end;      Begin wait(g);wait(h);wait(i);S7;end;          &

90、#160;                 Parendend  此題難度等級為：A200596. 利用記錄型信號(hào)量解決經(jīng)典同步問題：生產(chǎn)者消費(fèi)者此題答案為：解：  Var mutex,empty,full:semaphore:=1,n,0;     buffer:array0,.,n-1 of item;     in,out:integer:=

91、0,0;     begin       parbegin         proceducer:           begin             repeat  

92、0;             .              producer an item nextp;                .     

93、         wait(empty);              wait(mutex);              buffer(in):=nextp;        

94、60;     in:=(in+1) mod n;              signal(mutex);              signal(full);           

95、0; until false;           end         consumer:           begin             repeat   

96、           wait(full);              wait(mutex);              nextp:=buffer(out);      

97、60;       out:=(out+1) mod n;              signal(mutex);              signal(empty);         &

98、#160;    consumer the item in nextc;             until false;           end       patend     end  此題難度等級為：A200597. 利用記錄型

99、信號(hào)量解決經(jīng)典進(jìn)程同步問題：讀者寫者此題答案為：解：  Var rmutex,wmutex:semaphore:=1,1;      Readcount:integer:=0;      Begin        parbegin           Reader:    

100、60;        begin               repeat                wait(rmutex)         &

101、#160;      if Readcount=0 then wait(wmutex);                Readcount:=Readcount+1;                signal(rmutex)  

102、              .                perform read operation;                .  &#

103、160;             wait(rmutex);                Readcount:=Readcount-1;                if Re

104、adcount=0 then signal(wmutex);                signal(rmutex);              until false;            

105、end           Writer:              begin                repeat        

106、          wait(wmutex);                  perform write operation;                  si

107、gnal(wmutex);                until false              end          parend      End  此

108、題難度等級為：A200598. 有一個(gè)車間不斷取A和B進(jìn)行裝配，每次各取一個(gè)。為避免零件銹蝕，遵循先入庫者先出庫的原則。有兩組供應(yīng)商分別不斷供應(yīng)A和B（每次1個(gè)）。為保證齊套和合理庫存，當(dāng)某種零件的數(shù)量比另一種零件的數(shù)量多得超過n（n<m）時(shí)，暫停對數(shù)量大的零件的供貨，集中補(bǔ)充數(shù)量少的零件。  試用Wait和Signal原語正確實(shí)現(xiàn)。此題答案為：解： var mutex,emptya,emptyb,fulla,fullb,sa,sb:semaphore:=1,m,m,0,0,n,n;    Begin   &

109、#160;  cobegin        provider_A();        provider_B();        assembiling_shop();      coend      provider_A()    

110、0;   begin          repeat             wait(emptya);             wait(sa);        

111、60;    wait(mutex);             put A into the storehouse;             signal(mutex);             signal(

112、fulla);             signal(sb);          until false;        end      provider_B()        begin 

113、;         repeat             wait(emptyb);             wait(sb);             wai

114、t(mutex);             put B into the storehouse;             signal(mutex);             signal(fullb);   

115、          signal(sa);          until false;        end     asemmbling_shop()        begin     &

116、#160;    repeat             wait(fulla);             wait(fullb);             wait(mutex);  

117、60;          asemmbling A and B;             signal(mutex);             signal(emptya);        

118、     signal(emptyb);          until false;        end    corend    End  此題難度等級為：A200599. 一個(gè)主修動(dòng)物行為學(xué)，輔修計(jì)算機(jī)科學(xué)的學(xué)生參加了一個(gè)課題，調(diào)查花果山的猴子能否被教會(huì)理解死鎖。他找到一處峽谷，橫跨峽谷拉了一根繩索（假設(shè)為南北方向），這些

119、猴子就可以攀登著繩索跨過峽谷。只要它們朝著相同的方向，同一時(shí)刻可以有多個(gè)猴子通過。但是如果在相反方向商同時(shí)有猴子通過則會(huì)發(fā)生死鎖（這些猴子卡在繩子中間，假設(shè)這些猴子無法在繩索商從另一只猴子身上翻過去）。如果一只猴子想跨越峽谷，他必須看當(dāng)前是否有別的猴子在逆向通過。請使用信號(hào)量寫一個(gè)避免思索的程序來解決該問題。此題答案為：解：  Begin    var Smutex,Nmutex,SMonkeyCount,NMonkeyCount:Semaphore;        SMonkeyCo

120、unt:=0;        NMonkeyCount:=0;        Smutex:=1;        Nmutex:=1;        mutex:=1;        ParBegin    &

121、#160;     Southi(i=1,2,3,.)          Begin             wait(Smutex);             if SMonkeyCount=0 then wait(mutex)

122、;             SMonkeyCount:=SMonkeyCount+1;             signal(Smutex);             Cross the cordage;   

123、          wait(Smutex);             SMonkeyCount:=SMonkeyCount-1;             if SMonkeyCount=0 then signal(mutex);   &#

124、160;         signal(Smutex);          End          Northi(i=1,2,3,.)          Begin       

125、      wait(Smutex);             if NMonkeyCount=0 then wait(mutex);             NMonkeyCount:=NMonkeyCount+1;       

126、0;     signal(Nmutex);             Cross the cordage;             wait(Nmutex);             NMonkeyC

127、ount:=NMonkeyCount-1;             if NMonkeyCount=0 then signal(mutex);             signal(Nmutex);          End    

128、;    parEnd  End  此題難度等級為：A200600. 設(shè)有兩個(gè)生產(chǎn)者進(jìn)程A和B和一個(gè)銷售進(jìn)程C，它們共享一個(gè)無限大的倉庫，生產(chǎn)者每次循環(huán)生產(chǎn)一個(gè)產(chǎn)品，然后入庫供銷售者銷售；銷售者每次循環(huán)從倉庫中取出一個(gè)產(chǎn)品銷售。如果不允許同時(shí)入庫，也不允許同時(shí)出庫；而且要求生產(chǎn)和銷售A產(chǎn)品和B產(chǎn)品數(shù)量都滿足以下關(guān)系：-n<=A的件數(shù)-B的件數(shù)<=m，其中n，m是正整數(shù)。請用信號(hào)量機(jī)制寫出A，B，C三個(gè)進(jìn)程的工作流程。此題答案為：解：  Var difference:integer:=0;   

129、   SAB,SBA,S,SA,SB,mutex:semaphore:=m,n,0,0,0,1;      Begin        parbegin           process A:              begin

130、                repeat                  wait(SAB);               

131、   produce a product A;                  signal(SBA);                  wait(mutex);      &

132、#160;           add the product A to the storehouse;                  signal(mutex);             

133、60;    signal(SA);                  signal(S);                until false;        

134、60;     end            process B:              begin                repeat  

135、;                wait(SBA);                  produce b product B;            

136、60;     signal(SAB);                  wait(mutex);                  add the product B to the storehouse; 

137、                 signal(mutex);                  signal(SB);            

138、60;     signal(S);                until false;            process C:              beg

139、in                repeat                  wait(S);               

140、   if difference<=-n then                     begin                       

141、60;wait(SA);                        wait(mutex);                       

142、; take a product A from storehouse;                        signal(mutex);                  

143、0;     difference:=difference+1;                     end                  elseif difference>

144、=m then                     begin                        wait(SB);   &

145、#160;                    wait(mutex);                        take a product B from storeho

146、use;                        signal(mutex);                        diff

147、erence:=difference-1;                     end                  else        

148、             wait(mutex);                     take a product A or B from storehouse;         &#

149、160;           signal(mutex);                     if (product_type=A) then            

150、0;            begin                            wait(SA);         

151、                   difference:=difference+1;                         end    

152、;                  else                         begin       

153、                     wait(SB);                            difference:=difference-1;                         end