1、操作系統(tǒng)教程(第三版)CH4應(yīng)用題參考答案3答：CH4應(yīng)用題參考答案頁框數(shù)FIFOLRUOPT31615114141085128769771 在一個請求分頁虛擬存儲管理系統(tǒng)中，一個程序運行的頁面走向是：1、2、3、4、2、1、5、6、2、1、2、3、7、6、3、2、1、2、3、6。分別用FIFO、OPT和LRU算法，對分配給程序 3個頁框、4個頁框、5個頁框和6個 頁框的情況下，分別求出缺頁中斷次數(shù)和缺頁中斷率。只要把表中缺頁中斷次數(shù)除以 20，便得到缺頁中斷率。2在一個請求分頁虛擬存儲管理系統(tǒng)中，一個作業(yè)共有5頁，執(zhí)行時其訪問頁面次序為：(1)1、4、3、1、2、5、1、4、2、1、4、5。

2、(2) 3、2、1、4、4、5、5、3、4、3、2、1、5。若分配給該作業(yè)三個頁框，分別采用FIFO和LRU面替換算法，求出各自的缺頁中斷次數(shù)和缺頁中斷率。答：(1)采用 FIFO 為 9 次，9/12=75%。采用 LRU 為 8 次，8/12=67%。(2)采用 FIFO 和 LRU 均為 9 次，9/13=69%。3 一個頁式存儲管理系統(tǒng)使用 FIFO、OPT和LRU頁面替換算法，如果一個作業(yè)的頁 面走向為：(1) 2、3、2、1、5、2、4、5、3、2、5、2。4、3、2、1、4、3、5、4、3、2、1、5。(3 )1、2、3、4、1、2、5、1、2、3、4、5。當分配給該作業(yè)的物理塊

3、數(shù)分別為3和4時，試計算訪問過程中發(fā)生的缺頁中斷次數(shù)和缺頁中斷率。答：(1)作業(yè)的物理塊數(shù)為 3塊，使用FIFO為9次，9/12=75%。使用LRU為7次， 7/12=58%。使用 OPT 為 6 次，6/12=50%。作業(yè)的物理塊數(shù)為 4塊，使用FIFO為6次，6/12=50%。使用LRU為6次， 6/12=50%。使用 OPT 為 5 次，5/12=42%。(2)作業(yè)的物理塊數(shù)為 3塊，使用FIFO為9次，9/12=75%。使用LRU為10次， 10/12=83%。使用 OPT 為 7 次，7/12=58%。作業(yè)的物理塊數(shù)為 4塊，使用FIFO為10次，10/12=83%。使用LRU為8

4、次，8/12=66%。使用 OPT 為 6 次，6/12=50%。其中，出現(xiàn)了 BeIady現(xiàn)象，增加分給作業(yè)的內(nèi)存塊數(shù)，反使缺頁中斷率上升4 在可變分區(qū)存儲管理下，按地址排列的內(nèi)存空閑區(qū)為：10K、4K、20K、18K、7K、9K、12K和15K。對于下列的連續(xù)存儲區(qū)的請求：（1）12K、10K、9K，（2）12K、10K、15K、18K試問：使用首次適應(yīng)算法、最佳適應(yīng)算法、最差適應(yīng)算法和下次適應(yīng)算法， 哪個空閑區(qū)被使用？答：（1）空閑分區(qū)如圖所示。分區(qū)號分區(qū)長110KB24KB320KB418KB57KB69KB712KB815KB1）首次適應(yīng)算法12KB選中分區(qū)3 ,這時分區(qū)3還剩8KB

5、。10KB選中分區(qū)1,恰好分配故應(yīng)刪去分 區(qū)1。9KB選中分區(qū)4,這時分區(qū)4還剩9KB。2）最佳適應(yīng)算法12KB選中分區(qū)7,恰好分配故應(yīng)刪去分區(qū) 7。10KB選中分區(qū)1，恰好分配故應(yīng)刪 去分區(qū)1。9KB選中分區(qū)6 ,恰好分配故應(yīng)刪去分區(qū) 6。3）最差適應(yīng)算法12KB選中分區(qū)3,這時分區(qū)3還剩8KB °10KB選中分區(qū)4,這時分區(qū)4還剩8KB C 9KB選中分區(qū)8,這時分區(qū)3還剩6KB。4）下次適應(yīng)算法12KB選中分區(qū)3 ,這時分區(qū)3還剩8KB。10KB選中分區(qū)4,這時分區(qū)4還剩8KB C 9KB選中分區(qū)6,恰好分配故應(yīng)刪去分區(qū) 6。（2）原始分區(qū)情況同上圖。1）首次適應(yīng)算法12KB選

6、中分區(qū)3 ,這時分區(qū)3還剩8KB。10KB選中分區(qū)1,恰好分配故應(yīng)刪去分 區(qū)1。15KB選中分區(qū)4,這時分區(qū)4還剩3KB。最后無法滿否18KB的申請，應(yīng)該 等待。2）最佳適應(yīng)算法12KB選中分區(qū)7,恰好分配故應(yīng)刪去分區(qū) 7。1OKB選中分區(qū)1,恰好分配故應(yīng)刪 去分區(qū)1。15KB選中分區(qū)8,恰好分配故應(yīng)刪去分區(qū) & 18KB選中分區(qū)4,恰好 分配故應(yīng)刪去分區(qū)4。3）最差適應(yīng)算法12KB選中分區(qū)3,這時分區(qū)3還剩8KB °1OKB選中分區(qū)4,這時分區(qū)4還剩8KB C 15KB選中分區(qū)8 ,恰好分配故應(yīng)刪去分區(qū) &最后無法滿否18KB的申請，應(yīng)該等 待。4）下次適應(yīng)算法12

7、KB選中分區(qū)3,這時分區(qū)3還剩8KB。IOKB選中分區(qū)4,這時分區(qū)4還剩8KB15KB選中分區(qū)8 ,恰好分配故應(yīng)刪去分區(qū) &最后無法滿否18KB的申請，應(yīng)該等 待。5 給定內(nèi)存空閑分區(qū)，按地址從小到大為：100K、500K、200K、300K和600K。現(xiàn)有用戶進程依次分別為 212K、417K、112K 和 426K，分別用 first-fit、best-fit 和 WOrSt-fit算法將它們裝入到內(nèi)存的哪個分區(qū)？(2)哪個算法能最有效利用內(nèi)存？答：按題意地址從小到大進行分區(qū)如圖所示。分區(qū)號分區(qū)長1100KB2500KB3200KB4300KB5600KB(1) 1)first-f

8、it 212KB選中分區(qū)2,這時分區(qū)2還剩288KB。417KB選中分區(qū)5,這 時分區(qū)5還剩183KB。112KB選中分區(qū)2,這時分區(qū)2還剩176KB。426KB無分區(qū) 能滿足，應(yīng)該等待。2) best-fit 212KB選中分區(qū)4,這時分區(qū)4還剩88KB。417KB選中分區(qū)2,這 時分區(qū)2還剩83KB。112KB選中分區(qū)3,這時分區(qū)3還剩88KB。426KB選中分 區(qū)5 ,這時分區(qū)5還剩174KB。3) worst-fit212KB選中分區(qū)5,這時分區(qū) 5還剩388KB。417KB選中分區(qū)2,這時分區(qū)2還剩83KB。112KB選中分區(qū)5,這時分區(qū)5還剩176KB。426KB無分 區(qū)能滿足，應(yīng)

9、該等待。 對于該作業(yè)序列，best-fit算法能最有效利用內(nèi)存6 一個32位地址的計算機系統(tǒng)使用二級頁表，虛地址被分為9位頂級頁表，11位二級頁表和偏移。試問：頁面長度是多少？虛地址空間共有多少個頁面？答：由于32-9-1仁12 ,所以，頁面大小為 4KB ,頁面的個數(shù)為220個。7 一進程以下列次序訪問 5個頁：A、B、C、D、A、B、E、A、B、C、D、E;假定 使用FlFo替換算法，在內(nèi)存有 3個和4個空閑頁框的情況下，分別給出頁面替換次 數(shù)。答：內(nèi)存有3個和4個空閑頁框的情況下，頁面替換次數(shù)為9次和10次。出現(xiàn)了 BeIady 現(xiàn)象，增加分給作業(yè)的內(nèi)存塊數(shù)，反使缺頁中斷率上升。8某計算

10、機有緩存、內(nèi)存、輔存來實現(xiàn)虛擬存儲器。如果數(shù)據(jù)在緩存中，訪問它需要 Ans;如果在內(nèi)存但不在緩存，需要BnS將其裝入緩存，然后才能訪問；如果不在內(nèi)存而在輔存，需要CnS將其讀入內(nèi)存，然后，用 BnS再讀入緩存，然后才能訪問。假 設(shè)緩存命中率為(n-1)n,內(nèi)存命中率為(m-1) m,則數(shù)據(jù)平均訪問時間是多少？答:操作系統(tǒng)教程（第三版）CH4應(yīng)用題參考答案數(shù)據(jù)在緩存中的比率為：(n-1)n數(shù)據(jù)在內(nèi)存中的比率為：(1-(n-1)/n) × (m-1)m=(m-1)nm數(shù)據(jù)在輔存中的比率為：(1-(n-1)/n) × (1-(m-1)m)=1nm故數(shù)據(jù)平均訪問時間是=(n-1)n

11、) × A+(1-(n-1)n) × (m-1)m) × (A+B)+( (1-(n-1)n) ×(1-(m-1)m) × (A+B+C)=A+Bn+Cnm9某計算機有cache、內(nèi)存、輔存來實現(xiàn)虛擬存儲器。如果數(shù)據(jù)在CaChe中，訪問它需要20ns；如果在內(nèi)存但不在cache，需要60ns將其裝入緩存，然后才能訪問；如果不 在內(nèi)存而在輔存，需要12ms將其讀入內(nèi)存，然后，用60ns再讀入cache,然后才能訪問。假設(shè)CaChe命中率為0.9，內(nèi)存命中率為0.6,則數(shù)據(jù)平均訪問時間是多少(ns)？答：506ns。10有一個分頁系統(tǒng)，其頁表存放在

12、主存里，(1)如果對內(nèi)存的一次存取要1.2微秒，試問實現(xiàn)一次頁面訪問的存取需花多少時間？(2)若系統(tǒng)配置了聯(lián)想存儲器，命中率為80 × %,假定頁表表目在聯(lián)想存儲器的查找時間忽略不計，試問實現(xiàn)一次頁面訪問的 存取時間是多少？答: (1)2.4 微秒 (2) 0.8 × 1.2+0.2 × 2.4=0.76+0.48=1.24 微秒11給定段表如下:段號段首址段長02196001230014290100313275804195296給定地址為段號和位移：1)0，430、2)3，400、3)1，1、4)2，500、5)4，42,試求出對應(yīng)的內(nèi)存物理地址。答：1)449

13、2)17273)23014)越界 5)199412某計算機系統(tǒng)提供24位虛存空間，主存為 218B ,采用分頁式虛擬存儲管理，頁面 尺寸為1KB。假定用戶程序產(chǎn)生了虛擬地址11123456 (八進制)，而該頁面分得塊號為100(A進制)，說明該系統(tǒng)如何產(chǎn)生相應(yīng)的物理地址及寫出物理地址。答：虛擬地址11123456 (八進制)轉(zhuǎn)化為二進制為：001 001 001 010 011 100 101 110其中前面為頁號，而后 10位為位移：001 001 001 010 011 100 101 110。由于主存大小為218B ,頁面尺寸為1KB ,所以，主存共有256塊。所以，塊號為100(八進制

14、)是 合法地址，于是，物理地址為100與位移1 100 101 110并接，得到：八進制物理地址100 1 100 101 110。13主存中有兩個空間區(qū)如圖所示,現(xiàn)有作業(yè)序列依次為:Job3要求50K;使用首次適應(yīng)、最壞適應(yīng)和最佳適應(yīng)算法處理這個作業(yè)序列，試問哪種算法可以滿足分配？為什么?答：首次適應(yīng)、最壞適應(yīng)算法處理這個作業(yè)序列可以滿足分配，最佳適應(yīng)算法不行。因 為后者會分割出無法使用的碎片，浪費內(nèi)存，從而，不能滿足所有作業(yè)的內(nèi)存需求。14 設(shè)有一頁式存儲管理系統(tǒng)，向用戶提供的邏輯地址空間最大為16頁，每頁2048字節(jié)，內(nèi)存總共有8個存儲塊。試問邏輯地址至少應(yīng)為多少位？內(nèi)存空間有多大？答：

15、邏輯地址211 × 24 ,故為15位。內(nèi)存大小為23× 211=214B=16KB。15在一分頁存儲管理系統(tǒng)中，邏輯地址長度為16位，頁面大小為 4096字節(jié)，現(xiàn)有一邏輯地址為 2F6AH ,且第0、1、2頁依次存在物理塊 10、12、14號中，問 相應(yīng)的物理地址為多少？答：因為邏輯地址長度為 16位，而頁面大小為 4096字節(jié)，所以，前面的 4位表示頁號。把 2F6AH 轉(zhuǎn)換成二進制為：0010 1111 0110 1010 ,可知頁號為 2。故放在14號物理塊中，寫成十六進制為：EF6AH。16 有矩陣：VAR A : ARRAY1 100,1 100 OF inte

16、ger;元素按行存儲。在一虛存系統(tǒng)中，采用LRU淘汰算法，一個進程有 3頁內(nèi)存空間，每頁可以存放200個整數(shù)。其中第1頁存放程序，且假定程序已在內(nèi)存。程序A:FOR i : = 1 To 100 DOFOR j : = 1 TO 100 DOAi,j ：= 0；程序B:FOR j : = 1 TO 100 DOFOR i : = 1 TO 100 DOAi,j ：= 0；分別就程序A和B的執(zhí)行進程計算缺頁次數(shù)。答：題中100× 100=10000個數(shù)據(jù)，每頁可以存放 200個整數(shù)，故一共存放在 50個 頁面中。由于元素按行存儲，第 1行、第2行放在第1頁，第99行、第100行 放在第

17、50頁。故對于程序 A ,缺頁中斷為50次。對于程序 B,缺頁中斷為5000次。17 一臺機器有48位虛地址和32位物理地址，若頁長為8KB ,問頁表共有多少個頁表項？如果設(shè)計一個反置頁表，則有多少個頁表項？答：因為頁長8KB占用13住，所以，頁表項有 235個。反置頁表項有 219個。18 在虛擬頁式存儲管理中，為解決抖動問題，可采用工作集模型以決定分給進程 的物理塊數(shù)，有如下頁面訪問序列： 2 5 1 6 3 3 7 8 9 1 6 2 3 4 3 4 3 4 4 4 3 4 4 3 II I丨1t1t2窗口尺寸厶=9,試求t1、t2時刻的工作集。答：t1時刻的工作集為：1 , 2, 3,

18、 6, 7, 8, 9。t時刻的工作集為：3 , 419有一個分頁虛存系統(tǒng)，測得CPU和磁盤的利用率如下，試指出每種情況下的存在問題和可采取的措施：（I）CPU利用率為13%,磁盤利用率為 97% （2）CPU利 用率為87% ,磁盤利用率為 3% （3）CPU利用率為13% ,磁盤利用率為 3%。答：（1）系統(tǒng)可能出現(xiàn)抖動，可把暫停部分進程運行。（2）系統(tǒng)運行正常，可增加運行進程數(shù)以進一步提高資源利用率。（3）處理器和設(shè)備和利用率均很低，可增加并發(fā)運行的進程數(shù)。20在一個分頁虛存系統(tǒng)中，用戶編程空間32個頁，頁長1KB ,主存為16KB。如果用戶程序有10頁長，若己知虛頁 0、1、2、3,已

19、分到頁框 8、7、4、10 , 試把虛地址0AC5H和1AC5H轉(zhuǎn)換成對應(yīng)的物理地址。答：虛地址0AC5H對應(yīng)的物理地址為：12C5H。而執(zhí)行虛地址 1AC5H會發(fā)現(xiàn)頁表 中尚未有分配的頁框而發(fā)生缺頁中斷，由系統(tǒng)另行分配頁框。21某計算機有4個頁框，每頁的裝入時間、最后訪問時間、訪問位R、修改位 D如下所示（時間用時鐘點數(shù)表示）：Pageloadedlast refRD012627900123026010212027211316028011分別用FIFO、LRU、二次機會算法分別淘汰哪一頁 答：（1）FlFO 淘汰 Page2。（2）LRU 淘汰 PageIO（3）二次機會淘汰page022考

20、慮下面的程序：for （i=0;i<20 ； i+）for（j=0;j<10;j+）ai: =ai × j試舉例說明該程序的空間局部性和時間局部性。7操作系統(tǒng)教程（第三版）CH4應(yīng)用題參考答案答：當數(shù)組元素a0, a1,，a19存放在一個頁面中時，其空間局部性和時間局 部性較好，也就是說，在很 短時間內(nèi)執(zhí)行都掛行循環(huán)乘法程序，而且數(shù)組元素分布在緊鄰連續(xù)的存儲單元中。當數(shù)組元素存放在不同頁面中時，其時間局部性雖相同，但空 間局部性較差，因為處理的數(shù)組元素分布在不連續(xù)的存儲單元中。23 一個有快表的請頁式虛存系統(tǒng)，設(shè)內(nèi)存訪問周期為1微秒，內(nèi)外存?zhèn)魉鸵粋€頁面的平均時間為5毫秒。

21、如果快表命中率為 75%,缺頁中斷率為10%。忽略快表訪問時間, 試求內(nèi)存的有效存取時間。答：快表命中率為75% ,缺頁中斷率為10% ,所以，內(nèi)存命中率為 15%。故內(nèi)存的有效存 取時間=1 × 75%+2 × 15%+（5000+2） × 10%=501.25 微秒。24 假設(shè)某虛存的用戶空間為1024KB ,頁面大小為4KB ,內(nèi)存空間為512KB。已知用戶的虛頁10、11、12、13頁分得內(nèi)存頁框號為 62、78、25、36,求出虛地址 OBEBC（16進 制）的實地址（16進制）是多少？答：虛地址0BEBC（16進制）的二進制形式為：0000 1011

22、1110 1011 1100。由于頁面大小為4KB ,故其中后12位是位移，所以，虛地址的頁號為：11。查頁表分得內(nèi)存對應(yīng)頁框號為：78。已知內(nèi)存空間為 512KB ,故內(nèi)存共有128個頁框，78是合法物理塊。把 78化為16進 制是4E ,虛地址 0BEBC（16進制）的實地址（16進制）是：4EEBC。25某請求分頁存儲系統(tǒng)使用一級頁表，假設(shè)頁表全部放在主存內(nèi)，：1）若一次訪問主存花120 ns,那么，訪問一個數(shù)據(jù)的時間是多少？2）若增加一個快表，在命中或失誤時需有20ns開銷，如果快表命中率為80% ,則訪問一個數(shù)據(jù)的時間為多少 ？答：1) 120ns× 2=240ns。2)

23、(120+20) × 80%+(120+120+20) × 20%=174ns。20k的作業(yè)J4要裝入26設(shè)某系統(tǒng)中作業(yè)J1 , J2, J3占用主存的情況如圖。今有一個長度為 主存，當采用可變分區(qū)分配方式時，請回答：（1） J4裝入前的主存已分配表和未分配表的內(nèi)容。 寫出裝入J4時的工作流程，并說明你采用什么分配算法。答：（1）主存已分配表共有三項，由作業(yè)J1、J2、J3占用，長度依次為：10k、30k和54k。未分配表共有三項：空閑區(qū)1、空閑區(qū)2和空閑區(qū)3,長度依次為18k、40k和70k。（2）作業(yè)J4裝入時，采用直接分配，搜索未分配表，空閑區(qū)1不能滿足。所以，要繼續(xù)搜索未分配表，空閑區(qū) 2可以滿足J4的裝入要求。27考慮下列的段表：段號始址02005001890302120100312506004180088對下面的邏輯地址，求物理地址，如越界請指明。1) <0,480> 2)V1,25> 3)<1,14> 4)<2,200>5) <3,500> 6)<4,100>。答：1)6802)9153)9044)越界 5)17506)越界。28請頁式