(完整word版)操作系統(tǒng)第五版費祥林_課后習(xí)題答案解析參考(完整word版)操作系統(tǒng)第五版費祥林_課后習(xí)題答案解析參考(完整word版)操作系統(tǒng)第五版費祥林_課后習(xí)題答案解析參考第一章操作系統(tǒng)概論1、有一臺計算機，具有IMB內(nèi)存，操作系統(tǒng)占用200KB，每個用戶進程各占200KB。如果用戶進程等待I/O的時間為80%，若增加1MB內(nèi)存，則CPU的利用率提高多少？

答：設(shè)每個進程等待I/O的百分比為P，則n個進程同時等待刀O的概率是Pn，當(dāng)n個進程同時等待I/O期間CPU是空閑的，故CPU的利用率為1-Pn。由題意可知，除去操作系統(tǒng)，內(nèi)存還能容納4個用戶進程，由于每個用戶進程等待I/O的時間為80%,故：

CPU利用率＝l-（80%)4=0.59

若再增加1MB內(nèi)存，系統(tǒng)中可同時運行9個用戶進程，此時：cPu利用率＝l-（1-80%)9=0.87

故增加IMB內(nèi)存使CPU的利用率提高了47%:

87％/59％=147%

147％-100%=47%

2一個計算機系統(tǒng)，有一臺輸入機和一臺打印機，現(xiàn)有兩道程序投入運行，且程序A先開始做，程序B后開始運行。程序A的運行軌跡為：計算50ms、打印100ms、再計算50ms、打印100ms，結(jié)束。程序B的運行軌跡為：計算50ms、輸入80ms、再計算100ms，結(jié)束。試說明（1）兩道程序運行時，CPU有無空閑等待？若有，在哪段時間內(nèi)等待？為什么會等待？(2）程序A、B有無等待CPU的情況？若有，指出發(fā)生等待的時刻。

答：畫出兩道程序并發(fā)執(zhí)行圖如下：

（1）兩道程序運行期間，CPU存在空閑等待，時間為100至150ms之間（見圖中有色部分）

（2）程序A無等待現(xiàn)象，但程序B有等待。程序B有等待時間段為180rns至200ms間（見圖中有色部分）

3設(shè)有三道程序，按A、B、C優(yōu)先次序運行，其內(nèi)部計算和UO操作時間由圖給出。

試畫出按多道運行的時間關(guān)系圖（忽略調(diào)度執(zhí)行時間）。完成三道程序共花多少時間？比單道運行節(jié)省了多少時間？若處理器調(diào)度程序每次進行程序轉(zhuǎn)換化時lms,試畫出各程序狀態(tài)轉(zhuǎn)換的時間關(guān)系圖。

答：

1）忽略調(diào)度執(zhí)行時間,多道運行方式（搶占式）:

?

搶占式共用去190ms，單道完成需要260ms，節(jié)省70ms。

忽略調(diào)度執(zhí)行時間，多道運行方式（非搶占式）:

非搶占式共用去180ms，單道完成需要260ms，節(jié)省80ms。

2）調(diào)度執(zhí)行時間1ms,多道運行方式（搶占式）:

調(diào)度執(zhí)行時間ITns，多道運行方式（非搶占式）:

4在單CPU和兩臺I/O(I1,12）設(shè)備的多道程序設(shè)計環(huán)境下，同時投入三個作業(yè)運行。它們的執(zhí)行軌跡如下：

Jobl:I2(30ms）、CPU(10ms）、I1(30ms）、CPU(10ms）、I2(20ms)

Job2:I1(20ms）、CPU(20ms）、I2(40ms)

JOb3:CPU(30ms）、I1(20ms）、CPU(10ms）、I1(10ms)

如果CPU、I1和I2都能并行工作，優(yōu)先級從高到低為Jobl、Job2和Job3，優(yōu)先級高的作業(yè)可以搶占優(yōu)先級低的作業(yè)的CPU，但不搶占I1和I2。試求：(l）每個作業(yè)從投入到完成分別所需的時間。（2）從投入到完成CPU的利用率。（3）I2設(shè)備利用率。

答：畫出三個作業(yè)并行工作圖如下（圖中著色部分為作業(yè)等待時間）:,

(1)Job1從投入到運行完成需110ms,Job2從投入到運行完成需90ms,Job3從投入到運行完成需110ms.

CPU空閑時間段為：60ms至70ms,80ms至90ms,100ms至110ms。所以CPU利用率為（110-30）/10=72.7％。

設(shè)備I1空閑時間段為：20ms至40ms,90ms至100ms,故I1的利用率為(110-30)/l10=72.7％。

設(shè)備I2空閑時間段為：30ms至50ms，故I2的利用率為(110-20)/110=81.8％。5在單CPU和兩臺I/O(I1,12）設(shè)備的多道程序設(shè)計環(huán)境下，同時投入三個作業(yè)運行。它們的執(zhí)行軌跡如下：

Jobl:I2(30ms）、CPU(10rns）、I1(30ms）、CPU(10ms)

Job2:I1(20ms）、CPU(20ms）、I2(40ms)

Job3:CPU(30ms）、I1(20ms)

如果CPU、I1和I2都能并行工作，優(yōu)先級從高到低為Job1、Job2和Job3，優(yōu)先級高的作業(yè)可以搶占優(yōu)先級低的作業(yè)的CPU。

試求：(l）每個作業(yè)從投入到完成分別所需的時間．

(2）每個作業(yè)投入到完成CPU的利用率。

（3）I/0設(shè)備利用率。

答：畫出三個作業(yè)并行工作圖如下（圖中著色部分為作業(yè)等待時間）:

(1)Job1從投入到運行完成需80ms,Job2從投入到運行完成需90ms,Job3從投入到運行完成需90ms。

(2)CPU空閑時間段為：60ms至70ms,80ms至90ms。所以CPU利用率為(90-20)/90=77.78％。

(3）設(shè)備I1空閑時間段為：20ms至40ms，故I1的利用率為（90-20)/90=77.78％。設(shè)備I2空閑時間段為：30ms至50ms，故I2的利用率為（90-20)/90=77.78％。

6若內(nèi)存中有3道程序A、B、C，它們按A、B、C優(yōu)先次序運行。各程序的計算軌跡為：

A：計算（20）、I/O(30）、計算（10)

B：計算（40）、I/O(20）、計算（10)

c：計算（10）、I/O(30）、計算（20)

如果三道程序都使用相同設(shè)備進行I/O（即程序用串行方式使用設(shè)備，調(diào)度開銷忽略不計）。試分別畫出單道和多道運行的時間關(guān)系圖。兩種情況下，CPU的平均利用率各為多少？

答：分別畫出單道和多道運行的時間圖

(1）單道運行時間關(guān)系圖

單道總運行時間為190ms。CPU利用率為（190-80）/190=57.9%

單道運行時間關(guān)系圖

多道總運行時間為140ms。CPU利用率為（140-30)/140=78.6%

7若內(nèi)存中有3道程序A、B、C，優(yōu)先級從高到低為A、B和C，它們單獨運行時的CPU和I/O占用時間為：

如果三道程序同時并發(fā)執(zhí)行，調(diào)度開銷忽略不計，但優(yōu)先級高的程序可中斷優(yōu)先級低的程序，優(yōu)先級與I/O設(shè)備無關(guān)。試畫出多道運行的時間關(guān)系圖，并問最早與最遲結(jié)束的程序是哪個？每道程序執(zhí)行到結(jié)束分別用了多少時間？計算三個程序全部運算結(jié)束時的CPU利用率？

答：畫出三個作業(yè)并發(fā)執(zhí)行的時間圖：

(l）最早結(jié)束的程序為B，最后結(jié)束的程序為C。

(2）程序A為250ms。程序B為220ms。程序C為310ms。

(3)CPU利用率為（310-120)/310=61.3%

有兩個程序，A程序按順序使用：(CPU)10秒、（設(shè)備甲）5秒、（CPU）5秒、（設(shè)備乙）10秒、（CPU）10秒。B程序按順序使用：（設(shè)備甲）10秒、（CPU）10秒、（設(shè)備乙）5秒、(CPU)5秒、（設(shè)備乙）10秒。在順序環(huán)境下先執(zhí)行A，再執(zhí)行B，求出總的CPU利用率為多少？

答：程序A執(zhí)行了40秒，其中CPU用了25秒。程序B執(zhí)行了40秒，其中CPU用了15秒。兩個程序共用了80秒，CPU化40秒。故CPU利用率為40/80=50％。

9、在某計算機系統(tǒng)中，時鐘中斷處理程序每次執(zhí)行的時間為2ms（包括進程切換開銷）。若時鐘中斷頻率為60HZ，試問CPU用于時鐘中斷處理的時間比率為多少？答：因時鐘中斷頻率為60HZ，所以，時鐘周期為：l/60s=50/3ms。在每個時鐘周期中，CPU花2ms執(zhí)行中斷任務(wù)。所以，CPU用于時鐘中斷處理的時間比率為：2(50/3)=6/50=12％。第二章處理器管理1.下列指令中哪些只能在核心態(tài)運行？

(l）讀時鐘日期；(2）訪管指令；(3）設(shè)時鐘日期；(4）加載PSW;(5）置特殊寄存器：(6）改變存儲器映象圖；(7）啟動I/O指令。

答：(3),(4),(5),(6),(7).

2假設(shè)有一種低級調(diào)度算法是讓“最近使用處理器較少的進程”運行，試解釋這種算法對“I/O繁重”型作業(yè)有利，但并不是永遠不受理“處理器繁重”型作業(yè)。

答：因為I/O繁忙型作業(yè)忙于I/O，所以它CPU用得少，按調(diào)度策略能優(yōu)先執(zhí)行。同樣原因一個進程等待CPU足夠久時，由于它是“最近使用處理器較少的進程”，就能被優(yōu)先調(diào)度，故不會饑餓。

3并發(fā)進程之間有什么樣的相互制約關(guān)系？下列日常生活中的活動是屬哪種制約關(guān)系：(1）踢足球，(2）吃自助餐，(3）圖書館借書，(4）電視機生產(chǎn)流水線工序。

答：并發(fā)進程之間的基本相互制約關(guān)系有互斥和同步兩種。其中（1）、（3）為互斥問題．(2）、(4）為同步問題。

4在按動態(tài)優(yōu)先數(shù)調(diào)度進程的系統(tǒng)中，每個進程的優(yōu)先數(shù)需定時重新計算。在處理器不斷地在進程之間交替的情況下，重新計算進程優(yōu)先數(shù)的時間從何而來？

答：許多操作系統(tǒng)重新計算進程的優(yōu)先數(shù)在時鐘中斷處理例程中進行，由于中斷是隨機碰到哪個進程，就插入哪個進程中運行處理程序，并把處理時間記在這個進程的賬上。

5若后備作業(yè)隊列中等待運行的同時有三個作業(yè)J1、J2、J3，已知它們各自的運行時間為a、b、c，且滿足a<b＜c，試證明采用短作業(yè)優(yōu)先算法調(diào)度能獲得最小平均作業(yè)周轉(zhuǎn)時間。

答：采用短作業(yè)優(yōu)先算法調(diào)度時，三個作業(yè)的總周轉(zhuǎn)時間為：

Tl==a+(a+b)+(a+b+c)=3a+2b+c①

若不按短作業(yè)優(yōu)先算法調(diào)度，不失一般性，設(shè)調(diào)度次序為：J2、J1、J3。則三個作業(yè)的總周轉(zhuǎn)時間為：

T2=b＋(b＋a)＋(b＋a+c)=3b+2a+c②

令②-①式得到：

T2-Tl=b-a>0

可見，采用短作業(yè)優(yōu)先算法調(diào)度才能獲得最小平均作業(yè)周轉(zhuǎn)時間。

6、若有一組作業(yè)J1，…，Jn，其執(zhí)行時間依次為S1，…,Sn。如果這些作業(yè)同時到試找出一種作業(yè)調(diào)度算法到達系統(tǒng)，并在一臺單CPU處理器上按單道方式執(zhí)行。使得平均作業(yè)周轉(zhuǎn)時間最短。

答：首先，對n個作業(yè)按執(zhí)行時間從小到大重新進行排序，則對n個作業(yè)：J1'，…，Jn,創(chuàng)門的運行時間滿足：S1≤S2≤……≤S(n-l)≤Sn’。那么有：

由于任何調(diào)度方式下，S1'+S2'+S3'＋…＋Sn’為一個確定的數(shù)，而當(dāng)S1’≤S2’≤…≤S(n-1)’≤Sn’時才有：0*S1+1*S2+2*S3+…（n-1）Sn的值最大，也就是說，此時T值最小。所以，按短作業(yè)優(yōu)先調(diào)度算法調(diào)度時，使得平均作業(yè)周轉(zhuǎn)時間最短。

7、假定執(zhí)行表中所列作業(yè)，作業(yè)號即為到達順序，依次在時刻0按次序1、2、3、4、5進入單處理器系統(tǒng)。

（1）分別用先來先服務(wù)調(diào)度算法、時間片輪轉(zhuǎn)算法、短作業(yè)優(yōu)先算法及非強占優(yōu)先權(quán)調(diào)度算法算出各作業(yè)的執(zhí)行先后次序（注意優(yōu)先權(quán)高的數(shù)值小）;

（2）計算每種情況下作業(yè)的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。

(1）采用FCFS算法調(diào)度作業(yè)，運作情況：

(2）采用雙算法調(diào)度作業(yè)，若令時間片長＝l，各作業(yè)執(zhí)行情況為：1、2、3、4、5、l、3、5、1、5、1、5、1、5、1、l、l、1、1。

(3）采用SJF算法調(diào)度作業(yè)，運作情況：

(4）采用非剝奪優(yōu)先權(quán)算法調(diào)度作業(yè)，運作情況：

8對某系統(tǒng)進行監(jiān)測后表明平均每個進程在I/O阻塞之前的運行時間為T。一次進程‘切換的系統(tǒng)開銷時間為S。若采用時間片長度為Q的時間片輪轉(zhuǎn)法，對下列各種情況算出CPU利用率。

9有5個待運行的作業(yè)，各自預(yù)計運行時間分別是：9、6、3、5和x，采用哪種運行次序使得平均響應(yīng)時間最短？

答：按照最短作業(yè)優(yōu)先的算法可以使平均響應(yīng)時間最短。x取值不定，按照以下情況討論：

10.有5個批處理作業(yè)A到E均己到達計算中心，其運行時間分別2、4、6、8和10分鐘：各自的優(yōu)先級分跳狠掀完為、、飛、飛、氏積5、這里5為最高級。對于1)時間片輪轉(zhuǎn)算法、2）優(yōu)先數(shù)法、3）短作業(yè)優(yōu)先算法、4）先來先服務(wù)調(diào)度算法（按到達次序C、D、B、E、A)，在忽略進程切換時間的前提下，計算出平均作業(yè)周轉(zhuǎn)時間。(對l）每個作業(yè)獲得相同的2分鐘長的時間片；對2）到4）采用單道運行，直到結(jié)束。）

答：(l)FCFS調(diào)度算法

(2）優(yōu)先級調(diào)度算法

(3）時間片輪轉(zhuǎn)法

按次序ABCDEBCDECDEDEE輪轉(zhuǎn)執(zhí)行。(4)SJF調(diào)度算法

11、有5個批處理作業(yè)A到E均已到達計算中心，其運行時間分別10、6、2、4和8分鐘；各自的優(yōu)先級分別被規(guī)定為3、5、2、1和4，這里5為最高級。若不考慮系統(tǒng)切換開銷，計算出平均作業(yè)周轉(zhuǎn)時間。（1)FCFs（按A、B、C、D、E);(2)優(yōu)先級調(diào)度算法，(3）時間片輪轉(zhuǎn)法（每個作業(yè)獲得相同的2分鐘長的時間片）。

答：

(1)FCFS調(diào)度算法

(2）優(yōu)先級調(diào)度算法

(3）時間片輪轉(zhuǎn)法

按次序ABCDEABDEABEAEA輪轉(zhuǎn)執(zhí)行。

作業(yè)執(zhí)行時間等待時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間

A

B

C

D

E10

6

2

4

820

l6

4

l2

2030

22

6

16

283

3.66

3

4

3.5作業(yè)平均周轉(zhuǎn)時間作業(yè)平均帶權(quán)周轉(zhuǎn)時間T=(30+22+6+16+28)/5=20.4

W=(3+3.66+3+4+3.5)/5=3.43

12(l）假定一個處理器正在執(zhí)行兩道作業(yè)，一道以計算為主，另一道以輸入輸出為主，你將怎樣賦予它們占有處理器的優(yōu)先級？為什么？

(2）假定一個處理器正在執(zhí)行三道作業(yè)，一道以計算為主，第二道以輸入輸出為主，第三道為計算與輸入輸出均勻。應(yīng)該如何賦予它們占有處理器的優(yōu)先級使得系統(tǒng)效率較高？

答：處理器調(diào)度算法會考慮以下因素：作業(yè)響應(yīng)時間要求；讓CPU盡量和外圍設(shè)備并行工作；限制一個計算進程長時間霸占處理器。因而，(1)FO為主作業(yè)優(yōu)先級高。（2)輸入輸出為主作業(yè)優(yōu)先級最高，輸入輸出均勻的作業(yè)其次，而計算為主作業(yè)的優(yōu)先級最低。

13請你設(shè)計一種先進的計算機體系結(jié)構(gòu)，它使用硬件而不是中斷來完成進程切換，則CPU需要哪些信息？請描述用硬件完成進程切換的工作過程。

答：該計算機有一個專用硬件寄存器，它始終存放指向當(dāng)前運行進程的PCB的指針。當(dāng)系統(tǒng)中發(fā)生了一個事件，如FO結(jié)束事件，CPU便可把運行進程的上下文保存到專用硬件寄存器指針指向的PCB中保護起來，然后，CPU轉(zhuǎn)向中斷向量表，找到設(shè)備中斷處理程序入口，讓專用硬件寄存器指針指向（設(shè)備）中斷服務(wù)例程，于是，便可啟動中斷服務(wù)例程工作。14設(shè)計一條機器指令和一種與信號量機制不同的算法，使得并發(fā)進程對共享變量的使用不會出現(xiàn)與時間有關(guān)的錯誤。

解：

(l）設(shè)計機器指令。

設(shè)計一條如下的”測試、比較和交換”三地址指令，提供了一種硬件互斥解決方案：

TC&SR1R3B2D2該指令的功能如下：

l)C為一個共享變量，由地址2、即變址（B2)+D2給出，

（2）（Rl）與（C）比較，

（3）如果（Rl)=(C）則（R3）→C，并置條件碼為"00",

如果（R1）≠（c）則（C)→Rl，并置條件碼為"01".

(2）編寫進程訪問共享變量的程序。

對每個訪問共享變量C的進程，編寫訪問共享變量的程序段為：

陸界區(qū)程序說明(C）→Rl;

loop2:(R1)→R3;

Add/decreaseR3;

TC&S;

R(condition=01)loop2;共享變量C的值保護到RI中。

Rl的值傳送到R3中，進程修改共享變量時，先對R3操作（不是直接操作C）。

R3加1／減1，進程歸還／申請由共享變量C代表的共享資源（假定每次一個）。

執(zhí)行”測試、比較和交換”指令。

條件碼＝01，轉(zhuǎn)向循環(huán)loop2；否則離開臨界區(qū)。

(3）程序執(zhí)行說明。

此解與互斥使用共享變量的思路絕然不同，并發(fā)運行的進程可不互斥地訪問它們的共享變量。此方案認為造成共享變量C值錯誤的原因在于：一個進程（Pl）在改變C值的過程中，另一個進程伊2）插進來也改變了C的值，而本進程（Pl）卻不知道，造成了c值結(jié)果不正確。如果有辦法使本進程口1）能知道C值是否改變，改變的話在繼承改變了的C值的基礎(chǔ)上，再作自己的改變操作，則就不會導(dǎo)致共享變量C值的錯誤。為此，本解決方案中，當(dāng)一個進程l）準(zhǔn)備改變C值時，先把C的值保護在Rl中，然后，通過R3來改變共享變量C的值。當(dāng)要把新的值（即R3內(nèi)的值）送C之前，先要判斷一下在本進程（P1）工作期間是否有別的進程口2）插進來也改變了C的值（并發(fā)進程P1、P2的執(zhí)行完全會造成這種情況），方法是：將扭1）中被保護的C的原來值，與C的當(dāng)前值比較，若相等，說明C值未被改變過，則將本進程（Pl）修改過的新值送C（即（R3)一C)；若不相等，說明C值在工作期間被改變過，則應(yīng)該繼承C的新值（即（C）一Rl）并且返回到loop2處重新對C值計數(shù)，以此保證C值的最終結(jié)果的正確性。這里提及”進程工作期間”指的是一個進程從開始至結(jié)束對共享變量C值的操作的這段時間，也就是執(zhí)行進程，'I晦界區(qū)”這段程序的時間。此外，在進程進入臨界區(qū)之前，應(yīng)等待直到C為非。（即有資源可用）為止。

(4）舉例。

假定系統(tǒng)中有靜態(tài)分配資源磁帶機共3臺，被N個進程共享，由共享變量C來代表可用磁帶機臺數(shù)，其初值為3?，F(xiàn)有并發(fā)進程P1和P2均申請使用磁帶機，執(zhí)行臨界區(qū)程序。

進程Pl執(zhí)行臨界區(qū)程序

(C）→R1；因（C）=3，故（R1)=3。

loop2:(Rl）→R3因（R1)=3，故（R3）當(dāng)前也＝3。

decreaseR3：申請使用磁帶機，做減1操作，故（R3）=2.

TC&S執(zhí)行”測試、比較和交換，,TC&S指令。

如果R1=（C）則（R3）→C，即（C）=2，并置條件碼為”00",跳出臨界區(qū)程序，去使用磁帶機。

如果(Rl)≠(C)，例如，(C）=2，說明進程P2搶先申請了磁帶機，所以，C與保護在R1中的值不一樣了（C的值必

小于Rl的值），應(yīng)以C的當(dāng)前值為準(zhǔn)，執(zhí)行（C)Rl(R1此時變?yōu)?)，并置條件碼為”01"，轉(zhuǎn)向foopZ。于是伍1)=2,跟著（R3卜2。接著卿）減1后應(yīng)＝l了。再執(zhí)行TC&S時，由于伍1卜（C)=2，會使C變?yōu)?。

r(conditio二01)loop2;

巧單道批處理系統(tǒng)中，下列三個作業(yè)采用先來先服務(wù)調(diào)度算法和最高響應(yīng)比優(yōu)先算法進行調(diào)度，哪一種算法性能較好？請完成下表：

作業(yè)提交時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間1

2

310:00

10:10

10:252:00

1:00

0:25

平均作業(yè)周轉(zhuǎn)時間=

平均作業(yè)帶權(quán)周轉(zhuǎn)時間W=

答：

可見HRRF比FIFO要好

16若有如表所示四個作業(yè)進入系統(tǒng)，分別計算在FCFS、S開和HRR衛(wèi)算法下的平均周轉(zhuǎn)時間與帶權(quán)平均周轉(zhuǎn)時間。（時間以十進制表示）

答：

17Kleinrock提出一種動態(tài)優(yōu)先權(quán)算法：進程在就緒隊列等待時，其優(yōu)先權(quán)以速率a變化；當(dāng)進程在處理器上運行，時其優(yōu)先權(quán)以速率p變化。給參數(shù)a,b賦以不同值可得到不同算法。（l）若a＞b＞c是什么算法？(2）若a＜b＜c是什么算法

答：(l）是先進先出算法。因為在就緒隊列中的進程比在CPU上運行的進程的優(yōu)先數(shù)提高得快，故進程切換時，先進入就緒隊列的進程優(yōu)先權(quán)就越高。

(2）是后進先出算法。因為在就緒隊列中的進程比在CPU上運行的進程的優(yōu)先權(quán)下降得快，故后進入就緒隊列的進程此先進入的進程的優(yōu)先權(quán)高。

18有一個四道作業(yè)的操作系統(tǒng)，若在一段時間內(nèi)先后到達6個作業(yè)，它們的提交和估計運行時間由下表給出：

系統(tǒng)采用SJF調(diào)度算法，作業(yè)被調(diào)度進入系統(tǒng)后中途不會退出，但作業(yè)運行時可被更短作業(yè)搶占。（l）分別給出6個作業(yè)的執(zhí)行時間序列、即開始執(zhí)行時間、作業(yè)完成時間、作業(yè)周轉(zhuǎn)時間。（2）計算平均作業(yè)周轉(zhuǎn)時間。

答

說明：

(1)J2到達時搶占J1;J3到達時搶占J2。

(2）但J4到達時，因不滿足SJF，故J4不能被運行，J3繼續(xù)執(zhí)行5分鐘。

(3）由于是4道的作業(yè)系統(tǒng)，故后面作業(yè)不能進入主存而在后備隊列等待，直到有作業(yè)結(jié)束。

(4）根據(jù)進程調(diào)度可搶占原則，J3第一個做完。而這時J5、J6均己進入后備隊列，而J5可進入主存。

(5）因J5最短，故它第二個完成。這時J6方可進入主存。因J6最短，故它第三個完成。

(6）然后是：J4、J2和J1

(7)T=(155+95+20+55+15+20)/6=60

19、有一個具有兩道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法，進程調(diào)度采用以優(yōu)先數(shù)為基礎(chǔ)的搶占式調(diào)度算法，在下表所示的作業(yè)序列，作業(yè)優(yōu)先數(shù)即為進程優(yōu)先數(shù)，優(yōu)先數(shù)越小優(yōu)先級越高。

(1）列出所有作業(yè)進入內(nèi)存時間及結(jié)束時間。

(2）計算平均周轉(zhuǎn)時間。

答：每個作業(yè)運行將經(jīng)過兩個階段：作業(yè)調(diào)度（SJF算法）和進程調(diào)度（優(yōu)先數(shù)搶占式）。另外，批處理最多容納2道作業(yè)，更多的作業(yè)將在后備隊列等待。

(l)10:00，作業(yè)A到達并投入運行。

(3)10:2O，作業(yè)B到達且優(yōu)先權(quán)高于作業(yè)A，故作業(yè)B投入運行而作業(yè)A在就緒隊列等待。

(4)10:30，作業(yè)C到達，因內(nèi)存中已有兩道作業(yè)，故作業(yè)C進入作業(yè)后備隊列等待。

(5)10:50，作業(yè)B運行結(jié)束，作業(yè)D到達，按SJF短作業(yè)優(yōu)先算法，作業(yè)D被裝入內(nèi)存進入就緒隊列。而由于作業(yè)A的優(yōu)先級高于作業(yè)D，故作業(yè)A投入運行

(6)11:10，作業(yè)A運行結(jié)束，作業(yè)C被調(diào)入內(nèi)存，具作業(yè)c的優(yōu)先級高于作業(yè)D,故作業(yè)C投入運行。

(7)12:00，作業(yè)c運行結(jié)束，作業(yè)D投入運行。

(8)12:20，作業(yè)D運行結(jié)束。

各作業(yè)周轉(zhuǎn)時間為：作業(yè)A70，作業(yè)B30，作業(yè)C90，作業(yè)D90。平均作業(yè)周轉(zhuǎn)時間為70分鐘。

20、某多道程序設(shè)計系統(tǒng)供用戶使用的主存為100K，磁帶機2臺，打印機1臺。采用可變分區(qū)內(nèi)存管理，采用靜態(tài)方式分配外圍設(shè)備，忽略用戶作業(yè)FO時間?，F(xiàn)有作業(yè)序列如下：

作業(yè)調(diào)度采用FCFS策略，優(yōu)先分配主存低地址區(qū)且不準(zhǔn)移動已在主存的作業(yè)，在主存中的各作業(yè)平分CPU時間．現(xiàn)求：(l）作業(yè)被調(diào)度的先后次序？(2）全部作業(yè)運行結(jié)束的時間？(3）作業(yè)平均周轉(zhuǎn)時間為多少？(4）最大作業(yè)周轉(zhuǎn)時間為多少？

答：(l）作業(yè)調(diào)度選擇的作業(yè)次序為：作業(yè)1、作業(yè)3、作業(yè)4、作業(yè)2和作業(yè)5.

(2）全部作業(yè)運行結(jié)束的時間9:30。

(3）周轉(zhuǎn)時間：作業(yè)1為30分鐘、作業(yè)2為55分鐘、作業(yè)3為40分鐘、作業(yè)4為40分鐘和作業(yè)5為55分鐘。

(4）平均作業(yè)周轉(zhuǎn)時間＝44分鐘。

(5)最大作業(yè)周轉(zhuǎn)時間為55分鐘。

分析：本題綜合測試了作業(yè)調(diào)度、進程調(diào)度、及對外設(shè)的競爭、主存的競爭。8:oo作業(yè)1到達，占有資源并調(diào)入主存運行。

8:20作業(yè)2和3同時到達，但作業(yè)2因分不到打印機，只能在后備隊列等待。作業(yè)3資源滿足，可進主存運行，并與作業(yè)1平分CPU時間。8:30作業(yè)1在8:30結(jié)束，釋放磁帶與打印機。但作業(yè)2仍不能執(zhí)行，因不能移動而沒有30KB的空閑區(qū)，繼續(xù)等待。作業(yè)4在8:30到達，并進入主存執(zhí)行，與作業(yè)3分享CPU8:35作業(yè)5到達，因分不到磁帶/打印機，只能在后備隊列等待。9:00作業(yè)3運行結(jié)束，釋放磁帶機。此時作業(yè)2的主存及打印機均可滿足，投入運行。作業(yè)5到達時間晚，只能等待。9:10作業(yè)4運行結(jié)束，作業(yè)5因分不到打印機，只能在后備隊列繼續(xù)等待。9：15巧作業(yè)2運行結(jié)束，作業(yè)5投入運行。9:30作業(yè)全部執(zhí)行結(jié)束。

21、某多道程序設(shè)計系統(tǒng)采用可變分區(qū)內(nèi)存管理，供用戶使用的主存為200K，磁帶機5臺。采用靜態(tài)方式分配外圍設(shè)備，且不能移動在主存中的作業(yè)，忽略用戶作業(yè)I/O時間?，F(xiàn)有作業(yè)序列如下：

現(xiàn)求：(l)FIFO算法選中作業(yè)執(zhí)行的次序及作業(yè)平均周轉(zhuǎn)時間？(2)SJF算法選中作業(yè)執(zhí)行的次序及作業(yè)平均周轉(zhuǎn)時間？（進程調(diào)度也采用FCFS)

答：(1)FIFO算法選中作業(yè)執(zhí)行的次序為：A、B、D、C和E作業(yè)平均周轉(zhuǎn)時間為63分鐘

(2)SJF算法選中作業(yè)執(zhí)行的次序為：A、B、D、E和C。作業(yè)平均周轉(zhuǎn)時間為58分鐘

詳細說明：

1．先來先服務(wù)算法。說明：

(1)8:30作業(yè)A到達并投入運行。注意它所占用的資源。

(2)8:50作業(yè)B到達，資源滿足進主存就緒隊列等CPu。

(3)9:00作業(yè)C到達，主存和磁帶機均不夠，進后備作業(yè)隊列等待。

(4)9:05作業(yè)D到達，磁帶機不夠，進后備作業(yè)隊列等待。后備作業(yè)隊列有C、D。(5)9:10作業(yè)A運行結(jié)束，歸還資源磁帶，但注意主存不能移動（即不能緊縮）。作業(yè)B投入運行。作業(yè)C仍因主存不夠而等在后備隊列。這時作業(yè)E也到達了，。也由于主存不夠進入后備作業(yè)隊列。此時作業(yè)D因資源滿足（主存磁帶均滿足），進主存就緒隊列等待。后備作業(yè)隊列還有C、E。

(6)9:35作業(yè)B運行結(jié)束，作業(yè)D投入運行。這時作業(yè)C因資源滿足而調(diào)入主存進就緒隊列等CPU。而作業(yè)E因磁帶機不夠繼續(xù)在后備作業(yè)隊列等待。

(7)9:55作業(yè)D運行結(jié)束，作業(yè)C投入運行。這時作業(yè)E因資源滿足而調(diào)入主存進就緒隊列等CPU。

(8)10:30作業(yè)C運行結(jié)束，、作業(yè)E投入運行。

(9)10:40作業(yè)E運行結(jié)束。

2．短作業(yè)優(yōu)先算法。說明：

(1)8:30作業(yè)A到達并投入運行。注意它所占用的資源。

(2)8:50作業(yè)B到達，資源滿足進主存就緒隊列等CPU。

(3)9:00作業(yè)C到達，主存和磁帶機均不夠，進后備作業(yè)隊列等待。

(4)9:05作業(yè)D到達，磁帶機不夠，進后備作業(yè)隊列等待。后備作業(yè)隊列有C、D.

(5)9:10作業(yè)A運行結(jié)束，歸還資源磁帶，但注意主存不能移動（即不能緊縮）。作業(yè)B投入運行。作業(yè)C仍因主存不夠而等在后備隊列。這時作業(yè)E也到達了，雖然該作業(yè)最短，也由于主存不夠進入后備作業(yè)隊列．此時作業(yè)D因資源滿足（主存磁帶均滿腳，進主存就緒隊列等待。后備作業(yè)隊列還有C、E。

(6)9:35作業(yè)B運行結(jié)束，作業(yè)D投入運行。這時作業(yè)C和E資源均滿足，但按SJF應(yīng)把作業(yè)E調(diào)入主存進就緒隊列等CPU。而作業(yè)C因磁帶機不夠繼續(xù)在后備作業(yè)隊列等待。

(7)9:55作業(yè)D運行結(jié)束，作業(yè)C調(diào)入主存進就緒隊列等CPU.

(8)10:05作業(yè)E運行結(jié)束，作業(yè)C投入運行．

(9)10:40作業(yè)C運行結(jié)束。

上題中，若允許移動己在主存中的作業(yè)，其他條件不變，現(xiàn)求：(l)FIFO算法選中作業(yè)執(zhí)行的次序及作業(yè)平均周轉(zhuǎn)時間？(2)SJF算法選中作業(yè)執(zhí)行的次序及作業(yè)平均周轉(zhuǎn)時間？

答：

FIFO算法選中作業(yè)執(zhí)行的次序為：SJF算法選中作業(yè)執(zhí)行的次序為：

（l)A、B、D、E和C。作業(yè)平均周轉(zhuǎn)時間為58分鐘。

(2)A、B、E、D和C。作業(yè)平均周轉(zhuǎn)時間為56分鐘。

與上題類同，詳細說明略。

23、設(shè)計一個進程定時喚醒隊列和定時喚醒處理程序：(l）說明一個等待喚醒進程入隊v的過程。（2）說明時鐘中斷時，定時喚醒處理程序的處理過程。（3）現(xiàn)有進程P1要求20秒后運行，經(jīng)過40秒后再次運行；PZ要求25秒后運行；P3要求35秒后運行，經(jīng)過35秒后再次運行；P4要求60秒后運行。試建立相應(yīng)的進程定時喚醒隊列。

答：

組織如下的定時喚醒隊列

。

(l）當(dāng)一個需定時喚醒的進程要入隊時，根據(jù)它要喚醒的時間，被扦入隊列的適當(dāng)位置，注意，喚醒時間按增量方式存放。

(2）每當(dāng)時鐘中斷時，時鐘中斷例程判別把隊列中的第一個進程的時間量減1，直到該值為時喚醒進程工作。同時隊列中下一個進程成為隊列頭。

24、一個實時系統(tǒng)有4個周期性事件，周期分別為50、100、300和250ms。若假設(shè)其處理分別需要35、20、10和Xms，則該系統(tǒng)可調(diào)度允許的X值最大為多少？

實時任務(wù)可調(diào)度應(yīng)滿足：

35/50+20/100+10/300+X/250＜lX＜250(l-28/30)=250×0.067=16.75ms第三章同步、通訊與死鎖1、有三個并發(fā)進程：R負責(zé)從輸入設(shè)備讀入信息塊，M負責(zé)對信息塊加工處理；P負責(zé)打印輸出信息塊。今提供；l）一個緩沖區(qū)，可放置K個信息塊；2）二個緩沖區(qū)，每個可放置K個信息塊；試用信號量和P、V操作寫出三個進程正確工作的流程。

答：

1)varB:array[0,k-1]ofitem;

sread:semaPhore:=k;

smanage:semaPhore:=0;

swrite:semaphore:=0;

rptr:integer:=O;

mptr:integer:=O;

wptr：integer:=0;

x:item

cobegin

processreader;processmanager;processwriter;

beginbeginbegin

LI:readamessageintox;L2:P(smanage);L3:P(swnte);

P(sread);x:=B[mptr];x:=B[swrite];

B[rptr]:=x;mptr:=(mptr+1)modk;wptr:=(wptr+1)modk;

Rptr:=(rptr+1)modk;managethemessageinx;V(sread);

V(smanage);B[mptr]:=x;printthemessageinx;

GotoL1;V(swrite);gotoL3;

End;gotoL2;end;

End;

coend

2)varA,B:array[0,k-l]ofitem;

sPut1:semaphore:=k;

SPut2:semaPhore:=k;

sget1:semaPhore:=0;

sget2:semaphore:=0;

put1：integer：=O;

put2：integer:=0;

get1：integer：=O;

get2:integer:=O;

cobegin

processreader;processnmanager;processWriter;

beginbeginbegin

Ll:readamessageintox;L2:P(sgetl);L3:P(sgetZ);

P(SPut1);x:=A[get1];x:=B[get2];

A[put1]:=x;get1：(get1+1)modk;get2:=（get2+l)modk;

Put1:=(put1+1)modk;V(sput1);V(sput2);

V(sget1);managethemessageintox;printthemessageinx;

GotoL1;P(sput2);gotoL3;

Put2:=(put2+1)modk;

V(sget2);

GotoL2;

End;

Coend2設(shè)有n個進程共享一個互斥段，如果：

(1）每次只允許一個進程進入互斥段；

(2）每次最多允許m個進程（m簇n）同時進入互斥段。

試問：所采用的信號量初值是否相同？信號量值的變化范圍如何？

答：所采用的互斥信號量初值不同。

1）互斥信號量初值為1，變化范圍為［-n＋l,1］。

當(dāng)沒有進程進入互斥段時，信號量值為1；當(dāng)有1個進程進入互斥段但沒有進程等待進入互斥段時，信號量值為O；當(dāng)有1個進程進入互斥段且有一個進程等待進入互斥段時，信號量值為-1；最多可能有n-1個進程等待進入互斥段，故此時信號量的值應(yīng)為-（n-1）也就是-n+1。

2）互斥信號量初值為m，變化范圍為［-n＋m,m］。

當(dāng)沒有進程進入互斥段時，信號量值為m；當(dāng)有1個進程進入互斥段但沒有進程等待進入互斥段時，信號量值為m-1：當(dāng)有m個進程進入互斥段且沒有一個進程等待進入互斥段時，信號量值為0：當(dāng)有m個進程進入互斥段且有一個進程等待進入互斥段時，信號量值為一l；最多可能有n-m個進程等待進入互斥段，故此時信號量的值應(yīng)為-(n-m)也就是-n+m.

3有兩個優(yōu)先級相同的進程P1和P2，各自執(zhí)行的操作如下，信號量S1和S2初值均為0。試問Pl、P2并發(fā)執(zhí)行后，x、y、z的值各為多少？

P1:P2:

Beginbegin

Y:=1;x:=1;

Y:=y+3;x:=x+5;

V(S1);P(S1);

Z:=Y+1;X:X+Y;

P(s2);V(S2);

Y:=z+y;z:=z+x;

Endend

答：現(xiàn)對進程語句進行編號，以方便描述．

P1:P2:

beginbegin

y:=1；①x:=1;⑤

y:=y+3；②x：x+5;⑥

V(S1);P(S1);

Z:Y+1；③x：X＋Y;⑦

P(s2);V(S2);

Y:=z+y;④z：=Z+X；⑧

Endend

①、②、⑤和⑥是不相交語句，可以任何次序交錯執(zhí)行，而結(jié)果是唯一的。接著無論系統(tǒng)如何調(diào)度進程并發(fā)執(zhí)行，當(dāng)執(zhí)行到語句⑦時，可以得到x=10,y=4。按Bernstein條件，語句③的執(zhí)行結(jié)果不受語句⑦的影響，故語句③執(zhí)行后得到z=5。最后，語句④和⑧并發(fā)執(zhí)行，這時得到了兩種結(jié)果為：

語句④先執(zhí)行：x=10,y=9,z=150

語句⑧先執(zhí)行：x=10,y=19,z=15

此外，還有第三種情況，語句③被推遲，直至語句⑧后再執(zhí)行，于是依次執(zhí)行以下三個語句：

7：二z+X:

z:=y+1;

y:＝Z十y;

這時z的值只可能是y＋1=5，故y=Z＋Y=5+4=9，而x=10。

第三種情況為：x=10，Y=9,Z=5。

4有一閱覽室，讀者進入時必須先在一張登記表上登記，該表為每一座位列出一個表目，包括座號、姓名，讀者離開時要注銷登記信息；假如閱覽室共有100個座位。試用：l）信號量和P、V操作；2）管程，來實現(xiàn)用戶進程的同步算法。

答：1）使用信號量和P、v操作：

varname：array[l…100]ofA;

A=record

number：integer;

name：string;

end

fori:=1to100do{A[i].number：i；A[i].name:null;}

mutex,seatcount:semaphore;

i:integer；mutex:=l;seatcount:=100;

cobegin

{

processreaderi(varreadename：string)（i=1,2…)

{

P(seatcount);

P（mutex);

fori:=1to100doi++

ifA[i].name＝nullthenA[i].name：readername；

readergettheseatnumber=i；/*A[I].number

V(mutex)

進入閱覽室，座位號i，座下讀書；

P(mutex);

A[i]name：null;

V（mutex);

V(seatcount);

離開閱覽室；

}

}

coend

2）使用管程操作：

TYPEreadbook=monitor

VARR:condition;

I,seatcount：integer;

name：array[l:100]ofstring;

DEFINErcadercome,readerleave;

USEcheck,wait,signal,release;

Procedurereadercome(readername)

begin

check(IM);

ifseatcount≥100wait(R,IM)

seatcount:=seatcount+1;

fori=1to100doi++

ifname[i]==nullthenname[i]:=readername;

gettheseatnumber=i;

release(IM);

end

procedurereaderleave(readername)

begin

check(IM);

seatcount--;

fori=1to100doi++

ifname［i］readernamethenname［i］:null;

release(IM);

end

begin

seatcount:=1OO;name:＝null;

end

cobegin

{

processreaderi(i=1,2．…）

begin

readercome(readername）;

readthebook;

readerleave(readername）;

leavethereadroom;

end

}

coend.

5.在一個盒子里，混裝了數(shù)量相等的黑白圍棋子·現(xiàn)在用自動分揀系統(tǒng)把黑子、白子分開，設(shè)分揀系統(tǒng)有二個進程P1和P2，其中P1揀白子；P2揀黑子。規(guī)定每個進程每次揀一子；當(dāng)一個進程在揀時，不允許另一個進程去揀；當(dāng)一個進程揀了一子時，必須讓另一個進程去揀．試寫出兩進程P1和P2能并發(fā)正確執(zhí)行的程序。

答1：實質(zhì)上是兩個進程的同步問題，設(shè)信號量s1和s2分別表示可揀白子和黑子，不失一般性，若令先揀白子。

varS1,S2:semaphore;

S1:=l;S2：=0;

cobegin

{

processP1

begin

repeat

P(S1);

揀白子

V(S2);

untilfalse;

end

processP2

begin

repeat

P(S2);

揀黑子

V(S1);

untilfalse;

end

}

coend.

答2:

TYPEpickup-chess=MONITOR

VARflag:boolean;

S-black,s-white:codition;

DEFINEpickup-black,pickup-white;

USEwait,signal,check,release;

procedurepickup-black;

begin

check(IM);

ifflagthenwait(s-black,IM);

flag:＝true;

pickupablack;

signal(S-white,IM);

release(IM);

end

procedurepickup-white;

begin

check(IM);

ifnotflagthenwait(S-white,IM);

flag:=false;

pickupawhite;

signal(S-black,IM);

release(IM);

end

begin

flag:=true;

end

main()

{cobegin

process-B();

process-W();

coend

}

process-B()

begin

pickup-chess.pickup-black();

other;

end

process-W()

begin

pickup-chess.pickup-white();

other;

end

6管程的同步機制使用條件變量和wait及signal，嘗試為管程設(shè)計一種僅僅使用一個原語操作的同步機制。

答：可以采用形如waituntil＜條件表達式＞的同步原語。如waituntil(numbersum+number<K)表示進程由于條件不滿足而應(yīng)等待，當(dāng)進程號累加和小于K時，系統(tǒng)應(yīng)喚醒該進程工作．

7設(shè)公共汽車上，司機和售票員的活動分別如下：

司機的活動：啟動車輛：正常行車；到站停車。

售票員的活動：關(guān)車門；售票；開車門。

在汽車不斷地到站、停車、行駛過程中，這兩個活動有什么同步關(guān)系？用信號量和P、V操作實現(xiàn)它們的同步。

答：在汽車行駛過程中，司機活動與售票員活動之間的同步關(guān)系為：售票員關(guān)車門后，向司機發(fā)開車信號，司機接到開車信號后啟動車輛，在汽車正常行駛過程中售票員售票，到站時司機停車，售票員在車停后開門讓乘客上下車。因此，司機啟動車輛的動作必須與售票員關(guān)車門的動作取得同步；售票員開車門的動作也必須與司機停車取得同步。應(yīng)設(shè)置兩個信號量：S1、S2;S1表示是否允許司機啟動汽車（其初值為0);S2表示是否允許售票員開門（其初值為0）。用P、v原語描述如下：

varS1,S2:semaphore;

S1=0；S2=0；

cobegin

{

driver();

busman();

}

coend

driver()

begin

while(1){

P(S1)

啟動車輛；正常行車；到站停車；

V(S2);

}

end

busman()

begin

while(1){

關(guān)車門；

V(51)

售票;

P(S2)

開車門；

上下乘客；

}

end

8、一個快餐廳有4類職員：(l）領(lǐng)班：接受顧客點菜；(2）廚師：準(zhǔn)備顧客的飯菜；(3)包工：將做好的飯菜打包；(4）出納員：收款并提交食品。每個職員可被看作一個進程，試用一種同步機制寫出能讓四類職員正確并發(fā)運行的程序。

答：典型的進程同步問題，可設(shè)四個信號量51、S2、S3和S4來協(xié)調(diào)進程工作。

varS1,S2,S3,S4:semaphore;

S1:=1;S2：=S3:=S4:=0;

cobegin

{processP1

begin

repeat

有顧客到來；

P(S1)；

接受顧客點菜；

V(52)；

untilefalse；

end

processP2

begin

repeat

P(S2);

準(zhǔn)備顧客的飯菜；

v(S3);

untilefalse;

end

processP3

begin

repeat

P(S3);

將做好的飯菜打包；

V(S4);

untilefalse;

end

processP4

begin

repeat

P(54);

收款并提交食品；V(51);

ufltilefalse;

end

}

coend.

9、在信號量S上作P、v操作時，S的值發(fā)生變化，當(dāng)S>0、S=0、S<0時，它們的的物理意義是什么？

答：S的值表示它代表的物理資源的使用狀態(tài)：S>0表示還有共享資源可供使用。S閱表示共享資源正被進程使用但沒有進程等待使用資源。S<0表示資源已被分配完，還有進程等待使用資源。

10(1）兩個并發(fā)進程并發(fā)執(zhí)行，其中，A、B、C、D、E是原語，試給出可能的并發(fā)執(zhí)行路徑。

ProcessPProcessQ

beginbegin

A;D;

B;E;

C;end:

end;

(2）兩個并發(fā)進程P1和P2并發(fā)執(zhí)行，它們的程序分別如下：

P1P2

repeatrepeat

k:=k×2;printk;

k:=k+1;k:=0;

untilfalse;untilfalse;

若令k的初值為5，讓P1先執(zhí)行兩個循環(huán)，然后，P1和P2又并發(fā)執(zhí)行了一個循環(huán)，寫出可能的打印值，指出與時間有關(guān)的錯誤。

答：

(1）共有10種交錯執(zhí)行的路徑：

A、B、C、D、E;A、B、D、E、C;A、B、D、C、E;

A、D、B、E、C;A、D、B、C、E;A、D、E、B、C;

D、A、B、E、C;D、A、B、C、E;D、A、E、B、C;D、E、A、B、C。

(2）把語句編號，以便于描述：

P1P2

repeatrepeat

k:=k×2；①printk；③

k:=k+l；②k:=0；④

untilfalse;untilfalse;

l)K的初值為5，故P1執(zhí)行兩個循環(huán)后，K=23。

2）語句并發(fā)執(zhí)行有以下情況：

①、②、③、④，這時的打印值為：47

③、④、①、②，這時的打印值為：23

①、③、②、④，這時的打印值為：46

①、③、④、②，這時的打印值為：46

③、①、②、④，這時的打印值為：23

③、①、④、②，這時的打印值為：23

由于進程P1和P2并發(fā)執(zhí)行，共享了變量K，故產(chǎn)生了‘結(jié)果不唯一’。

11證明信號量與管程的功能是等價的：

(l）用信號量實現(xiàn)管程；

(2）用管程實現(xiàn)信號量。

答：(1）用信號量實現(xiàn)管程；

Hoare是用信號量實現(xiàn)管程的一個例子，詳見課文內(nèi)容。下面介紹另一種簡單方法：每一個管程都對應(yīng)一個mutex，其初值為1，用來控制進程互斥調(diào)用管程。再設(shè)一個初值為0的信號量，用來阻塞等待資源的進程。相應(yīng)的用信號量實現(xiàn)的管程庫過程為：

Varmutex,c:semaphore;

mutex:=1;c:=0;

voidenter-monitor()/*進入管程代碼，保證互斥

P(mutex);

}

voidleave-monitor-normally()/*不發(fā)信號退出管程

{

V(mutex);

}

voidleave-with-sigal(c)/*在條件c上發(fā)信號并退出管程，釋放一個等待c條件的進程。｛注意這時沒有開放管程，因為剛剛被釋放的進程己在管程中。

V(c);

}

voidwait(c)/*等待條件c，開放管程

{

V(mutex);

P(c);

}

(2）用管程實現(xiàn)信號量。

TYPEsemaphore=monitor

VARS;condition;

C:integer;

DEFINEP,V;

USEcheck,wait,signal,release;

procedureP

begin

check(IM);

C:=C-1:

ifC<0thenwait(S,IM);

release(IM);

end

procedureV

begin

check(IM):

C:=C+1;

ifC≤0thensignal(S,IM);

release(IM);

end

begin

C:=初值;

End.

12證明消息傳遞與管程的功能是等價的：

(1）用消息傳遞實現(xiàn)管程；

(2）用管程實現(xiàn)消息傳遞。

答：(1）用消息傳遞實現(xiàn)管程；

用消息傳遞可以實現(xiàn)信號量（見13(2))，用信號量可以實現(xiàn)管程（見11(1))，那么，把兩種方法結(jié)合起來，就可以用用消息傳遞實現(xiàn)管程。

(2）用管程實現(xiàn)消息傳遞。

TYPEmailbox=monitor

VARr,k,count:integer;

buffer：array[0…n-1]ofmessage;

full,empty:condition;

DEFINEadd,get;

USEcheck,wait,signal,release;

procedureadd(r);

begin

check(IM);

ifcount=nthenwait(full,IM);

buffer[r]:=message;

r:＝(r+1)modn

count:=count+1;

ifcount=1thensighal(empty,IM);

release(IM);

end

procedureget(m);

begin

check(IM);

ifcount=0thenwait(empty,IM);

m:=buffer[k」；

count:=count-1;

ifcount＝n-1thensignal(full,IM);

release(IM);

end

begin

r:=0;k:=0;count:=0;

end

13證明信號量與消息傳遞是等價的：

(1）用信號量實現(xiàn)消息傳遞；

(2）用消息傳遞實現(xiàn)信號量。

答：(l）用信號量實現(xiàn)消息傳遞；

1）把消息隊列組織成一個共享隊列，用一個互斥信號量管理對該隊列的入隊操作和出隊操作.

2）發(fā)送消息是一個入隊操作，當(dāng)隊列存儲區(qū)滿時，設(shè)計一個同步信號量阻塞send操作。

3）接收消息是一個出隊操作，當(dāng)隊列存儲區(qū)空時，設(shè)計另一個同步信號量阻塞receive操作。

(2）用消息傳遞實現(xiàn)信號量。

l）為每一個信號量建立一個同步管理進程，它包含了一個計數(shù)器，記錄信號量值；還為此信號量設(shè)立一個等待進程隊列

2）應(yīng)用進程執(zhí)行P或V操作時，將會調(diào)用相應(yīng)P、V庫過程。庫過程的功能是：把應(yīng)用進程封鎖起來，所執(zhí)行的P、V操作的信息組織成消息，執(zhí)行send發(fā)送給與信號量對應(yīng)的同步管理進程，之后，再執(zhí)行receive操作以接收同步管理進程的應(yīng)答。

3）當(dāng)消息到達后，同步管理進程計數(shù)并查看信號量狀態(tài)。如果信號量的值為負的話，執(zhí)行P操作的應(yīng)用進程被阻塞，掛到等待進程隊列，所以，不再要送回答消息。此后，當(dāng)V操作執(zhí)行完后，同步管理進程將從信號量相應(yīng)隊列中選取一個進程喚醒，并回送一個應(yīng)答消息。正常情況下，同步管理進程回送一個空應(yīng)答消息，然后，解鎖執(zhí)行P、V操作的應(yīng)用程序。

14使用（1）消息傳遞，(2）管程，實現(xiàn)生產(chǎn)者和消費者問題。答：(1）見課文ch33.5.4節(jié)。（2）見課文Ch33.4.3節(jié)。

15試?yán)糜涗浶托盘柫亢蚉、V操作寫出一個不會出現(xiàn)死鎖的五個哲學(xué)家進餐問題的算法。答：

varforki:array[0…4]ofsemaphore;

forki:=1;

cobegin

{

processPi/*i=0,1,2,3*/

begin

L1:

思考：

P(fork[i]);/*i=4,P(fork[0])*/

P(fork[i+1]mod5)/*i=4P（fork[4]）*/

吃通心面；

V(fork[i];

V(fork([i+1]mod5);

gotoL1;

end;

}

coend;

16Dijkstra臨界區(qū)軟件算法描述如下：

varflag：array[0…n]of(idle,want-in，in_cs);

turn:integer;tune:0or1or…or,n-1;

processPi(i=0,1，…,n-1)

varj;integer;

begin

repeat

repeat

flag[i]:want_in;

whileturn≠1do

ifflag[turn]==idlethenturn:=i;

flag[i]:=ip_cs;

j:=0;

while(j<n)&(j==1orflag[j]≠in_cs)

doj:=j+1;

untilj≥n:

criticalsection;

flag[i]:=idle;

……

untilfalse;

end.

試說明該算法滿足臨界區(qū)原則。

答：為方便描述，把Dijkstra程序的語句進行編號：

repeat

flag[i]:=want_in；①

whileturn≠ido②

ifflag[trun]==idlethenturn:=i；③

flag[i]:=in_cs；④

j:=O;

while(j<n)&(j==1orflag[j]≠in_cs）⑤

doj:=j+1;@

untilj≥n;

criticalsection;

flag[i]:=idle；⑦

…

(l）滿足互斥條件

當(dāng)所有的巧都不在臨界區(qū)中，滿足flag[j]≠in_cs（對于所有j,j≠i）條件時，Pi才能進入它的臨界區(qū)，而且進程Pi不會改變除自己外的其他進程所對應(yīng)的flag[j]的值。另外，進程Pi總是先置自己的flag[j]為in_cs后，才去判別Pj進程的flag[j]的值是否等于in_cs所以，此算法能保證n個進程互斥地進入臨界區(qū)。

(2）不會發(fā)生無休止等待進入臨界區(qū)

由于任何一個進程Pi在執(zhí)行進入臨界區(qū)代碼時先執(zhí)行語句①，其相應(yīng)的flag[i]的值不會是idle。注意到flag[i]＝in_cs并不意味著turn的值一定等于i。我們來看以下情況，不失一般性，令turn的初值為0，且P0不工作，所以，flag[turn]=flag[0]=idle。但是若干個其他進程是可能同時交替執(zhí)行的，假設(shè)讓進程Pj(j=l,2,…n-l）交錯執(zhí)行語句①后（這時flag[j]=want_in），再做語句②（第一個while語句），來查詢flag[turn]的狀態(tài)。顯然，都滿足turn≠i，所以，都可以執(zhí)行語句③，讓自己的turn為j。但turn僅有一個值，該值為最后一個執(zhí)行此賦值語句的進程號，設(shè)為k、即turn=k(1≤k≤n-1）。接著，進程Pj(j=1,2,…n-l)交錯執(zhí)行語句④，于是最多同時可能有n-1個進程處于in_cs狀態(tài)，但不要忘了僅有一個進程能成功執(zhí)行語句④，將加m置為自己的值。

假設(shè)｛P1,P2，…Pm｝是一個己將flag[i]置為in_cs(i=1,2,…,m)(m≤n-1）的進程集合，并且已經(jīng)假設(shè)當(dāng)前turn=k(1≤k≤m)，則Pk必將在有限時間內(nèi)首先進入臨界區(qū)。因為集合中除了Pk之外的所有其他進程終將從它們執(zhí)行的語句⑤（第二個while循環(huán)語句）退出，且這時的j值必小于n，故內(nèi)嵌until起作用，返回到起始語句①重新執(zhí)行，再次置flag[i]=want_in，繼續(xù)第二輪循環(huán)，這時的情況不同了，flag[turn]=flag[k]必定≠idle（而為in_cs）。而進程Pk發(fā)現(xiàn)最終除自身外的所有進程Pj的flag[j]≠in_cs，并據(jù)此可進入其臨界區(qū)。

17另一個經(jīng)典同步問題：吸煙者問題(patil,1971）。三個吸煙者在一個房間內(nèi)，還有一個香煙供應(yīng)者。為了制造并抽掉香煙，每個吸煙者需要三樣?xùn)|西：煙草、紙和火柴，供應(yīng)者有豐富貨物提供。三個吸煙者中，第一個有自己的煙草，第二個有自己的紙和第三個有自己的火柴。供應(yīng)者隨機地將兩樣?xùn)|西放在桌子上，允許一個吸煙者進行對健康不利的吸煙。當(dāng)吸煙者完成吸煙后喚醒供應(yīng)者，供應(yīng)者再把兩樣?xùn)|西放在桌子上，喚醒另一個吸煙者。試采用：(1）信號量和P、v操作，(2）管程編寫他們同步工作的程序。答：(1）用信號量和P、v操作。

vars,S1,S2,S3;semaphore;

S:=1;S1:=S2:=S3:=0;

fiag1,flag2,fiag3:Boolean;

fiag1:=flag2:=flag3:=true;

cobegin

{

process供應(yīng)者

begin

repeat

P(S);

取兩樣香煙原料放桌上，由flagi標(biāo)記；/*nago1、nage2、nage3代表煙草、紙、火柴

ifflag2&flag3thenV(S1);/＊供紙和火柴

elseifflag1&fiag3thenV(S2);/＊供煙草和火柴

elseV(S3);/＊供煙草和紙

untilefalse;

end

process吸煙者1

begin

repeat

P(S1);

取原料；

做香煙；

V(S);

吸香煙；

untilefalse;

process吸煙者2

begin

repeat

P(S2);

取原料；

做香煙；

V(S);

吸香煙；

untilefalse;

process吸煙者3

begin

repeat

P(S3);

取原料；

做香煙；

V(S);

吸香煙；

untilefalse;

coend.

(3）用管程。

TYPEmskesmoke=moonitor

VARS,S1,S2,S3:condition;

flag1,flag2,flag3:boolean

DEFINEgive,take1,take2,take3;

USEcheck,wait,signal,release;

proceduregive

begin

check(IM);

準(zhǔn)備香煙原料；

if桌上有香煙原料thenwait(S,IM);把準(zhǔn)備的香煙原料放桌上；

iffiag2&flag3thensignal(S1,IM）;

ifflag1&flag3thensignal(S2,IM);elsesignal(S3,IM);

release(IM);

end

proceduretake1

begin

check(IM):

if桌上沒有香煙原料thenwait(S1,IM）;

else取原料；

signal(S,IM);

release(IM);

end

proceduretake2

begin

check(IM):

if桌上沒有香煙原料thenwait(S2,IM);

else取原料；

signal(S,IM);

release（IM）;

end

proceduretake3

begin

check(IM):

if桌上沒有香煙原料thenwait(S3,IM);

else取原料

signal(S,IM);

release(IM);

end

begin

flag1:=flag2:=flag3:=true;

end.

cobegin

{

process供應(yīng)者

begin

repeat

Callmakesmoke.give();

……

untilfalse;

end

process吸煙者1

begin

repeat

Callmakesmoke.take1();

做香煙，吸香煙；

untilfalse;

end

process吸煙者2

begin

repeat

Callmakesmoke.take2();

做香煙，吸香煙；

untilfalse;

end

process吸煙者3

begin

repeat

Callmakesmke.take3();

做香煙，吸香煙；

untilfalse;

end

}

coend.

18、如圖所示，四個進程Pi（i=0…3）和四個信箱Mj(j=0…3)，進程間借助相鄰信箱傳遞消息，即Pi每次從Mi中取一條消息，經(jīng)加工后送入M(i+1)mod4，其中M0、M1、M2、M3;可存放3、3、2、2個消息。初始狀態(tài)下，MO裝了三條消息，其余為空。試以P、V為操作工具