【正文】 ation, 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ū)的高 。 為此，須利用以下兩類支持硬件： 1．移位寄存器： 定時右移 2．棧： 當進程訪問某頁時，將其移出壓入“棧頂”，“棧底”換出。 （ 4）外存地址。 （ 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就會選擇掛起一個進程，把它 的頁寫出去，將它的內存塊分配給其它其它進程。 在環(huán)系統(tǒng)中，程序的訪問和調用應遵循以下規(guī)則： （ 1）一個程序可以訪問駐留在相同環(huán)或較低特權環(huán)中的數(shù)據(jù)； (內環(huán)可訪問外環(huán)數(shù)據(jù) ) （ 2）一個程序可以調用駐留在相同環(huán)或較高特權環(huán)中的服務。在該機制中規(guī)定：低編號的環(huán)具有高優(yōu)先權， OS核心處于 0環(huán)內；某些重要的實用程序和操作系統(tǒng)服務，占居中間環(huán)；而一般的應用程序，則被安排在外環(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)中的中斷處理過程 從中可以看出 ， 對缺段中斷的處理要比對缺頁中斷的處理復雜 ， 因為段是不定長的 。如果 ?太小，那么它不能包含整個局部；如果 ?為無窮大，那么工作集合是進程執(zhí)行所碰到的所有頁的集合。如此反復，使得整個系統(tǒng)的頁面替換非常頻繁，使大部分機器時間都用在來回進行的頁面調度上，這種局面稱為系統(tǒng)顛簸（ thrashing) ?結果： 缺頁率急劇增加，內存有效存取時間加長，系統(tǒng)吞吐量驟減；系統(tǒng)已基本不能完成什么任務。由于內存中的每一頁都在外存上保留一份副本，因此，若未被修改，在置換該頁時就不須將該寫回到外存上，以減少系統(tǒng)的開銷和啟動磁盤的次數(shù)；若已被修改，則必須將該頁重寫到外存上，以保證外存中所保留的始終是最新副本 。 Operating System Page 115 2022/8/16 Operating System Page 116 2022/8/16 Operating System Page 117 2022/8/16 2. 改進型 Clock置換算法 在將一個頁面換出時 ， 如果該頁已被修改過 ， 便須將它重新寫到磁盤上；但如果該頁未被修改過 ， 則不必將它拷回磁盤 。 用于指示該頁是否調入內存，供程序訪問時參考。 文件區(qū) 對換區(qū) Operating System Page 105 2022/8/16 3. 頁面調入過程 頁面調入 頁面在內存 頁面未在內存 內存能容納新頁 內存已滿 該頁未被修改過 該頁已被修改 缺頁中斷 置換算法 寫回磁盤 Operating System Page 106 2022/8/16 第四章 存儲器管理 ?程序的裝入和鏈接 ?連續(xù)分配方式 ?基本分頁存儲管理 ?基本分段存儲管理 ?虛擬存儲器的基本概念 ?請求分頁存儲管理方式 ?頁面置換算法 ?請求分段存儲管理方式 Operating System Page 107 2022/8/16 頁面置換算法 ?最佳置換算法和先進先出置換算法 ?最近最久未使用（ LRU）置換算法 ?CLOCK置換算法 ?其它置換算法 Operating System Page 108 2022/8/16 最佳置換算法和先進先出置換算法 例：假定系統(tǒng)為某進程分配了三個物理塊 ， 并考慮有以下的頁面號引用串： 7， 0， 1， 2， 0， 3， 0， 4， 2， 3，0， 3， 2， 1， 2， 0， 1， 7， 0， 1進程運行時 ， 先將 7， 0，1三個頁面裝入內存 。 Operating System Page 90 2022/8/16 虛擬存儲器的引入 ?虛擬存儲器 定義 ?是指具有 請求調入功能 和 置換功能 ， 能從 邏輯上 對內存容量加以擴充的一種存儲器系統(tǒng) 。 第一次訪問 ，是訪問內存中的段表。 ? STORE 1,[B]|C。 若給定一個邏輯地址空間中的地址為 A， 頁面的大小為 L， 則頁號 P和頁內地址 d可按下式求得： 例如：其系統(tǒng)的頁面大小為 1KB， 設 A=2170B， 則由下式可以求得 P= ， d= 。 一般說來 ， 沒有硬件支持 ， 實現(xiàn)有效的存儲保護是困難的 。工作集。內存保護 ? 2. 交換與覆蓋 ? 3. 連續(xù)分配管理方式 ? 4. 非連續(xù)分配管理方式 ? 分頁管理方式 。 2022年新大綱 Operating System Page 4 2022/8/16 考查范圍與考查目標 ? 三、 內存管理 ? (二 ) 虛擬內存管理 ? 1. 虛擬內存基本概念 ? 2. 請求分頁管理方式 ? 3. 頁面置換算法 ? 最佳置換算法 (OPT)。根據(jù)回收區(qū)的位置，有四種情況需處理： ? 回收區(qū)與插入點的 前一個 空閑分區(qū)相鄰接 ? 回收區(qū)與插入點的 后一個 空閑分區(qū)相鄰接 ? 回收區(qū)同時與插入點的 前、后 兩個分區(qū)相鄰接 ? 回收區(qū)不與任何空閑區(qū)鄰接 Operating System Page 25 2022/8/16 動態(tài)分區(qū)分配 空閑區(qū) 回收區(qū) 回收區(qū) 空閑區(qū) 空閑區(qū) 回收區(qū) 空閑區(qū) 回收區(qū) 情況 1 情況 2 情況 3 情況 4 Operating System Page 26 2022/8/16 2) 回收內存 回收區(qū) F1 F2 回收區(qū) F2 回收區(qū) F1 回收區(qū) 回收區(qū) Operating System Page 27 2022/8/16 動態(tài)分區(qū)分配 ?碎片問題 ?經(jīng)過一段時間的分配回收后，內存中存在很多很小的空閑塊。如果一個進程對共享區(qū)域的訪問違反了權限規(guī)定，則發(fā)生操作越權 即讀寫保護 可重定位分區(qū)分配 Operating System Page 40 2022/8/16 ?保護鍵方式 可重定位分區(qū)分配 Operating System Page 41 2022/8/16 基本分頁存儲管理方式 連續(xù)分配方式會形成許多“碎片”，通過“緊湊”方法將碎片拼接成可用的大塊空間，但須為此付出很大開銷。 161。 段則是信息的邏輯單位 ， 它含有一組其意義相對完整的信息 。 由于它的基本原理與分頁及分段時的情況相似，故在此不再詳述。其所表現(xiàn)出來的最重要的特征是虛擬性。即淘汰沒有使用的時間最長的頁。 （ 3）修改位 M。 用于指示該頁是否調入內存，供程序訪問時參考。 Operating System Page 119 2022/8/16 CLOCK置換算法 ? ? (1) 從指針所指示的當前位置開始， 掃描循環(huán)隊列， 尋找 A=0且 M=0的第一類頁面， 將所遇到的第一個頁面作為所選中的淘汰頁。 Operating System Page 123 2022/8/16 系統(tǒng)顛簸（抖動） Thrashing ?防止系統(tǒng)顛簸 (抖動 )方法： ?采用局部置換策略： 如果一個進程出現(xiàn)抖動，它不能從另外的進程取幀、不會引發(fā)其它進程出現(xiàn)抖動，使抖動局限于一個小范圍內。 ?利用工作集模型可以防止抖動。 在環(huán)系統(tǒng)中，程序的訪問和調用應遵循以下規(guī)則： （ 1）一個程序可以訪問駐留在相同環(huán)或較低特權環(huán)中的數(shù)據(jù)； （ 2）一個程序可以調用駐留在相同環(huán)或較高特權環(huán)中的