操作系統(tǒng)第四章4

第四章存儲器管理趙恒主講定義：在進程運行過程中，若其訪問的頁面不在內(nèi)存而需將其調(diào)入，但內(nèi)存已無空閑空間時，需從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)，送入磁盤的對換區(qū)。但應(yīng)將哪個頁面調(diào)出，需根據(jù)一定的算法來確定。把選擇換出頁面的算法稱為頁面置換算法，其好壞直接影響系統(tǒng)的性能。一個好的置換算法應(yīng)具有較低的頁面更換頻率。從理論上講，應(yīng)將那些以后不會再訪問的頁面換出，或者把那些在較長時間內(nèi)不會再訪問的頁面換出。§5.3頁面置換算法抖動（顫動）現(xiàn)象（Thrashing）請求頁式存儲管理系統(tǒng)中，若頁面置換算法不當(dāng)，可能會導(dǎo)致下面的情形：剛被調(diào)出得頁面，不久又要訪問，因此要調(diào)入，調(diào)入后不久又被淘汰，再訪問再調(diào)入，如此反復(fù)，整個系統(tǒng)的頁面置換十分頻繁，CPU時間主要花費在頁面的交換上。這種導(dǎo)致系統(tǒng)效率急劇下降的現(xiàn)象稱為抖動現(xiàn)象。缺頁中斷率過高§5.3頁面置換算法頁面置換的過程（1）找出所需頁面在磁盤上的位置；（2）找出可用空閑內(nèi)存塊。如果有，就立即使用，否則，就進行頁面置換，選擇一個老的頁面置換到外存磁盤。（3）將所需頁面裝入內(nèi)存，修改相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。（4）繼續(xù)執(zhí)行用戶進程。§5.3頁面置換算法最佳置換算法（OPT，Optimal）：最佳置換算法置換那些以后永不再使用的或者在最長的時間以后才會用到的頁面。顯然，這種算法的缺頁率最低。然而，該算法只是一種理論上的算法，因為很難估計哪一個頁面是以后永遠不再使用或在最長時間以后才會用到的頁面，所以，這種算法是不能實現(xiàn)的。盡管如此，該算法仍然是有意義的，可以把它作為衡量其它算法優(yōu)劣的一個標(biāo)準(zhǔn)。⑴算法：淘汰永不使用的或是在最長時間內(nèi)不再被訪問的頁。⑵通?？杀ＷC獲得最低的缺頁率。⑶無實現(xiàn)價值，作為其它算法的衡量標(biāo)準(zhǔn)。1.最佳(Optimal)置換算法假定系統(tǒng)為某進程分配了三個物理塊，并考慮有以下的頁面號引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。1.最佳(Optimal)置換算法7F7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1引用序列缺頁標(biāo)志70F701F201F201203F203243F243243203F203203201F201201201701F701701缺頁9次，總訪問次數(shù)20次，缺頁率9/20＝45％2.先進先出(FIFO)頁面置換算法（1）原理：該算法總是淘汰最先進入內(nèi)存的頁面，即選擇在內(nèi)存中的駐留時間最久的頁面予以淘汰。該算法實現(xiàn)簡單，只需把一個進程已調(diào)入內(nèi)存的頁面，按先后次序鏈接成一個隊列，并設(shè)置一個指針，稱為替換指針，使它總是指向最老頁面。（2）實現(xiàn)：已調(diào)入內(nèi)存的頁面，按先后次序鏈接成一隊列。（3）依據(jù):

先進入的可能已經(jīng)使用完畢。（4）隨著物理塊數(shù)的增多缺頁率增大?。˙elady現(xiàn)象）

內(nèi)存3個物理塊：內(nèi)存4個物理塊：缺頁率=9/12缺頁率=10/12

Belady異?，F(xiàn)象：一般而言，分配給進程的物理塊越多，運行時的缺頁次數(shù)應(yīng)該越少。但是Belady在1969年發(fā)現(xiàn)了一個反例，使用FIFO算法時，四個物理塊時的缺頁次數(shù)比三個物理塊時的多，這種反常的現(xiàn)象稱為Belady異常。舉例：設(shè)進程有5頁，訪問順序：0，1，2，3，0，1，4，0，1，2，3，4，分3塊物理塊和4塊物理塊時。2.先進先出(FIFO)頁面置換算法7F7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1引用序列缺頁標(biāo)志70F701F201F201231F230F430F420F423F023F023023013F012F012012712F702F701F缺頁15次，總訪問次數(shù)20次，缺頁率15/20＝75％假定系統(tǒng)為某進程分配了三個物理塊，并考慮有以下的頁面號引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。5.3.2最近最久未使用(LRU)置換算法1.LRU(LeastRecentlyUsed)置換算法7F7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1引用序列缺頁標(biāo)志70F701F201F201203F203403F402F432F032F032032132F132102F102107F107107缺頁12次，總訪問次數(shù)20次，缺頁率12/20＝60％算法：最近最久未使用置換算以“最近的過去”作為“不久將來”的近似，選擇最近一段時間內(nèi)最久沒有使用的頁面淘汰掉。它的實質(zhì)是：當(dāng)需要置換一頁時，選擇在最近一段時間里最久沒有使用過的頁面予以淘汰。LRU的實現(xiàn)：把LRU算法作為頁面置換算法是比較好的，它對于各種類型的程序都能適用，但實現(xiàn)起來有相當(dāng)大的難度，因為它要求系統(tǒng)具有較多的支持硬件。所要解決的問題有：一個進程在內(nèi)存中的各個頁面各有多久時間未被進程訪問；如何快速地知道哪一頁最近最久未使用的頁面。為此，須利用以下兩類支持硬件：1．移位寄存器：定時右移。2．棧：當(dāng)進程訪問某頁時，將其移出壓入“棧頂”，“棧底”換出。最近最久未使用（LRU）置換算法LRU置換算法的硬件支持寄存器為了記錄某進程在內(nèi)存中各頁的使用情況，須為每個在內(nèi)存中的頁面配置一個移位寄存器，可表示為訪問時將Rn-1位置成1，定時信號每隔一時間間隔右移一位，則具有最小數(shù)值的寄存器所對應(yīng)的頁面，就是最近最久未使用的頁面。R=Rn-1Rn-2Rn-3…R2R1R0

實頁R7R6R5R4R3R2R1R0101010010210101100實頁R7R6R5R4R3R2R1R010010100102010101100t0t1實頁R7R6R5R4R3R2R1R010001010012001010110t2實頁R7R6R5R4R3R2R1R0110010100200101011訪問1實頁R7R6R5R4R3R2R1R010100101002000101011t3最近最久未使用（LRU）置換算法棧：進程訪問某頁時，將該頁面的頁號從棧中移出，再壓入棧頂。

用棧保存當(dāng)前使用頁面時棧的變化情況4740747041704017410742107412074210746210747071012126

【例】假定系統(tǒng)為某進程分配了3個物理塊，頁面訪問序列為：5、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、5、0、1。采用最近最久未使用置換算法，計算缺頁中斷次數(shù)和缺頁中斷率。解：頁面置換過程如下表所示：頁面訪問序列50120304230321201501501203042303212015015012030423032120150501223042203312015++++-+-++++--+-+-+--缺頁中斷次數(shù)=12缺頁中斷率=12/20=60%

5.3.3Clock置換算法1.簡單的Clock置換算法利用Clock算法時，只須為每頁設(shè)置一位訪問位，在將內(nèi)存中的所有頁面都通過鏈接指針鏈成一個循環(huán)隊列。當(dāng)某頁被訪問時，其訪問位被置1。置換算法在選擇一頁淘汰時，只須檢查其訪問位。頁號物理塊號狀態(tài)位P訪問字段A修改位M外存地址頁號物理塊號狀態(tài)位P訪問字段A修改位M外存地址現(xiàn)對其中各字段說明如下：（1）狀態(tài)位(存在位)P。用于指示該頁是否調(diào)入內(nèi)存，供程序訪問時參考。（2）訪問字段A。用于記錄本頁在一段時間內(nèi)被訪問的次數(shù)，或最近已有多長時間未被訪問，提供給置換算法選擇換出頁面時參考。（3）修改位M。表示該頁在調(diào)入內(nèi)存后是否被修改過。由于內(nèi)存中的每一頁都在外存上保留一份副本，因此，若未被修改，在置換該頁時就不須將該寫回到外存上，以減少系統(tǒng)的開銷和啟動磁盤的次數(shù)；若已被修改，則必須將該頁重寫到外存上，以保證外存中所保留的始終是最新副本。（4）外存地址。用于指出該頁在外存上的地址，通常是物理塊號，供調(diào)入該頁時使用。簡單的CLOCK置換算法（近似的LRU算法）當(dāng)采用簡單的CLOCK算法時，只需為每頁設(shè)置一位訪問位，再將內(nèi)存中的所有頁面都通過鏈接指針鏈接成一個循環(huán)隊列。當(dāng)某頁被訪問時，其訪問位被置1。置換算法在選擇一頁淘汰時，只需檢查頁的訪問位，是0換出，是1重新置0且暫不換出，再按FIFO檢查下一個頁面。檢查到最后一個頁面，若其訪問位仍為1，則再返到隊首檢查。由于該算法是循環(huán)地檢查各頁面的訪問情況，故稱為CLOCK算法，置換的是未使用過的頁，又稱為最近未用算法NRU（NotRecentlyUsed）。

簡單Clock置換算法的流程和示例注意：是循環(huán)隊列??！Page202023/2/1Page212023/2/1Page222023/2/12.改進型Clock置換算法在將一個頁面換出時，如果該頁已被修改過，便須將它重新寫到磁盤上；但如果該頁未被修改過，則不必將它拷回磁盤。同時滿足兩條件的頁面作為首選淘汰的頁。頁號物理塊號狀態(tài)位P訪問字段A修改位M外存地址Page232023/2/1頁號物理塊號狀態(tài)位P訪問字段A修改位M外存地址現(xiàn)對其中各字段說明如下：（1）狀態(tài)位(存在位)P。用于指示該頁是否調(diào)入內(nèi)存，供程序訪問時參考。（2）訪問字段A。用于記錄本頁在一段時間內(nèi)被訪問的次數(shù)，或最近已有多長時間未被訪問，提供給置換算法選擇換出頁面時參考。（3）修改位M。表示該頁在調(diào)入內(nèi)存后是否被修改過。由于內(nèi)存中的每一頁都在外存上保留一份副本，因此，若未被修改，在置換該頁時就不須將該寫回到外存上，以減少系統(tǒng)的開銷和啟動磁盤的次數(shù)；若已被修改，則必須將該頁重寫到外存上，以保證外存中所保留的始終是最新副本。（4）外存地址。用于指出該頁在外存上的地址，通常是物理塊號，供調(diào)入該頁時使用。Page242023/2/1CLOCK置換算法改進型Clock置換算法考慮使用情況和置換代價，換出的最好是未使用且未被修改過的由訪問位A和修改位M組合：1類(A=0,M=0)：表示該頁最近既未被訪問，又未被修改，是最佳淘汰頁2類(A=0,M=1)：表示該頁最近未被訪問，但已被修改，并不是很好的淘汰頁3類(A=1,M=0)：最近已被訪問，但未被修改，該頁有可能再被訪問4類(A=1,M=1)：最近已被訪問且被修改，該頁可能再被訪問Page252023/2/1CLOCK置換算法其執(zhí)行過程可分成以下三步(1)從指針?biāo)甘镜漠?dāng)前位置開始，掃描循環(huán)隊列，尋找A=0且M=0的第一類頁面，將所遇到的第一個頁面作為所選中的淘汰頁。在第一次掃描期間不改變訪問位A。(2)如果第一步失敗，即查找一周后未遇到第一類頁面，則開始第二輪掃描，尋找A=0且M=1的第二類頁面，將所遇到的第一個這類頁面作為淘汰頁。在第二輪掃描期間，將所有掃描過的頁面的訪問位A都置0。(3)如果第二步也失敗，亦即未找到第二類頁面，則將指針返回到開始的位置，并將所有的訪問位A復(fù)0。然后重復(fù)第一步，如果仍失敗，必要時再重復(fù)第二步，此時就一定能找到被淘汰的頁。Page262023/2/1改進型Clock置換算法-示例頁號塊號AM05001301210103111141411最佳淘汰頁次佳淘汰頁0005.3.4其它置換算法

1）最少使用(LFU：LeastFrequentlyUsed)置換算法選擇到當(dāng)前時間為止被訪問次數(shù)最少的頁面被置換；每頁設(shè)置訪問計數(shù)器，每當(dāng)頁面被訪問時，該頁面的訪問計數(shù)器加1；發(fā)生缺頁中斷時，淘汰計數(shù)值最小的頁面，并將所有計數(shù)清零；這種算法并不能真正反映出頁面的使用情況，因在每一時間間隔內(nèi)只是用寄存器的一位來記錄頁的使用情況，因此訪問1次和10000次是等效的2）頁面緩沖算法(PBA)被置換頁面的選擇和處理：用FIFO算法選擇被置換頁。如果頁面未被修改，就將其歸入到空閑頁面鏈表的末尾否則將其歸入到已修改頁面鏈表。此時頁面在內(nèi)存中并不做物理上的移動，只是將頁表中的表項移到上述兩鏈表之一需要調(diào)入新的頁面時，將新頁面內(nèi)容讀入到空閑頁面鏈表的第一項所指的頁面?？臻e頁面和已修改頁面，仍停留在內(nèi)存中一段時間，如果這些頁面被再次訪問，只需較小開銷，而被訪問的頁面可以返還作為進程的內(nèi)存頁。當(dāng)已修改頁面達到一定數(shù)目后，再將它們一起調(diào)出到外存，然后將它們歸入空閑頁面鏈表，這樣能大大減少I/O操作的次數(shù)。頁面抖動（顛簸）的定義：在頁面置換過程中的一種最糟糕的情形是，剛剛換出的頁面馬上又要換入主存，剛剛換入的頁面馬上就要換出主存，這種頻繁的頁面調(diào)度行為稱為抖動，或顛簸。如果一個進程在換頁上用的時間多于執(zhí)行時間，那么這個進程就在顛簸。

抖動的原因：

頻繁的發(fā)生缺頁中斷（抖動），其主要原因是某個進程頻繁訪問的頁面數(shù)目高于可用的物理頁幀數(shù)目。虛擬內(nèi)存技術(shù)可以在內(nèi)存中保留更多的進程以提髙系統(tǒng)效率。在穩(wěn)定狀態(tài)，幾乎主存的所有空間都被進程塊占據(jù)，處理機和操作系統(tǒng)可以直接訪問到盡可能多的進程。但如果管理不當(dāng)，處理機的大部分時間都將用于交換塊，即請求調(diào)入頁面的操作，而不是執(zhí)行進程的指令，這就會大大降低系統(tǒng)效率。工作集（駐留集）概念：工作集（或駐留集）是指在某段時間間隔內(nèi)，進程要訪問的頁面集合。經(jīng)常被使用的頁面需要在工作集中，而長期不被使用的頁面要從工作集中被丟棄。為了防止系統(tǒng)出現(xiàn)抖動現(xiàn)象，需要選擇合適的工作集大小。

工作集模型的原理：讓操作系統(tǒng)跟蹤每個進程的工作集，并為進程分配大于其工作集的物理塊。如果還有空閑物理塊，則可以再調(diào)一個進程到內(nèi)存以增加多道程序數(shù)。如果所有工作集之和增加以至于超過了可用物理塊的總數(shù)，那么操作系統(tǒng)會暫停一個進程，將其頁面調(diào)出并且將其物理塊分配給其他進程，防止出現(xiàn)抖動現(xiàn)象。

正確選擇工作集的大小，對存儲器的利用率和系統(tǒng)吞吐量的提嵩，都將產(chǎn)生重要影響。5.5請求分段存儲管理方式段表機制存取方式用于標(biāo)識本分段存取屬性是只執(zhí)行、只讀還是允許讀/寫存在位P

用于指示該段是否已調(diào)入內(nèi)存訪問字段A

用于記錄本頁在一段時間內(nèi)被訪問的次數(shù)，或記錄本頁在最近多長時間未被訪問修改位M

表示該段在調(diào)入內(nèi)存后是否被修改過外存地址本段在外存上的地址，盤塊塊號增補位本段在運行過程中是否做過動態(tài)增長段名段長段的基址存取方式訪問字段A修改位M存在位P增補位外存始址請求分段中的硬件支持

請求分段系統(tǒng)中的中斷處理過程從中可以看出，對缺段中斷的處理要比對缺頁中斷的處理復(fù)雜，因為段是不定長的。3.地址變換機構(gòu)請求分段系統(tǒng)中的地址變換機構(gòu)，是在分段系統(tǒng)地址變換機構(gòu)的基礎(chǔ)上形成的。因為被訪問的段并非全在內(nèi)存，因而在地址變換時，若發(fā)現(xiàn)所要訪問的段不在內(nèi)存時，必須先將所缺的段調(diào)入內(nèi)存，并修改了段表之后，才能再利用段表進行地址變換。為此，在地址變換機制中又增加了某些功能，如缺段中斷的請求及其處理等。圖4-32示出了請求分段系統(tǒng)的地址變換過程。請求分段中的硬件支持

請求分段系統(tǒng)的地址變換過程段號S段內(nèi)地址W分段的共享與保護共享段表為了實現(xiàn)分段共享，可在系統(tǒng)中配置一張共享段表所有各共享段都在共享段表中占有一表項共享進程計數(shù)count記錄有多少個進程需要共享該分段存取控制字段對于一個共享段，應(yīng)給不同的進程以不同的權(quán)限段號對于一個共享段，不同的進程可以各用不同的段號去共享該段分段的共享與保護段名段長內(nèi)存始址狀態(tài)外存始址共享進程計數(shù)count狀態(tài)進程名進程號段號存取控制………………共享段表4.8.2分段的共享與保護1.共享段表圖4-33共享段表項非共享段僅為一個進程所需要。當(dāng)進程不再需要該段時，可立即釋放該段，并由系統(tǒng)回收該段所占用的空間。而共享段是為多個進程所需要的，當(dāng)某進程因不在需要而釋放它時，系統(tǒng)并不回收該段所占內(nèi)存區(qū)。4.8.2分段的共享與保護1.共享段表圖4-33共享段表項對于同一個共享段，不同的進程可以使用不同的段號去共享該段。4.8.2分段的共享與保護1.共享段表圖4-33共享段表項對于一個共享段，應(yīng)給不同的進程以不同的存取權(quán)限。

分段的共享與保護共享段分配與回收共享段的分配對第一個請求使用該共享段的進程，由系統(tǒng)為該共享段分配一物理區(qū)，再把共享段調(diào)入該區(qū)，同時將該區(qū)的始址填入請求進程的段表的相應(yīng)項中，還須在共享段表中增加一表項，填寫有關(guān)數(shù)據(jù)，把count置為1；當(dāng)又有其它進程需要調(diào)用該共享段時，無須再為該段分配內(nèi)存，而只需在調(diào)用進程的段表中，增加一表項，填寫該共享段的物理地址；在共享段的段表中，填上調(diào)用進程的進程名、存取控制等，再執(zhí)行count∶=count+1操作，以表明有兩個進程共享該段分段的共享與保護分段保護越界檢查

存取控制檢查

只讀只執(zhí)行讀/寫環(huán)保護機構(gòu)

低編號的環(huán)具有高優(yōu)先權(quán)，操作系統(tǒng)位于最核心環(huán)一個程序可以訪問駐留在相同環(huán)或較低特權(quán)環(huán)中的數(shù)據(jù)一個程序可以調(diào)用駐留在相同環(huán)或較高特權(quán)環(huán)中的服務(wù)Page432023/2/13.分段保護1）越界檢查在段表寄存器中放有段表長度信息；同樣，在段表中也為每個段設(shè)置有段長字段。在進行存儲訪問時，首先，將邏輯地址空間的段號與段表長度進行比較，如果段號等于或大于段表長度，將發(fā)出地址越界中斷信號；其次，還要檢查段內(nèi)地址是否等于或大于段長，若大于段長，將產(chǎn)生地址越界中斷信號，從而保證了每個進程只能在自己的地址空間內(nèi)運行。Page442023/2/13.分段保護2）存取控制檢查在段表的每個表項中，都設(shè)置了一個“存取控制”字段，用于規(guī)定對該段的訪問方式。通常的訪問方式有：（1）只讀。只允許程序?qū)υ摱沃械某绦蚧驍?shù)據(jù)進行讀訪問；（2）只執(zhí)行。只允許程序調(diào)用該段去執(zhí)行，但不準(zhǔn)讀該段的內(nèi)容，也不允許對該段執(zhí)行寫操作；（3）讀/寫。允許程序?qū)υ摱芜M行讀寫訪問。Page452023/2/13.分段保護3）環(huán)保護機構(gòu)它是一種功能較完善的保護機構(gòu)。在該機制中規(guī)定：低編號的環(huán)具有高優(yōu)先權(quán)，OS核心處于0環(huán)內(nèi)；某些重要的實用程序和操作系統(tǒng)服務(wù)，占居中間環(huán)；而一般的應(yīng)用程序，則被安排在外環(huán)上。在環(huán)系統(tǒng)中，程序的訪問和調(diào)用應(yīng)遵循以下規(guī)則：（1）一個程序可以訪問駐留在相同環(huán)或較低特權(quán)環(huán)中的數(shù)據(jù)；（2）一個程序可以調(diào)用駐留在相同環(huán)或較高特權(quán)環(huán)中的服務(wù)。Page462023/2/13.分段保護3）環(huán)保護機構(gòu)它是一種功能較完善的保護機構(gòu)。在該機制中規(guī)定：低編號的環(huán)具有高優(yōu)先權(quán)，OS核心處于0環(huán)內(nèi)；某些重要的實用程序和操作系統(tǒng)服務(wù)，占居中間環(huán)；而一般的應(yīng)用程序，則被安排在外環(huán)上。在環(huán)系統(tǒng)中，程序的訪問和調(diào)用應(yīng)遵循以下規(guī)則：（1）一個程序可以訪問駐留在相同環(huán)或較低特權(quán)環(huán)中的數(shù)據(jù)；(內(nèi)環(huán)可訪問外環(huán)數(shù)據(jù))

（2）一個程序可以調(diào)用駐留在相同環(huán)或較高特權(quán)環(huán)中的服務(wù)。3.分段保護3）環(huán)保護機構(gòu)它是一種功能較完善的保護機構(gòu)。在該機制中規(guī)定：低編號的環(huán)具有高優(yōu)先權(quán)，OS核心處于0環(huán)內(nèi)；某些重要的實用程序和操作系統(tǒng)服務(wù)，占居中間環(huán)；而一般的應(yīng)用程序，則被安排在外環(huán)上。在環(huán)系統(tǒng)中，程序的訪問和調(diào)用應(yīng)遵循以下規(guī)則：（1）一個程序可以訪問駐留在相同環(huán)或較低特權(quán)環(huán)中的數(shù)據(jù)；(內(nèi)環(huán)可訪問外環(huán)數(shù)據(jù))

（2）一個程序可以調(diào)用駐留在相同環(huán)或較高特權(quán)環(huán)中的服務(wù)。(外環(huán)可請求內(nèi)環(huán)服務(wù))

分段的共享與保護

環(huán)保護機構(gòu)一進程剛獲得三個主存塊的使用權(quán)，若該進程訪問頁面的次序是{1321215123}，當(dāng)采用先進先出調(diào)度算法時，發(fā)生缺頁次數(shù)是___次，而采用LRU算法時，缺頁數(shù)是___次。A.1B.3C.4D.5E.6在請求分頁存儲管理系統(tǒng)中，設(shè)一個作業(yè)訪問頁面的序列為{432143543215}，設(shè)分配給該作業(yè)的存儲空間有4塊，且最初未裝入任何頁。試計算FIFO和LRU算法的失頁率。(1)采用FIFO頁面置換算法時,該作業(yè)運行時缺頁情況如下表所示:缺頁中斷次數(shù)為F=10;失頁率為f=10/12=83%。(2)采用LRU頁面置換算法時,該作業(yè)運行時缺頁情況如下表所示:缺頁中斷次數(shù)為F=8;失頁率為f=8/12=67%。現(xiàn)有一請求調(diào)頁系統(tǒng)，其頁表保存在寄存器中。若有一個可用的空頁或被替換的頁未被修改，則它處理一個缺頁中斷需要8ms。若被替換頁已被修改，則處理一個缺頁中斷需要20ms。內(nèi)存存取時間為1us。假定70%被替換頁被修改過，為保證有效存取時間不超過2us，可接受的最大缺頁中斷率是多少？參考答案：設(shè)最大缺頁率為p，則

0.3p×8ms+0.7p×20ms+(1-p)×1us<=2us2400p+14000p+1-p<=2(1ms=1000us)16399p<=1p<=0.00006補充：存儲保護在多道程序設(shè)計的環(huán)境下，系統(tǒng)中有系統(tǒng)程序和多個用戶程序同時存在，如何保證用戶程序不破壞系統(tǒng)程序，用戶程序之間不相互干擾？這就是存儲保護所要解決的問題。什么是存儲保護？把系統(tǒng)程序空間與用戶程序空間（由不同的用戶空間組成）分隔開來。使多個用戶程序之間隔離，保證每道程序只能在給定的區(qū)域內(nèi)活動。常用的存儲保護有兩種：用戶1用戶2用戶3OS系統(tǒng)空間用戶空間120k下界寄存器130k上界寄存器程序120k130k0120k≤D<130kD——物理地址

存儲保護——上下界保護存儲保護——上下界保護下界寄存器：存放程序裝入內(nèi)存后的開始地址（首址）上界寄存器：存放程序裝入內(nèi)存后的末地址判別式：下界寄存器≤

物理地址

＜上界寄存器存儲保護——基址、限長寄存器保護例：有一程序裝入內(nèi)存的首地址是500，末地址是1400，訪問內(nèi)存的邏輯地址是500、345、1000。

下界寄存器：500

上界寄存器：1400

邏輯地址＋裝入內(nèi)存的首地＝物理地址

1、500＋500＝1000500≤1000＜1400√2、345＋500＝845500≤845＜1400√

3、1000＋500＝1500500≤1500＜1400×基址限長寄存器

120k基址寄存器10k限長寄存器程序120k130k0D<10kD——邏輯地址判別式：0≤邏輯地址<限長寄存器存儲保護——基址、限長寄存器保護存儲保護——基址、限長寄存器保護例：有一程序裝入內(nèi)存的首地址是500，末地址是1400，訪問內(nèi)存的邏輯地址是500、345、1000。 限長寄存器：900=1400-5001、0≤500＜900√2、0≤345＜900√

3、0≤1000＜900×兩種存儲保護技術(shù)的區(qū)別區(qū)別：1、寄存器的設(shè)置不同；2、判別式中用的判別條件不同上下界寄存器保護法用的是物理地址基址、限長寄存器保護法用的是程序的邏輯地址對于合法的訪問地址這兩者的效率是相同的，對不合法的訪問地址來說，上下界存儲保護浪費的CPU時間相對來說要多些。華中科技大學(xué)2001某系統(tǒng)采用基址、限長寄存器防護方法顯現(xiàn)存儲保護，在這些方法中判斷是否越界的判別式是：A0≤被訪問的物理地址<基址寄存器的內(nèi)容B0≤被訪問的物理地址≤基址寄存器的內(nèi)容C0≤被訪問的邏輯地址<限長寄存器的內(nèi)容D0≤被訪問的邏輯地址≤限長寄