dhu-第二章習題

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

2、過橋時，另一方向的行人必須等待；當某一方向無人過橋時，另一方向的行人可以過橋。將獨木橋的兩個方向分別標記為A和B；并用整形變量countA和countB分別表示A、B方向上已在獨木橋上的行人數，初值為0；再設置三個初值都1的互斥信號量：SA用來實現對countA的互斥訪問，SB用來實現對countB的互斥訪問，mutex用來實現兩個方向的行人對獨木橋的互斥使用。則具體描述如下：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);過獨木橋；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);過獨木橋；wait(SB); countB:=countB-1; if (countB=0) then signal(mutex);signa(SB); endp

4、arend endl 設公共汽車上，司機和售票員的活動分別是：司機的活動：啟動車輛；正常行車；到站停車；售票員的活動：關車門；售票；開車門；請用記錄型信號量機制實現上述問題的同步。Var s1,s2:semaphore:=0,0; /*s1表示是否允許司機啟動汽車，s2表示是否允許售票員開門*/ begin parbegin driver: begin repeatwait(s1);啟動車輛；正常行車；到站停車；signal(s2); until false; end busman: begin repeat關車門；signal(s1);售票；wait(s2);開車門；上下乘客；until f

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

6、為V(S)，其中S為一信號量，它執(zhí)行時主要完成下述動作： S=S+1若S>0，則進程繼續(xù)運行。若S<=0，則從信號量的等待隊列中移出隊首進程。使其變?yōu)榫途w狀態(tài)。（2）描述如下：Var empty1,empty2,full1,full2:semaphore:=1,1,0,0; begin parbegin process1: begin repeat 從磁盤讀一個記錄； P(empty1); 將記錄存入緩沖區(qū)1； V(full1); until false; end process 2: begin repeat P(full1); 從緩沖區(qū)1取出紀錄； V(empty1); P(e

7、mpty2); 將記錄存入緩沖區(qū)2； V(full2); until false; endprocess 3: begin推薦精選 repeat P(full2); 從緩沖區(qū)2取出紀錄； V(empty2); 打印記錄； until false;end parend l 假如一個程序的段表如下，其中存在位為1表示段在內存，對于下面指令，在執(zhí)行時會產生什么樣的結果。(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，表示該段未裝入內存，因此產生缺段中斷。(2)從段表

8、第1項可看到，指令中邏輯地址合法，段也已經在內存，但存取控制字段不符，故產生保護性中斷信號。 (3)邏輯地址合法，存取方式合法，形成物理地址8050后，執(zhí)行指定操作。 (4)邏輯地址中段內地址超長，產生越界中斷信號。(5)邏輯地址及訪問方式合法，形成物理地址3150，指令執(zhí)行后，將條轉到內存單元3150處繼續(xù)執(zhí)行。l 現有一請求分頁的虛擬存儲器 , 內存最多容納 4 個頁面 , 對于下面的引用串： 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 頁面替換算法 , 各將產生多少次缺頁中斷 ? 3. FIFO:1234

9、5341678789789545421111555555888888888882222222111111999999999333333666666666555554444447777777774444推薦精選LRU12345341678789789545421111222534111666678889222345341666789789995334534167878978954544534167878978954542OPT12345341678789789545421111111166888888888882222555555555555555555333333377777777744444

10、444444444999999999FIFO共13次缺頁中斷，LRU也要13次缺頁中斷，OPT要11次缺頁中斷。2. 已知某分頁系統，主存容量為64K，頁面大小為1K，對一個4頁大的作業(yè)，其0、1、2、3頁分別被分配到主存的2、4、6、7塊中。（1）將十進制的邏輯地址1023、2500、3500、4500轉換成物理地址。（2）以十進制的邏輯地址1023為例畫出地址變換過程圖。2.3. 假設一個可移動磁頭的磁盤具有200個磁道,其編號為0199,當前位于第143道，假設系統當前I/O請求隊列如下: 86,147,91,177,94,150,102,175,130 試對以下的磁盤I/O調度算法而言

11、,滿足以上請求隊列,磁頭尋道順序如何? 尋道總長度是多少 ？(1) 先來先服務算法(FCFS) (2) 最短尋道時間優(yōu)先調度(SSTF) (3) 掃描算法(SCAN) (4) 循環(huán)掃描算法 (CSCAN)l 有三個進程PA、PB和PC合作解決文件打印問題：PA將文件記錄從磁盤讀入主存的緩沖區(qū)1，每執(zhí)行一次讀一個記錄；PB將緩沖區(qū)1的內容復制到緩沖區(qū)2，每執(zhí)行一次復制一個記錄；PC將緩沖區(qū)2的內容打印出來，每執(zhí)行一次打印一個記錄。緩沖區(qū)的大小等于一個記錄大小。解釋P、V操作的含義，并用P、V操作來保證文件的正確打印。2在一個請求分頁系統中，假如一個作業(yè)的頁面走向-為7，0，1，2，0，3，0，4

12、，2，3，0，3，2，1，2，0，1，7，0，1當分配給該作業(yè)的物理塊數為3時，分別采用LRU、OPT 頁面置換算法時，試計算訪問過程中所發(fā)生的中斷次數。推薦精選3設作業(yè)的頁面映象表如下圖所示：（一頁 = 一塊 =1024 字節(jié)） 頁號 塊號 中斷位 訪問位 修改位 輔存地址   問： 指出頁表中 中斷位、訪問位、修改位、輔存地址的含義？ 當執(zhí)行到單元的指令“ ，”時，系統是怎樣進行地址變換（即在主存的哪個單元中） 當執(zhí)行到單元指令（ ，）時，會發(fā)生什么現象？4在兩道環(huán)境下有四個作業(yè)，已知它們進入系統的時間、估計運行時間，系統分別采用短作業(yè)優(yōu)先作業(yè)調度算法（可搶占式）和最高響應比優(yōu)先

13、調度算法（可搶占式），分別給出這四個作業(yè)的執(zhí)行時間序列，并計算出平均周轉時間及帶權平均周轉時間。l 假設有 4 道作業(yè)，它們提交的時刻及執(zhí)行時間由下表給出，計算在單道程序環(huán)境下，采用先來先服務調度算法、最短作業(yè)優(yōu)先算法、最高響應比優(yōu)先算法的平均周轉時間和平均帶權周轉時間，并指出它們的調度順序。 作業(yè)提交時間運行時間18.02.028.50.539.00.149.50.2先來先服務調度算法作業(yè)提交時間運行時間開始時間完成時間周轉時間帶權周轉時間18.02.08.010.02.01.028.50.510.010.52.04.039.00.110.510.61.616.049.50.210.610.

14、81.36.5T=1.725W=6.875最短作業(yè)優(yōu)先算法作業(yè)提交時間運行時間開始時間完成時間周轉時間帶權周轉時間推薦精選18.02.08.010.02128.50.510.310.82.34.639.00.110.010.11.11149.50.210.110.30.84T=1.55W=5.15最高響應比優(yōu)先算法 響應比Rp作業(yè)響應時間運行時間作業(yè)等待時間作業(yè)運行時間 作業(yè)等待時間作業(yè)運行時間作業(yè)提交時間運行時間開始時間完成時間Rp周轉時間帶權周轉時間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個進程P1、P2和P 3并發(fā)執(zhí)行。進程P1需使用資源r3和r1，進程P2需使用資源r1和r2，進程P3需使用資源r2和r3。若對資源分配不加限制，會發(fā)生什么情況，為什么？為保證進程能執(zhí)行到結束，應采用怎樣的資源分配策略？（1