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

1、第2章 習(xí)題答案2-9. (1) x=3 運(yùn)行順序?yàn)?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 運(yùn)行順序?yàn)?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時(shí)，每個(gè)進(jìn)程最多可以請(qǐng)求個(gè)該類資源 當(dāng)m=n時(shí)，每個(gè)進(jìn)程最多可以請(qǐng)求1個(gè)該類資源 當(dāng)mn時(shí)，每個(gè)進(jìn)程最多可以請(qǐng)求(m+n-1)/n個(gè)該類資源）3-15解答：這是進(jìn)程之間

2、的同步問(wèn)題。M2、M3和M4必須在接收到M1的消息后才能運(yùn)行。同理，M6必須在M2和M3之后運(yùn)行，M7必須在M4，M5之后運(yùn)行，M8必須在M3、M7之后運(yùn)行。如何保證呢？需設(shè)置相應(yīng)的信號(hào)量來(lái)保證：S12，S13，S14，用來(lái)制約M2、M3和M4的運(yùn)行；S26，S36，用來(lái)制約M6的運(yùn)行；S47，S57，用來(lái)制約M7的運(yùn)行；S38，S78用來(lái)制約M8的運(yùn)行。各進(jìn)程的制約關(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. 叉子是臨界資源，在一段時(shí)間內(nèi)只允許一個(gè)哲學(xué)家使用。一個(gè)信號(hào)量表示一把叉子，五個(gè)信號(hào)量構(gòu)成信號(hào)量數(shù)組，這些信號(hào)量的初值為1。int fork0=fork1=fork4=1;第i個(gè)哲學(xué)家所執(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）公平競(jìng)爭(zhēng)（無(wú)寫者時(shí)，讀者仍遵循多個(gè)讀者可以同時(shí)讀）rmutex互斥共享readcount; rwmutex讀寫互斥，寫寫互斥；讀寫進(jìn)程在z上排隊(duì)。

5、int rmutex=1,rwmutex=1,readcount=0;reader:begin p(z); /讀寫進(jìn)程在z上排隊(duì)。 p(rmutex); if(readcount=0) then p(rwmutex); end if +readcount; v(rmutex); v(z); /無(wú)寫者時(shí)，多個(gè)讀者可以同時(shí)讀. read data;寫z讀寫寫讀讀讀寫 p(rmutex); -readcount; if(readcount=0 then v(rwmutex); end if; v(rmutex); endwriter:begin p(z); /讀寫進(jìn)程在z上排隊(duì)。 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：/當(dāng)來(lái)了一個(gè)寫進(jìn)程時(shí)，通過(guò)p(x)禁止其后讀進(jìn)程讀，直到寫進(jìn)程寫完為止。 while(1)p(z); /其他讀進(jìn)程在z上排隊(duì)p(x); /一個(gè)讀進(jìn)程與一個(gè)寫進(jìn)程在x上競(jìng)爭(zhēng)p(rmutex); /讀進(jìn)程互斥訪問(wèn)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); /寫進(jìn)程互斥訪問(wèn)writecount+writecount;if(writecount=1) p(x); /一個(gè)寫進(jìn)程與一個(gè)讀進(jìn)程在x上競(jìng)爭(zhēng)v(wmutex);p(rwmutex); /其他寫進(jìn)程在rwmutex上排隊(duì)write data; /臨界區(qū)v(rwmutex);p(wmutex);-writecount;if(writecount=0) v(x); /寫進(jìn)程都寫完時(shí)

8、，通過(guò)v(x)允許讀進(jìn)程讀v(wmutex); 附加題：讀者優(yōu)先，規(guī)定僅允許5個(gè)進(jìn)程同時(shí)讀，怎樣修改程序？解：增加一個(gè)資源信號(hào)量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;顧客進(jìn)程：P(s2);V(s1);坐椅子等理發(fā)理發(fā)師進(jìn)程：P(s1);給顧客理發(fā)V(s2)讀寫管程兩個(gè)計(jì)數(shù)器rc和wc分別對(duì)讀進(jìn)程和寫進(jìn)程計(jì)數(shù)，用R和W分別表示允許讀和允許寫的條件變量，于是管理該文件的管程可如下設(shè)計(jì)：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.任何一個(gè)進(jìn)程讀（寫）文件前，首先調(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í)行的情況下，讀寫進(jìn)程都能正確工作，請(qǐng)讀3-19（2）和（4）會(huì)發(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個(gè)資源，剩余3個(gè)資源請(qǐng)求。P2占有2個(gè)資源，剩余4個(gè)資源請(qǐng)求。P3占有0個(gè)資源，剩余7個(gè)資源請(qǐng)求。系統(tǒng)剩余3個(gè)資源。（2）P1的請(qǐng)求最先滿足。進(jìn)程完成序

13、列：P1，P2，P3。3-21（1） 最大需求矩陣： 分配矩陣： 剩余請(qǐng)求矩陣：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）當(dāng)前系統(tǒng)是安全的。判斷系統(tǒng)是否安全，只要檢查系統(tǒng)剩余資源向量能否對(duì)各進(jìn)程的剩余請(qǐng)求向量找到一個(gè)進(jìn)程完成序列，當(dāng)按照這個(gè)序列為各進(jìn)程分配資源時(shí)，各進(jìn)程都能成功完成。若能找到，則系統(tǒng)是安全的，否則，為不安

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

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

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

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

18、1*4096+1004=5100（3）虛地址 8300變?yōu)轫?yè)號(hào)2 和頁(yè)內(nèi)偏移108 由頁(yè)號(hào)查頁(yè)表得2頁(yè)對(duì)應(yīng)內(nèi)存塊號(hào)為6 ，可計(jì)算得 物理地址=塊號(hào)*頁(yè)的大小+頁(yè)內(nèi)偏移=6*4096+108=24684（4）虛地址 47000變?yōu)轫?yè)號(hào)11 和頁(yè)內(nèi)偏移1944 117 頁(yè)號(hào)越界4-16一個(gè)作業(yè)在執(zhí)行過(guò)程中，按如下順序依次訪問(wèn)各頁(yè)，作業(yè)分得四個(gè)主存塊，問(wèn)分別采用FIFO、LRU和OPT算法時(shí)，要產(chǎn)生多少次缺頁(yè)中斷?設(shè)進(jìn)程開(kāi)始運(yùn)行時(shí)，主存沒(méi)有頁(yè)面。 頁(yè)訪問(wèn)串順序?yàn)椋? 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次缺頁(yè)中斷。（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算法時(shí)，產(chǎn)生11次缺頁(yè)中斷。4-17 考慮如圖所示的段表，給出如下所示的邏輯地址所對(duì)應(yīng)的物理地址。段始址段的長(zhǎng)度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 一臺(tái)計(jì)算機(jī)含有65536字節(jié)的存儲(chǔ)空間，這一空間被分成許多長(zhǎng)度為4096字節(jié)的頁(yè)。有一程序，其代碼段為32768字節(jié)，數(shù)據(jù)段為16386字節(jié)，棧段為15870字節(jié)。試問(wèn)該機(jī)器的主存空間適合這個(gè)作業(yè)嗎

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

22、（2）缺頁(yè)中斷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級(jí)頁(yè)表第5章 文件系統(tǒng)5-9. 文件存貯空間管理可采用成組自由塊鏈表或位示圖。若一磁盤有B個(gè)盤塊，其中有F個(gè)自由塊。若盤塊號(hào)用D位表示。試給出使用自由塊鏈表比使用位示圖占用更少的空間的條件。當(dāng)D為16時(shí)，給出滿足條件的自由空間占整個(gè)空間的百分比。解：一磁盤有B個(gè)盤塊，用位圖表示要使用B位 現(xiàn)有F個(gè)自由塊，若表示一個(gè)盤塊需用D位。則采用鏈表接連F個(gè)盤塊，需要F個(gè)鏈指針，共占F*D位。使用自由塊鏈表比使用位示圖占

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

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