第二章習(xí)題65764

1、假定一個(gè)閱覽室最多可容納100 人，讀者進(jìn)入和離開閱覽室時(shí)都必須在閱覽室門口的一個(gè)登記表上進(jìn)行登記，而且每次只允許一人進(jìn)行登記操作，請用記錄型信號量機(jī)制實(shí)現(xiàn)上述問題的同步。定義信號量sum,mutex,初值分別為100, 1。(3分)則第i個(gè)讀者的活動(dòng)描述為：procedure P i(i=1,2,3 )beginwait(sum);wait(mutex);登記；signal(mutex);進(jìn)入閱覽室；閱讀 ;wait(mutex);登記；signal(mutex);離開閱覽室； signal(sum); end請用信號量解決以下的“過獨(dú)木橋”問題：同一方向的行人可連續(xù)過橋，當(dāng)某一方向有人過橋

2、時(shí)，另一方向的行人必須等待；當(dāng)某一方向無人過橋時(shí)，另一方向的行人可以過橋。將獨(dú)木橋的兩個(gè)方向分別標(biāo)記為A和B;并用整形變量countA和countB分別表示 A B方向上已在獨(dú)木橋上的行人數(shù)，初值為0;再設(shè)置三個(gè)初值都1的互斥信號量：SA用來實(shí)現(xiàn)對countA的互斥訪問，SB用來實(shí)現(xiàn)對countB的互斥訪問，mutex用來實(shí)現(xiàn)兩個(gè)方向的行人 對獨(dú)木橋的互斥使用。則具體描述如下：Var SA,SB,mutex:semaphore:=1,1,1;CountA,countB:integer:=0,0: begin parbeginprocess A: beginwait(SA);if(countA=

3、0) then wait(mutex);countA:=countA+1;signal(SA);過獨(dú)木橋；wait(SA);countA:=countA-1;if (countA=0) then signal(mutex);signa(SA);endprocess B: beginwait(SB);if(countB=0) then wait(mutex); countB:=countB+1;signal(SB);過獨(dú)木橋；wait(SB);countB:=countB-1;if (countB=0) then signal(mutex); signa(SB);endparendend設(shè)公共汽

4、車上，司機(jī)和售票員的活動(dòng)分別是：司機(jī)的活動(dòng)：啟動(dòng)車輛；正常行車；到站停車；售票員的活動(dòng)：關(guān)車門；售票；開車門；請用記錄型信號量機(jī)制實(shí)現(xiàn)上述問題的同步。s2 表示是否允許售票員開Var s1,s2:semaphore:=0,0; /*s1 表示是否允許司機(jī)啟動(dòng)汽車， 門 */beginparbegindriver: beginrepeat wait(s1); 啟動(dòng)車輛； 正常行車； 到站停車； signal(s2);until false;endbusman: beginrepeat關(guān)車門；signal(s1);曲蕈.口 ,wait(s2);精品開車門；上下乘客;until false;endp

5、arend end有三個(gè)進(jìn)程PA PB和PC合作解決文件才T印問題：PA將文件記錄從磁盤讀入主存的緩沖區(qū)1,每執(zhí)行一次讀一個(gè)記錄；PB將緩沖區(qū)1的內(nèi)容復(fù)制到緩沖區(qū) 2,每執(zhí)行一次復(fù)制一個(gè)記錄；PC將緩沖區(qū)2的內(nèi)容打印出來，每執(zhí)行一次打印一個(gè)記錄。緩沖區(qū)的大 小等于一個(gè)記錄大小。解釋 P、V操作的含義，并用 P、V操作來保證文件的正確打印。(1) P、V操作是兩條原語，定義如下：P操作：P操作記為P(S),其中S為一信號量，它執(zhí)行時(shí)主要完成下述動(dòng)作：S=S-1若S>=0,則進(jìn)程繼續(xù)運(yùn)行。若S<0,則該進(jìn)程被阻塞，并將它插入該信號量的等待隊(duì)列中。V操作：V操作記為V(S),其中S為一信

6、號量，它執(zhí)行時(shí)主要完成下述動(dòng)作：S=S+1若S>0,則進(jìn)程繼續(xù)運(yùn)行。若S<=0,則從信號量的等待隊(duì)列中移出隊(duì)首進(jìn)程。使其變?yōu)榫途w狀態(tài)。(2)描述如下：Var empty1,empty2,full1,full2:semaphore:=1,1,0,0;beginparbeginprocess1: beginrepeat從磁盤讀一個(gè)記錄；P(empty1);將記錄存入緩沖區(qū)1;V(full1);until false;endprocess 2: beginrepeatP(full1);從緩沖區(qū)1取出紀(jì)錄;V(empty1);P(empty2);將記錄存入緩沖區(qū)2;V(full2);unt

7、il false;endprocess 3: beginrepeatP(full2);從緩沖區(qū)2取出紀(jì)錄;V(empty2);打印記錄；until false;endparend假如一個(gè)程序的段表如下，其中存在位為1表示段在內(nèi)存，對于下面指令，在執(zhí)行時(shí)會(huì)產(chǎn)生什么樣的結(jié)果。段號存在位內(nèi)存始址段長存取控制00500100W11100030R213000200E31800080R40500040RSTORE R1,0,70(2)STORE R1,1,20(3)LOAD R1,3,50(4)LOAD R1,3,100(5)JMP 2,150(1)由于第0段的存在位為0,表示該段未裝入內(nèi)存，因此產(chǎn)生缺段

8、中斷。(2)從段表第1項(xiàng)可看到，指令中邏輯地址合法，段也已經(jīng)在內(nèi)存，但存取控制字段不符， 故產(chǎn)生保護(hù)性中斷信號。(3)邏輯地址合法，存取方式合法，形成物理地址 8050后，執(zhí)行指定操作。(4)邏輯地址中段內(nèi)地址超長，產(chǎn)生越界中斷信號。(5)邏輯地址及訪問方式合法，形成物理地址 3150,指令執(zhí)行后，將條轉(zhuǎn)到內(nèi)存單元3150處繼續(xù)執(zhí)行。現(xiàn)有一請求分頁的虛擬存儲器，內(nèi)存最多容納4個(gè)頁面，對于下面的引用串:1,2,3,4,5,3,4,1,6,7,8,7,8,9,7,8,9,5,4,5,4,2分別采用FIFO, LRU, OPT 頁面替換算法，各將產(chǎn)生多少次缺頁中斷？3. FIFO:123453416

9、78789789545421111555555888888888882222222111111999999999333333666666666555554444447777777774444VVVVVVVVVVVVLRU12345341678789789545421111222534111666678889222345341666789789995334534167878978954544534167878978954542VVVVVVVVVVVVVOPT1234534167878978954542111111116688888888888222255555555555555555533333

10、3377777777744444444444444999999999VVVVVVVVVVVFIFO共13次缺頁中斷，LRU也要13次缺頁中斷，OPT要11次缺頁中斷。2 .已知某分頁系統(tǒng)，主存容量為64K,頁面大小為1K,對一個(gè)4頁大的作業(yè)，其0、1、2、3頁分別被分配到主存的2、4、6、7塊中。(1)將十進(jìn)制的邏輯地址1023、2500、3500、4500轉(zhuǎn)換成物理地址。(2)以十進(jìn)制的邏輯地址1023為例畫出地址變換過程圖。3 .假設(shè)一個(gè)可移動(dòng)磁頭的磁盤具有200個(gè)磁道，其編號為0199，當(dāng)前位于第143道，假設(shè)系統(tǒng)當(dāng)前I/O請求隊(duì)列如下：86,147,91,177,94,150,102,

11、175,130試對以下的磁盤I/O調(diào)度算法而言，滿足以上請求隊(duì)列，磁頭尋道順序如何？尋道總長度 是多少？(1)先來先服務(wù)算法(FCFS)(2)最短尋道時(shí)間優(yōu)先調(diào)度(SSTF)(3)掃描算法(SCAN)(4)循環(huán)掃描算法(CSCAN)有三個(gè)進(jìn)程PA PB和PC合作解決文件才T印問題：PA將文件記錄從磁盤讀入主存的緩沖區(qū)1,每執(zhí)行一次讀一個(gè)記錄；PB將緩沖區(qū)1的內(nèi)容復(fù)制到緩沖區(qū) 2,每執(zhí)行一次復(fù)制一個(gè)記錄；PC將緩沖區(qū)2的內(nèi)容打印出來，每執(zhí)行一次打印一個(gè)記錄。緩沖區(qū)的大 小等于一個(gè)記錄大小。解釋P、V操作的含義，并用 P、V操作來保證文件的正確打印。2 .在一個(gè)請求分頁系統(tǒng)中，假如一個(gè)作業(yè)的頁面走

12、向-為7, 0, 1, 2, 0, 3, 0, 4,2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 當(dāng)分配給該作業(yè)的物理塊數(shù)為 3時(shí)，分別采用LRU OPT頁面置換算法時(shí)，試計(jì)算訪問過程中所發(fā)生的中斷次數(shù)。3 .設(shè)作業(yè)A的頁面映象表如下圖所示：（一頁=一塊=1024字節(jié)）頁號塊號中斷位訪問位修改位輔存地址0811110 0 0151003 0 0 0271105 0 0 030008 0 0 0問：指出頁表中 中斷位、訪問位、修改位、輔存地址的含義？當(dāng)執(zhí)行到1 0 0。單元的指令“LOAD 1, 1 8 0 0 ”時(shí)，系統(tǒng)是怎樣進(jìn)行地址變換（即1 8 0。在主存的哪個(gè)單元

13、中）當(dāng)執(zhí)行到1 5 0 0單元指令（LOAD 1, 3600）時(shí)，會(huì)發(fā)生什么現(xiàn)象？4 .在兩道環(huán)境下有四個(gè)作業(yè)，已知它們進(jìn)入系統(tǒng)的時(shí)間、估計(jì)運(yùn)行時(shí)間，系統(tǒng)分別采用短作業(yè)優(yōu)先作業(yè)調(diào)度算法（可搶占式）和最高響應(yīng)比優(yōu)先調(diào)度算法（可搶占式），分別給出這四個(gè)作業(yè)的執(zhí)行時(shí)間序列，并計(jì)算出平均周轉(zhuǎn)時(shí)間及帶權(quán)平均周轉(zhuǎn)時(shí)間。trik進(jìn)入時(shí)間估說運(yùn)行 時(shí)間 城JOB1L0： 003DJOB210； Of2QJOB3L0： 105JOB4L& 2010假設(shè)有4道作業(yè)，它們提交的時(shí)刻及執(zhí)行時(shí)間由下表給出，計(jì)算在單道程序環(huán)境下, 采用先來先服務(wù)調(diào)度算法、最短作業(yè)優(yōu)先算法、最高響應(yīng)比優(yōu)先算法的平均周轉(zhuǎn)時(shí)間 和平均

14、帶權(quán)周轉(zhuǎn)時(shí)間，并指出它們的調(diào)度順序。作業(yè)提交時(shí)間運(yùn)行時(shí)間18.02.028.50.539.00.149.50.2先來先服務(wù)調(diào)度算法作業(yè)提交時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間18.02.08.010.02.01.028.50.510.010.52.04.039.00.110.510.61.616.049.50.2i0.6i0.8i.36.5T=1.725 W=6.875最短作業(yè)優(yōu)先算法作業(yè)提交時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間i8.02.08.0i0.02i28.50.5i0.3i0.82.34.639.00.ii0.0i0.ii.iii49.50.2i0.ii0.3

15、0.84T=1.55 W=5.15最高響應(yīng)比優(yōu)先算法響應(yīng)比Rp=作業(yè)響應(yīng)時(shí)間/運(yùn)行時(shí)間 =作業(yè)等待時(shí)間+作業(yè)運(yùn)行時(shí)間=1+作業(yè)等待時(shí)間/作業(yè)運(yùn)行時(shí)間作業(yè)提交時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)1可Rp周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間i8.02.08.0i0.0i2i28.50.5i0.ii0.63.22.i4.239.00.ii0.0i0.ii0i.iii49.50.2i0.6i0.85.5i.36.5T=1.625W=5.675有3個(gè)進(jìn)程P1、P2和P 3并發(fā)執(zhí)行。進(jìn)程 P1需使用資源r3和ri ,進(jìn)程P2需使用資源ri和r2 ,進(jìn)程P3需使用資源r2和r3。若對資源分配不加限制，會(huì)發(fā)生什么情況，為什么？為保證進(jìn)程能執(zhí)行到