第二章習(xí)題42835

1、l 假定一個(gè)閱覽室最多可容納100人，讀者進(jìn)入和離開閱覽室時(shí)都必須在閱覽室門口的一個(gè)登記表上進(jìn)行登記，而且每次只允許一人進(jìn)行登記操作，請(qǐng)用記錄型信號(hào)量機(jī)制實(shí)現(xià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);離開閱覽室；signal(sum); endl 請(qǐng)用信號(hào)量解決以下的“過獨(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的互斥信號(hào)量：SA用來實(shí)現(xiàn)對(duì)countA的互斥訪問，SB用來實(shí)現(xiàn)對(duì)countB的互斥訪問，mutex用來實(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);過獨(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);過獨(dú)木橋；wait(SB); countB:=countB-1; if (countB=0) then signal(mutex);signa(SB); endparen

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

5、; end parendendl 有三個(gè)進(jìn)程PA、PB和PC合作解決文件打印問題：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為一信號(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 從磁盤讀一個(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)地址超長

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

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

10、頁分別被分配到主存的2、4、6、7塊中。（1）將十進(jìn)制的邏輯地址1023、2500、3500、4500轉(zhuǎn)換成物理地址。（2）以十進(jìn)制的邏輯地址1023為例畫出地址變換過程圖。2.3. 假設(shè)一個(gè)可移動(dòng)磁頭的磁盤具有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ì)以下的磁盤I/O調(diào)度算法而言,滿足以上請(qǐng)求隊(duì)列,磁頭尋道順序如何? 尋道總長度是多少 ？(1) 先來先服務(wù)算法(FCFS) (2) 最短尋道時(shí)間優(yōu)先調(diào)度(SSTF) (3) 掃描算法(SCAN) (4) 循環(huán)掃描算法 (CSCAN)

11、l 有三個(gè)進(jìn)程PA、PB和PC合作解決文件打印問題：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è)請(qǐng)求分頁系統(tǒng)中，假如一個(gè)作業(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 頁面置換算法時(shí)，試計(jì)算訪問過程中所發(fā)生的中斷次數(shù)。3設(shè)作業(yè)的頁面映象表如下圖所示：（一頁 = 一塊

12、=1024 字節(jié)） 頁號(hào) 塊號(hào) 中斷位 訪問位 修改位 輔存地址 問： 指出頁表中 中斷位、訪問位、修改位、輔存地址的含義？ 當(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)境下，采用先來先服務(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先來先服務(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.210.610.81.36.5T=1.725W=6.875最短作業(yè)優(yōu)先算法作業(yè)提交時(shí)間運(yùn)行時(shí)間開始時(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í)間開始時(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)