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

1、第四章第四章 存儲器管理存儲器管理趙恒趙恒 主講主講2定義：定義：在進程運行過程中，若其訪問的頁面不在內(nèi)存在進程運行過程中，若其訪問的頁面不在內(nèi)存而需將其調(diào)入，但內(nèi)存已無空閑空間時，需從而需將其調(diào)入，但內(nèi)存已無空閑空間時，需從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)，送入磁盤的對換內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)，送入磁盤的對換區(qū)。但應將哪個頁面調(diào)出，需根據(jù)一定的算法區(qū)。但應將哪個頁面調(diào)出，需根據(jù)一定的算法來確定。把選擇換出頁面的算法稱為頁面置換來確定。把選擇換出頁面的算法稱為頁面置換算法，其好壞直接影響系統(tǒng)的性能。算法，其好壞直接影響系統(tǒng)的性能。一個好的置換算法應具有較低的頁面更換頻率。一個好的置換算法應具有較低的

2、頁面更換頻率。從理論上講，應將那些以后不會再訪問的頁面從理論上講，應將那些以后不會再訪問的頁面換出，或者把那些在較長時間內(nèi)不會再訪問的換出，或者把那些在較長時間內(nèi)不會再訪問的頁面換出。頁面換出。5.3 頁面置換算法頁面置換算法3抖動（顫動）現(xiàn)象（抖動（顫動）現(xiàn)象（Thrashing）n請求頁式存儲管理系統(tǒng)中，若頁面置換算法請求頁式存儲管理系統(tǒng)中，若頁面置換算法不當，可能會導致下面的情形：剛被調(diào)出得不當，可能會導致下面的情形：剛被調(diào)出得頁面，不久又要訪問，因此要調(diào)入，調(diào)入后頁面，不久又要訪問，因此要調(diào)入，調(diào)入后不久又被淘汰，再訪問再調(diào)入，如此反復，不久又被淘汰，再訪問再調(diào)入，如此反復，整個系統(tǒng)的

3、頁面置換十分頻繁，整個系統(tǒng)的頁面置換十分頻繁，CPU時間主時間主要花費在頁面的交換上。這種導致系統(tǒng)效率要花費在頁面的交換上。這種導致系統(tǒng)效率急劇下降的現(xiàn)象稱為抖動現(xiàn)象。急劇下降的現(xiàn)象稱為抖動現(xiàn)象。n缺頁中斷率過高缺頁中斷率過高45.3 頁面置換算法頁面置換算法n頁面置換的過程頁面置換的過程（1）找出所需頁面在磁盤上的）找出所需頁面在磁盤上的位置；位置；（2）找出可用空閑內(nèi)存塊。如）找出可用空閑內(nèi)存塊。如果有，就立即使用，否則，就果有，就立即使用，否則，就進行頁面置換，選擇一個老的進行頁面置換，選擇一個老的頁面置換到外存磁盤。頁面置換到外存磁盤。（3）將所需頁面裝入內(nèi)存，修）將所需頁面裝入內(nèi)存，

4、修改相應的數(shù)據(jù)結構。改相應的數(shù)據(jù)結構。（4）繼續(xù)執(zhí)行用戶進程。）繼續(xù)執(zhí)行用戶進程。55.3 頁面置換算法頁面置換算法672. 2. 先進先出先進先出(FIFO)(FIFO)頁面置換算法頁面置換算法 （1）原理：）原理：該算法總是淘汰最先進入內(nèi)存的頁面，該算法總是淘汰最先進入內(nèi)存的頁面，即選擇即選擇在內(nèi)存中的駐留時間最久的頁面予以淘汰在內(nèi)存中的駐留時間最久的頁面予以淘汰。該算法實現(xiàn)簡單，只需把一個進程已調(diào)入內(nèi)存的該算法實現(xiàn)簡單，只需把一個進程已調(diào)入內(nèi)存的頁面，按先后次序鏈接成一個隊列，并設置一個頁面，按先后次序鏈接成一個隊列，并設置一個指針，稱為指針，稱為替換指針替換指針，使它總是指向最老頁面。

5、，使它總是指向最老頁面。8 （2）實現(xiàn)：實現(xiàn)：已調(diào)入內(nèi)存的頁面，按先后次序鏈接成一隊列。已調(diào)入內(nèi)存的頁面，按先后次序鏈接成一隊列。 （3）依據(jù)依據(jù): 先進入的可能已經(jīng)使用完畢。先進入的可能已經(jīng)使用完畢。 （4） 隨著物理塊數(shù)的增多缺頁率增大！隨著物理塊數(shù)的增多缺頁率增大?。˙elady現(xiàn)象）現(xiàn)象） 內(nèi)存內(nèi)存3個個物理塊：物理塊：內(nèi)存內(nèi)存4個個物理塊：物理塊：缺頁率缺頁率=9/12缺頁率缺頁率=10/12 Belady異常現(xiàn)象：異?，F(xiàn)象：一般而言，分配給進程的物理塊越多，運行時的缺頁次數(shù)應該越少。但是Belady在1969年發(fā)現(xiàn)了一個反例，使用FIFO算法時，四個物理塊時的缺頁次數(shù)比三個物理塊時

6、的多，這種反常的現(xiàn)象稱為Belady異常。舉例：設進程有舉例：設進程有5頁，訪問順序：頁，訪問順序：0，1，2，3，0，1，4，0， 1，2，3，4，分分3塊物理塊和塊物理塊和4塊物理塊時。塊物理塊時。 92.先進先出先進先出(FIFO)頁面置換算法頁面置換算法 10最近最久未使用置換算以最近最久未使用置換算以“最近的過去最近的過去”作為作為“不久不久將來將來”的近似的近似，選擇最近一段時間內(nèi)最久沒有使用的頁面淘汰，選擇最近一段時間內(nèi)最久沒有使用的頁面淘汰掉。它的實質是：當需要置換一頁時，選擇在掉。它的實質是：當需要置換一頁時，選擇在最近一段時間里最近一段時間里最久沒有使用過的頁面最久沒有使用

7、過的頁面予以淘汰予以淘汰 。11LRU的實現(xiàn)：把LRU算法作為頁面置換算法是比較好的，它對于各種類型的程序都能適用，但實現(xiàn)起來有相當大的難度，因為它要求系統(tǒng)具有較多的支持硬件。所要解決的問題有： 一個進程在內(nèi)存中的各個頁面各有多久時間未被進程訪問； 如何快速地知道哪一頁最近最久未使用的頁面。為此，須利用以下兩類支持硬件：1移位寄存器：移位寄存器：定時右移。2棧：棧：當進程訪問某頁時，將其移出壓入“棧頂”，“棧底”換出。12最近最久未使用（最近最久未使用（LRU）置換算法）置換算法LRU置換算法的硬件支持n寄存器w為了記錄某進程在內(nèi)存中各頁的使用情況，須為每個在內(nèi)存中的頁面配置一個移位寄存器，可

8、表示為 w訪問時將Rn-1位置成1，定時信號每隔一時間間隔右移一位，則具有最小數(shù)值的寄存器所對應的頁面，就是最近最久未使用的頁面。R=Rn-1Rn-2Rn-3 R2R1R0 13實頁實頁R7R6R5R4R3R2R1R0101010010210101100實頁實頁R7R6R5R4R3R2R1R010010100102010101100t0t1實頁實頁R7R6R5R4R3R2R1R010001010012001010110t2實頁實頁R7R6R5R4R3R2R1R0110010100200101011訪問訪問1實頁實頁R7R6R5R4R3R2R1R010100101002000101011t314

9、最近最久未使用（最近最久未使用（LRU）置換算法）置換算法n棧：進程訪問某頁時，將該頁面的頁號從棧中移出，再壓入棧頂。 用棧保存當前使用頁面時棧的變化情況用棧保存當前使用頁面時棧的變化情況 474074704170401741074210741207421074621074707101212615 【例】假定系統(tǒng)為某進程分配了3個物理塊，頁面訪問序列為：5、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、5、0、1。采用最近最久未使用置換算法，計算缺頁中斷次數(shù)和缺頁中斷率。 解：頁面置換過程如下表所示：頁面訪問序列50120304230321201501501203042303

10、212015015012030423032120150501223042203312015+-+-+-+-+-+-缺頁中斷次數(shù)缺頁中斷次數(shù)=12缺頁中斷率缺頁中斷率=12/20=60% 165.3.3 Clock置換算法置換算法 1. 簡單的簡單的Clock置換算法置換算法 利用Clock算法時，只須為每頁設置一位訪問位，在將內(nèi)存中的所有頁面都通過鏈接指針鏈成一個循環(huán)隊列。當某頁被訪問時，其訪問位被置1。置換算法在選擇一頁淘汰時，只須檢查其訪問位。 頁號頁號 物理塊號物理塊號 狀態(tài)位狀態(tài)位P 訪問字段訪問字段A 修改位修改位M外存地址外存地址 17頁號頁號 物理塊號物理塊號 狀態(tài)位狀態(tài)位P 訪

11、問字段訪問字段A 修改位修改位M外存地址外存地址 現(xiàn)對其中各字段說明如下：現(xiàn)對其中各字段說明如下：（1）狀態(tài)位）狀態(tài)位(存在位存在位)P。用于指示該頁是否調(diào)入內(nèi)存，供程序用于指示該頁是否調(diào)入內(nèi)存，供程序訪問時參考。訪問時參考。（3）修改位）修改位M。表示該頁在調(diào)入內(nèi)存后是否被修改過。由于內(nèi)表示該頁在調(diào)入內(nèi)存后是否被修改過。由于內(nèi)存中的每一頁都在外存上保留一份副本，因此，若未被修改，存中的每一頁都在外存上保留一份副本，因此，若未被修改，在置換該頁時就不須將該寫回到外存上，以減少系統(tǒng)的開銷和在置換該頁時就不須將該寫回到外存上，以減少系統(tǒng)的開銷和啟動磁盤的次數(shù)；若已被修改，則必須將該頁重寫到外存上，

12、啟動磁盤的次數(shù)；若已被修改，則必須將該頁重寫到外存上，以保證外存中所保留的始終是最新副本。以保證外存中所保留的始終是最新副本。（4）外存地址。）外存地址。用于指出該頁在外存上的地址，通常是物理塊用于指出該頁在外存上的地址，通常是物理塊號，供調(diào)入該頁時使用。號，供調(diào)入該頁時使用。18簡單的簡單的CLOCK置換算法（近似的置換算法（近似的LRU算法）算法） n當采用簡單的CLOCK算法時，只需為每頁設置一位訪問位，再將內(nèi)存中的所有頁面都通過鏈接指針鏈接成一個循環(huán)隊列。n當某頁被訪問時，其訪問位被置1。n置換算法在選擇一頁淘汰時，只需檢查頁的訪問位，是0換出，是1重新置0且暫不換出，再按FIFO檢查

13、下一個頁面。檢查到最后一個頁面，若其訪問位仍為1，則再返到隊首檢查。n由于該算法是循環(huán)地檢查各頁面的訪問情況，故稱為CLOCK算法，置換的是未使用過的頁，又稱為最近未用算法NRU（Not Recently Used）。19 簡單簡單Clock置換算法的流程和示例置換算法的流程和示例 入入口口查查尋尋指指針針前前進進一一步步，指指向向下下一一個個表表目目頁頁面面訪訪問問位位0? ?選選擇擇該該頁頁面面淘淘汰汰是是返返回回置置頁頁面面訪訪問問位位“0”否否塊塊號號頁頁號號訪訪問問位位指指針針0124034215650711替替換換指指針針注意：是循環(huán)注意：是循環(huán)隊列！隊列！20Page 20202

14、2-5-821Page 212022-5-8Operating SystemOperating SystemPage 222022-5-82. 改進型改進型Clock置換算法置換算法 在將一個頁面換出時，如果該頁已被修改過，便須將它重新寫到磁盤上；但如果該頁未被修改過，則不必將它拷回磁盤。同時滿足兩條件的頁面作為首選淘汰的頁。頁號頁號 物理塊號物理塊號 狀態(tài)位狀態(tài)位P 訪問字段訪問字段A 修改位修改位M外存地址外存地址 Operating SystemOperating SystemPage 232022-5-8頁號頁號 物理塊號物理塊號 狀態(tài)位狀態(tài)位P 訪問字段訪問字段A 修改位修改位M外存

15、地址外存地址 現(xiàn)對其中各字段說明如下：（1）狀態(tài)位(存在位)P。用于指示該頁是否調(diào)入內(nèi)存，供程序訪問時參考。（4）外存地址。用于指出該頁在外存上的地址，通常是物理塊號，供調(diào)入該頁時使用。Operating SystemOperating SystemPage 242022-5-8q改進型改進型Clock置換算法置換算法v考慮考慮使用情況使用情況和和置換代價，置換代價，換出的最好是未換出的最好是未使用且未被修改過的使用且未被修改過的v由由訪問位訪問位A和和修改位修改位M組合：組合：1類類(A=0, M=0)：表示該頁最近既未被表示該頁最近既未被訪問，又未被修改，是最佳淘汰頁訪問，又未被修改，是最

16、佳淘汰頁2類類(A=0, M=1)：表示該頁最近未被訪：表示該頁最近未被訪問，但已被修改，并不是很好的淘汰頁問，但已被修改，并不是很好的淘汰頁3類類(A=1, M=0)：最近已被訪問，但未：最近已被訪問，但未被修改，被修改， 該頁有可能再被訪問該頁有可能再被訪問4類類(A=1, M=1)：最近已被訪問且被修：最近已被訪問且被修改，該頁可能再被訪問改，該頁可能再被訪問Operating SystemOperating SystemPage 252022-5-8v其執(zhí)行過程可分成以下三步其執(zhí)行過程可分成以下三步(1) 從指針所指示的當前位置開始，從指針所指示的當前位置開始， 掃描循環(huán)隊掃描循環(huán)隊列

17、，列， 尋找尋找A=0且且M=0的第一類頁面，的第一類頁面， 將所遇到將所遇到的第一個頁面作為所選中的淘汰頁。的第一個頁面作為所選中的淘汰頁。 在在第一次掃第一次掃描期間不改變訪問位描期間不改變訪問位A。(2) 如果第一步失敗，即查找一周后未遇到第一類如果第一步失敗，即查找一周后未遇到第一類頁面，頁面， 則開始第二輪掃描，則開始第二輪掃描，尋找尋找A=0且且M=1的第的第二類頁面，將所遇到的第一個這類頁面作為淘汰頁。二類頁面，將所遇到的第一個這類頁面作為淘汰頁。在第二輪掃描期間，在第二輪掃描期間，將所有掃描過的頁面的訪問位將所有掃描過的頁面的訪問位A都置都置0。(3) 如果第二步也失敗，亦即未

18、找到第二類頁面，如果第二步也失敗，亦即未找到第二類頁面，則將則將指針返回到開始指針返回到開始的位置，并將的位置，并將所有的訪問位所有的訪問位A復復0。 然后然后重復第一步重復第一步，如果仍失敗，必要時再重，如果仍失敗，必要時再重復第二步，此時就一定能找到被淘汰的頁。復第二步，此時就一定能找到被淘汰的頁。Operating SystemOperating SystemPage 262022-5-8頁號頁號塊號塊號AM05001301210103111141411最佳淘汰頁最佳淘汰頁次佳淘汰頁次佳淘汰頁000275.3.4 其它置換算法其它置換算法選擇到當前時間為止選擇到當前時間為止被訪問次數(shù)最少

19、被訪問次數(shù)最少的頁面被置的頁面被置換；換；每頁設置每頁設置訪問計數(shù)器訪問計數(shù)器，每當頁面被訪問時，該頁，每當頁面被訪問時，該頁面的訪問計數(shù)器加面的訪問計數(shù)器加1 1；發(fā)生缺頁中斷時，淘汰計數(shù)值最小的頁面，并將發(fā)生缺頁中斷時，淘汰計數(shù)值最小的頁面，并將所有計數(shù)清零；所有計數(shù)清零；這種算法并不能真正反映出頁面的使用情況，因在每一時間這種算法并不能真正反映出頁面的使用情況，因在每一時間間隔內(nèi)只是用寄存器的一位來記錄頁的使用情況，因此訪問間隔內(nèi)只是用寄存器的一位來記錄頁的使用情況，因此訪問1次和次和10000次是等效的次是等效的282）頁面緩沖算法）頁面緩沖算法(PBA)q 被置換頁面的選擇和處理：被

20、置換頁面的選擇和處理：用用FIFO算法選擇被置算法選擇被置換頁。換頁。 如果頁面未被修改，就將其歸入到空閑頁面鏈如果頁面未被修改，就將其歸入到空閑頁面鏈表的末尾表的末尾 否則將其歸入到已修改頁面鏈表。否則將其歸入到已修改頁面鏈表。 此時頁面在內(nèi)存中并不做此時頁面在內(nèi)存中并不做物理上的移動物理上的移動，只是，只是將頁表中的表項移到上述兩鏈表之一將頁表中的表項移到上述兩鏈表之一29q 需要調(diào)入需要調(diào)入新的頁面新的頁面時，將時，將新頁面新頁面內(nèi)容讀入到內(nèi)容讀入到空閑空閑頁面鏈表的第一項頁面鏈表的第一項所指的頁面。所指的頁面。q 空閑頁面和已修改頁面，仍空閑頁面和已修改頁面，仍停留停留在內(nèi)存中一段時在

21、內(nèi)存中一段時間，如果這些頁面間，如果這些頁面被再次訪問被再次訪問，只需較小開銷，只需較小開銷，而被訪問的頁面可以而被訪問的頁面可以返還返還作為進程的內(nèi)存頁。作為進程的內(nèi)存頁。q 當當已修改頁面達到已修改頁面達到一定數(shù)目一定數(shù)目后，再將它們后，再將它們一起調(diào)一起調(diào)出出到外存，然后將它們歸入空閑頁面鏈表，這樣到外存，然后將它們歸入空閑頁面鏈表，這樣能大大能大大減少減少I/O操作的次數(shù)操作的次數(shù)。30頁面抖動（顛簸）的定義：頁面抖動（顛簸）的定義：在頁面置換過程中的一種最糟糕的情形是，剛剛換出的頁面馬上又要換入主存，剛剛換入的頁面馬上就要換出主存，這種頻繁的頁面調(diào)度行為稱為抖動，或顛簸。如果一個進程

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

23、要從工作集中被丟棄。為了防止系統(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)生重要影響。Operating SystemOperating Systemq段表機制段表機制v存取方式存取方式 用于標識本分段存取屬性是只執(zhí)行、只讀還用于標識本分段存取屬性是只

24、執(zhí)行、只讀還是允許讀是允許讀/寫寫v存在位存在位P 用于指示該段是否已調(diào)入內(nèi)存用于指示該段是否已調(diào)入內(nèi)存v訪問字段訪問字段A 用于記錄本頁在一段時間內(nèi)被訪問的次數(shù)，用于記錄本頁在一段時間內(nèi)被訪問的次數(shù)，或記錄本頁在最近多長時間未被訪問或記錄本頁在最近多長時間未被訪問v修改位修改位M 表示該段在調(diào)入內(nèi)存后是否被修改過表示該段在調(diào)入內(nèi)存后是否被修改過v外存地址外存地址 本段在外存上的地址，盤塊塊號本段在外存上的地址，盤塊塊號v增補位增補位 本段在運行過程中是否做過動態(tài)增長本段在運行過程中是否做過動態(tài)增長段名段名 段長段長 段的基址段的基址 存取方式存取方式 訪問字訪問字段段A 修改位修改位M 存在

25、位存在位P 增補位增補位 外存始外存始址址 Operating SystemOperating System虛段虛段S不在內(nèi)存不在內(nèi)存阻塞請求進程阻塞請求進程內(nèi)存中有合適內(nèi)存中有合適的空閑區(qū)嗎？的空閑區(qū)嗎？從外存讀入段從外存讀入段S修改段表及內(nèi)存空區(qū)鏈修改段表及內(nèi)存空區(qū)鏈喚醒請求進程喚醒請求進程返回返回空區(qū)容量總空區(qū)容量總和能否滿足？和能否滿足？空區(qū)拼接，以形成空區(qū)拼接，以形成一個合適的空區(qū)一個合適的空區(qū)淘汰一個或幾個實淘汰一個或幾個實段，以形成一個合適段，以形成一個合適空區(qū)空區(qū)否否否否是是是是 請求分段系統(tǒng)中的中斷處理過程請求分段系統(tǒng)中的中斷處理過程從中可以看出，對缺段中斷的從中可以看出，對

26、缺段中斷的處理要比對缺頁中斷的處理復處理要比對缺頁中斷的處理復雜，因為段是不定長的。雜，因為段是不定長的。Operating SystemOperating System3. 地址變換機構地址變換機構 請求分段系統(tǒng)中的地址變換機構，是在分段系統(tǒng)地請求分段系統(tǒng)中的地址變換機構，是在分段系統(tǒng)地址變換機構的基礎上形成的。因為被訪問的段并非址變換機構的基礎上形成的。因為被訪問的段并非全在內(nèi)存，因而在地址變換時，若發(fā)現(xiàn)所要訪問的全在內(nèi)存，因而在地址變換時，若發(fā)現(xiàn)所要訪問的段不在內(nèi)存時，必須先將所缺的段調(diào)入內(nèi)存，并修段不在內(nèi)存時，必須先將所缺的段調(diào)入內(nèi)存，并修改了段表之后，才能再利用段表進行地址變換。為改

27、了段表之后，才能再利用段表進行地址變換。為此，在地址變換機制中又增加了某些功能，如缺段此，在地址變換機制中又增加了某些功能，如缺段中斷的請求及其處理等。圖中斷的請求及其處理等。圖4-32示出了請求分段系示出了請求分段系統(tǒng)的地址變換過程。統(tǒng)的地址變換過程。 Operating SystemOperating System訪問訪問sww 段長?段長?符合存取方式?符合存取方式?段段S在主存?在主存?修改訪問字段,如寫修改訪問字段,如寫訪問,置修改位訪問,置修改位 1形成訪問主存地址形成訪問主存地址(A) (主存始址主存始址)(位移量位移量w)返回返回分段越界分段越界中斷處理中斷處理分段保護分段保護

28、中斷處理中斷處理缺段中缺段中斷處理斷處理是是是是是是否否否否否否 請求分段系統(tǒng)的地址變換過程請求分段系統(tǒng)的地址變換過程段號段號S段內(nèi)地址段內(nèi)地址WOperating SystemOperating Systemq共享段表共享段表v為了實現(xiàn)分段共享，可在系統(tǒng)中配置一張共為了實現(xiàn)分段共享，可在系統(tǒng)中配置一張共享段表所有各共享段都在共享段表中占有一享段表所有各共享段都在共享段表中占有一表項表項v共享進程計數(shù)共享進程計數(shù)count記錄有多少個進程需要共享該分段記錄有多少個進程需要共享該分段v存取控制字段存取控制字段對于一個共享段，應給不同的進程以不同對于一個共享段，應給不同的進程以不同的權限的權限v段

29、號段號對于一個共享段，不同的進程可以各用不對于一個共享段，不同的進程可以各用不同的段號去共享該段同的段號去共享該段Operating SystemOperating System段名段名段長段長內(nèi)存始址內(nèi)存始址狀態(tài)狀態(tài)外存始址外存始址共享進程計數(shù)共享進程計數(shù) count狀態(tài)狀態(tài) 進程名進程名進程號進程號段號段號存取控制存取控制共享段表共享段表Operating SystemOperating System4.8.2 分段的共享與保護分段的共享與保護 1. 共享段表共享段表 圖 4-33 共享段表項 段名段長內(nèi)存始址狀態(tài)外存始址共享進程計數(shù) count狀態(tài)進程名進程號段號存取控制共享段表非共享段

30、僅為一個進程所需要。當進程不再需要該段非共享段僅為一個進程所需要。當進程不再需要該段時，可立即釋放該段，并由系統(tǒng)回收該段所占用的空時，可立即釋放該段，并由系統(tǒng)回收該段所占用的空間。而共享段是為多個進程所需要的，當某進程因不間。而共享段是為多個進程所需要的，當某進程因不在需要而釋放它時，系統(tǒng)并不回收該段所占內(nèi)存區(qū)。在需要而釋放它時，系統(tǒng)并不回收該段所占內(nèi)存區(qū)。Operating SystemOperating System4.8.2 分段的共享與保護分段的共享與保護 1. 共享段表共享段表 圖 4-33 共享段表項 段名段長內(nèi)存始址狀態(tài)外存始址共享進程計數(shù) count狀態(tài)進程名進程號段號存取控制

31、共享段表對于同一個共享段，不同的進程可以使用不同的段號去共享該段。 Operating SystemOperating System4.8.2 分段的共享與保護分段的共享與保護 1. 共享段表共享段表 圖 4-33 共享段表項 段名段長內(nèi)存始址狀態(tài)外存始址共享進程計數(shù) count狀態(tài)進程名進程號段號存取控制共享段表對于一個共享段，應給不同的進程以不同的存取權限。 Operating SystemOperating Systemq共享段分配與回收共享段分配與回收v共享段的分配共享段的分配對第一個請求使用該共享段的進程，由系統(tǒng)為該共對第一個請求使用該共享段的進程，由系統(tǒng)為該共享段分配一物理區(qū)，再把

32、共享段調(diào)入該區(qū)，同時將享段分配一物理區(qū)，再把共享段調(diào)入該區(qū)，同時將該區(qū)的始址填入請求進程的段表的相應項中，還須該區(qū)的始址填入請求進程的段表的相應項中，還須在共享段表中增加一表項，填寫有關數(shù)據(jù)，把在共享段表中增加一表項，填寫有關數(shù)據(jù)，把count置為置為1；當又有其它進程需要調(diào)用該共享段時，無須再為該當又有其它進程需要調(diào)用該共享段時，無須再為該段分配內(nèi)存，而只需在調(diào)用進程的段表中，增加一段分配內(nèi)存，而只需在調(diào)用進程的段表中，增加一表項，填寫該共享段的物理地址；在共享段的段表表項，填寫該共享段的物理地址；在共享段的段表中，填上調(diào)用進程的進程名、存取控制等，再執(zhí)行中，填上調(diào)用進程的進程名、存取控制等

33、，再執(zhí)行count =count+1操作，以表明有兩個進程共享操作，以表明有兩個進程共享該段該段Operating SystemOperating Systemq分段保護分段保護v越界檢查越界檢查 v存取控制檢查存取控制檢查 只讀只讀 只執(zhí)行只執(zhí)行 讀讀/寫寫 v環(huán)保護機構環(huán)保護機構 低編號的環(huán)具有高優(yōu)先權，操作系統(tǒng)位于最核心低編號的環(huán)具有高優(yōu)先權，操作系統(tǒng)位于最核心環(huán)環(huán)一個程序可以訪問駐留在相同環(huán)或較低特權環(huán)中一個程序可以訪問駐留在相同環(huán)或較低特權環(huán)中的數(shù)據(jù)的數(shù)據(jù)一個程序可以調(diào)用駐留在相同環(huán)或較高特權環(huán)中一個程序可以調(diào)用駐留在相同環(huán)或較高特權環(huán)中的服務的服務Operating SystemO

34、perating SystemPage 432022-5-83. 分段保護分段保護 1）越界檢查 在段表寄存器中放有段表長度信息；同樣，在段表中也為每個段設置有段長字段。 在進行存儲訪問時，首先，將邏輯地址空間的段號段號與段表長度段表長度進行比較，如果段號等于或大于段表長度，將發(fā)出地址越界中斷信號； 其次，還要檢查段內(nèi)地址段內(nèi)地址是否等于或大于段長段長，若大于段長，將產(chǎn)生地址越界中斷信號，從而保證了每個進程只能在自己的地址空間內(nèi)運行。Operating SystemOperating SystemPage 442022-5-83. 分段保護分段保護 2）存取控制檢查 在段表的每個表項中，都設置

35、了一個“存取控制”字段，用于規(guī)定對該段的訪問方式。通常的訪問方式有： 只允許程序對該段中的程序或數(shù)據(jù)進行讀訪問； 只允許程序調(diào)用該段去執(zhí)行，但不準讀該段的內(nèi)容，也不允許對該段執(zhí)行寫操作； 允許程序對該段進行讀寫訪問。Operating SystemOperating SystemPage 452022-5-83. 分段保護分段保護 3）環(huán)保護機構 它是一種功能較完善的保護機構。在該機制中規(guī)定：低編號的環(huán)具有高優(yōu)先權，OS核心處于0環(huán)內(nèi)；某些重要的實用程序和操作系統(tǒng)服務，占居中間環(huán)；而一般的應用程序，則被安排在外環(huán)上。 在環(huán)系統(tǒng)中，程序的訪問和調(diào)用應遵循以下規(guī)則： （1）一個程序可以訪問駐留在相

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

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

38、留在相同環(huán)或較低特權環(huán)中的數(shù)據(jù)；的數(shù)據(jù)；( (內(nèi)環(huán)可訪問外環(huán)數(shù)據(jù)內(nèi)環(huán)可訪問外環(huán)數(shù)據(jù)) ) （2）一個程序可以調(diào)用駐留在相同環(huán)或較高特權環(huán)中）一個程序可以調(diào)用駐留在相同環(huán)或較高特權環(huán)中的服務。的服務。( (外環(huán)可請求內(nèi)環(huán)服務外環(huán)可請求內(nèi)環(huán)服務) ) Operating SystemOperating System 環(huán)保護機構環(huán)保護機構 調(diào)用調(diào)用返回返回調(diào)用調(diào)用返回返回環(huán)環(huán)0環(huán)環(huán)1環(huán)環(huán)2(a) 程序間的控制傳輸程序間的控制傳輸數(shù)據(jù)訪問數(shù)據(jù)訪問環(huán)環(huán)0環(huán)環(huán)1環(huán)環(huán)2(b) 數(shù)據(jù)訪問數(shù)據(jù)訪問數(shù)據(jù)訪問數(shù)據(jù)訪問49一進程剛獲得三個主存塊的使用權，若該進程訪一進程剛獲得三個主存塊的使用權，若該進程訪問頁面的次序

39、是問頁面的次序是1 3 2 1 2 1 5 1 2 3，當采用先進，當采用先進先出調(diào)度算法時，發(fā)生缺頁次數(shù)是先出調(diào)度算法時，發(fā)生缺頁次數(shù)是_次，而采次，而采用用LRU算法時，缺頁數(shù)是算法時，缺頁數(shù)是_次。次。A.1 B.3 C.4 D.5 E.6在請求分頁存儲管理系統(tǒng)中，設一個作業(yè)訪問頁在請求分頁存儲管理系統(tǒng)中，設一個作業(yè)訪問頁面的序列為面的序列為4 3 2 1 4 3 5 4 3 2 1 5，設分配給該作，設分配給該作業(yè)的存儲空間有業(yè)的存儲空間有4塊，且最初未裝入任何頁。試塊，且最初未裝入任何頁。試計算計算FIFO和和LRU算法的失頁率。算法的失頁率。50(1)采用采用FIFO頁面置換算法時

40、頁面置換算法時,該作業(yè)運行時缺頁情況如下表所示該作業(yè)運行時缺頁情況如下表所示:缺頁中斷次數(shù)為缺頁中斷次數(shù)為F=10; 失頁率為失頁率為f=10/12=83%。51(2)采用采用LRU頁面置換算法時頁面置換算法時,該作業(yè)運行時缺頁情況如下表所示該作業(yè)運行時缺頁情況如下表所示:缺頁中斷次數(shù)為缺頁中斷次數(shù)為F=8; 失頁率為失頁率為f=8/12=67%。52現(xiàn)有一請求調(diào)頁系統(tǒng)，其頁表保存在寄存器中?，F(xiàn)有一請求調(diào)頁系統(tǒng)，其頁表保存在寄存器中。若有一個可用的空頁或被替換的頁未被修改，若有一個可用的空頁或被替換的頁未被修改，則它處理一個缺頁中斷需要則它處理一個缺頁中斷需要8ms。若被替換頁。若被替換頁已被

41、修改，則處理一個缺頁中斷需要已被修改，則處理一個缺頁中斷需要20ms。內(nèi)。內(nèi)存存取時間為存存取時間為1us。假定。假定70%被替換頁被修改被替換頁被修改過，為保證有效存取時間不超過過，為保證有效存取時間不超過2us，可接受，可接受的最大缺頁中斷率是多少？的最大缺頁中斷率是多少？53參考答案：參考答案：設最大缺頁率為設最大缺頁率為p，則，則 0.3p8ms+0.7p 20ms+(1-p) 1us=2us2400p+14000p+1-p=2 (1ms=1000us)16399p=1 p=0.0000654補充：存儲保護補充：存儲保護在多道程序設計的環(huán)境下，系統(tǒng)中有系統(tǒng)在多道程序設計的環(huán)境下，系統(tǒng)中

42、有系統(tǒng)程序和程序和多個用戶程序多個用戶程序同時存在，如何保證同時存在，如何保證用戶程序不破壞系統(tǒng)程序，用戶程序之間用戶程序不破壞系統(tǒng)程序，用戶程序之間不相互干擾？不相互干擾？這就是這就是存儲保護存儲保護所要解決的問題。所要解決的問題。55n什么是存儲保護？什么是存儲保護？w把系統(tǒng)程序空間與用戶程序空間（由不同的用戶空間組成）分隔開來。w使多個用戶程序之間隔離，保證每道程序只能在給定的區(qū)域內(nèi)活動。常用的存儲保護有兩種：常用的存儲保護有兩種：用戶1用戶2用戶3OS系統(tǒng)空間用戶空間56120k下界寄存器下界寄存器130k上界寄存器上界寄存器程序程序120k130k0120k D 130k D 物理地

43、址物理地址存儲保護存儲保護 上下界保護上下界保護57存儲保護存儲保護 上下界保護上下界保護下界寄存器：存放程序裝入內(nèi)存后的開始地址（首址）上界寄存器 ：存放程序裝入內(nèi)存后的末地址判別式：下界寄存器 物理地址 上界寄存器58存儲保護存儲保護 基址、限長寄存器保護基址、限長寄存器保護例：例： 有一程序裝入內(nèi)存的首地址是有一程序裝入內(nèi)存的首地址是500，末地址是，末地址是1400，訪問內(nèi)存的邏輯地址是訪問內(nèi)存的邏輯地址是500、345、1000。 下界寄存器：下界寄存器：500 上界寄存器：上界寄存器：1400 邏輯地址裝入內(nèi)存的首地邏輯地址裝入內(nèi)存的首地 物理地址物理地址 1、500500 100

44、0 500 1000 1400 2、345500 845 500 845 1400 3、1000500 1500 500 1500 140059基址限長寄存器 120k 基址寄存器基址寄存器10k 限長寄存器限長寄存器程序程序120k130k0D 10k D 邏輯地址邏輯地址判別式：判別式：00邏輯地址邏輯地址 限長寄存器限長寄存器存儲保護存儲保護 基址、限長寄存器保護基址、限長寄存器保護60存儲保護存儲保護 基址、限長寄存器保護基址、限長寄存器保護例：有一程序裝入內(nèi)存的首地址是例：有一程序裝入內(nèi)存的首地址是500，末地址是，末地址是1400，訪問內(nèi)存的邏輯地址是訪問內(nèi)存的邏輯地址是500、3

45、45、1000。 限長寄存器：限長寄存器：900=1400-500 1、 0 500 900 2、 0 345 900 3、 0 1000 90061兩種存儲保護技術的區(qū)別兩種存儲保護技術的區(qū)別區(qū)別：區(qū)別：1、寄存器的設置不同；、寄存器的設置不同；2、判別式中用的判別條件不同、判別式中用的判別條件不同上下界寄存器保護法用的是上下界寄存器保護法用的是物理地址物理地址基址、限長寄存器保護法用的是程序的基址、限長寄存器保護法用的是程序的邏輯地址邏輯地址對于合法的訪問地址這兩者的效率是相同的，對不合法對于合法的訪問地址這兩者的效率是相同的，對不合法的訪問地址來說，上下界存儲保護浪費的的訪問地址來說，上

46、下界存儲保護浪費的CPU時間相對時間相對來說要多些。來說要多些。62華中科技大學華中科技大學2001某系統(tǒng)采用基址、限長寄存器防護方法顯現(xiàn)存儲保護，某系統(tǒng)采用基址、限長寄存器防護方法顯現(xiàn)存儲保護，在這些方法中判斷是否越界的判別式是：在這些方法中判斷是否越界的判別式是：A 0被訪問的物理地址被訪問的物理地址基址寄存器的內(nèi)容基址寄存器的內(nèi)容B 0被訪問的物理地址被訪問的物理地址基址寄存器的內(nèi)容基址寄存器的內(nèi)容C 0被訪問的邏輯地址被訪問的邏輯地址限長寄存器的內(nèi)容限長寄存器的內(nèi)容D 0被訪問的邏輯地址被訪問的邏輯地址限長寄存器的內(nèi)容限長寄存器的內(nèi)容答案：答案：C63小小 結結1、請求式分頁內(nèi)存管理方

47、式和、請求式分頁內(nèi)存管理方式和LRU內(nèi)存置換算法目前內(nèi)存置換算法目前在大型機、小型機和微機上流行的各種操作系統(tǒng)所采在大型機、小型機和微機上流行的各種操作系統(tǒng)所采用的內(nèi)存管理方式，學好它，對深入理解計算機系統(tǒng)用的內(nèi)存管理方式，學好它，對深入理解計算機系統(tǒng)結構，工作原理等都有重要的意義。結構，工作原理等都有重要的意義。2、通過學習請求分頁中的硬件支持，使同學們明晰了、通過學習請求分頁中的硬件支持，使同學們明晰了請求式分頁管理方式下頁表機制、缺頁機制和實現(xiàn)邏請求式分頁管理方式下頁表機制、缺頁機制和實現(xiàn)邏輯地址到物理地址的轉換方法。輯地址到物理地址的轉換方法。643、在內(nèi)存分配策略固定分配局部置換、可變分配全局、在內(nèi)存分配策略固定分配局部置換、可變分配全局置換、可變分配全局置換等三種策略，以及最優(yōu)置換置換、可變分配全局置換等三種策略，以及最優(yōu)置換算法、先進先出置換算法、最近最久未使用（算法、先進先出置換算法、最近最久未使用（L