第二章習(xí)題42835

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

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

3、tA=0) then wait(mutex);countA:=countA+1;signal(SA);過(guò)獨(dú)木橋；wait(SA); countA:=countA-1; if (countA=0) then signal(mutex);signa(SA); endprocess B: begin wait(SB);if(countB=0) then wait(mutex);countB:=countB+1;signal(SB);過(guò)獨(dú)木橋；wait(SB); countB:=countB-1; if (countB=0) then signal(mutex);signa(SB); endparen

4、d endl 設(shè)公共汽車(chē)上，司機(jī)和售票員的活動(dòng)分別是：司機(jī)的活動(dòng)：?jiǎn)?dòng)車(chē)輛；正常行車(chē)；到站停車(chē)；售票員的活動(dòng)：關(guān)車(chē)門(mén)；售票；開(kāi)車(chē)門(mén)；請(qǐng)用記錄型信號(hào)量機(jī)制實(shí)現(xiàn)上述問(wèn)題的同步。Var s1,s2:semaphore:=0,0; /*s1表示是否允許司機(jī)啟動(dòng)汽車(chē)，s2表示是否允許售票員開(kāi)門(mén)*/ begin parbegin driver: begin repeatwait(s1);啟動(dòng)車(chē)輛；正常行車(chē)；到站停車(chē)；signal(s2); until false; end busman: begin repeat關(guān)車(chē)門(mén)；signal(s1);售票；wait(s2);開(kāi)車(chē)門(mén)；上下乘客；until false

5、; end parendendl 有三個(gè)進(jìn)程PA、PB和PC合作解決文件打印問(wèn)題：PA將文件記錄從磁盤(pán)讀入主存的緩沖區(qū)1，每執(zhí)行一次讀一個(gè)記錄；PB將緩沖區(qū)1的內(nèi)容復(fù)制到緩沖區(qū)2，每執(zhí)行一次復(fù)制一個(gè)記錄；PC將緩沖區(qū)2的內(nèi)容打印出來(lái)，每執(zhí)行一次打印一個(gè)記錄。緩沖區(qū)的大小等于一個(gè)記錄大小。解釋P、V操作的含義，并用P、V操作來(lái)保證文件的正確打印。（1）P、V操作是兩條原語(yǔ)，定義如下： P操作：P操作記為P(S)，其中S為一信號(hào)量，它執(zhí)行時(shí)主要完成下述動(dòng)作： S=S-1若S=0，則進(jìn)程繼續(xù)運(yùn)行。若S0，則進(jìn)程繼續(xù)運(yùn)行。若S=0，則從信號(hào)量的等待隊(duì)列中移出隊(duì)首進(jìn)程。使其變?yōu)榫途w狀態(tài)。（2）描述如下：

6、Var empty1,empty2,full1,full2:semaphore:=1,1,0,0; begin parbegin process1: begin repeat 從磁盤(pán)讀一個(gè)記錄； P(empty1); 將記錄存入緩沖區(qū)1； V(full1); until false; end process 2: begin repeat P(full1); 從緩沖區(qū)1取出紀(jì)錄； V(empty1); P(empty2); 將記錄存入緩沖區(qū)2； V(full2); until false; endprocess 3: begin repeat P(full2); 從緩沖區(qū)2取出紀(jì)錄； V(em

7、pty2); 打印記錄； until false;end parend l 假如一個(gè)程序的段表如下，其中存在位為1表示段在內(nèi)存，對(duì)于下面指令，在執(zhí)行時(shí)會(huì)產(chǎn)生什么樣的結(jié)果。(1)STORE 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)生缺段中斷。(2)從段表第1項(xiàng)可看到，指令中邏輯地址合法，段也已經(jīng)在內(nèi)存，但存取控制字段不符，故產(chǎn)生保護(hù)性中斷信號(hào)。 (3)邏輯地址合法，存取方式合法，形成物理地址8050后，執(zhí)行指定操作。 (4)邏輯地址中段內(nèi)地址超長(zhǎng)

8、，產(chǎn)生越界中斷信號(hào)。(5)邏輯地址及訪問(wèn)方式合法，形成物理地址3150，指令執(zhí)行后，將條轉(zhuǎn)到內(nèi)存單元3150處繼續(xù)執(zhí)行。l 現(xiàn)有一請(qǐng)求分頁(yè)的虛擬存儲(chǔ)器 , 內(nèi)存最多容納 4 個(gè)頁(yè)面 , 對(duì)于下面的引用串： 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 頁(yè)面替換算法 , 各將產(chǎn)生多少次缺頁(yè)中斷 ? 3. FIFO:123453416787897895454211115555558888888888822222221111119999999993333336666666665555544444477777777744

9、44LRU12345341678789789545421111222534111666678889222345341666789789995334534167878978954544534167878978954542OPT12345341678789789545421111111166888888888882222555555555555555555333333377777777744444444444444999999999FIFO共13次缺頁(yè)中斷，LRU也要13次缺頁(yè)中斷，OPT要11次缺頁(yè)中斷。2. 已知某分頁(yè)系統(tǒng)，主存容量為64K，頁(yè)面大小為1K，對(duì)一個(gè)4頁(yè)大的作業(yè)，其0、1、2、3

10、頁(yè)分別被分配到主存的2、4、6、7塊中。（1）將十進(jìn)制的邏輯地址1023、2500、3500、4500轉(zhuǎn)換成物理地址。（2）以十進(jìn)制的邏輯地址1023為例畫(huà)出地址變換過(guò)程圖。2.3. 假設(shè)一個(gè)可移動(dòng)磁頭的磁盤(pán)具有200個(gè)磁道,其編號(hào)為0199,當(dāng)前位于第143道，假設(shè)系統(tǒng)當(dāng)前I/O請(qǐng)求隊(duì)列如下: 86,147,91,177,94,150,102,175,130 試對(duì)以下的磁盤(pán)I/O調(diào)度算法而言,滿足以上請(qǐng)求隊(duì)列,磁頭尋道順序如何? 尋道總長(zhǎng)度是多少 ？(1) 先來(lái)先服務(wù)算法(FCFS) (2) 最短尋道時(shí)間優(yōu)先調(diào)度(SSTF) (3) 掃描算法(SCAN) (4) 循環(huán)掃描算法 (CSCAN)

11、l 有三個(gè)進(jìn)程PA、PB和PC合作解決文件打印問(wèn)題：PA將文件記錄從磁盤(pán)讀入主存的緩沖區(qū)1，每執(zhí)行一次讀一個(gè)記錄；PB將緩沖區(qū)1的內(nèi)容復(fù)制到緩沖區(qū)2，每執(zhí)行一次復(fù)制一個(gè)記錄；PC將緩沖區(qū)2的內(nèi)容打印出來(lái)，每執(zhí)行一次打印一個(gè)記錄。緩沖區(qū)的大小等于一個(gè)記錄大小。解釋P、V操作的含義，并用P、V操作來(lái)保證文件的正確打印。2在一個(gè)請(qǐng)求分頁(yè)系統(tǒng)中，假如一個(gè)作業(yè)的頁(yè)面走向-為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 頁(yè)面置換算法時(shí)，試計(jì)算訪問(wèn)過(guò)程中所發(fā)生的中斷次數(shù)。3設(shè)作業(yè)的頁(yè)面映象表如下圖所示：（一頁(yè) = 一塊

12、=1024 字節(jié)） 頁(yè)號(hào) 塊號(hào) 中斷位 訪問(wèn)位 修改位 輔存地址 問(wèn)： 指出頁(yè)表中 中斷位、訪問(wèn)位、修改位、輔存地址的含義？ 當(dāng)執(zhí)行到單元的指令“ ，”時(shí)，系統(tǒng)是怎樣進(jìn)行地址變換（即在主存的哪個(gè)單元中） 當(dāng)執(zhí)行到單元指令（ ，）時(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í)間。l 假設(shè)有 4 道作業(yè)，它們提交的時(shí)刻及執(zhí)行時(shí)間由下表給出，計(jì)算在單道程序環(huán)境下，采用先來(lái)先服務(wù)調(diào)度算法、最短作業(yè)優(yōu)先算法、最高響

13、應(yīng)比優(yōu)先算法的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間，并指出它們的調(diào)度順序。 作業(yè)提交時(shí)間運(yùn)行時(shí)間18.02.028.50.539.00.149.50.2先來(lái)先服務(wù)調(diào)度算法作業(yè)提交時(shí)間運(yùn)行時(shí)間開(kāi)始時(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.210.610.81.36.5T=1.725W=6.875最短作業(yè)優(yōu)先算法作業(yè)提交時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間18.02.08.010.02128.50.510.310.82.34.639.00.110.010.11.11

14、149.50.210.110.30.84T=1.55W=5.15最高響應(yīng)比優(yōu)先算法 響應(yīng)比Rp作業(yè)響應(yīng)時(shí)間運(yùn)行時(shí)間作業(yè)等待時(shí)間作業(yè)運(yùn)行時(shí)間 作業(yè)等待時(shí)間作業(yè)運(yùn)行時(shí)間作業(yè)提交時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間Rp周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間18.02.08.010.012128.50.510.110.63.22.14.239.00.110.010.1101.11149.50.210.610.85.51.36.5T=1.625W=5.675l 有3個(gè)進(jìn)程P1、P2和P 3并發(fā)執(zhí)行。進(jìn)程P1需使用資源r3和r1，進(jìn)程P2需使用資源r1和r2，進(jìn)程P3需使用資源r2和r3。若對(duì)資源分配不加限制，會(huì)發(fā)生什么情況，為什么？為保證進(jìn)