操作系統(tǒng)習(xí)習(xí)題及答案四

1、四、計(jì)算題1、某虛擬存儲(chǔ)器的用戶編程空間共32個(gè)頁面，每頁為1KB，內(nèi)存為16KB。假定某時(shí)刻一用戶頁表中已調(diào)入內(nèi)存的頁面的頁號(hào)和物理塊號(hào)的對照表如下：頁號(hào)物理塊號(hào)031721138則邏輯地址0A5C(H)所對應(yīng)的物理地址是什么要求：寫出主要計(jì)算過程。1解： 頁式存儲(chǔ)管理的邏輯地址分為兩部分：頁號(hào)和頁內(nèi)地址。由已知條件“用戶編程空間共32個(gè)頁面”，可知頁號(hào)部分占5位；由“每頁為1KB”，1K=210，可知內(nèi)頁地址占10位。由“內(nèi)存為16KB”，可知有16塊，塊號(hào)為4位。 邏輯地址0A5C（H）所對應(yīng)的二進(jìn)制表示形式是：000 1010 0101 1100 ，根據(jù)上面的分析，下劃線部分為頁內(nèi)地址

2、，編碼 “000 10” 為頁號(hào)，表示該邏輯地址對應(yīng)的頁號(hào)為2。查頁表，得到物理塊號(hào)是11（十進(jìn)制），即物理塊地址為：10 11，拼接塊內(nèi)地址10 0101 1100，得10 1110 0101 1100，即2E5C（H）。2、對于如下的頁面訪問序列：1， 2， 3， 4， 1， 2， 5， 1， 2， 3， 4， 5 當(dāng)內(nèi)存塊數(shù)量為3時(shí)，試問：使用FIFO、LRU置換算法產(chǎn)生的缺頁中斷是多少寫出依次產(chǎn)生缺頁中斷后應(yīng)淘汰的頁。（所有內(nèi)存開始時(shí)都是空的，凡第一次用到的頁面都產(chǎn)生一次缺頁中斷。要求寫出計(jì)算步驟。）2解： 采用先進(jìn)先出（FIFO）調(diào)度算法，頁面調(diào)度過程如下：頁面次序123412512

3、345主存頁面情況111444555222111333332224共產(chǎn)生缺頁中斷9次。依次淘汰的頁是1、2、3、4、1、2。 采用最近最少使用（LRU）調(diào)度算法，頁面調(diào)度過程如下：頁面次序123412512345主存頁面情況111444533322211114433322225共產(chǎn)生缺頁中斷10次。依次淘汰的頁是1、2、3、4、5、1、2。3、下表給出了某系統(tǒng)中的空閑分區(qū)表，系統(tǒng)采用可變式分區(qū)存儲(chǔ)管理策略。現(xiàn)有以下作業(yè)序列：96K、20K、200K。若用首次適應(yīng)算法和最佳適應(yīng)算法來處理這些作業(yè)序列，試問哪一種算法可以滿足該作業(yè)序列的請求，為什么空閑分區(qū)表1234532K10K5K218K90K

4、100K150K200K 220K530K分區(qū)號(hào)1 7 5 02 3 5 60 6 5 20 6 5 6P2P3P4大小1 7 5 02 3 5 60 6 5 20 6 5 6P2P3P4起始地址1 7 5 02 3 5 60 6 5 20 6 5 6P2P3P43解：若采用最佳適應(yīng)算法，在申請96K存儲(chǔ)區(qū)時(shí)，選中的是5號(hào)分區(qū)，5號(hào)分區(qū)大小與申請空間大d,-致，應(yīng)從空閑分區(qū)表中刪去該表項(xiàng)；接著申請20K時(shí)，選中1號(hào)分區(qū)，分配后1號(hào)分區(qū)還剩下12K；最后申請200K，選中4號(hào)分區(qū)，分配后剩下18K。顯然采用最佳適應(yīng)算法進(jìn)行內(nèi)存分配，可以滿足該作業(yè)序列的需求。為作業(yè)序列分配了內(nèi)存空間后，空閑分區(qū)表

5、如表5-3(a)所示。 若采用首次適應(yīng)算法，在申請96K存儲(chǔ)區(qū)時(shí)，選中的是4號(hào)分區(qū)，進(jìn)行分配后4號(hào)分區(qū)還剩下122K；接著申請20K，選中1號(hào)分區(qū)，分配后剩下12K；最后申請200K，現(xiàn)有的五個(gè)分區(qū)都無法滿足要求，該作業(yè)等待。顯然采用首次適應(yīng)算法進(jìn)行內(nèi)存分配，無法滿足該作業(yè)序列的需求。這時(shí)的空閑分區(qū)表如表53(b)所示。 分配后的空閑分區(qū)表(a)123412K10K5K18K100K150K200K 220K分區(qū)號(hào)1 7 5 02 3 5 60 6 5 20 6 5 6P2P3P4大小1 7 5 02 3 5 60 6 5 20 6 5 6P2P3P4起始地址1 7 5 02 3 5 60 6

6、 5 20 6 5 6P2P3P4 (b)1234512K10K5K122K96K100K150K200K 220K530K分區(qū)號(hào)1 7 5 02 3 5 60 6 5 20 6 5 6P2P3P4大小1 7 5 02 3 5 60 6 5 20 6 5 6P2P3P4起始地址1 7 5 02 3 5 60 6 5 20 6 5 6P2P3P44、某采用段式存儲(chǔ)管理的系統(tǒng)為裝入主存的一個(gè)作業(yè)建立下表所示的段表 段表段號(hào)段長主存起始地址06602219114033002100903580123749601959回答下列問題：（1）計(jì)算該作業(yè)訪問0, 432, l, 10, 2, 500時(shí)（方括號(hào)

7、中第一元素為段號(hào)，第二元素為段內(nèi)地址）的絕對地址（2）總結(jié)段式存儲(chǔ)管理的地址轉(zhuǎn)換過程4答： (1)0,432 (432<660)2219+432=2651 1，10 (10<140)3300+10=3310 2，500(因500>100所以地址越界，產(chǎn)生中斷) (2)總結(jié)段式存儲(chǔ)管理的地址轉(zhuǎn)換過程如下： 從邏輯地址中取出段號(hào)和段內(nèi)地址。 根據(jù)段號(hào)，從段表中取出該段在主存中的始址和段長。 比較段內(nèi)地址和段長，如段內(nèi)地址段長，則繼續(xù)下一步，否則產(chǎn)生越界中段，程序中斷(非法操作)。 計(jì)算本段始址+段內(nèi)地址，得到絕對地址。1.假設(shè)一個(gè)系統(tǒng)中有5個(gè)進(jìn)程,它們的到達(dá)時(shí)間和服務(wù)時(shí)間如表1所

8、示,忽略I/0以及其他開銷時(shí)間,若分別按先來先服務(wù)(FCFS)、非搶占及搶占的短進(jìn)程優(yōu)先（SPF）、高響應(yīng)比優(yōu)先(HRRF)、時(shí)間片輪轉(zhuǎn)(RR,時(shí)間片=1)調(diào)度算法進(jìn)行CPU調(diào)度,請給出各進(jìn)程的完成時(shí)間、周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間、平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。表1進(jìn)程到達(dá)和需服務(wù)時(shí)間進(jìn)程到達(dá)時(shí)間服務(wù)時(shí)間A03B26C44D65E82        分析：進(jìn)程調(diào)度的關(guān)鍵是理解和掌握調(diào)度所采用的算法。FCFS算法選擇最早進(jìn)入就緒隊(duì)列的進(jìn)程投入執(zhí)行;SPF算法選擇估計(jì)運(yùn)行時(shí)間最短的進(jìn)程投入執(zhí)行,采用搶占方式時(shí),若新就緒的

9、進(jìn)程運(yùn)行時(shí)間比正在執(zhí)行的進(jìn)程的剩余運(yùn)行時(shí)間短,則新進(jìn)程將搶占CPU;HRRF算法選擇響應(yīng)比最高的進(jìn)程投入執(zhí)行;RR算法中,就緒進(jìn)程按FIFO方式排隊(duì),CPU總是分配給隊(duì)首的進(jìn)程,并只能執(zhí)行一個(gè)時(shí)間片。答：各進(jìn)程的完成時(shí)間、周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間(如表2所示)表2進(jìn)程的完成時(shí)間和周轉(zhuǎn)時(shí)間 進(jìn)程   ABCDE平 均 FCFS完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間339713918122012 SPF(非搶占)完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間339715112014113 SPF(搶占)完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間33151384201410

10、2  HRRF 完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間33971392014157 8 RR(q=1) 完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間44181617132014157   3.在銀行家算法中，若出現(xiàn)下述資源分配情況： 進(jìn)  程AllocationNeedAvailableA  B  C  DA  B  C  DA  B  C&#

11、160; DP0P1P2P3P40  0  3  21  0  0  01  3  5  40  3  3  20  0  1  40  0  1  21  7  5  

12、02  3  5  60  6  5  20  6  5  61  6  2  2 試問:（1)該狀態(tài)是否安全(2)如果進(jìn)程P2提出請求Request（0,2,2,2后,系統(tǒng)能否將資源分配給它解:(1)利用銀行家算法對此時(shí)刻的資源分配情況進(jìn)行分析,可得此時(shí)刻的安全性分析情況。 進(jìn) 程WorkNeedAllocationWork+Alloc

13、ationFinishA  B  C  DA  B  C  DA  B  C  D A  B  C  DP0P3P4P1P21  6  2  21  6  5  41  9  8 

14、 61  9  9  102  9  9  100  0  1  20  6  5  20  6  5  61  7  5  02  3  5  60  0&#

15、160; 3  20  3  3  20  0  1  41  0  0  01  3  5  41  6  5  41  9  8  61  9  9 

16、60;102  9  9  103  12  14  14truetruetruetruetrue 從上述分析中可以看出，此時(shí)存在一個(gè)安全序列P0,P3,P4,P1,P2,故該狀態(tài)是安全的。（2）P2提出請求Request2(1,2,2,2),按銀行家算法進(jìn)行檢查：     Request2(1,2,2,2)Need2(2,3,5,6)     Request2(1,

17、2,2,2)Available(1,6,2,2)     試分配并修改相應(yīng)數(shù)據(jù)結(jié)構(gòu)，資源分配情況如下：進(jìn)  程AllocationNeedAvailableA  B  C  DA  B  C  DA  B  C  DP0P1P2P3P40  0  3  21  0

18、60; 0  02  5  7  60  3  3  20  0  1  40  0  1  21  7  5  01  1  3  40  6  5 

19、0;20  6  5  60  4  0  0 再利用安全性算法檢查系統(tǒng)是否安全,可用資源Available (0,4,0,0)已不能滿足任何進(jìn)程的需要,故系統(tǒng)進(jìn)入不安全狀態(tài),此時(shí)系統(tǒng)不能將資源分配給P2。 3某請求分頁系統(tǒng)，用戶空間為32KB，每個(gè)頁面1KB，主存16KB。某用戶程序有7頁長，某時(shí)刻該用戶進(jìn)程的頁表如下：頁號(hào)物理塊號(hào)是否在TLB08是17是24否310否45否53是62是（1）計(jì)算兩個(gè)邏輯地址：0AC5H、1AC5H對應(yīng)的物理地址。（2）

20、已知主存的一次存取為，對于TLB表（快表）的查詢時(shí)間可以忽略，則訪問上述兩個(gè)邏輯地址共耗費(fèi)多少時(shí)間答 （1） 每頁1kb代表頁內(nèi)偏移量為低地址10位，剩余的為頁號(hào)，所以0AC5H對應(yīng)的頁號(hào)為2，物理塊為4，說以物理地址為12C5H, 同理可得1AC5H對應(yīng)的物理地址為0AC5H.（2）耗時(shí)為1×+2×=4什么叫重定位它有哪兩種方式這兩種方式有什么區(qū)別 由于經(jīng)過緊湊后的某些用戶程序在內(nèi)存中的位置發(fā)生了變化，此時(shí)若不對程序和數(shù)據(jù)的地址加以修改(變換)，則程序必將無法執(zhí)行。為此，在每次“緊湊”后，都必須對移動(dòng)了的程序或數(shù)據(jù)進(jìn)行重定位。5在具有快表的段頁式存儲(chǔ)管理方式中，如何實(shí)現(xiàn)地

21、址變換 答：物理地址=該段在主存的起始地址+頁框號(hào)*大小+頁內(nèi)地址。第二次作業(yè)：1、 在某請求分頁管理系統(tǒng)中，一個(gè)作業(yè)共5頁，作業(yè)執(zhí)行時(shí)一次訪問如下頁面：1，4，3，1，2，5，1，4，2，1，4，5，若分配給該作業(yè)的主存塊數(shù)為3，分別采用FIFO，LRU，Clock頁面置換算法，試求出缺頁中斷的次數(shù)及缺頁率。答 FIFO 缺頁次數(shù)為9，缺頁率為3/4LRU缺頁數(shù)為9，缺頁率為3/4Clock缺頁數(shù)為9，缺頁率為3/42、 某請求分頁管理系統(tǒng)，假設(shè)進(jìn)程的頁表如下：頁號(hào)頁框號(hào)有效位裝入時(shí)間0101H12102254H14頁面大小為4KB，一次內(nèi)存的訪問時(shí)間為100納秒（ns），一次快表（TLB）

22、的訪問時(shí)間是10ns，處理一次缺頁的平均時(shí)間為100毫秒（已含更新TLB和頁表的時(shí)間），進(jìn)程的駐留集大小固定為2個(gè)頁框，采用FIFO法置換頁面。假設(shè)1）TLB初始為空；2）地址轉(zhuǎn)換時(shí)，先訪問TLB，若TLB未命中時(shí)再訪問頁表（忽略TLB更新時(shí)間）；3）有效位為0表示頁面不在內(nèi)存中。請問：（1）該系統(tǒng)中，一次訪存的時(shí)間下限和上限各是多少（給出計(jì)算過程）（2）若已經(jīng)先后訪問過0、2號(hào)頁面，則虛地址1565H的物理地址是多少（給出計(jì)算過程）答（1）一次訪存時(shí)間下限10ns+100ns+100ns，上限10ns+100ns+100ms+100ns （2）基于上述訪問序列，當(dāng)訪問虛地址1565H時(shí)產(chǎn)生缺

23、頁中斷，合法駐留集為2，必須從表中淘汰一個(gè)頁面，根據(jù)題目的置換算法，應(yīng)淘汰0號(hào)頁面，因此1565H的對應(yīng)頁框號(hào)為101H。由此可得1565H的物理地址為101565H3、設(shè)某計(jì)算機(jī)的邏輯地址空間和物理地址空間均為128KB，按字節(jié)編址。若某進(jìn)程最多需要6頁數(shù)據(jù)存儲(chǔ)空間，頁面大小為1KB，操作系統(tǒng)采用固定分配局部置換策略為該進(jìn)程分配4個(gè)頁框（物理塊）。在時(shí)刻300前該進(jìn)程各頁面的訪問情況如下表所示：頁號(hào)頁框號(hào)（塊號(hào)）裝入時(shí)間訪問位071301142301222001391801當(dāng)進(jìn)程執(zhí)行到時(shí)刻300時(shí)，要訪問邏輯地址為17CAH的數(shù)據(jù)，請回答下列問題：（1）該邏輯地址對應(yīng)的頁號(hào)是多少（2）若采用

24、先進(jìn)先出（FIFO）置換算法，該邏輯地址對應(yīng)的物理地址是多少要求給出計(jì)算過程。（3）若采用時(shí)鐘（CLOCK）置換算法，該邏輯地址對應(yīng)的物理地址是多少要求給出計(jì)算過程。設(shè)搜索下一頁的指針順時(shí)針方向移動(dòng)，且當(dāng)前指向2號(hào)頁框，示意圖如下：17CAH=(0001 0111 1100 1010)2（1）頁大小為1K，則頁內(nèi)偏移地址為10位，前6位是頁號(hào)，所以邏輯地址對應(yīng)的頁號(hào)為：5 （2）FIFO：被置換的頁面所在頁框?yàn)?，所以對應(yīng)的物理地址為（0001 1111 1100 1010）2=1FCAH （3）CLOCK：被置換

25、的頁面所在頁框?yàn)?，所以對應(yīng)的物理地址為（0000 1011 1100 1010）2=0BCAH并有一下請求序列等待訪問磁盤：請求序列： 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9預(yù)訪問柱面號(hào)：150，50 ，178，167 ，87，43 ，23 ，160 ，85試用最短尋找時(shí)間優(yōu)先算法和電梯調(diào)度算法，分別排出實(shí)際處理上述請求的次序第一題：序列（柱面號(hào)）最短尋找時(shí)間優(yōu)先算法9(85)、5(87)、2(50)、6(43)、7(23)、1(150)、8(160)、4(167)、3(178)電梯調(diào)度算法9(85)、5(87)、1(150)、8(160)、4(16

26、7)、3(178)、2(50)、6(43)、7(23)第二題：磁盤有199個(gè)磁道，當(dāng)前磁頭在54#磁道上，并向磁道號(hào)減小的方向上移動(dòng)，現(xiàn)有一下請求序列等待訪問磁盤：請求序列 1 2 3 4 5 6 7 8 帶訪問的柱面號(hào) 99 184 38 123 15 125 66 68試用最短尋找時(shí)間優(yōu)先算法和電梯調(diào)度算法，分別排出實(shí)際處理上述請求的次序，并計(jì)算出他們的平均尋道長度 第二題：序列（柱面號(hào)）最短尋找時(shí)間優(yōu)先算法7(66) 8(68) 3(38) 5(15) 1(99) 4(123) 6(125) 2(184)12+2+30+23+84+24+2+59=236平均尋道長度236/8=電梯調(diào)度算

27、法3(38) 5(15) 7(66) 8(68) 1(99) 4(123) 6(125) 2(184)16+23+51+2+31+24+2+59=208平均尋道長度208/8=26四、計(jì)算題1、假定在單CPU條件下有下列要執(zhí)行的作業(yè)：作業(yè)運(yùn)行時(shí)間優(yōu)先級(jí)1102243335 作業(yè)到來的時(shí)間是按作業(yè)編號(hào)順序進(jìn)行的（即后面作業(yè)依次比前一個(gè)作業(yè)遲到一個(gè)時(shí)間單位）。 （1）用一個(gè)執(zhí)行時(shí)間圖描述在采用非搶占式優(yōu)先級(jí)算法時(shí)執(zhí)行這些作業(yè)的情況。（2）對于上述算法，各個(gè)作業(yè)的周轉(zhuǎn)時(shí)間是多少平均周轉(zhuǎn)時(shí)間是多少（3）對于上述算法，各個(gè)作業(yè)的帶權(quán)周轉(zhuǎn)時(shí)間是多少平均帶權(quán)周轉(zhuǎn)時(shí)間是多少1解： (1) 非搶占式優(yōu)先級(jí)算法（

28、3分） 作業(yè)1 作業(yè)3 作業(yè)2 | | | | t 0 10 13 17 (2) 和（3）作業(yè)到達(dá)時(shí)間運(yùn)行時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間1010101021417163231311平均周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間2、若后備作業(yè)隊(duì)列中等待運(yùn)行的同時(shí)有三個(gè)作業(yè)J1、J2、J3，已知它們各自的運(yùn)行 時(shí)間為a、b、c，且滿足a<b<a，試證明采用短作業(yè)優(yōu)先算法調(diào)度能獲得最小平均作業(yè)周轉(zhuǎn)時(shí)間。2證明：采用短作業(yè)優(yōu)先算法調(diào)度時(shí)，三個(gè)作業(yè)的總周轉(zhuǎn)時(shí)間為：T1=a+(a+b)+(a+b+c)=3a+2b+c 若不按短作業(yè)優(yōu)先算法調(diào)度，不失一般性，設(shè)調(diào)度次序?yàn)椋篔2、J1、J3。則三個(gè)作業(yè)的總周轉(zhuǎn)時(shí)間為： T2=b+(b+a)+(b+a+c)=3b+2a+c 令一式得到： T2-Tl=b-a>0可見，采用短作業(yè)優(yōu)先算法調(diào)度才能獲得最小平均作業(yè)周轉(zhuǎn)時(shí)間。3、若有如表所示四個(gè)作業(yè)進(jìn)入系統(tǒng)，分別計(jì)算在FCFS、SJF和HRRF算法下的平均周轉(zhuǎn)時(shí)間與帶權(quán)平均周轉(zhuǎn)時(shí)間。作業(yè)提交時(shí)間（時(shí)）估計(jì)運(yùn)行時(shí)間（分）12348:008:509:009:501205010203答：作業(yè)FCFSSJFHRRF開始 完成 周轉(zhuǎn)時(shí)間 時(shí)間 時(shí)間開始 完成 周轉(zhuǎn)