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

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

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

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

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

87％/59％=147%

147％-100%=47%

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

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

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

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

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

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

答：

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

?

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

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

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

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

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

4在單CPU和兩臺(tái)I/O(I1,12）設(shè)備的多道程序設(shè)計(jì)環(huán)境下，同時(shí)投入三個(gè)作業(yè)運(yùn)行。它們的執(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)先級(jí)從高到低為Jobl、Job2和Job3，優(yōu)先級(jí)高的作業(yè)可以搶占優(yōu)先級(jí)低的作業(yè)的CPU，但不搶占I1和I2。試求：(l）每個(gè)作業(yè)從投入到完成分別所需的時(shí)間。（2）從投入到完成CPU的利用率。（3）I2設(shè)備利用率。

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

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

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

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

設(shè)備I2空閑時(shí)間段為：30ms至50ms，故I2的利用率為(110-20)/110=81.8％。5在單CPU和兩臺(tái)I/O(I1,12）設(shè)備的多道程序設(shè)計(jì)環(huán)境下，同時(shí)投入三個(gè)作業(yè)運(yùn)行。它們的執(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)先級(jí)從高到低為Job1、Job2和Job3，優(yōu)先級(jí)高的作業(yè)可以搶占優(yōu)先級(jí)低的作業(yè)的CPU。

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

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

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

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

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

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

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

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

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

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

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

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

答：分別畫出單道和多道運(yùn)行的時(shí)間圖

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

單道總運(yùn)行時(shí)間為190ms。CPU利用率為（190-80）/190=57.9%

單道運(yùn)行時(shí)間關(guān)系圖

多道總運(yùn)行時(shí)間為140ms。CPU利用率為（140-30)/140=78.6%

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

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

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

(l）最早結(jié)束的程序?yàn)锽，最后結(jié)束的程序?yàn)镃。

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

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

有兩個(gè)程序，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秒。兩個(gè)程序共用了80秒，CPU化40秒。故CPU利用率為40/80=50％。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

令②-①式得到：

T2-Tl=b-a>0

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

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

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

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

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

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

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

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

(2）采用雙算法調(diào)度作業(yè)，若令時(shí)間片長(zhǎng)＝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è)，運(yùn)作情況：

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

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

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

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

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

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

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

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

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

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

答：

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

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

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

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

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

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)時(shí)間作業(yè)平均帶權(quán)周轉(zhuǎn)時(shí)間T=(30+22+6+16+28)/5=20.4

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

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

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

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

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

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

解：

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

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

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

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

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

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

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

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

對(duì)每個(gè)訪問共享變量C的進(jìn)程，編寫訪問共享變量的程序段為：

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

loop2:(R1)→R3;

Add/decreaseR3;

TC&S;

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

Rl的值傳送到R3中，進(jìn)程修改共享變量時(shí)，先對(duì)R3操作（不是直接操作C）。

R3加1／減1，進(jìn)程歸還／申請(qǐng)由共享變量C代表的共享資源（假定每次一個(gè)）。

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

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

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

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

(4）舉例。

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

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

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

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

decreaseR3：申請(qǐng)使用磁帶機(jī)，做減1操作，故（R3）=2.

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

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

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

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

r(conditio二01)loop2;

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

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

2

310:00

10:10

10:252:00

1:00

0:25

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

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

答：

可見HRRF比FIFO要好

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

答：

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

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

(2）是后進(jìn)先出算法。因?yàn)樵诰途w隊(duì)列中的進(jìn)程比在CPU上運(yùn)行的進(jìn)程的優(yōu)先權(quán)下降得快，故后進(jìn)入就緒隊(duì)列的進(jìn)程此先進(jìn)入的進(jìn)程的優(yōu)先權(quán)高。

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

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

答

說明：

(1)J2到達(dá)時(shí)搶占J1;J3到達(dá)時(shí)搶占J2。

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

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

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

(5）因J5最短，故它第二個(gè)完成。這時(shí)J6方可進(jìn)入主存。因J6最短，故它第三個(gè)完成。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

詳細(xì)說明：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

答：

FIFO算法選中作業(yè)執(zhí)行的次序?yàn)椋篠JF算法選中作業(yè)執(zhí)行的次序?yàn)椋?/p>

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

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

與上題類同，詳細(xì)說明略。

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

答：

組織如下的定時(shí)喚醒隊(duì)列

。

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

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

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

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

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

答：

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個(gè)進(jìn)程共享一個(gè)互斥段，如果：

(1）每次只允許一個(gè)進(jìn)程進(jìn)入互斥段；

(2）每次最多允許m個(gè)進(jìn)程（m簇n）同時(shí)進(jìn)入互斥段。

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

答：所采用的互斥信號(hào)量初值不同。

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

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

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

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

3有兩個(gè)優(yōu)先級(jí)相同的進(jìn)程P1和P2，各自執(zhí)行的操作如下，信號(hào)量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)對(duì)進(jìn)程語句進(jìn)行編號(hào)，以方便描述．

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

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

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

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

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

7：二z+X:

z:=y+1;

y:＝Z十y;

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

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

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

答：1）使用信號(hào)量和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)

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

答1：實(shí)質(zhì)上是兩個(gè)進(jìn)程的同步問題，設(shè)信號(hào)量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管程的同步機(jī)制使用條件變量和wait及signal，嘗試為管程設(shè)計(jì)一種僅僅使用一個(gè)原語操作的同步機(jī)制。

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

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

司機(jī)的活動(dòng)：?jiǎn)?dòng)車輛：正常行車；到站停車。

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

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

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

varS1,S2:semaphore;

S1=0；S2=0；

cobegin

{

driver();

busman();

}

coend

driver()

begin

while(1){

P(S1)

啟動(dòng)車輛；正常行車；到站停車；

V(S2);

}

end

busman()

begin

while(1){

關(guān)車門；

V(51)

售票;

P(S2)

開車門；

上下乘客；

}

end

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

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

varS1,S2,S3,S4:semaphore;

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

cobegin

{processP1

begin

repeat

有顧客到來；

P(S1)；

接受顧客點(diǎn)菜；

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、在信號(hào)量S上作P、v操作時(shí)，S的值發(fā)生變化，當(dāng)S>0、S=0、S<0時(shí)，它們的的物理意義是什么？

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

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

ProcessPProcessQ

beginbegin

A;D;

B;E;

C;end:

end;

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

P1P2

repeatrepeat

k:=k×2;printk;

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

untilfalse;untilfalse;

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

答：

(1）共有10種交錯(cuò)執(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）把語句編號(hào)，以便于描述：

P1P2

repeatrepeat

k:=k×2；①printk；③

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

untilfalse;untilfalse;

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

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

①、②、③、④，這時(shí)的打印值為：47

③、④、①、②，這時(shí)的打印值為：23

①、③、②、④，這時(shí)的打印值為：46

①、③、④、②，這時(shí)的打印值為：46

③、①、②、④，這時(shí)的打印值為：23

③、①、④、②，這時(shí)的打印值為：23

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

11證明信號(hào)量與管程的功能是等價(jià)的：

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

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

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

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

Varmutex,c:semaphore;

mutex:=1;c:=0;

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

P(mutex);

}

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

{

V(mutex);

}

voidleave-with-sigal(c)/*在條件c上發(fā)信號(hào)并退出管程，釋放一個(gè)等待c條件的進(jìn)程。｛注意這時(shí)沒有開放管程，因?yàn)閯倓偙会尫诺倪M(jìn)程己在管程中。

V(c);

}

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

{

V(mutex);

P(c);

}

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

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證明消息傳遞與管程的功能是等價(jià)的：

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

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

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

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

(2）用管程實(shí)現(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證明信號(hào)量與消息傳遞是等價(jià)的：

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

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

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

1）把消息隊(duì)列組織成一個(gè)共享隊(duì)列，用一個(gè)互斥信號(hào)量管理對(duì)該隊(duì)列的入隊(duì)操作和出隊(duì)操作.

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

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

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

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

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

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

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

15試?yán)糜涗浶托盘?hào)量和P、V操作寫出一個(gè)不會(huì)出現(xiàn)死鎖的五個(gè)哲學(xué)家進(jìn)餐問題的算法。答：

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程序的語句進(jìn)行編號(hào)：

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（對(duì)于所有j,j≠i）條件時(shí)，Pi才能進(jìn)入它的臨界區(qū)，而且進(jìn)程Pi不會(huì)改變除自己外的其他進(jìn)程所對(duì)應(yīng)的flag[j]的值。另外，進(jìn)程Pi總是先置自己的flag[j]為in_cs后，才去判別Pj進(jìn)程的flag[j]的值是否等于in_cs所以，此算法能保證n個(gè)進(jìn)程互斥地進(jìn)入臨界區(qū)。

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

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

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

17另一個(gè)經(jīng)典同步問題：吸煙者問題(patil,1971）。三個(gè)吸煙者在一個(gè)房間內(nèi)，還有一個(gè)香煙供應(yīng)者。為了制造并抽掉香煙，每個(gè)吸煙者需要三樣?xùn)|西：煙草、紙和火柴，供應(yīng)者有豐富貨物提供。三個(gè)吸煙者中，第一個(gè)有自己的煙草，第二個(gè)有自己的紙和第三個(gè)有自己的火柴。供應(yīng)者隨機(jī)地將兩樣?xùn)|西放在桌子上，允許一個(gè)吸煙者進(jìn)行對(duì)健康不利的吸煙。當(dāng)吸煙者完成吸煙后喚醒供應(yīng)者，供應(yīng)者再把兩樣?xùn)|西放在桌子上，喚醒另一個(gè)吸煙者。試采用：(1）信號(hào)量和P、v操作，(2）管程編寫他們同步工作的程序。答：(1）用信號(hào)量和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、如圖所示，四個(gè)進(jìn)程Pi（i=0…3）和四個(gè)信箱Mj(j=0…3)，進(jìn)程間借助相鄰信箱傳遞消息，即Pi每次從Mi中取一條消息，經(jīng)加工后送入M(i+1)mod4，其中M0、M1、M2、M3;可存放3、3、2、2個(gè)消息。初始狀態(tài)下，MO裝了三條消息，其余為空。試以P、V為操作工具