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

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

練習(xí)1

1.i-i.10題解見(jiàn)書(shū)

1.11有一臺(tái)輸入設(shè)備和一臺(tái)輸出設(shè)備的計(jì)算機(jī)系統(tǒng)上，運(yùn)行有兩道程序。兩道程序投

入運(yùn)行情況如下：

程序1先開(kāi)始運(yùn)行，其運(yùn)行軌跡為：計(jì)算50ms、輸出100ms,計(jì)算50ms、輸出100ms,

結(jié)束；

程序2后開(kāi)始運(yùn)行，其運(yùn)行軌跡為：計(jì)算50ms、輸入100ms、計(jì)算100ms、結(jié)束。

1.忽略調(diào)度時(shí)間，指出兩道程序運(yùn)行時(shí)，CPU是否有空閑？在哪部分空閑？指出程序1

和程序

2.有無(wú)等待CPU的情況？如果有，發(fā)生在哪部分？

題解：

由題畫(huà)出CPU利用圖如下:

由圖可知，1.CPU有空閑，在100ms-l50nls時(shí)間段是空閑的。

2.程序1無(wú)等待時(shí)間，而程序2在一開(kāi)始的0ms~50ms時(shí)間段會(huì)等待。

1.12在計(jì)算機(jī)系統(tǒng)上.運(yùn)行三道程序，運(yùn)行次序?yàn)槌绦?、程序2、程序3。程序1的運(yùn)

行軌跡為：計(jì)算20ms、輸入40ms、計(jì)算10ms。

程序2的運(yùn)行軌跡為：計(jì)算40ms、輸入30ms、計(jì)算10ms。

程序3的運(yùn)行軌跡為：計(jì)算60ms、輸入30ms、計(jì)算20ms。

忽略調(diào)度時(shí)間，畫(huà)出三道程序運(yùn)行的時(shí)間關(guān)系圖；完成三道程序共花多少時(shí)間？與單道

程序比較，節(jié)省了多少時(shí)間？

解答：三道程序運(yùn)行，完成三道程序共花170ms。與單道程序（260ms）比較，節(jié)省了

90mso

（始終按照1-2-3的次序，即程序1一程序2-程序3f程序1-程序2f（在程序3運(yùn)

行前會(huì)停10ms等待輸入完成）程序3o

（如果不是按照程序1、2、3的次序完成則會(huì)有多種情況。）

1.13在計(jì)算機(jī)系統(tǒng)上有兩臺(tái)輸入/輸出設(shè)備，運(yùn)行兩道程序。

程序1的運(yùn)行軌跡為：計(jì)算10ms、輸入5ms、計(jì)算5ms、輸出10ms、計(jì)算10ms。

程序2的運(yùn)行軌跡為：輸入10ms、計(jì)算10ms、輸出5ms、計(jì)算5ms、輸出10ms。

在順序環(huán)境下，先執(zhí)行程序1,再執(zhí)行程序2,求總的CPU利用率為多少?

CPU利用率=40ms/80ms*100%=50%

1.14一個(gè)計(jì)算機(jī)系統(tǒng)有足夠的內(nèi)存空間存放3道程序，這些程序有一半的時(shí)間在空閑

等待I/O操作。問(wèn)多大比例的CPU時(shí)間被浪費(fèi)掉了。

題解：由題畫(huà)圖如下:

程序1

程序2

程序3

------------------------------------------------------------------------>t

01/21/41/8--------1

因?yàn)槊總€(gè)程序有一半的時(shí)間在等待I/O操作，所以在并發(fā)狀態(tài)下，程序1、程序

2、程序3所占時(shí)間比依次減半（如上圖），所以浪費(fèi)的時(shí)間比例為1/8。

練習(xí)2

2.18某系統(tǒng)中進(jìn)程狀態(tài)變化如圖2.22所示，當(dāng)對(duì)系統(tǒng)中的進(jìn)程進(jìn)行觀察時(shí)，發(fā)現(xiàn)某

一進(jìn)程產(chǎn)生的?次狀態(tài)變化會(huì)引起另一進(jìn)程發(fā)生狀態(tài)變化。

（1）在什么情況下，一個(gè)進(jìn)程的狀態(tài)變化3能夠立即引起另一進(jìn)程的狀態(tài)變化1?

（2）在什么情況下，一個(gè)進(jìn)程的狀態(tài)變化2能夠立即引起另一進(jìn)程的狀態(tài)變化1?

（3）進(jìn)程的狀態(tài)變化3是否可能引起另一進(jìn)程的狀態(tài)變化2?進(jìn)程的狀態(tài)變化3是否可

能引起另一進(jìn)程的狀態(tài)變化1?

解答：

(1)當(dāng)就緒隊(duì)列中還存在其它進(jìn)程的情況下，一個(gè)進(jìn)程的狀態(tài)變化3能夠立即引起另

一進(jìn)程的狀態(tài)變化2。

(2)當(dāng)就緒隊(duì)列中還存在其它進(jìn)程的情況下，一個(gè)進(jìn)程從運(yùn)行狀態(tài)變化到就緒狀態(tài)

后，另一個(gè)就緒進(jìn)程能夠從就緒狀態(tài)變?yōu)檫\(yùn)行狀態(tài)。

(3)不可能，可能。

2.19分別寫(xiě)出相應(yīng)的程序來(lái)描述圖2.23中的前趨圖。

解答

程序：SI:a:=x+lS2:b:=a+2S3:c:=a+3S4:d:=b+4S5:e:=b+cS6:f:=e+5S7:g=e+6

程序：SI:a:=x+lS2:b:=a+2S3:c:=a+3S4:d:=b+4S5:e:=b+cS6:f:=d+eS7:g:=c+e

2.20假設(shè)在一個(gè)系統(tǒng)中，新進(jìn)程以每分鐘8個(gè)進(jìn)程的速率到達(dá)，每個(gè)進(jìn)程請(qǐng)

S4

求服務(wù)的平均時(shí)間為6s,估計(jì)在一個(gè)單處理器系統(tǒng)中CPU忙的時(shí)間比率。如果新進(jìn)程

以每分鐘10個(gè)進(jìn)程的速率到達(dá)，每個(gè)進(jìn)程請(qǐng)求服務(wù)的平均時(shí)間也為6s,估計(jì)在一個(gè)單處

理器系統(tǒng)中CPU忙的時(shí)間比率。

如果新進(jìn)程創(chuàng)建以每分鐘超過(guò)10個(gè)進(jìn)程的速率到達(dá)，每個(gè)進(jìn)程請(qǐng)求服務(wù)的平均時(shí)間為

6s,估計(jì)在一個(gè)單處理器系統(tǒng)中CPU忙得時(shí)間比率，并解釋此時(shí)的情況。

解答：

因?yàn)樾逻M(jìn)程每分鐘8個(gè)進(jìn)程的速率到達(dá)，每個(gè)進(jìn)程之間達(dá)到的時(shí)間間隔為

7.5s。由于每個(gè)進(jìn)程占用6s的CPU時(shí)間。所以，1分鐘之內(nèi)CPU的空間時(shí)間為

8*1.5s=12soCPU的利用率為48/60=0.8,即805。

因?yàn)樾逻M(jìn)程每分鐘10個(gè)進(jìn)程的速率到達(dá)，每個(gè)進(jìn)程之間達(dá)到的時(shí)間間隔為6s。由于每

個(gè)進(jìn)程占用6s的CPU時(shí)間。所以，1分鐘之內(nèi)CPU的空間時(shí)間為Os。CPU的利用率為

100%。

如果新進(jìn)程創(chuàng)建以每分鐘超過(guò)10個(gè)進(jìn)程的速率到達(dá)，每個(gè)進(jìn)程請(qǐng)求服務(wù)的平均時(shí)間為

6s,則請(qǐng)求服務(wù)時(shí)間會(huì)大于1分鐘，CPU一直會(huì)處于繁忙，所以CPU忙的時(shí)間比率同樣為

100%。

2.21一個(gè)系統(tǒng)中有4個(gè)進(jìn)程，進(jìn)程P1要求20s后運(yùn)行，經(jīng)過(guò)40s后再次運(yùn)行；進(jìn)程P2

要求25s后運(yùn)行；進(jìn)程P3要求35s后運(yùn)行，經(jīng)過(guò)35s后再次運(yùn)行；進(jìn)程P4要求60s后運(yùn)

行。進(jìn)程在阻塞隊(duì)列等待被喚醒后運(yùn)行，試創(chuàng)建進(jìn)程的喚醒隊(duì)列。

解答：進(jìn)程的喚醒隊(duì)列為P1-P2-P3-P4-P1-P3

注意：“經(jīng)過(guò)40s后再次運(yùn)行”表示第1次運(yùn)行完成后再過(guò)40so

2.22如果線程是在用戶空間線程庫(kù)中實(shí)現(xiàn)，解釋為什么當(dāng)進(jìn)程中的一個(gè)線程阻塞時(shí)，

進(jìn)程內(nèi)的所有其它線程都會(huì)阻塞？如果線程是在內(nèi)核空間中實(shí)現(xiàn)，而進(jìn)程內(nèi)的?個(gè)線程阻

塞不會(huì)引起進(jìn)程內(nèi)的其他線程被阻塞，為什么？

解答：

用戶級(jí)線程由用戶空間運(yùn)行的用戶級(jí)線程庫(kù)實(shí)現(xiàn)。當(dāng)一個(gè)應(yīng)用程序提交給操作系統(tǒng)后，

操作系統(tǒng)首先為該應(yīng)用程序建立一個(gè)內(nèi)核管理進(jìn)程，然后用戶級(jí)線程庫(kù)為該進(jìn)程創(chuàng)建一個(gè)

或多個(gè)用戶級(jí)線程，但內(nèi)核并不知道用戶空間線程的活動(dòng)，內(nèi)核只是以進(jìn)程為單位，實(shí)現(xiàn)

進(jìn)程狀態(tài)的轉(zhuǎn)換，因此當(dāng)進(jìn)程中的一個(gè)線程阻塞時(shí)，進(jìn)程內(nèi)的所有其它線程都會(huì)阻塞。

如果線程是在內(nèi)核空間中實(shí)現(xiàn)的，這些內(nèi)核級(jí)線程都由內(nèi)核創(chuàng)建和控制管理，內(nèi)核為整

個(gè)進(jìn)程及進(jìn)程中的所有線程維護(hù)現(xiàn)場(chǎng)信息，內(nèi)核的調(diào)度是在線程的基礎(chǔ)上進(jìn)行的，因而進(jìn)

程的一個(gè)線程阻塞不會(huì)引起進(jìn)程內(nèi)的其他線程被阻塞。

練習(xí)3

3.13證明作業(yè)調(diào)度算法中短作業(yè)優(yōu)先調(diào)度算法具有最小平均等待時(shí)間。

證明:假設(shè)在作業(yè)隊(duì)列中等待運(yùn)行的作業(yè)有N道,分別為NO,Nl,N2,,,,Nn-1,它們的

運(yùn)行時(shí)間分別為t0,tl,tnT,且滿足

由于短作業(yè)有限調(diào)度算法總是選擇最短的作業(yè)先調(diào)度，故這些作業(yè)總的等待時(shí)間為：

Tl=0+t0+(t0+tl)+(tO+tl+t2)+?+(tO+tl+t2+?+tn-2)

=(N-1)tO+(N-2)tl+(N-3)t2+?+tn-2(1)

如果不按照短作業(yè)優(yōu)先調(diào)度算法，可設(shè)調(diào)度順序?yàn)椋篘l,NO,N2,”，Nn-1,故這些作

業(yè)總的等待時(shí)間為：

T2=0+tl+(tO+tl)+(tO+tl+t2)+”+(tO+tl+t2+?+tn-2)

=(N-2)tO+(N-1)tl+(N-3)t2+,,+tn-2(2)

(2)-(1)得:

T2T1=tltO>0

說(shuō)明任何一種作業(yè)調(diào)度順序的作業(yè)的平均等待時(shí)間都大于按照短作業(yè)優(yōu)先的作業(yè)的平均

等待時(shí)間。

3.14假設(shè)在一個(gè)處理器上執(zhí)行5個(gè)作業(yè)，作業(yè)到達(dá)的次序和需要執(zhí)行的時(shí)間分別為:

JO(75ms)、JI(15ms)、J2(5ms)、J3(15ms)、J4(45ms),

假定系統(tǒng)中使用FCFS調(diào)度算法，作業(yè)J3的周轉(zhuǎn)時(shí)間是多少？作業(yè)的平均等待時(shí)間是多

少？

周轉(zhuǎn)時(shí)間(ms)等待時(shí)間(ms：

J0750

J19075

129590

J311095

J4155110

平均等待時(shí)間(ms)74

3.15在單道批處理系統(tǒng)中，三個(gè)作業(yè)的提交時(shí)間分別為：10：00、10：10、10：20,需

要執(zhí)行時(shí)間分別為：2小時(shí)、1小時(shí)、0.5小時(shí)，分別按照短作'也優(yōu)先調(diào)度算法和高響應(yīng)比

優(yōu)先調(diào)度算法進(jìn)行調(diào)度，比較哪一種調(diào)度算法更好？解：

(1)不搶占：

執(zhí)行順序?yàn)锳,C,B

平均周轉(zhuǎn)時(shí)間：(120+130+200)/3=150(min)

平均帶勸周轉(zhuǎn)時(shí)間：(120/120+130/30+200/60)/3=26/9

搶占：

A(10：10),B(10：20),C(10:50),B(ll:40),A(13:30)

平均周轉(zhuǎn)時(shí)間：(210+90+30)/3=110(min)

平均帶勸周轉(zhuǎn)時(shí)間：(210/120+90/60+30/30)/3=510/360=17/12

(2)響應(yīng)比高者優(yōu)先調(diào)度算法不會(huì)搶占，因此，只存在這樣一種情況:

執(zhí)行順序?yàn)锳,C,B

平均周轉(zhuǎn)時(shí)間：(120+130+200)/3=150(min)

平均帶勸周轉(zhuǎn)時(shí)間：(120/120+130/30+200/60)/3=26/9所以，如果要比較哪一種算

法好自然針對(duì)不搶占的情況。根據(jù)比較結(jié)果，它們的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)相同，

這主要是該應(yīng)用正好發(fā)生了這樣湊巧的情況。

3.16假設(shè)在具有一個(gè)處理器的系統(tǒng)上執(zhí)行下面的作業(yè)，假如采用搶占式短作業(yè)優(yōu)先調(diào)度

算法，作業(yè)需要處理時(shí)間T和到達(dá)時(shí)間A分別如下：那么：

IT到達(dá)時(shí)間A

0500

13510

22010

32555

41095

作業(yè)1答：

1,執(zhí)行順序?yàn)椋?(10),2(30),1(65),3(90),0(130),4(170)作業(yè)0

的周轉(zhuǎn)時(shí)間為：130,

作業(yè)1的周轉(zhuǎn)時(shí)間為：55,

作業(yè)2的周轉(zhuǎn)時(shí)間為：20,

作業(yè)3的周轉(zhuǎn)時(shí)間為：35

作業(yè)4的周轉(zhuǎn)時(shí)間為：65

平均周轉(zhuǎn)時(shí)間=305/5=61

作業(yè)0的等待時(shí)間為：130-50=80,

作業(yè)1的等待時(shí)間為：55-35=20,

作業(yè)2的等待時(shí)間為：10T0=0,

作業(yè)3的等待時(shí)間為：，35-25=10

作業(yè)4的等待時(shí)間為：，65-40=25

3.17假如在具有一個(gè)處理器系統(tǒng)中，采用優(yōu)先級(jí)高者優(yōu)先的進(jìn)程調(diào)度算法，優(yōu)

IT優(yōu)先級(jí)

0753

1151

254

3155

4452

T、優(yōu)先數(shù)分別如下：

(12的周轉(zhuǎn)時(shí)間是多少？進(jìn)程的平均等待時(shí)間是多少？

(3)有優(yōu)先級(jí)搶占情況下，寫(xiě)出進(jìn)程的執(zhí)行先后序列，進(jìn)程2的周轉(zhuǎn)時(shí)間是多少？進(jìn)

程的平均等待時(shí)間是多少？

答：

(1)無(wú)搶占：

執(zhí)行順序?yàn)椋?(15),4(60),0(135),2(140),3(155)

進(jìn)程0的周轉(zhuǎn)時(shí)間為：135

進(jìn)程1的周轉(zhuǎn)時(shí)間為：15

進(jìn)程2的周轉(zhuǎn)時(shí)間為：140

進(jìn)程3的周轉(zhuǎn)時(shí)間為：155

進(jìn)程4的周轉(zhuǎn)時(shí)間為：60

進(jìn)程的平均等待時(shí)間=((135-75)+(15-15)+(140-5)+(155-15)+(60-45))/5

=70

(2)有搶占：

優(yōu)先級(jí)搶占同上一樣。

3.18假如在具有一個(gè)處理器的系統(tǒng)中，采用時(shí)間片輪轉(zhuǎn)調(diào)度算法，時(shí)間片大小為10。

進(jìn)程需要處理時(shí)間T和到達(dá)時(shí)間A分別如下：

IT到達(dá)時(shí)間A

0500

13510

22010

31580

4-1085

寫(xiě)出進(jìn)程的執(zhí)行序列，進(jìn)程3的周轉(zhuǎn)時(shí)間是多少？進(jìn)程的平均等待時(shí)間是多少？

答：

進(jìn)程的執(zhí)行序列為：0，1,2,0,1,2,0,1,3,4,0,1,3,4,0,4進(jìn)程0的周

轉(zhuǎn)時(shí)間T0=140

進(jìn)程1的周轉(zhuǎn)時(shí)間Tl=105

進(jìn)程2的周轉(zhuǎn)時(shí)間門=50

進(jìn)程3的周轉(zhuǎn)時(shí)間Tl=40

進(jìn)程4的周轉(zhuǎn)時(shí)間Tl=75

進(jìn)程的平均等待時(shí)間為：((140-50)+(105-35)+(50-20)+(40-15)+(75-

40))/5=50

3.18在時(shí)間片輪轉(zhuǎn)調(diào)度算法中，有n個(gè)進(jìn)程共享CPU。

(1)如果進(jìn)程切換的時(shí)間不可忽略，每次進(jìn)程切換用去時(shí)間為s秒，在保證每個(gè)進(jìn)程

至少每t秒內(nèi)能夠在CPU上輪回一次的前提下，確定時(shí)間片大小q使得進(jìn)程切換所造成的

負(fù)載最小。

(2)如果n=100,t=l,s=0.001,那么q的大小應(yīng)該是多少？

答：

(1)時(shí)間片大小q=(t-ns)/n

(2)q=(1-100*0.001)/100=0.009

3.19有一個(gè)四道作業(yè)的操作系統(tǒng)，若在一段時(shí)間內(nèi)先后到達(dá)6個(gè)作'也，它們的提交時(shí)

間和估計(jì)運(yùn)行時(shí)間由下表給出：

作業(yè)提交時(shí)間估計(jì)運(yùn)行時(shí)間（分鐘）

18：0060

28：2035

38：2520

48：3025

58：355

68：4010

系統(tǒng)采用短作'也優(yōu)先調(diào)度算法，作'也被調(diào)度進(jìn)入系統(tǒng)后中途不得退出。但作'也運(yùn)行時(shí)可

被更短的作業(yè)搶占。分別給出6個(gè)作、業(yè)的執(zhí)行時(shí)間序列，作業(yè)的周轉(zhuǎn)時(shí)間，平均周轉(zhuǎn)時(shí)

間。

答:

作業(yè)的執(zhí)行順序?yàn)椋?（8：20）,2（8：25）,3（8：45）,5（8：50）,6（9：

00）,4（9：25），2（9：55），1（10：35）

作業(yè)1的周轉(zhuǎn)時(shí)間=155min

作業(yè)2的周轉(zhuǎn)時(shí)間二95min

作業(yè)3的周轉(zhuǎn)時(shí)間二20min

作業(yè)4的周轉(zhuǎn)時(shí)間二55min

作業(yè)5的周轉(zhuǎn)時(shí)間二15min

作業(yè)6的周轉(zhuǎn)時(shí)間二20min

作業(yè)的平均周轉(zhuǎn)時(shí)間為：360/6=60

3.20在一個(gè)實(shí)時(shí)系統(tǒng)中有4個(gè)周期性事件，周期分別為50、100、150、200mso假設(shè)其

處理時(shí)間分別需要30、25、20和xms,則該系統(tǒng)可調(diào)度允許的x值最大為多少？

解:

30/50+25/100+150/20+200/x=1

X=10/3

3.21某系統(tǒng)的進(jìn)程狀態(tài)變化如圖3.23所示，該系統(tǒng)的進(jìn)程調(diào)度為非搶占方式，根據(jù)該

狀態(tài)圖敘述系統(tǒng)的調(diào)度策略、調(diào)度效果。

圖3.23狀態(tài)變化圖

答：首先采用優(yōu)先權(quán)高者優(yōu)先調(diào)度算法，然后采用時(shí)間片為100ms的調(diào)度算法。該調(diào)

度算法如果調(diào)度效果考慮更周到的話，應(yīng)該讓阻塞隊(duì)列上的進(jìn)程喚醒后進(jìn)入低優(yōu)先級(jí)就緒

隊(duì)列，這樣能夠保證優(yōu)先級(jí)高的進(jìn)程及時(shí)調(diào)度，優(yōu)先級(jí)低的進(jìn)程能夠合理的得到調(diào)度。

第4章

4.13如果有n個(gè)進(jìn)程共享一個(gè)互斥段

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

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

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

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

(1)互斥信號(hào)量初值為1,變化范圍為bn+1,1］。

當(dāng)沒(méi)有進(jìn)程進(jìn)入互斥段時(shí)，信號(hào)量值為1;

當(dāng)有1個(gè)進(jìn)程進(jìn)入互斥段時(shí)，但沒(méi)有進(jìn)程等待進(jìn)入互斥段時(shí)，信號(hào)量值為0；當(dāng)有1個(gè)

進(jìn)程進(jìn)入互斥段，有,1個(gè)進(jìn)程等待進(jìn)入互斥段時(shí)，信號(hào)量值為-1;最多可有n-1個(gè)進(jìn)程

等待進(jìn)入互斥段，故此時(shí)信號(hào)量的值為-(n-1)。

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

當(dāng)沒(méi)有進(jìn)程進(jìn)入互斥段時(shí)，信號(hào)量值為m；

當(dāng)有1個(gè)進(jìn)程進(jìn)入互斥段時(shí)，但沒(méi)有進(jìn)程等待進(jìn)入互斥段時(shí)，信號(hào)量值為mT；當(dāng)有m

個(gè)進(jìn)程進(jìn)入互斥段，但沒(méi)有進(jìn)程等待進(jìn)入互斥段時(shí)，信號(hào)量值為0；當(dāng)有m個(gè)進(jìn)程進(jìn)入互

斥段，有1個(gè)進(jìn)程等待進(jìn)入互斥段時(shí)，信號(hào)量值為T;最多可有n-m個(gè)進(jìn)程等待進(jìn)入互

斥段，故此時(shí)信號(hào)量的值為-(n-m)。

4.14在兩條雙向道路的交叉路口，沒(méi)有行人通過(guò)，只有汽車通過(guò)。交通情況如下：

(1)任何給定的時(shí)刻只能有一輛車過(guò)馬路；

(2)當(dāng)一輛車到達(dá)交叉路口并且另一條街道上沒(méi)有車來(lái)到的時(shí)候，應(yīng)該允許此車通

過(guò)；

(3)當(dāng)兩個(gè)方向上都有車到達(dá)的時(shí)候，它們應(yīng)該輪流通過(guò)，以防止在其中一個(gè)方向上

的無(wú)限期延遲。

用信號(hào)量操作實(shí)現(xiàn)道路交通問(wèn)題。

解：

semphoreSl=0,S2=0;//有無(wú)車到達(dá)，為0時(shí)無(wú)到達(dá)

semphoreMl=l,M2=0;〃路中被占

Pl:

if(車到達(dá))

v(Sl);

while(!S2);

if(!S2)

過(guò)一輛車；

else

p(M2);p(Ml);

過(guò)一輛車；

v(Ml);

}

P2:

if(車到達(dá))

v(S2);

while(!S2);

if(!Sl)

過(guò)一輛車；

else

(

p(Ml);

P(S2);

過(guò)一輛車；

v(M2);

)

4.15在哲學(xué)家進(jìn)餐問(wèn)題中，假設(shè)5個(gè)哲學(xué)家中第i個(gè)執(zhí)行下面的代碼段p(mutex);

p(fork[i]);

p(fork[i+l%5]);

v(mutex);

eat;

v(fork[i]);

v(fork[i+l%5]);

(1)說(shuō)明這段代碼是否滿足哲學(xué)家進(jìn)餐問(wèn)題的所有需求。

(2)如果V(mutex)語(yǔ)句改在第二個(gè)V()操作之后，或者在兩個(gè)P()操作之間，說(shuō)明這兩

種解決方法是改進(jìn)了算法還是變壞了算法。

答：

(a)滿足

(b)都不行

4.16有兩個(gè)優(yōu)先級(jí)相同的進(jìn)程P1和P2,各自執(zhí)行的操作如下，信號(hào)量S1和S2的初

值都為0,試問(wèn)Pl、P2并發(fā)執(zhí)行后，x、y、z的值各為多少？

Pl：P2：

beginbegin

y:=1;(1)x:=1;(5)

y:=y+3;(2)x:=x+5;(6)V(S1);P(S1);

z:=y+1;(3)x:x+y;(7)

P(S2);V(S2);

y:=y+z;(4)z:=x+z;(8)

end;end;答：語(yǔ)句(1)(2)(5)(6)不相交，任何執(zhí)行順序，結(jié)果相同。

情況1：語(yǔ)句(4)先執(zhí)行x=10,y=9,z=15；

情況2：語(yǔ)句(8)先執(zhí)行x=10,y=19,z=15；

情況3：語(yǔ)句(3)推遲到語(yǔ)句(8)之后，x不定，y=4,z不定;

4.17兩個(gè)進(jìn)程A、B,考慮下面的信號(hào)量編碼

semaphores=1;

intx=10,y=2;

fork(A,0);

fork(B,0);

A(){BO{

(1)x++;(4)if(x>10)

(2)V(s);(5)x——;

(3)y=x—2;(6)else{P(s);

}x---;}

}

分別說(shuō)明(1)、(2)、(3)、(4)、(5)、(6)語(yǔ)句之后的x、y值為多少？

答：

(1)x=ll,y=2(2)x=ll,y=2(3)x=ll,y=9

(4)x=ll,y=9(5)x=10,y=9(6)x=10,y=8

4.18三個(gè)進(jìn)程：輸入、計(jì)算、輸出。它們通過(guò)兩個(gè)緩沖區(qū)傳遞數(shù)據(jù)，如圖4.11所示。

每個(gè)緩沖區(qū)次只能放入一條數(shù)據(jù)。寫(xiě)出用信號(hào)量進(jìn)行同步。

(7)U公共緩沖區(qū)1卜——(p)

解：varemptyl,fulll,empty2,ful12:semaphore:=1,0,1,0;

begin

parbegin

I:begin

repeat

wait(empty1);

puttobufferl;

signal(fulll);

untilfalse;

end;P:begin

repeat

wait(fulll);

getfrombufferl;

signal(emptyl);

wait(empty2);

puttobuffer2;

signal(full2);

untilfalse;

end;

0:begin

repeat

wait(full2)

getfrombuffer2;

signal(empty2);

untilfalse;

end;

parend;

end;

第5章

5.1什么是死鎖？引起死鎖的原因和必要條件是什么？

死鎖是指多個(gè)進(jìn)程因?yàn)楦?jìng)爭(zhēng)資源造成的一種僵局。

原因：并發(fā)進(jìn)程對(duì)臨界資源的競(jìng)爭(zhēng)和并發(fā)進(jìn)程推進(jìn)順序不當(dāng)。

必要條件：互斥條件，占有并請(qǐng)求條件，不剝奪條件，環(huán)路等待條件。

5.2比較解決死鎖的方法中，那種方法最容易實(shí)現(xiàn)？那種方法使得資源的利用率最高？

解決死鎖的方法：預(yù)防死鎖，避免死鎖，檢測(cè)死鎖，解除死鎖。

預(yù)防死鎖是通過(guò)設(shè)計(jì)協(xié)同資源管理程序，在進(jìn)程運(yùn)行期間，柏懷死鎖產(chǎn)生的四個(gè)條件之

中的任何一個(gè)，是指不成立。是最容易實(shí)現(xiàn)的方法。

解除死鎖是在發(fā)現(xiàn)死鎖后，解除死鎖，釋放資源。是資源利用率最高的方法。

5.3預(yù)防死鎖的方法有哪些？

破壞互斥條件，破壞占有并請(qǐng)求，阻止環(huán)路等待，允許剝奪

5.8系統(tǒng)中有3個(gè)進(jìn)程共享4個(gè)資源，每個(gè)進(jìn)程每次只能申請(qǐng)或釋放一個(gè)資源，每個(gè)進(jìn)

程最多需要2個(gè)資源，給進(jìn)程是否會(huì)發(fā)生死鎖，為什么？

解：

不會(huì)發(fā)生死鎖。3個(gè)進(jìn)程共享4個(gè)資源，每個(gè)進(jìn)程最多需要2個(gè)資源?？傆幸粋€(gè)進(jìn)程的

請(qǐng)求會(huì)滿足，運(yùn)行并釋放資源。不會(huì)形成環(huán)路等待。

5.9系統(tǒng)中有20個(gè)進(jìn)程，每個(gè)進(jìn)程最多使用3個(gè)資源，每個(gè)進(jìn)程逐個(gè)申請(qǐng)并競(jìng)爭(zhēng)使用

60個(gè)同類資源。一旦某進(jìn)程獲得所需要的資源，完成后立即釋放全部資源。系統(tǒng)是否會(huì)發(fā)

生死鎖？為什么？

系統(tǒng)不會(huì)發(fā)生死鎖。以最壞的情況來(lái)考慮，20個(gè)進(jìn)程都需要使用3個(gè)資源。當(dāng)前，每個(gè)

進(jìn)程都持有2個(gè)資源。(20*2=40).都在申請(qǐng)第3個(gè)資源(60-40=20)對(duì)于剩余的20個(gè)

資源，每個(gè)進(jìn)程多會(huì)得到一個(gè)資源。不會(huì)形成環(huán)路等待。

5.10一臺(tái)計(jì)算機(jī)有8臺(tái)打印機(jī)，被N個(gè)進(jìn)程競(jìng)爭(zhēng)使用，每個(gè)進(jìn)程最多需要3臺(tái)。請(qǐng)

問(wèn)N為多少時(shí)，系統(tǒng)沒(méi)有死鎖的危險(xiǎn)，說(shuō)明原因。解：

N=3時(shí)，沒(méi)有死鎖的危險(xiǎn)。

對(duì)于N個(gè)進(jìn)程，都持有2臺(tái)打印機(jī)時(shí)，申請(qǐng)第3臺(tái)打印機(jī)，只要有一臺(tái)的多余的打印機(jī)

能被申請(qǐng)到，則系統(tǒng)就沒(méi)有死鎖的危險(xiǎn)。即N*2+l<=8,得N<=3。

5.11考慮圖5.9所示的資源分配圖，哪個(gè)進(jìn)程會(huì)發(fā)生死鎖？

進(jìn)程P3,P4會(huì)發(fā)生死鎖。

對(duì)于進(jìn)程Pl,P2,進(jìn)程的推進(jìn)不需要等待其他進(jìn)程的完成。

進(jìn)程P3,P4。P3要等P4完成并釋放資源后方能推進(jìn)。而P4要等到P3完成后才能。結(jié)

果是P3,P4都不能完成。形成死鎖。

5.12假定有3個(gè)人排隊(duì)等候上電梯。當(dāng)電梯門打開(kāi)的時(shí)候，3個(gè)人都朝門口沖去，但是

門不夠大，他們3人不能同時(shí)進(jìn)門。描述解決這種死鎖的方法，可以讓3個(gè)人都上電梯。

說(shuō)明你的解決方案清除了哪個(gè)死鎖的必要條件。答：讓3個(gè)人輪流進(jìn)電梯。

破壞了死鎖發(fā)生的4個(gè)必要條件中的“不剝奪條件”。

5.13假定一個(gè)系統(tǒng)具有四種資源類型，分別為：R={3,7,2,3},最大資源需求數(shù)表

如圖5.10所示。資源分配器根據(jù)圖5.11中的表來(lái)分配資源，這個(gè)狀態(tài)安全嗎？為什么？

圖5.10圖5.11

答：這個(gè)狀態(tài)安全。存在安全執(zhí)行序列｛P4,PO,P1,P3,P2｝；

6.9如果一個(gè)分頁(yè)系統(tǒng)能夠向用戶提供的邏輯地址最大為16頁(yè)，頁(yè)面大小為2K,內(nèi)存

總共有8個(gè)存儲(chǔ)塊。請(qǐng)問(wèn)邏輯地址應(yīng)該為多少位？?jī)?nèi)存空間為多大？

解：邏輯地址應(yīng)該為4+11=15(位)

內(nèi)存空間為8*2K=16K

6.10如果一個(gè)分頁(yè)系統(tǒng)的頁(yè)表存放在內(nèi)存。

(1)若對(duì)內(nèi)存的一次存取需要L2s,請(qǐng)問(wèn)一次頁(yè)面訪問(wèn)的存取需要花多少時(shí)間？

(2)若系統(tǒng)配置了聯(lián)想寄存器，對(duì)快表的命中率為70%,假如查詢聯(lián)想寄存器的時(shí)間

忽略不計(jì)，請(qǐng)問(wèn)實(shí)現(xiàn)一次頁(yè)面訪問(wèn)的存取時(shí)間是多少？

解：(1)訪問(wèn)一次頁(yè)面的存取需要花費(fèi)的時(shí)間為2*1.2s=2.4s

(2)實(shí)現(xiàn)一-次頁(yè)面訪問(wèn)的存取時(shí)間=0.3*1.2s+1.2s=L56s

6.11如果一個(gè)分頁(yè)系統(tǒng)邏輯地址長(zhǎng)度為16位，頁(yè)面大小為4KB,第0、1、2頁(yè)對(duì)應(yīng)

10、12、14號(hào)物理塊，請(qǐng)問(wèn)邏輯地址為2F6AH對(duì)應(yīng)的物理地址為多少？解：邏輯地址為

2F6AH對(duì)應(yīng)的二進(jìn)制碼為：0010111101101010,頁(yè)號(hào)為：2,頁(yè)內(nèi)偏移為F6AH。

查詢頁(yè)表2號(hào)頁(yè)面對(duì)應(yīng)14號(hào)塊，所以，物理地址為1110111101101010,最終物理

地址為:EF6AH

6.12如果內(nèi)存中有4個(gè)空閑塊，每個(gè)空閑塊的大小為10MB。有10個(gè)請(qǐng)求，每次請(qǐng)求

1MB的內(nèi)存大小，對(duì)于下面列出的內(nèi)存分配方法中的每一種，確定所有10個(gè)請(qǐng)求都被滿足

之后剩余空閑塊的大小。

(a)首次適應(yīng)算法

(b)循環(huán)首次適應(yīng)算法

(c)最佳適應(yīng)算法

(d)最壞適應(yīng)算法

解：(a)首次適應(yīng)算法：塊1用完，塊2,3,4剩余10MB。

(b)循環(huán)首次適應(yīng)算法：塊1,2余7MB,塊3.4余8MB。

(c)最佳適應(yīng)算法：塊1用完，塊2,3,4余10MB。

進(jìn)程RiR2思

P。3411

P.2512

p23223

P33113

P40312

進(jìn)程K.RiR2R3

P。2100

Pi0201

P20100

P30010

P40101

(d)最壞適應(yīng)算法：塊1,2余7MB,塊3,4余8MB。

段號(hào)始址段長(zhǎng)

0200510

190030

|210080

31200500

4180080

｛0,380｝、｛1,20｝、｛1,24｝、｛2,200｝、｛3,500｝、｛4,120｝。

解：｛0,380｝表示為0段，段內(nèi)偏移為380,物理地址為580；

｛1,20｝表示為1段，段內(nèi)偏移為20,物理地址為920；

｛1,24｝表示為1段，段內(nèi)偏移為24,物理地址為924：

｛2,200｝表示為2段，段內(nèi)偏移為200,已經(jīng)越界；

（3,500｝表示為3段，段內(nèi)偏移為500,物理地址為1700；

｛4,120｝表示為4段，段內(nèi)偏移為120,已經(jīng)越界。

7.5在分頁(yè)虛擬存儲(chǔ)器管理中，如果已知時(shí)間利用率為：CPU20%、分頁(yè)磁盤92樂(lè)外設(shè)

50%,請(qǐng)問(wèn)采取哪些措施可以改善CPU的利用率？解：增大分頁(yè)磁盤空間。

7.6-個(gè)32位地址的計(jì)算機(jī)系統(tǒng)使用二級(jí)頁(yè)表，虛擬地址為9位頂級(jí)頁(yè)表，11位二級(jí)

頁(yè)表和偏移。請(qǐng)問(wèn)：頁(yè)面長(zhǎng)度為多少？虛擬地址空間有多少個(gè)頁(yè)面？

解