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

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

2、址，編碼 “000 10” 為頁號，表示該邏輯地址對應(yīng)的頁號為2。查頁表，得到物理塊號是11（十進制），即物理塊地址為：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時，試問：使用FIFO、LRU置換算法產(chǎn)生的缺頁中斷是多少？寫出依次產(chǎn)生缺頁中斷后應(yīng)淘汰的頁。（所有內(nèi)存開始時都是空的，凡第一次用到的頁面都產(chǎn)生一次缺頁中斷。要求寫出計算步驟。）2解： 采用先進先出（FIFO）調(diào)度算法，頁面調(diào)度過程如下：頁面次序1234125

3、12345主存頁面情況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ū)存儲管理策略?，F(xiàn)有以下作業(yè)序列：96K、20K、200K。若用首次適應(yīng)算法和最佳適應(yīng)算法來處理這些作業(yè)序列，試問哪一種算法可以滿足該作業(yè)序列的請求，為什么?空閑分區(qū)表1234532K10K5K218K

4、90K100K150K200K 220K530K分區(qū)號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存儲區(qū)時，選中的是5號分區(qū)，5號分區(qū)大小與申請空間大d,-致，應(yīng)從空閑分區(qū)表中刪去該表項；接著申請20K時，選中1號分區(qū)，分配后1號分區(qū)還剩下12K；最后申請200K，選中4號分區(qū)，分配后剩下18K。顯然采用最佳適應(yīng)算法進行內(nèi)存分配，可以滿足該作業(yè)序列的需求。為作業(yè)序列分配了內(nèi)存空間后，空閑

5、分區(qū)表如表5-3(a)所示。 若采用首次適應(yīng)算法，在申請96K存儲區(qū)時，選中的是4號分區(qū)，進行分配后4號分區(qū)還剩下122K；接著申請20K，選中1號分區(qū)，分配后剩下12K；最后申請200K，現(xiàn)有的五個分區(qū)都無法滿足要求，該作業(yè)等待。顯然采用首次適應(yīng)算法進行內(nèi)存分配，無法滿足該作業(yè)序列的需求。這時的空閑分區(qū)表如表53(b)所示。 分配后的空閑分區(qū)表(a)123412K10K5K18K100K150K200K 220K分區(qū)號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 6

6、0 6 5 20 6 5 6P2P3P4 (b)1234512K10K5K122K96K100K150K200K 220K530K分區(qū)號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、某采用段式存儲管理的系統(tǒng)為裝入主存的一個作業(yè)建立下表所示的段表 段表段號段長主存起始地址06602219114033002100903580123749601959回答下列問題：（1）計算該作業(yè)訪問0, 432, l, 10, 2, 500時（

7、方括號中第一元素為段號，第二元素為段內(nèi)地址）的絕對地址（2）總結(jié)段式存儲管理的地址轉(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é)段式存儲管理的地址轉(zhuǎn)換過程如下： 從邏輯地址中取出段號和段內(nèi)地址。 根據(jù)段號，從段表中取出該段在主存中的始址和段長。 比較段內(nèi)地址和段長，如段內(nèi)地址段長，則繼續(xù)下一步，否則產(chǎn)生越界中段，程序中斷(非法操作)。 計算本段始址+段內(nèi)地址，得到絕對地址。1.假設(shè)一個系統(tǒng)中有5個進程,它們的到達時間和服務(wù)時間如

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

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

10、801131.5 7.61.84SPF(搶占)完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間331.0015132.16841.0020142.801021.00 7.21.59 HRRF 完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間331.00971.171392.2520142.801573.5 82.14 RR(q=1) 完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間441.3318162.6717133.2520142.81573.5 10.82.71  3.在銀行家算法中，若出現(xiàn)下述資源分配情況： 進  程

11、AllocationNeedAvailableA  B  C  DA  B  C  DA  B  C  DP0P1P2P3P40  0  3  21  0  0  01  3  5  40  3  3

12、  20  0  1  40  0  1  21  7  5  02  3  5  60  6  5  20  6  5  61  6  2  2 試

13、問:（1)該狀態(tài)是否安全?(2)如果進程P2提出請求Request（0,2,2,2后,系統(tǒng)能否將資源分配給它?解:(1)利用銀行家算法對此時刻的資源分配情況進行分析,可得此時刻的安全性分析情況。 進 程WorkNeedAllocationWork+AllocationFinishA  B  C  DA  B  C  DA  B  C  D A  B  C&#

14、160; DP0P3P4P1P21  6  2  21  6  5  41  9  8  61  9  9  102  9  9  100  0  1  20  6  5  20&

15、#160; 6  5  61  7  5  02  3  5  60  0  3  20  3  3  20  0  1  41  0  0  01  3 &#

16、160;5  41  6  5  41  9  8  61  9  9  102  9  9  103  12  14  14truetruetruetruetrue 從上述分析中可以看出，此時存在一個安全序列P0,P3,P4,P1,P2,故該狀態(tài)是安全的。（2）P2提

17、出請求Request2(1,2,2,2),按銀行家算法進行檢查：     Request2(1,2,2,2)Need2(2,3,5,6)     Request2(1,2,2,2)Available(1,6,2,2)     試分配并修改相應(yīng)數(shù)據(jù)結(jié)構(gòu)，資源分配情況如下：進  程AllocationNeedAvailableA  B  C  DA  

18、B  C  DA  B  C  DP0P1P2P3P40  0  3  21  0  0  02  5  7  60  3  3  20  0  1  40  0 

19、60;1  21  7  5  01  1  3  40  6  5  20  6  5  60  4  0  0 再利用安全性算法檢查系統(tǒng)是否安全,可用資源Available (0,4,0,0)已不能滿足任何進程的需要,故系統(tǒng)進入不安全狀態(tài),此時系統(tǒng)不能將資源分配給P

20、2。 3某請求分頁系統(tǒng)，用戶空間為32KB，每個頁面1KB，主存16KB。某用戶程序有7頁長，某時刻該用戶進程的頁表如下：頁號物理塊號是否在TLB08是17是24否310否45否53是62是（1）計算兩個邏輯地址：0AC5H、1AC5H對應(yīng)的物理地址。（2）已知主存的一次存取為1.5us，對于TLB表（快表）的查詢時間可以忽略，則訪問上述兩個邏輯地址共耗費多少時間？答 （1） 每頁1kb代表頁內(nèi)偏移量為低地址10位，剩余的為頁號，所以0AC5H對應(yīng)的頁號為2，物理塊為4，說以物理地址為12C5H, 同理可得1AC5H對應(yīng)的物理地址為0AC5H.（2）耗時為1×1.5us+2

21、×1.5us=4.5us4什么叫重定位？它有哪兩種方式？這兩種方式有什么區(qū)別？ 由于經(jīng)過緊湊后的某些用戶程序在內(nèi)存中的位置發(fā)生了變化，此時若不對程序和數(shù)據(jù)的地址加以修改(變換)，則程序必將無法執(zhí)行。為此，在每次“緊湊”后，都必須對移動了的程序或數(shù)據(jù)進行重定位。5在具有快表的段頁式存儲管理方式中，如何實現(xiàn)地址變換？ 答：物理地址=該段在主存的起始地址+頁框號*大小+頁內(nèi)地址。第二次作業(yè)：1、 在某請求分頁管理系統(tǒng)中，一個作業(yè)共5頁，作業(yè)執(zhí)行時一次訪問如下頁面：1，4，3，1，2，5，1，4，2，1，4，5，若分配給該作業(yè)的主存塊數(shù)為3，分別采用FIFO，LRU，Clock頁面置換算法，

22、試求出缺頁中斷的次數(shù)及缺頁率。答 FIFO 缺頁次數(shù)為9，缺頁率為3/4LRU缺頁數(shù)為9，缺頁率為3/4Clock缺頁數(shù)為9，缺頁率為3/42、 某請求分頁管理系統(tǒng)，假設(shè)進程的頁表如下：頁號頁框號有效位裝入時間0101H12102254H14頁面大小為4KB，一次內(nèi)存的訪問時間為100納秒（ns），一次快表（TLB）的訪問時間是10ns，處理一次缺頁的平均時間為100毫秒（已含更新TLB和頁表的時間），進程的駐留集大小固定為2個頁框，采用FIFO法置換頁面。假設(shè)1）TLB初始為空；2）地址轉(zhuǎn)換時，先訪問TLB，若TLB未命中時再訪問頁表（忽略TLB更新時間）；3）有效位為0表示頁面不在內(nèi)存中。

23、請問：（1）該系統(tǒng)中，一次訪存的時間下限和上限各是多少？（給出計算過程）（2）若已經(jīng)先后訪問過0、2號頁面，則虛地址1565H的物理地址是多少？（給出計算過程）答（1）一次訪存時間下限10ns+100ns+100ns，上限10ns+100ns+100ms+100ns （2）基于上述訪問序列，當(dāng)訪問虛地址1565H時產(chǎn)生缺頁中斷，合法駐留集為2，必須從表中淘汰一個頁面，根據(jù)題目的置換算法，應(yīng)淘汰0號頁面，因此1565H的對應(yīng)頁框號為101H。由此可得1565H的物理地址為101565H3、設(shè)某計算機的邏輯地址空間和物理地址空間均為128KB，按字節(jié)編址。若某進程最多需要6頁數(shù)據(jù)存儲空間，頁面大小

24、為1KB，操作系統(tǒng)采用固定分配局部置換策略為該進程分配4個頁框（物理塊）。在時刻300前該進程各頁面的訪問情況如下表所示：頁號頁框號（塊號）裝入時間訪問位071301142301222001391801當(dāng)進程執(zhí)行到時刻300時，要訪問邏輯地址為17CAH的數(shù)據(jù)，請回答下列問題：（1）該邏輯地址對應(yīng)的頁號是多少？（2）若采用先進先出（FIFO）置換算法，該邏輯地址對應(yīng)的物理地址是多少？要求給出計算過程。（3）若采用時鐘（CLOCK）置換算法，該邏輯地址對應(yīng)的物理地址是多少？要求給出計算過程。設(shè)搜索下一頁的指針順時針方向移動，且當(dāng)前指向2號頁框，示意圖如下：17CAH=(0001 011

25、1 1100 1010)2（1）頁大小為1K，則頁內(nèi)偏移地址為10位，前6位是頁號，所以邏輯地址對應(yīng)的頁號為：5 （2）FIFO：被置換的頁面所在頁框為7，所以對應(yīng)的物理地址為（0001 1111 1100 1010）2=1FCAH （3）CLOCK：被置換的頁面所在頁框為2，所以對應(yīng)的物理地址為（0000 1011 1100 1010）2=0BCAH并有一下請求序列等待訪問磁盤：請求序列： 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9預(yù)訪問柱面號：150，50 ，178，167 ，87，

26、43 ，23 ，160 ，85試用最短尋找時間優(yōu)先算法和電梯調(diào)度算法，分別排出實際處理上述請求的次序第一題：序列（柱面號）最短尋找時間優(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(167)、3(178)、2(50)、6(43)、7(23)第二題：磁盤有199個磁道，當(dāng)前磁頭在54#磁道上，并向磁道號減小的方向上移動，現(xiàn)有一下請求序列等待訪問磁盤：請求序列 1 2 3 4 5 6 7 8 帶訪問的柱面號 99 184 38 123 15 125 66 6

27、8試用最短尋找時間優(yōu)先算法和電梯調(diào)度算法，分別排出實際處理上述請求的次序，并計算出他們的平均尋道長度 第二題：序列（柱面號）最短尋找時間優(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=29.5電梯調(diào)度算法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四、計算題1、假定在單CPU條件下有下列要執(zhí)行的作業(yè)：作業(yè)運行時間優(yōu)先級110224

28、3335 作業(yè)到來的時間是按作業(yè)編號順序進行的（即后面作業(yè)依次比前一個作業(yè)遲到一個時間單位）。 （1）用一個執(zhí)行時間圖描述在采用非搶占式優(yōu)先級算法時執(zhí)行這些作業(yè)的情況。（2）對于上述算法，各個作業(yè)的周轉(zhuǎn)時間是多少？平均周轉(zhuǎn)時間是多少？（3）對于上述算法，各個作業(yè)的帶權(quán)周轉(zhuǎn)時間是多少？平均帶權(quán)周轉(zhuǎn)時間是多少？1解： (1) 非搶占式優(yōu)先級算法（3分） 作業(yè)1 作業(yè)3 作業(yè)2 | | | | t 0 10 13 17 (2) 和（3）作業(yè)到達時間運行時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間101010101.021417164.032313113.7平均周轉(zhuǎn)時間12.3平均帶權(quán)周轉(zhuǎn)時間2.92、若后備作業(yè)

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