操作系統(tǒng)原理答案張麗芬

1、第2章 習題答案2-9. (1) x=3 運行順序為 Px，P3，P5，P6，P9T=(x+(x+3)+(x+3+5)+(x+3+5+6)+(x+3+5+6+9)/5=x+9.6(2) 3x=5 運行順序為 P3，Px，P5，P6，P9T=(3+(3+x)+(3+x+5)+(3+x+5+6)+(3+x+5+6+9)/5=0.8x+10.2(3) 5x=6 T=0.6x+11.2(4) 6x=9 T=0.4x+12.4(5) 9n時，每個進程最多可以請求個該類資源 當m=n時，每個進程最多可以請求1個該類資源 當mn時，每個進程最多可以請求(m+n-1)/n個該類資源）3-15解答：這是進程之間

2、的同步問題。M2、M3和M4必須在接收到M1的消息后才能運行。同理，M6必須在M2和M3之后運行，M7必須在M4，M5之后運行，M8必須在M3、M7之后運行。如何保證呢？需設(shè)置相應的信號量來保證：S12，S13，S14，用來制約M2、M3和M4的運行；S26，S36，用來制約M6的運行；S47，S57，用來制約M7的運行；S38，S78用來制約M8的運行。各進程的制約關(guān)系描述如下。S12,S13,S14,S26,S36,S47,S57,S38,S78:semaphore;S12:=0;S13:=0;S14:=0;S26:=0;S36:=0;S47:=0;S57:=0;S38:=0;S78:=0

3、;COBEGIN PROCESS M1: PROCESS M2: BEGIN BEGIN V(S12); P(S12); V(S13); V(S26); V(S14); END ENDPROCESS M3: PROCESS M4:BEGIN BEGIN P(S13); P(S14); V(S36); V(S47); V(S38); ENDENDPROCESS M5: PROCESS M6:BEGIN BEGIN V(S57); P(S26);END P(S36); ENDPROCESS M7: PROCESS M8BEGIN BEGIN P(S47); P(S38); P(S57); P(S7

4、8); V(S78); ENDENDCOEND3-16. 叉子是臨界資源，在一段時間內(nèi)只允許一個哲學家使用。一個信號量表示一把叉子，五個信號量構(gòu)成信號量數(shù)組，這些信號量的初值為1。int fork0=fork1=fork4=1;第i個哲學家所執(zhí)行的程序：do P(mutex); P(forki); P(fork(i+1)mod5); V(mutex); 吃飯 V(forki); V(fork(i+1)mod5); while(1)；3-17. （1）公平競爭（無寫者時，讀者仍遵循多個讀者可以同時讀）rmutex互斥共享readcount; rwmutex讀寫互斥，寫寫互斥；讀寫進程在z上排隊。

5、int rmutex=1,rwmutex=1,readcount=0;reader:begin p(z); /讀寫進程在z上排隊。 p(rmutex); if(readcount=0) then p(rwmutex); end if +readcount; v(rmutex); v(z); /無寫者時，多個讀者可以同時讀. read data;寫z讀寫寫讀讀讀寫 p(rmutex); -readcount; if(readcount=0 then v(rwmutex); end if; v(rmutex); endwriter:begin p(z); /讀寫進程在z上排隊。 p(rwmutex

6、); write data; v(rwmutex); v(z); end（2）寫者優(yōu)先int readcount,writecount;semaphore rmutex=1,wmutex=1,rwmutex=1,z=1,x=1;reader：/當來了一個寫進程時，通過p(x)禁止其后讀進程讀，直到寫進程寫完為止。 while(1)p(z); /其他讀進程在z上排隊p(x); /一個讀進程與一個寫進程在x上競爭p(rmutex); /讀進程互斥訪問readcount+readcount;if(readcount=1) p(rwmutex); v(rmutex);v(x);rwmutexxz讀讀讀

7、讀寫讀寫寫v(z);read data; /臨界區(qū)p(rmutex);-readcount;if(readcount=0) v(rwmutex);v(rmutex); Writer： while(1)p(wmutex); /寫進程互斥訪問writecount+writecount;if(writecount=1) p(x); /一個寫進程與一個讀進程在x上競爭v(wmutex);p(rwmutex); /其他寫進程在rwmutex上排隊write data; /臨界區(qū)v(rwmutex);p(wmutex);-writecount;if(writecount=0) v(x); /寫進程都寫完時

8、，通過v(x)允許讀進程讀v(wmutex); 附加題：讀者優(yōu)先，規(guī)定僅允許5個進程同時讀，怎樣修改程序？解：增加一個資源信號量s，初值為5。 int s=5;Reader：beginP(rmutex);readcount=readcount+1;if(readcount=1)then P(rwmutex);V(rmutex);P(s);read_file();V(s);P(rmutex);readcount=readcount-1;if(readcount=0)then V(rwmutex);V(rmutex);endwriter:begin p(rwmutex); write data;

9、v(rwmutex); end3-18int s1=0, s2=n;顧客進程：P(s2);V(s1);坐椅子等理發(fā)理發(fā)師進程：P(s1);給顧客理發(fā)V(s2)讀寫管程兩個計數(shù)器rc和wc分別對讀進程和寫進程計數(shù)，用R和W分別表示允許讀和允許寫的條件變量，于是管理該文件的管程可如下設(shè)計：type read-writer = MONITORvar rc, wc : integer;R, W : condition;define start-read, end-read, start-writer, end-writer;use wait, signal, check, release;proced

10、ure start-read;begincheck(IM);if wc0 then wait(R,IM);rc := rc + 1;signal(R, IM);release(IM);end;procedure end-read;begincheck(IM);rc := rc - 1;if rc=0 then signal(W,IM);release(IM);end;procedure start-write;begincheck(IM);wc := wc + 1;if rc0 or wc1 then wait(W,IM);release(IM);end;procedure end-write

11、;begincheck(IM);wc := wc - 1;if wc0 then signal(W,IM);else signal(R, IM);release(IM);end;beginrc := 0; wc := 0; R := 0; W := 0;end.任何一個進程讀（寫）文件前，首先調(diào)用start-read（start-write），執(zhí)行完讀（寫）操作后，調(diào)用end-read（end-write）。即：cobeginprocess readerbegincall read-writer.start-read;read;call read-writer.end-read;end;pro

12、cess writerbegincall read-writer.start-write;write;call rear-writer.end-write;end;coend.上述程序能保證在各種并發(fā)執(zhí)行的情況下，讀寫進程都能正確工作，請讀3-19（2）和（4）會發(fā)生死鎖。3-20P1/剩余P2/剩余P3/剩余系統(tǒng)剩余13/5722/4534（不安全）45/3352（不安全）6(5+3)/00(8)74/348(2+2)/229（1）P1占有5個資源，剩余3個資源請求。P2占有2個資源，剩余4個資源請求。P3占有0個資源，剩余7個資源請求。系統(tǒng)剩余3個資源。（2）P1的請求最先滿足。進程完成序

13、列：P1，P2，P3。3-21（1） 最大需求矩陣： 分配矩陣： 剩余請求矩陣：0 0 0 00 7 5 01 0 0 20 0 2 00 6 4 20 0 1 21 0 0 01 3 5 40 6 3 20 0 1 40 0 1 21 7 5 02 3 5 60 6 5 20 6 5 6Max = Allocation = Need = 剩余資源向量：Available=(1 5 0 2)（2）當前系統(tǒng)是安全的。判斷系統(tǒng)是否安全，只要檢查系統(tǒng)剩余資源向量能否對各進程的剩余請求向量找到一個進程完成序列，當按照這個序列為各進程分配資源時，各進程都能成功完成。若能找到，則系統(tǒng)是安全的，否則，為不安

14、全。先找到p0, 因為p0已滿足最大資源請求，它可以完成，釋放其占有的資源，使系統(tǒng)剩余資源向量為（1 5 1 4）之后，系統(tǒng)剩余資源向量（1 5 1 4），可滿足進程p2, 使p2 可以完成，釋放其占有的資源，使系統(tǒng)剩余資源向量為（2 8 6 8）。之后無論選哪一個進程都可成功完成。故找到的進程完成序列可為：p0,p2,p4,p3,p1; 或 p0,p2,p3,p1,p4 等，故系統(tǒng)是安全的。（3）因系統(tǒng)剩余可用向量為（1502），p2的剩余請求向量為（1002），即（1502）（1002）。故，當p2提出（1001）請求時，能滿足。進程完成序列：p0,p2,p4,p3,p1第4 章 習題答案

15、4-14 內(nèi)存有如下順序排列的空閑塊：10K，40K，20K，18K，7K，9K，12K和15K，有如下的請求序列：12K，10K，9K。（1）若采用首次適應法： (內(nèi)存塊的拆分)l 12K的請求：將分配40K的空閑塊， 40K變?yōu)槭Ｓ嗟模?0-12）K=28K，空閑隊列變?yōu)椋?0K，28K，20K，18K，7K，9K，12K和15K；l 10K的請求：將分配10K的空閑塊，空閑隊列變?yōu)椋?8K，20K，18K，7K，9K，12K和15K；l 9K的請求：將分配28K的空閑塊，空閑隊列變?yōu)椋海?8-9）=18K，20K，18K，7K，9K，12K和15K；（2）若采用最佳適應法：l 12K的請

16、求：將分配12K的空閑塊，空閑隊列變?yōu)椋?0K，40K，20K，18K，7K，9K和15K；l 10K的請求：將分配10K的空閑塊，空閑隊列變?yōu)椋?0K，20K，18K，7K，9K，12K和15K；l 9K的請求：將分配9K的空閑塊，空閑隊列變?yōu)椋?40K，20K，18K，7K， 12K和15K；（3）若采用最壞適應法：l 12K的請求，將分配40K的空閑塊，空閑隊列變?yōu)椋?0K，28K，20K，18K，7K，9K和15K；l 10K的請求：將分配28K的空閑塊，空閑隊列變?yōu)椋?20K，18K，7K，9K，12K和15K；l 9K的請求：將分配20K的空閑塊，空閑隊列變?yōu)椋?0K，18K，11

17、K， 18K，7K， 12K和15K。4-15 有如下圖所示的頁表中的虛地址與物理地址之間的關(guān)系，即該進程分得6個內(nèi)存塊。頁的大小為4096。給出對應下面虛地址的物理地址：(1)20； (2) 5100； (3) 8300； (4) 47000.01234567216043xx解：（1）虛地址 20變?yōu)轫撎? 和頁內(nèi)偏移20 由頁號查頁表得0頁對應內(nèi)存塊號為2 ，可計算得 物理地址=塊號*頁的大小+頁內(nèi)偏移=2*4096+20=8212（2）虛地址 5100變?yōu)轫撎? 和頁內(nèi)偏移1004（5100/4096） 由頁號查頁表得1頁對應內(nèi)存塊號為1 ，可計算得 物理地址=塊號*頁的大小+頁內(nèi)偏移=

18、1*4096+1004=5100（3）虛地址 8300變?yōu)轫撎? 和頁內(nèi)偏移108 由頁號查頁表得2頁對應內(nèi)存塊號為6 ，可計算得 物理地址=塊號*頁的大小+頁內(nèi)偏移=6*4096+108=24684（4）虛地址 47000變?yōu)轫撎?1 和頁內(nèi)偏移1944 117 頁號越界4-16一個作業(yè)在執(zhí)行過程中，按如下順序依次訪問各頁，作業(yè)分得四個主存塊，問分別采用FIFO、LRU和OPT算法時，要產(chǎn)生多少次缺頁中斷?設(shè)進程開始運行時，主存沒有頁面。 頁訪問串順序為：0 1 7 2 3 2 7 1 0 3 2 5 1 7（1）FIFO0 1 7 2 3 2 7 1 0 3 2 5 1 70 1 7 2

19、3 3 3 3 0 0 0 5 1 7 0 1 7 2 2 2 2 3 3 3 0 5 1 0 1 7 7 7 7 2 2 2 3 0 5 0 1 1 1 1 7 7 7 2 3 0 F F F F F S S S F S S F F F 采用FIFO淘汰算法，產(chǎn)生9次缺頁中斷。（2）LRU 0 1 7 2 3 2 7 1 0 3 2 5 1 70 1 7 2 3 2 7 1 0 3 2 5 1 7 0 1 7 2 3 2 7 1 0 3 2 5 1 0 1 7 7 3 2 7 1 0 3 2 5 0 1 1 1 3 2 7 1 0 3 2 F F F F F S S S F F F F F

20、F采用LRU算法時，產(chǎn)生11次缺頁中斷。4-17 考慮如圖所示的段表，給出如下所示的邏輯地址所對應的物理地址。段始址段的長度219600230014921001326580195496（1）0，430 219+430=649（2）1，10 2300+10=2310（3）2，500 500100段內(nèi)地址越界（4）3，400 1326+400=1726（5）4，112 11296 段內(nèi)地址越界4-18 一臺計算機含有65536字節(jié)的存儲空間，這一空間被分成許多長度為4096字節(jié)的頁。有一程序，其代碼段為32768字節(jié)，數(shù)據(jù)段為16386字節(jié)，棧段為15870字節(jié)。試問該機器的主存空間適合這個作業(yè)嗎

21、?如果每頁改成512字節(jié)，適合嗎?答：（1）存儲空間每塊為4096個字節(jié)，共可分成16塊。程序代碼段占32768/4096=8塊，數(shù)據(jù)段占16386/4096=5塊，棧段占15870/4096=4塊，合計為8+5+4=17塊，故該機器的主存空間不適合這個作業(yè)。（2） 當存儲空間每塊為512個字節(jié)，共可分成128塊。程序代碼段占32768/512=64塊，數(shù)據(jù)段占16386/512=33塊，棧段占15870/512=31塊，合計為64+33+31=128塊，故該機器的主存空間是適合這個作業(yè)的。4-19 邏輯地址中，用9位表示頁號，用10位表示頁內(nèi)地址。4-20 （1）缺頁中斷50次； 5000次

22、（2）缺頁中斷100次； 10000次4-21 0.9(0.751+0.258)+0.10(8+5000+8)+84-23 8192/4=204864=7+11+11+11+11+13 5級頁表第5章 文件系統(tǒng)5-9. 文件存貯空間管理可采用成組自由塊鏈表或位示圖。若一磁盤有B個盤塊，其中有F個自由塊。若盤塊號用D位表示。試給出使用自由塊鏈表比使用位示圖占用更少的空間的條件。當D為16時，給出滿足條件的自由空間占整個空間的百分比。解：一磁盤有B個盤塊，用位圖表示要使用B位 現(xiàn)有F個自由塊，若表示一個盤塊需用D位。則采用鏈表接連F個盤塊，需要F個鏈指針，共占F*D位。使用自由塊鏈表比使用位示圖占

23、用更少的空間的條件是F*DB。當D=16時，滿足條件的自由空間占整個空間的百分比為F/B1/16=6.25%。5-10. 文件系統(tǒng)的執(zhí)行速度依賴于緩沖池中找到盤塊的比率。假設(shè)盤塊從緩沖池讀出用1毫秒，從盤上讀出用40毫秒。從緩沖池找到盤塊的比率為n，請給出一個公式計算讀盤塊的平均時間，并畫出n從0到1.0的函數(shù)圖像。 解：讀一個盤塊的平均時間=n+40(1-n)=40-39n40 10 1n5-13. 1574/256=638， 因此，要訪問文件的第7個記錄內(nèi)的38B處。每個塊放兩個記錄，所要訪問的字節(jié)處在第4個邏輯塊內(nèi)，其對應的物理塊號為4，應訪問4號塊內(nèi)的第38個字節(jié)。要訪問4次磁盤才能將

24、該字節(jié)的內(nèi)容讀出。5-14共需要4次磁盤操作5-151GB=230 ，16KB=214 ， 230/214 =216 ，每個磁盤塊號需要2個字節(jié)表示，即2B。 （1）10KB16KB, 所以，只占用1個磁盤塊。（2）1089KB/16KB=69 需一個索引塊和69個數(shù)據(jù)塊，共70個盤塊。（3）129MB/16KB=8256 ， 16KB/2B=8K（個索引項）8256 所以，需2個一級索引表和一個1個二級索引表，8256個數(shù)據(jù)塊。 共需8259個磁盤塊。第6章 設(shè)備管理6-6下列工作各是在四層I/O軟件的哪一層上實現(xiàn)的? (1) 對于讀磁盤，計算柱面、磁頭和扇區(qū)（設(shè)備驅(qū)動） (2) 維持最近所用塊而設(shè)的高速緩沖（獨立于設(shè)備的軟件層） (3) 向設(shè)備寄存器寫命令（設(shè)備驅(qū)動） (4)