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

1、 練習(xí)11.1-1.10題解見書1.11 有一臺(tái)輸入設(shè)備和一臺(tái)輸出設(shè)備的計(jì)算機(jī)系統(tǒng)上，運(yùn)行有兩道程序。兩道程序投入運(yùn)行情況如下： 程序1先開始運(yùn)行，其運(yùn)行軌跡為：計(jì)算50ms、輸出100ms、計(jì)算50ms、輸出100ms，結(jié)束； 程序2后開始運(yùn)行，其運(yùn)行軌跡為：計(jì)算50ms、輸入100ms、計(jì)算100ms、結(jié)束。 1. 忽略調(diào)度時(shí)間，指出兩道程序運(yùn)行時(shí)，CPU是否有空閑？在哪部分空閑？指出程序1和程序 2. 有無等待CPU的情況？如果有，發(fā)生在哪部分？題解:由題畫出CPU利用圖如下： 由圖可知，1.CPU有空閑，在100ms150ms時(shí)間段是空閑的。 2.程序1無等待時(shí)間，而程序2在一開始的0

2、ms50ms時(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í)間，畫出三道程序運(yùn)行的時(shí)間關(guān)系圖；完成三道程序共花多少時(shí)間？與單道程序比較，節(jié)省了多少時(shí)間？解答：三道程序運(yùn)行，完成三道程序共花170ms。與單道程序（260ms）比較，節(jié)省了90ms。（始終按照1-2-3的次序，即程序1程序2程序3程序1程序2（在程序3運(yùn)行前會(huì)停10ms等待輸入完成）程序3。（如果不是

3、按照程序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利用圖如下：由圖可知，在總共80ms的時(shí)間里，CPU空閑時(shí)間為40ms，即： CPU利用率=40ms/80ms*100%=50%1.14 一個(gè)計(jì)算機(jī)系統(tǒng)有足夠的內(nèi)存空間存放3道程序，這些程序有一半的時(shí)間在空閑等待I/O操作。問多

4、大比例的CPU時(shí)間被浪費(fèi)掉了。題解：由題畫圖如下：因?yàn)槊總€(gè)程序有一半的時(shí)間在等待I/O操作，所以在并發(fā)狀態(tài)下，程序1、程序2、程序3所占時(shí)間比依次減半（如上圖），所以浪費(fèi)的時(shí)間比例為1/8。 練習(xí)2218 某系統(tǒng)中進(jìn)程狀態(tài)變化如圖2.22所示，當(dāng)對系統(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)就

5、緒隊(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）不可能，可能。219分別寫出相應(yīng)的程序來描述圖2.23中的前趨圖。解答S1S2S3S4S5S6S7程序：S1:a:=x+1 S2:b:=a+2 S3:c:=a+3 S4:d:=b+4 S5:e:=b+c S6:f:=e+5 S7:g=e+6 S1S2S3S4S5S6S7程序：S1:a:=x+1 S2:b:=a+2 S3:c:=a+3 S4:d:=b+4 S5:e:=b+c S6:f:=

6、d+e S7:g:=c+e2.20 假設(shè)在一個(gè)系統(tǒng)中，新進(jìn)程以每分鐘8個(gè)進(jìn)程的速率到達(dá)，每個(gè)進(jìn)程請求服務(wù)的平均時(shí)間為6s，估計(jì)在一個(gè)單處理器系統(tǒng)中CPU忙的時(shí)間比率。 如果新進(jìn)程以每分鐘10個(gè)進(jìn)程的速率到達(dá)，每個(gè)進(jìn)程請求服務(wù)的平均時(shí)間也為6s，估計(jì)在一個(gè)單處理器系統(tǒng)中CPU忙的時(shí)間比率。 如果新進(jìn)程創(chuàng)建以每分鐘超過10個(gè)進(jìn)程的速率到達(dá)，每個(gè)進(jìn)程請求服務(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=1

7、2s。CPU的利用率為48/60=0.8，即80%。 因?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í)間為0s。CPU的利用率為100%。 如果新進(jìn)程創(chuàng)建以每分鐘超過10個(gè)進(jìn)程的速率到達(dá)，每個(gè)進(jìn)程請求服務(wù)的平均時(shí)間為6s，則請求服務(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)過40s后再次運(yùn)行；進(jìn)程P2要求25s后運(yùn)行；進(jìn)程P3要求35s后運(yùn)行，經(jīng)過35s后再次運(yùn)行；進(jìn)程P4要求60s后運(yùn)行。進(jìn)程在阻塞隊(duì)列等待被

8、喚醒后運(yùn)行，試創(chuàng)建進(jìn)程的喚醒隊(duì)列。解答：進(jìn)程的喚醒隊(duì)列為P1P2P3P4P1P3注意：“經(jīng)過40s后再次運(yùn)行”表示第1次運(yùn)行完成后再過40s。2.22 如果線程是在用戶空間線程庫中實(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í)線程庫實(shí)現(xiàn)。當(dāng)一個(gè)應(yīng)用程序提交給操作系統(tǒng)后，操作系統(tǒng)首先為該應(yīng)用程序建立一個(gè)內(nèi)核管理進(jìn)程，然后用戶級(jí)線程庫為該進(jìn)程創(chuàng)建一個(gè)或多個(gè)用戶級(jí)線程，但內(nèi)核并不知道用戶空間線程的活動(dòng)，內(nèi)核只是以進(jìn)程為單位，實(shí)現(xiàn)進(jìn)程狀態(tài)的轉(zhuǎn)換，因

9、此當(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)場信息，內(nèi)核的調(diào)度是在線程的基礎(chǔ)上進(jìn)行的，因而進(jìn)程的一個(gè)線程阻塞不會(huì)引起進(jìn)程內(nèi)的其他線程被阻塞。練習(xí)33.13 證明作業(yè)調(diào)度算法中短作業(yè)優(yōu)先調(diào)度算法具有最小平均等待時(shí)間。證明:假設(shè)在作業(yè)隊(duì)列中等待運(yùn)行的作業(yè)有N道,分別為N0，N1，N2，Nn-1，它們的運(yùn)行時(shí)間分別為t0，t1，tn-1，且滿足t0<t1<<tn-1。 由于短作業(yè)有限調(diào)度算法總是選擇最短的作業(yè)先調(diào)度，故這些作業(yè)總的等待時(shí)間為:T1=0 + t0

10、+ （t0 + t1）+（t0 + t1 + t2 ） + + （t0 + t1 + t2 + + tn-2）=( N - 1) t0 + ( N - 2) t1 + ( N - 3) t2 + + tn-2 (1)如果不按照短作業(yè)優(yōu)先調(diào)度算法，可設(shè)調(diào)度順序?yàn)椋篘1，N0，N2，Nn-1，故這些作業(yè)總的等待時(shí)間為:T2= 0 + t1 +（t0 + t1）+（t0 + t1 + t2 ） + + （t0 + t1 + t2 + + tn-2）=( N - 2) t0 + ( N - 1) t1 + ( N - 3) t2 + + tn-2 (2)（2）-（1）得：T2 T1 = t1 t0 &

11、gt;0說明任何一種作業(yè)調(diào)度順序的作業(yè)的平均等待時(shí)間都大于按照短作業(yè)優(yōu)先的作業(yè)的平均等待時(shí)間。3.14 假設(shè)在一個(gè)處理器上執(zhí)行5個(gè)作業(yè)，作業(yè)到達(dá)的次序和需要執(zhí)行的時(shí)間分別為：J0（75ms）、J1（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）J0750J19075J29590J311095J4155110平均等待時(shí)間（ms）743.15在單道批處理系統(tǒng)中，三個(gè)作業(yè)的提交時(shí)間分別為：10：00、10：10、10：20，需要執(zhí)行時(shí)間分別為：2小時(shí)、1小時(shí)、0.

12、5小時(shí)，分別按照短作業(yè)優(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(11: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)锳

13、，C，B平均周轉(zhuǎn)時(shí)間：（120+130+200）/3=150（min）平均帶勸周轉(zhuǎn)時(shí)間：（120/120+130/30+200/60）/3 =26/9 所以，如果要比較哪一種算法好自然針對不搶占的情況。根據(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í)間A050013510220103255544095作業(yè)1的周轉(zhuǎn)時(shí)間是多少？作業(yè)的平均等待時(shí)間是多少？答：1。執(zhí)行順序?yàn)椋?（10），2（30），1（65），3（9

14、0），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í)間為：10-10=0，作業(yè)3的等待時(shí)間為：，35-25=10作業(yè)4的等待時(shí)間為：，65-40=253.17假如在具有一個(gè)處理器系統(tǒng)中，采用優(yōu)先級(jí)高者優(yōu)先的進(jìn)程調(diào)度算法，優(yōu)先數(shù)小代表優(yōu)先級(jí)高，進(jìn)程達(dá)到順序I和需要處理時(shí)間T、優(yōu)先數(shù)分別如下：IT優(yōu)先級(jí)0753115125431554452（1）沒有優(yōu)先級(jí)搶占情況下，寫出

15、進(jìn)程的執(zhí)行先后序列，進(jìn)程2的周轉(zhuǎn)時(shí)間是多少？進(jìn)程的平均等待時(shí)間是多少？（3）有優(yōu)先級(jí)搶占情況下，寫出進(jìn)程的執(zhí)行先后序列，進(jìn)程2的周轉(zhuǎn)時(shí)間是多少？進(jìn)程的平均等待時(shí)間是多少？答：（1）無搶占：執(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)度算

16、法，時(shí)間片大小為10。進(jìn)程需要處理時(shí)間T和到達(dá)時(shí)間A分別如下：IT到達(dá)時(shí)間A050013510220103158044085寫出進(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í)間 T1= 105進(jìn)程2的周轉(zhuǎn)時(shí)間 T1= 50進(jìn)程3的周轉(zhuǎn)時(shí)間 T1= 40進(jìn)程4的周轉(zhuǎn)時(shí)間 T1= 75 進(jìn)程的平均等待時(shí)間為：（140-50）+（105-35）+（50-20）+（40-15）+（75-40）/5=503.18 在時(shí)間片輪轉(zhuǎn)調(diào)度算法中，有 n個(gè)進(jìn)程共享C

17、PU。（1）如果進(jìn)程切換的時(shí)間不可忽略，每次進(jìn)程切換用去時(shí)間為s秒，在保證每個(gè)進(jìn)程至少每t秒內(nèi)能夠在CPU上輪回一次的前提下，確定時(shí)間片大小q使得進(jìn)程切換所造成的負(fù)載最小。 (2) 如果n=100，t=1，s=0.001，那么q的大小應(yīng)該是多少？答：（1）時(shí)間片大小q =（t-ns）/n （2）q=（1-100*0.001）/100 = 0.0093.19 有一個(gè)四道作業(yè)的操作系統(tǒng)，若在一段時(shí)間內(nèi)先后到達(dá)6個(gè)作業(yè)，它們的提交時(shí)間和估計(jì)運(yùn)行時(shí)間由下表給出： 作業(yè) 提交時(shí)間 估計(jì)運(yùn)行時(shí)間（分鐘） 1 8：00 60 2 8：20 353 8：25 204 8：30 255 8：35 56 8：40

18、 10系統(tǒng)采用短作業(yè)優(yōu)先調(diào)度算法，作業(yè)被調(diào)度進(jìn)入系統(tǒng)后中途不得退出。但作業(yè)運(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í)間 = 155 min作業(yè)2的周轉(zhuǎn)時(shí)間 = 95 min作業(yè)3的周轉(zhuǎn)時(shí)間 = 20 min作業(yè)4的周轉(zhuǎn)時(shí)間 = 55 min作業(yè)5的周轉(zhuǎn)時(shí)間 = 15 min作業(yè)6的周轉(zhuǎn)時(shí)間 = 20 min作業(yè)的平均周轉(zhuǎn)時(shí)間為：360/6=603.20 在一個(gè)實(shí)時(shí)系統(tǒng)中有4個(gè)周期性事件

19、，周期分別為50、100、150、200ms。假設(shè)其處理時(shí)間分別需要30、25、20和xms，則該系統(tǒng)可調(diào)度允許的x值最大為多少？解:30/50 + 25/100 +150/20 +200/x =1X = 10/33.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ùn)行低優(yōu)先級(jí)就緒首先選擇100ms高優(yōu)先級(jí)就緒其次選擇100msy答：首先采用優(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ì)列，這樣能夠保

20、證優(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）。 問采用的信號(hào)量初值是否相同？信號(hào)量值的變化范圍如何？答：所采用互斥信號(hào)量的初值不同。（1）互斥信號(hào)量初值為1，變化范圍為-n+1，1。當(dāng)沒有進(jìn)程進(jìn)入互斥段時(shí)，信號(hào)量值為1；當(dāng)有1個(gè)進(jìn)程進(jìn)入互斥段時(shí)，但沒有進(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）互斥信

21、號(hào)量初值為m，變化范圍為m-n，m。當(dāng)沒有進(jìn)程進(jìn)入互斥段時(shí)，信號(hào)量值為m；當(dāng)有1個(gè)進(jìn)程進(jìn)入互斥段時(shí)，但沒有進(jìn)程等待進(jìn)入互斥段時(shí)，信號(hào)量值為m-1；當(dāng)有m個(gè)進(jìn)程進(jìn)入互斥段，但沒有進(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)量值為-1；最多可有n-m個(gè)進(jìn)程等待進(jìn)入互斥段，故此時(shí)信號(hào)量的值為-（n-m）。4.14 在兩條雙向道路的交叉路口，沒有行人通過，只有汽車通過。交通情況如 下： （1）任何給定的時(shí)刻只能有一輛車過馬路； （2）當(dāng)一輛車到達(dá)交叉路口并且另一條街道上沒有車來到的時(shí)候，應(yīng)該允許此車通過； （3）當(dāng)兩個(gè)方向上都有車到達(dá)的時(shí)候，它們應(yīng)該輪流

22、通過，以防止在其中一個(gè)方向上的無限期延遲。 用信號(hào)量操作實(shí)現(xiàn)道路交通問題。解： semphore S1=0,S2=0;/有無車到達(dá)，為0時(shí)無到達(dá) semphore M1=1,M2=0;/路中被占 P1:if(車到達(dá)) v(S1); while(!S1); if(!S2) 過一輛車； else p(M2); p(M1); 過一輛車； v(M1); P2: if(車到達(dá)) v(S2); while(!S2); if(!S1) 過一輛車； else p(M1); p(S2); 過一輛車； v(M2); 4.15 在哲學(xué)家進(jìn)餐問題中，假設(shè)5個(gè)哲學(xué)家中第i個(gè)執(zhí)行下面的代碼段 p(mutex); p(fo

23、rki); p(forki+1%5); v(mutex); eat; v(forki); v(forki+1%5);（1）說明這段代碼是否滿足哲學(xué)家進(jìn)餐問題的所有需求。（2）如果V(mutex)語句改在第二個(gè)V()操作之后，或者在兩個(gè)P()操作之間，說明這兩種解決方法是改進(jìn)了算法還是變壞了算法。答：(a) 滿足(b) 都不行4.16 有兩個(gè)優(yōu)先級(jí)相同的進(jìn)程P1和P2，各自執(zhí)行的操作如下，信 號(hào)量S1和S2的初值都為0，試問P1、P2并發(fā)執(zhí)行后，x、y、z 的值各為多少？ P1： P2： begin begin y: = 1; （1） x: = 1; （5） y: = y + 3; （2） x:

24、 = 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;答：語句（1）（2）（5）（6）不相交，任何執(zhí)行順序，結(jié)果相同。 情況1：語句（4）先執(zhí)行x=10，y=9，z=15；情況2：語句（8）先執(zhí)行x=10，y=19，z=15；情況3：語句（3）推遲到語句（8）之后，x不定，y=4，z不定； ?4.17 兩個(gè)進(jìn)程A、B，考慮下面的信號(hào)量編碼 semaphore s = 1; int x=10,y=2; fork(

25、A，0); fork(B，0); A( ) B( ) （1） x+; （4） if (x>10) （2） V(s); （5） x;（3） y=x2; （6） else P(s); x ; 分別說明（1）、（2）、（3）、（4）、（5）、（6）語句之后的x、y值為多少？答：（1）x=11,y=2 (2) x=11,y=2 (3) x=11,y=9(4)x=11,y=9 (5) x=10,y=9 (6) x=10,y=84.18 三個(gè)進(jìn)程：輸入、計(jì)算、輸出。它們通過兩個(gè)緩沖區(qū)傳遞數(shù)據(jù)，如圖4.11所示。每個(gè)緩沖區(qū)一次只能放入一條數(shù)據(jù)。寫出用信號(hào)量進(jìn)行同步。解：var empty1,full1

26、,empty2,full2:semaphore:=1,0,1,0;begin parbeginI:begin repeat wait(empty1); put to buffer1; signal(full1); until false; end;P:begin repeat wait(full1); get from buffer1; signal(empty1); wait(empty2); put to buffer2; signal(full2); until false; end;O:begin repeat wait(full2) get from buffer2; signal(

27、empty2); until false; end;parend;end;第5章5.1什么是死鎖？引起死鎖的原因和必要條件是什么？ 死鎖是指多個(gè)進(jìn)程因?yàn)楦偁庂Y源造成的一種僵局。 原因：并發(fā)進(jìn)程對臨界資源的競爭和并發(fā)進(jìn)程推進(jìn)順序不當(dāng)。 必要條件：互斥條件，占有并請求條件，不剝奪條件，環(huán)路等待條件。5.2 比較解決死鎖的方法中，那種方法最容易實(shí)現(xiàn)？那種方法使得資源的利用率最高？ 解決死鎖的方法：預(yù)防死鎖，避免死鎖，檢測死鎖，解除死鎖。 預(yù)防死鎖是通過設(shè)計(jì)協(xié)同資源管理程序，在進(jìn)程運(yùn)行期間，柏懷死鎖產(chǎn)生的四個(gè)條件之中的任何一個(gè)，是指不成立。 是最容易實(shí)現(xiàn)的方法。 解除死鎖是在發(fā)現(xiàn)死鎖后，解除死鎖，釋放

28、資源。是資源利用率最高的方法。5.3預(yù)防死鎖的方法有哪些？ 破壞互斥條件，破壞占有并請求，阻止環(huán)路等待，允許剝奪5.8系統(tǒng)中有3個(gè)進(jìn)程共享4個(gè)資源，每個(gè)進(jìn)程每次只能申請或釋放一個(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)程的請求會(huì)滿足，運(yùn)行并釋放資源。不會(huì)形成環(huán)路等待。5.9系統(tǒng)中有20個(gè)進(jìn)程，每個(gè)進(jìn)程最多使用3個(gè)資源，每個(gè)進(jìn)程逐個(gè)申請并競爭使用60個(gè)同類資源。一旦某進(jìn)程獲得所需要的資源，完成后立即釋放全部資源。系統(tǒng)是否會(huì)發(fā)生死鎖？為什么？ 系統(tǒng)不會(huì)發(fā)生死鎖。以最壞的情況來考慮，20個(gè)進(jìn)程都需要

29、使用3個(gè)資源。當(dāng)前，每個(gè)進(jìn)程都持有2個(gè)資源。（20*2=40）.都在申請第3個(gè)資源（60-40=20）對于剩余的20個(gè)資源，每個(gè)進(jìn)程多會(huì)得到一個(gè)資源。不會(huì)形成環(huán)路等待。5.10 一臺(tái)計(jì)算機(jī)有8臺(tái)打印機(jī)，被N個(gè)進(jìn)程競爭使用，每個(gè)進(jìn)程最多需 要3臺(tái)。 請問N為多少時(shí)，系統(tǒng)沒有死鎖的危險(xiǎn)，說明原因。 解: N=3時(shí)，沒有死鎖的危險(xiǎn)。 對于N個(gè)進(jìn)程，都持有2臺(tái)打印機(jī)時(shí)，申請第3臺(tái)打印機(jī)，只要有一臺(tái)的多余的打印機(jī)能被申請到，則系統(tǒng)就沒有死鎖的危險(xiǎn)。即N*2+1<=8 ，得 N<=3。5.11 考慮圖5.9所示的資源分配圖，哪個(gè)進(jìn)程會(huì)發(fā)生死鎖？進(jìn)程P3,P4會(huì)發(fā)生死鎖。 對于進(jìn)程P1,P2，進(jìn)

30、程的推進(jìn)不需要等待其他進(jìn)程的完成。進(jìn)程P3,P4。P3要等P4完成并釋放資源后方能推進(jìn)。而P4要等到P3完成后才能。結(jié)果是P3,P4都不能完成。形成死鎖。5.12 假定有3個(gè)人排隊(duì)等候上電梯。當(dāng)電梯門打開的時(shí)候，3個(gè)人都朝門口沖去，但是門不夠大，他們3人不能同時(shí)進(jìn)門。描述解決這種死鎖的方法，可以讓3個(gè)人都上電梯。說明你的解決方案清除了哪個(gè)死鎖的必要條件。答：讓3個(gè)人輪流進(jìn)電梯。 破壞了死鎖發(fā)生的4個(gè)必要條件中的“不剝奪條件”。5.13 假定一個(gè)系統(tǒng)具有四種資源類型，分別為：R=3，7，2，3，最大資源需求數(shù)表如圖5.10所示。資源分配器根據(jù)圖5.11中的表來分配資源，這個(gè)狀態(tài)安全嗎？為什么？圖

31、5.10圖5.11 答：這個(gè)狀態(tài)安全。存在安全執(zhí)行序列P4,P0,P1,P3,P2；6.9 如果一個(gè)分頁系統(tǒng)能夠向用戶提供的邏輯地址最大為16頁，頁面大 小為2K，內(nèi)存總共有8個(gè)存儲(chǔ)塊。請問邏輯地址應(yīng)該為多少位？內(nèi) 存空間為多大？解：邏輯地址應(yīng)該為4+11=15（位） 內(nèi)存空間為8*2K =16K6.10 如果一個(gè)分頁系統(tǒng)的頁表存放在內(nèi)存。 （1）若對內(nèi)存的一次存取需要1.2ms，請問一次頁面訪問的存取需 要花多少時(shí)間？ （2）若系統(tǒng)配置了聯(lián)想寄存器，對快表的命中率為70%，假如查詢 聯(lián)想寄存器的時(shí)間忽略不計(jì)，請問實(shí)現(xiàn)一次頁面訪問的存取 時(shí)間是多少？解：（1）訪問一次頁面的存取需要花費(fèi)的時(shí)間為

32、2*1.2ms=2.4ms （2）實(shí)現(xiàn)一次頁面訪問的存取時(shí)間=0.3*1.2ms+1.2ms=1.56ms6.11 如果一個(gè)分頁系統(tǒng)邏輯地址長度為16位，頁面大小為4KB，第0、1、2頁對應(yīng)10、12、14號(hào)物理塊， 請問邏輯地址為2F6AH對應(yīng)的物理地址為多少？解：邏輯地址為2F6AH對應(yīng)的二進(jìn)制碼為：0010 1111 0110 1010，頁號(hào)為：2，頁內(nèi)偏移為F6AH。 查詢頁表2號(hào)頁面對應(yīng)14號(hào)塊，所以，物理地址為 1110 1111 0110 1010，最終物理地址為：EF6AH6.12 如果內(nèi)存中有4個(gè)空閑塊，每個(gè)空閑塊的大小為10MB。有10個(gè)請求，每次請求1MB的內(nèi)存大小，對于

33、下面列出的內(nèi)存分配方法中的每一種，確定所有10個(gè)請求都被滿足之后剩余空閑塊的大小。 （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。 （d）最壞適應(yīng)算法：塊1，2余7MB，塊3，4余8MB。6.13 如果一個(gè)系統(tǒng)的段表為：段 號(hào)始 址段 長0200510190030210080312005004180080求下列邏輯地址相應(yīng)的物理地址。如果越界請指明。0,380、1,20、1,24、2

34、,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 在分頁虛擬存儲(chǔ)器管理中，如果已知時(shí)間利用率為：CPU20%、分頁 磁盤92%、外設(shè)50%，請問采取哪些措施可以改善CPU的利用率？解：增大分頁磁盤空間。7.6 一個(gè)32位地址的計(jì)算機(jī)系統(tǒng)使用二級(jí)頁表，虛擬地址為9位頂級(jí)頁 表，11位二級(jí)頁表和偏移。請問：頁面長度為多少？虛擬地址空間 有多少個(gè)頁面？解：頁面占用的位數(shù)=32-9-11=12位，頁面長度為4K。虛擬地址空間有1M個(gè)頁面。7.7