操作系統(tǒng)第五答案復習題及習題解答

1、虛擬內(nèi)存8.1 簡單分頁與虛擬分頁有什么區(qū)別？簡單分頁：一個程序中的所有的頁都必須在主存儲器中程序才能正常運行，除非使用覆蓋技術。虛擬內(nèi)存分頁：不是程序的每一頁都必須在主存儲器的幀中來使程序運行，頁在需要的時候進行讀取。8.2 解釋什么是抖動。虛擬內(nèi)存結構的震動現(xiàn)象，在這個過程中處理器大部分的時間都用于交換塊，而不是執(zhí)行指令。8.3 為什么在使用虛擬內(nèi)存時，局部性原理是至關重要的？可以根據(jù)局部性原理設計算法來避免抖動。總的來說，局部性原理允許算法預測哪一個當前頁在最近的未來是最少可能被使用的，并由此就決定候選的替換出的頁。8.4 哪些元素是頁表項中可以找到的元素？簡單定義每個元素。幀號：用來表

2、示主存中的頁來按順序排列的號碼。存在位（P）：表示這一頁是否當前在主存中。修改位（M）：表示這一頁在放進主存后是否被修改過。8.5 轉移后備緩沖器的目的是什么？轉移后備緩沖器（TLB）是一個包含最近經(jīng)常被使用過的頁表項的高速緩沖存儲器。它的目的是為了減少從磁盤中恢復一個頁表項所需的時間。8.6 簡單定義兩種可供選擇的頁讀取策略。在請求式分頁中，只有當訪問到某頁中的一個單元時才將該頁取入主存。在預約式分頁中，讀取的并不是頁錯誤請求的頁。8.7 駐留集管理和頁替換策略有什么區(qū)別？駐留集管理主要關注以下兩個問題：（1）給每個活動進程分配多少個頁幀。（2）被考慮替換的頁集是僅限在引起頁錯誤的進程的駐留

3、集中選擇還是在主存中所有的頁幀中選擇。頁替換策略關注的是以下問題：在考慮的頁集中，哪一個特殊的頁應該被選擇替換。8.8 FIFO和Clock頁替換算法有什么區(qū)別？時鐘算法與FIFO算法很接近，除了在時鐘算法中，任何一個使用位為一的頁被忽略。8.9 頁緩沖實現(xiàn)的是什么？（1）被替換出駐留集的頁不久又被訪問到時，仍在主存中，減少了一次磁盤讀寫。（2）被修改的頁以簇的方式被寫回，而不是一次只寫一個，這就大大減少了I/O操作的數(shù)目，從而減少了磁盤訪問的時間。8.10 為什么不可能把全局替換策略和固定分配策略組合起來？固定分配策略要求分配給一個進程的幀的數(shù)目是確定的，當一個進程中取入一個新的頁時，這個進

4、程的駐留頁集中的一頁必須被替換出來（保持分配的幀的數(shù)目不變），這是一種局部替換策略。8.11 駐留集和工作集有什么區(qū)別？一個進程的駐留集是指當前在主存中的這個進程的頁的個數(shù)。一個進程的工作集是指這個進程最近被使用過的頁的個數(shù)。8.12 請求式清除和預約式清除有什么區(qū)別？在請求式清除中，只有當一頁被選擇用于替換時才被寫回輔存；在預約式清除中，將這些被修改的多個頁在需要用到它們所占據(jù)的頁幀之前成批的寫回輔存。習題解答8.1 假設在處理器上執(zhí)行的進程的也表如下所示。所有數(shù)字均為十進制數(shù)，每一項都是從0開始記數(shù)的，并且所有的地址都是內(nèi)存字節(jié)地址。頁尺寸為1024個字節(jié)。虛擬頁號有效位訪問位修改位頁幀號

5、0110411117200031002400051010a 描述CPU產(chǎn)生的虛擬地址通常是如何轉化成一個物理主存地址的。b 下列虛擬地址對應于哪個物理地址（不用考略頁錯誤）？（i）1052 （ii）2221 （iii）5499解答a：由虛擬地址求得頁號和偏移量，用虛擬頁號作為索引頁表，得到頁幀號，聯(lián)系偏移量得到物理地址b:(i)1052=1024+28查表對應的頁幀號是7，因此物理地址為7*1024+28=7196(ii)2221=2*1024+173 此時出現(xiàn)頁錯誤(iii)5499=5*1024+379 對應的頁幀號為0 因此物理地址是3798.2 考慮一個使用32位的地址和1KB大小的頁

6、的分頁虛擬內(nèi)存系統(tǒng)。每個頁表項需要32位。需要限制頁表的大小為一個頁。a頁表一共需要使用幾級？b每一級頁表的大小是多少？提示：一個頁表的大小比較小。c在第一級使用的頁較小與在最底下一級使用的頁較小相比，那種策略使用最小個數(shù)的頁？解答a：虛擬內(nèi)存可以分為232/210= 222頁，所以需要22個bit來區(qū)別虛擬內(nèi)存中的一頁，每一個頁表可以包含210/4=28項，因此每個頁表可以包含22bit中的8個bit，所以需要三級索引。b：第二級頁表有28個頁表項，第一級頁表有26個頁表項。c：如果頂層有26個頁表項將會減少使用空間，在這種情況下，中間層頁表有26個并且每個都有28個頁表項，底層有214個頁

7、并且每個都有28個頁表項，因此共有1+26+214頁=16,449頁。如果中間層有26個頁表項，那么總的頁數(shù)有1+28+214頁=16,641頁。如果底層有26個頁表項，那么總的頁表數(shù)是1+28+216頁=65,973頁。8.3 a：圖8.4中的用戶表需要多少內(nèi)存空間？ b：假設需要設計一個哈希反向頁表來實現(xiàn)與圖8.4中相同的尋址機制，使用一個哈希函數(shù)來將20位頁號映射到6位哈希表。表項包含頁號幀號和鏈指針。如果頁表可以給每個哈希表項分配最多3個溢出項的空間，則哈希反向頁表需要占用多大的內(nèi)存空間？解答a：4Mbyteb：行數(shù)：26+2=128項。每項包含：20（頁號）+20（幀號）+8bits

8、（鏈索引）=48bits=6bytes。總共：128*6=768bytes8.4 一個進程分配給4個頁幀（下面的所有數(shù)字均為十進制數(shù)，每一項都是從0開始計數(shù)的）。上一次把一頁裝入到一個頁幀的時間，上一次訪問頁幀中的頁的時間，每個頁幀中的虛擬頁號以及每個頁幀的訪問位（R）和修改位（M）如下表所示（時間均為從進程開始到該事件之間的時鐘時間，而不是從事件發(fā)生到當前的時鐘值）。虛擬頁號頁幀加載時間訪問時間R位M位2060161011113016010022616210332016311當虛擬頁4發(fā)生錯誤時，使用下列內(nèi)存管理策略，哪一個頁幀將用于置換？解釋原因。a.FIFO（先進先出）算法b.LRU（最

9、近最少使用）算法c.Clock算法d.最佳（使用下面的訪問串）算法e.在頁錯誤之前給定上述內(nèi)存狀態(tài)，考慮下面的虛擬頁訪問序列： 4,0,0,2,4,2,1,0,3,2 如果使用窗口大小為4的工作集策略來代替固定分配，會發(fā)生多少頁錯誤？每個頁錯誤何時發(fā)生？解答a:頁幀3，在時間20加載，時間最長。b:頁幀1，在時間160訪問距現(xiàn)在時間最長。c:清除頁幀3的R位（最早加載），清除頁幀2的R位，（次最早加載），換出的是頁幀0因為它的R位為0。d:換出的是頁幀3中的虛擬頁3，因為它將最晚被訪問到。e:一共有6個錯誤，如下8.5 一個進程訪問5頁：A,B,C,D和E，訪問順序如下： A;B;C;D;A;

10、B;E;A;B;C;D;E假設置換算法為先進后出，該進程在主存中有三個頁幀，開始時為空，請查找在這個訪問順序中傳送的頁號。對于4個頁幀的情況，請重復上面的過程。解答分別有9次和10次頁錯誤，這被稱之為“Beladys現(xiàn)象”（An Anomaly in Space-Time Characteristics of Certain Programs Running in a Paging Machine, by Belady et al, Communications of the ACM, June 1969.）8.6 一個進程在磁盤上包含8個虛擬頁，在主存中固定分配給4個頁幀。發(fā)生如下順序的頁訪

11、問： 1,0,2,2,1,7,0,1,2,0,3,0,4,5,1,5,2,4,5,6,7,6,7,2,4,2,7,3,3,2,3a.如果使用LRU替換策略，給出相繼駐留在這4個頁幀中的頁。計算主存的命中率。假設這些幀最初是空的。b.如果使用FIFO策略，重復問題（a）。c.比較使用這兩種策略的命中率。解釋為什么這個特殊的訪問順序，使用FIFO的效率接近于LRU。解答a:LRU：命中率=16/33b:FIFO：命中率=16/33c:這兩種策略對這個特殊的頁軌跡（執(zhí)行順序）是等效的。8.7 在VAX中，用戶頁表以系統(tǒng)空間的虛擬地址進行定位。讓用戶頁表位于虛存而不是主存中有什么好處？有什么缺點？解答

12、最主要的優(yōu)點是在物理內(nèi)存空間上的節(jié)省。這主要是兩方面的原因：（1）一個用戶頁表可以僅當使用時才取入內(nèi)存。（2）操作系統(tǒng)可以動態(tài)的分配用戶頁表，產(chǎn)生一個頁表僅當程序被創(chuàng)建時。當然，也有一個缺點：地址轉換需要多余的工作。8.8 假設在主存中執(zhí)行下列程序語句： for(i=1;in;i+) ai=bi+ci;頁尺寸為1000個字。令n=1000。使用一臺具有所有寄存器指令并使用了索引寄存器的機器，寫出實現(xiàn)上述語句的一個假想程序，然后給出在執(zhí)行過程中的頁訪問順序。解答由機器語言編寫的程序，在主存中地址4000處開始運行。運行情況如下：4000 （R1）1 建立索引記錄i4001 （R1）n 在R2中建

13、立n4002 比較R2，R1 檢查in4003 如果大于則跳轉到40094004 （R3）B（R1） 使用索引記錄R1到達Bi4005 （R3）（R3）+C（R1）使用索引記錄R1加上Ci4006 A（R1）（R3）使用索引記錄R1將總和存入Ai中4007 （R1）（R1）+1 i加一4008 跳到400260006999 存儲A70007999 存儲B80008999 存儲C9000 存儲19001 存儲n由這個循環(huán)產(chǎn)生的參考串為494944（47484649444）1000包括11.000個參考，但僅包括5個不尋常的頁8.9 IBM System/370體系結構使用兩級存儲器結構，并且分別

14、把這兩級稱為段和頁，這里的分段方法缺少本章所描述的關于段的許多特征。對于這個基本的370體系結構，頁尺寸可以是2KB或4KB，段大小固定為64KB或1MB。這種方案缺少一般分段系統(tǒng)的那些優(yōu)點？370的分段方法有什么好處？解答S/370分段系統(tǒng)是固定的且對程序員是不可見的，因此沒有一個分段系統(tǒng)的優(yōu)點在S/370中實現(xiàn)（無保護情況下）每一個段表項的P位提供整個段表的保護。8.10 假設頁尺寸為4KB，頁表項大小位4字節(jié)。如果要映射一個64位地址空間，并且最頂層的頁表對應于一頁，則需要幾級頁表？解答因為每個頁表項有4bytes，每個頁表有4Kbytes，所以每個頁表可以映射1024=210個頁，標識

15、出210212=222bytes的地址空間。然而，地址空間是264bytes。增加一個二層頁表，頂層頁表指向210個頁表，標識出232個頁表，將這個過程繼續(xù)下去就得到：深度地址空間1222bytes2232bytes3242bytes4252bytes5262bytes6272bytes（264bytes）我們可以看到5層是不夠表示64位的地址空間，但是6層達到了要求。但是6層中只有2位被使用，而不是全部的10位。所以不是使用72位的虛擬地址空間，而是將除了最低兩位外的其他位全部屏蔽忽略。這樣將會得到一個64位地址空間，頂層頁只有4個頁表項。另外一種方法是修改規(guī)則將頂層頁做成一個單獨的物理頁并

16、且讓它適合4個頁。這樣將會節(jié)省一個頁。8.11 考慮一個系統(tǒng)該系統(tǒng)采用基于頁的內(nèi)存映射，并使用一級頁表。假設頁表總是在主存中。a.如果一次存儲器訪問需要200ns，那么一次需要調(diào)頁的存儲器訪問要多長時間？b.現(xiàn)在增加一個MMU，在命中或未命中時有20ns的開銷。如果假設有85%的存儲器訪問命中都在MMU TLB中，那么哪些是有效的存儲器訪問時間？c.解釋TLB命中率如何影響有效的存儲器訪問時間。解答a.400ns。200ns用來得到頁表項，200ns用來到達存儲位置b.這是一個常見的有效時間計算公式： （2200.85）+（4200.15）=250兩種情況：第一種，TLB中包含所需的頁表項。在

17、這種情況下在200ns外多了20ns的存儲訪問時間。第二種，TLB中不包含所需的頁表項。這時我們會再多花200ns來把所需的頁表項取入TLB。c.TLB命中率越高有效存儲器訪問時間就越短，因為額外的200ns來得到頁表項的時間被節(jié)省了。8.12 考慮一個進程的頁訪問序列，工作集為M幀，最初都是空的。頁訪問串的長度為P，包含N個不同的頁號。對任何一種頁替換算法，a.頁錯誤次數(shù)的下限是多少？b.頁錯誤次數(shù)的上限是多少？解答a.Nb.P8.13 在論述一種頁替換算法時，一位作者用一個在循環(huán)軌道上來回移動的雪犁機來模擬說明：雪均勻地落在軌道上，雪犁機一恒定的速度在軌道上不斷的循環(huán)，軌道上被掃落的雪從系

18、統(tǒng)中消失。a.8.2節(jié)討論的哪一種頁替換算法可以用它來模擬？b.這個模擬說明了頁替換算法的那些行為？解答a.這是一個很好的時鐘算法的類似。雪落在軌道上類似于頁到達循環(huán)頁緩存中。時鐘算法時鐘算法指針的移動類似于雪犁機的移動。b.注意到在時鐘指針最近的前面可替換頁的密度是最高的，就好像在雪犁機最近的前面的雪是最厚的一樣。因此我們可以認為時鐘算法在尋找替換頁時是非常有效的。事實上可以看到雪犁機前雪的厚度是軌道上雪平均厚度的兩倍。通過這種類似，在單循環(huán)中被時鐘策略替換的頁的號碼是被隨機替換的頁的號碼的兩倍。這個近似不是最完美的，因為時鐘指針并不是以一個確定的速率移動，但是直觀意義還是有的。8.14 在

19、S/370體系結構中，存儲關鍵字是與實存中每個頁幀相關聯(lián)的控制字段。這個關鍵字中與頁替換有關的有兩位：訪問位和修改位。當在幀中的任何單元執(zhí)行寫操作時，修改位被置為1；當一個新頁被裝入到該幀中時，訪問位被置為1。請給出一種方法，僅僅使用訪問位來確定哪個頁幀是最近最少使用的。解答處理器硬件置訪問位為0當一個新頁被加入到幀時，置為1當這個頁幀的位置被訪問到時。操作系統(tǒng)可以維護幾個頁幀表隊列，一個頁幀表項從一個隊列移動到另一個隊列取決于這個頁幀的訪問位被值為零的時間長短。當必須有頁被替換時，被替換的頁將從具有最長未被訪問時間的頁幀隊列中選取。8.15 考慮如下的頁訪問序列（序列中的每一個元素都是頁號）

20、：定義經(jīng)過k次訪問后平均工作集大小為Sk（）=1/kW（t，）（t=1k），并且定義經(jīng)過k次訪問后錯過頁的概率為Mk（）=1/kF（t，）（t=1k），其中如果頁錯誤發(fā)生在虛擬時間t，則F（t，）=1，否則F（t，）=0。a.當=1，2，3，4，5，6時，繪制與圖8.19類似的圖標來說明剛定義的頁訪問序列的工作集。b.寫出S20（）關于的表達式。b.寫出M20（）關于的表達式。解答a.b.c.S20是一個的增函數(shù)，M20是一個的非增函數(shù)。8.16 VSWS駐留集管理策略的性能關鍵是Q的值。經(jīng)驗表明，如果對于一個進程使用固定的的Q值，則在不同的執(zhí)行階段，頁錯誤發(fā)生的頻率有很大的差別。此外對不同的

21、進程使用相同的Q值，則發(fā)生頁錯誤的頻率會完全不同。這些差別表明，如果有一種機制可以在一個進程的生命周期中動態(tài)的調(diào)整Q得知，則會提高算法的性能。請基于這種目標設計一種簡單的機制。解答PIZZ89推薦使用如下策略。在窗口中使用一個機構在窗口時間調(diào)整Q的值作為實際頁錯誤率的函數(shù)，頁錯誤率被計算出并且同作為系統(tǒng)值的作業(yè)理想頁錯誤率比較。Q的值被上調(diào)（下調(diào)）當實際的頁錯誤率比理想值高（低）。使用這種調(diào)整機制的實驗證明可以動態(tài)調(diào)整Q值的測試作業(yè)在每次運行時產(chǎn)生較少的頁錯誤和減小的駐留集，相比于固定Q值的作業(yè)的運行（在很大程度上）。存儲時間在相對于Q值使用可調(diào)整機制時也會產(chǎn)生一個固定且可觀的改進，比較于使用固定的Q值。8.17 假設一個任務被劃分為4個大小相等的段，并且系統(tǒng)為每個