【正文】 也局限于某個區(qū)域 。 Operating System Page 91 2022/8/16 虛擬存儲器的基本概念 ?交換與覆蓋 ?虛擬存儲器的引入 ?虛擬存儲器的實現(xiàn)方法 ?虛擬存儲器的特征 Operating System Page 92 2022/8/16 虛擬存儲器的實現(xiàn)方法 ?虛擬存儲器的實現(xiàn)都是建立在 離散分配 的存儲管理方式基礎上的 ?主要有 ?請求分頁系統(tǒng) ?請求分段系統(tǒng) Operating System Page 93 2022/8/16 虛擬存儲器的基本概念 ?交換與覆蓋 ?虛擬存儲器的引入 ?虛擬存儲器的實現(xiàn)方法 ?虛擬存儲器的特征 Operating System Page 94 2022/8/16 虛擬存儲器的特征 虛擬存儲器最基本的特征是離散性，在此基礎上又形成了多次性及對換性的特征。于是可組合出以下三種適用的策略 ? 固定分配局部置換 (Fixed Allocation, Local Replacement) ? 可變分配全局置換 (Variable Allocation, Global Replacement) ? 可變分配局部置換 (Variable Allocation, Local Replacemen Operating System Page 101 2022/8/16 請求分頁存儲管理方式 ?請求分頁中的硬件支持 ?內存分配策略和分配算法 ?調頁策略 Operating System Page 102 2022/8/16 1. 何時調入頁面 2. 從何處調入頁面 3. 頁面調入過程 Operating System Page 103 2022/8/16 調頁策略 ?何時調入頁面 ?預調頁策略 ? 采用一種以預測為基礎的預調頁策略，將那些預計在不久之后便會被訪問的頁面預先調入內存，成功率 50% ?請求調頁策略 ? 當進程在運行中需要訪問某部分程序和數(shù)據(jù)時，若發(fā)現(xiàn)其所在的頁面不在內存，便提出請求，由 OS將其所需頁面調入內存 ? 目前的虛擬存儲中大多采用此種策略 Operating System Page 104 2022/8/16 2. 從何處調入頁面 在請求分頁系統(tǒng)中的外存分為兩部分： 通常 ， 由于對換區(qū)是采用連續(xù)分配方式 ， 而文件是采用離散分配方式 ， 故對換區(qū)的磁盤 I/O速度比文件區(qū)的高 。 此時 OS根據(jù)最佳置換算法 ， 將選擇頁面7予以淘汰 7 7 0 7 0 1 2 0 1 2 0 3 2 4 3 2 0 1 7 0 1 引用率 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 頁框 (物理塊） 2 0 3 利用最佳頁面置換算法時的置換圖 7 0 1 26次頁面置換 Operating System Page 109 2022/8/16 最佳置換算法和先進先出置換算法 ?先進先出 (FIFO) 選擇在內存中 駐留時間最長 的頁并淘汰之 7 7 0 7 0 1 2 0 1 2 3 1 4 3 0 0 1 3 7 0 2 2 3 0 4 2 0 4 2 3 0 2 3 0 1 2 7 1 2 7 0 1 頁框 引用率 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 1 利用 FIFO置換算法時的置換圖 12次頁面置換 Operating System Page 110 2022/8/16 頁面置換算法 ?最佳置換算法和先進先出置換算法 ?最近最久未使用（ LRU）置換算法 ?CLOCK置換算法 ?其它置換算法 Operating System Page 111 2022/8/16 最近最久未使用（ LRU）置換算法 ?LRU(Least Recently Used)置換算法的描述 選擇 最后一次訪問時間距離當前時間最長 的一頁并淘汰之。 為此，須利用以下兩類支持硬件： 1．移位寄存器： 定時右移 2．棧： 當進程訪問某頁時，將其移出壓入“棧頂”，“棧底”換出。 用于記錄本頁在一段時間內被訪問的次數(shù)，或最近已有多長時間未被訪問，提供給置換算法選擇換出頁面時參考。 （ 4）外存地址。 頁號 物理塊號 狀態(tài)位 P 訪問字段 A 修改位 M 外存地址 Operating System Page 118 2022/8/16 頁號 物理塊號 狀態(tài)位 P 訪問字段 A 修改位 M 外存地址 現(xiàn)對其中各字段說明如下： （ 1）狀態(tài)位 (存在位 )P。 （ 3）修改位 M。 用于指出該頁在外存上的地址，通常是物理塊號，供調入該頁時使用。 然后 重復第一步 ，如果仍失敗，必要時再重復第二步，此時就一定能找到被淘汰的頁 A = 0M = 0A = 0M = 1A = 1M = 0A = 1M = 1NN N換 出Operating System Page 120 2022/8/16 頁面置換算法 ?影響缺頁次數(shù)的因素 ? 分配給進程的 物理頁面數(shù) ? 頁面本身的 大小 ? 程序的 編制方法 ? 頁面 淘汰算法 Operating System Page 121 2022/8/16 頁面置換算法 ?性能問題 ?顛簸（抖動） 在虛存中，頁面在內存與外存之間 頻繁調度 ，以至于調度頁面所需時間比進程實際運行的時間還多，此時系統(tǒng)效率急劇下降，甚至導致系統(tǒng)崩潰。新進程啟動運行，導致缺頁，從其他進程中取幀，進行換入換出。 ? 如果頁面正在使用，它就落在工作集中；如果不再使用，它將不出現(xiàn)在相應的工作集中，所以，工作集是程序局部性的近似表示。 工作集頁面置換法 基本思想：找出一個不在工作集中的頁面，把它淘汰。 ?如果所有工作集之和增加以至于超過了可用內存塊的總數(shù)，則 OS就會選擇掛起一個進程，把它 的頁寫出去，將它的內存塊分配給其它其它進程。在該機制中規(guī)定：低編號的環(huán)具有高優(yōu)先權， OS核心處于 0環(huán)內；某些重要的實用程序和操作系統(tǒng)服務，占居中間環(huán)；而一般的應用程序，則被安排在外環(huán)上。 在環(huán)系統(tǒng)中，程序的訪問和調用應遵循以下規(guī)則： （ 1）一個程序可以訪問駐留在相同環(huán)或較低特權環(huán)中的數(shù)據(jù)； (內環(huán)可訪問外環(huán)數(shù)據(jù) ) （ 2）一個程序可以調用駐留在相同環(huán)或較高特權環(huán)中的服務。 (外環(huán)可請求內環(huán)服務 ) Operating System Page 135 2022/8/16 分段的共享與保護 環(huán)保護機構 調用 返回調用返回環(huán) 0環(huán) 1環(huán) 2( a ) 程序間的控制傳輸數(shù)據(jù)訪問環(huán) 0環(huán) 1環(huán) 2( b ) 數(shù)據(jù)訪問數(shù)據(jù)訪問Operating System Page 136 2022/8/16 。在該機制中規(guī)定：低編號的環(huán)具有高優(yōu)先權， OS核心處于 0環(huán)內；某些重要的實用程序和操作系統(tǒng)服務，占居中間環(huán)；而一般的應用程序，則被安排在外環(huán)上。 Operating System Page 133 2022/8/16 3. 分段保護 3）環(huán)保護機構 它是一種功能較完善的保護機構。 Operating System Page 126 2022/8/16 第四章 存儲器管理 ?程序的裝入和鏈接 ?連續(xù)分配方式 ?基本分頁存儲管理 ?基本分段存儲管理 ?虛擬存儲器的基本概念 ?請求分頁存儲管理方式 ?頁面置換算法 ?請求分段存儲管理方式 Operating System Page 127 2022/8/16 請求分段存儲管理方式 ?請求分段中的硬件支持 ?分段的共享與保護 Operating System Page 128 2022/8/16 請求分段中的硬件支持 ?段表機制 ?存取方式 用于標識本分段存取屬性是只執(zhí)行、只讀還是允許讀 /寫 ?存在位 P 用于指示該段是否已調入內存 ?訪問字段 A 用于記錄本頁在一段時間內被訪問的次數(shù)，或記錄本頁在最近多長時間未被訪問 ?修改位 M 表示該段在調入內存后是否被修改過 ?外存地址 本段在外存上的地址，盤塊塊號 ?增補位 本段在運行過程中是否做過動態(tài)增長 段名 段長 段的基址 存取方式 訪問字段 A 修改位M 存在位P 增補位 外存始址 Operating System Page 129 2022/8/16 請求分段中的硬件支持 虛段 S 不在內存阻塞請求進程內存中有合適的空閑區(qū)嗎？從外存讀入段 S修改段表及內存空區(qū)鏈喚醒請求進程返回空區(qū)容量總和能否滿足？空區(qū)拼接，以形成一個合適的空區(qū)淘汰一個或幾個實段，以形成一個合適空區(qū)否否是是 請求分段系統(tǒng)中的中斷處理過程 從中可以看出 ， 對缺段中斷的處理要比對缺頁中斷的處理復雜 ， 因為段是不定長的 。 ? OS監(jiān)視每個進程的工作集，并且給它分配工作集所需的內存塊。如果 ?太小，那么它不能包含整個局部；如果 ?為無窮大，那么工作集合是進程執(zhí)行所碰到的所有頁的集合。 ?利用工作集策略防止抖動 ?掛起某些進程： 優(yōu)先級低、缺頁進程、最大的進程等 Operating System Page 124 2022/8/16 系統(tǒng)顛簸（抖動） － 工作集（駐留集） ? 工作集 :就是一個進程在某一小段時間 ?內訪問頁面的集合。如此反復，使得整個系統(tǒng)的頁面替換非常頻繁，使大部分機器時間都用在來回進行的頁面調度上，這種局面稱為系統(tǒng)顛簸（ thrashing) ?結果： 缺頁率急劇增加，內存有效存取時間加長，系統(tǒng)吞吐量驟減；系統(tǒng)已基本不能完成什么任務。 在 第一次掃描期間不改變訪問位 A ? (2) 如果第一步失敗，即查找一周后未遇到第一類頁面， 則開始第二輪掃描， 尋找 A=0且 M=1的第二類頁面，將所遇到的第一個這類頁面作為淘汰頁。由于內存中的每一頁都在外存上保留一份副本，因此，若未被修改，在置換該頁時就不須將該寫回到外存上，以減少系統(tǒng)的開銷和啟動磁盤的次數(shù)；若已被修改，則必須將該頁重寫到外存上，以保證外存中所保留的始終是最新副本 。 （ 2）訪問字段 A。 Operating System Page 115 2022/8/16 Operating System Page 116 2022/8/16 Operating System Page 117 2022/8/16 2. 改進型 Clock置換算法 在將一個頁面換出時 ， 如果該頁已被修改過 ， 便須將它重新寫到磁盤上；但如果該頁未被修改過 ， 則不必將它拷回磁盤 。 表示該頁在調入內存后是否被修改過。 用于指示該頁是否調入內存，供程序訪問時參考。實現(xiàn)代價很高（時間戳或硬件方法） LRU頁面置換算法 引用率 7 0 7 7 0 1 7 0 1 2 2 0 1 0 3 2