3.5 虛擬存儲技術(shù).ppt

3 5虛擬存儲器管理 為什么要引入虛擬存儲器 實存管理 必須為進程分配足夠的空間 裝入全部信息 即使對換 也是針對整個進程 一次性 駐留性 存在問題 進程運行時不用的 或暫時不用的 或某種條件下才用的程序和數(shù)據(jù) 全部駐留于主存是對寶貴的存儲資源的浪費 主存資源不夠用怎么辦 解決方法 部分裝入 部分替換 部分裝入 不必裝入進程的全部信息 僅將當前使用部分先裝入主存 其余部分存放在磁盤中 待使用時系統(tǒng)自動將其裝進來 當進程所訪問的程序和數(shù)據(jù)在主存時 可順利執(zhí)行 如果不在主存 系統(tǒng)自動將這部分信息從外存裝入內(nèi)存 請求調(diào)入功能 部分替換 如果沒有足夠的空閑物理空間 便把主存中暫時不用的信息移至磁盤 頁面置換功能 通過部分裝入和部分替換 當主存空間小于進程的需要量時 進程也能運行 當多個進程的總長超出主存總?cè)萘繒r 也可將進程全部裝入主存 實現(xiàn)多道程序運行所有這些 部分換入換出 對用戶完全是透明的 用戶編程時不必考慮物理空間的實際容量 允許用戶的邏輯地址空間大于主存物理地址空間 用戶感覺到的是比實際物理內(nèi)存大的多的主存 虛擬存儲器 虛擬存儲技術(shù)的思想 總結(jié) 將外存作為內(nèi)存的擴充 進程運行不需要將進程的全部信息放入內(nèi)存 將暫時將不運行的進程信息放在外存 通過內(nèi)存與外存之間的對換 使系統(tǒng)逐步將進程信息放入內(nèi)存 最終達到能夠運行整個進程 從邏輯上擴充內(nèi)存的目的 虛擬內(nèi)存實現(xiàn)基礎(chǔ) 局部性原理 早在1968年 Denning P就曾指出 1 順序性 程序執(zhí)行時 除了少部分的轉(zhuǎn)移和過程調(diào)用指令外 在大多數(shù)情況下仍是順序執(zhí)行的 2 局限性 過程調(diào)用將會使程序的執(zhí)行軌跡由一部分區(qū)域轉(zhuǎn)至另一部分區(qū)域 但經(jīng)研究看出 過程調(diào)用的深度在大多數(shù)情況下都不超過5 程序中還包括許多對數(shù)據(jù)結(jié)構(gòu)的處理 如對數(shù)組進行操作 它們往往都局限于很小的范圍內(nèi) 3 多次性 程序中存在許多循環(huán)結(jié)構(gòu) 這些雖然只由少數(shù)指令構(gòu)成 但是它們將多次執(zhí)行 4 獨立性 程序中有些部分彼此互斥 不是每次運行都用到 程序局部性原理 在一段時間內(nèi)一個程序的執(zhí)行往往呈現(xiàn)出高度的局部性 聚集成群 表現(xiàn)在時間與空間兩方面 一 時間局部性 一條指令被執(zhí)行了 則在不久的將來它可能再被執(zhí)行 指令在一定時間執(zhí)行 二 空間局部性 若某一存儲單元被使用 則在一定時間內(nèi) 與該存儲單元相鄰的單元可能被使用 程序使用一定的空間 虛擬內(nèi)存實現(xiàn)基礎(chǔ) 局部性原理 虛擬存儲器的定義 在具有層次結(jié)構(gòu)存儲器的計算機系統(tǒng)中 自動實現(xiàn)部分裝入和部分替換 單位是頁或段 功能 能從邏輯上為用戶提供一個比物理主存容量大的多的 可尋址的 主存儲器 對用戶隱蔽了可用物理存儲器的容量和具體操作細節(jié) 虛擬存儲器的組織形式 硬盤的這部分特殊區(qū)域稱作對換區(qū) 虛擬存儲器相關(guān)注意事項 支持虛存的物質(zhì)基礎(chǔ) 一定的主存 存放正在運行的一部分信息 一部分外存 作為主存的補充 地址變換機構(gòu) 以實現(xiàn)程序的虛地址向?qū)嵉刂返霓D(zhuǎn)換虛擬存儲器的容量 即給進程提供的邏輯地址空間 由CPU的地址長度決定 與實際內(nèi)存的大小沒有關(guān)系例如 如果計算機系統(tǒng)的地址為32位 則可尋址的范圍為0 4G 如果計算機系統(tǒng)的地址為20位 則可尋址的范圍為0 1M 計算機系統(tǒng)的可尋址范圍為虛擬存儲器的最大范圍 而物理內(nèi)存一般是小于虛擬存儲大小的 3 6請求分頁虛擬存儲管理 什么是請求分頁存儲管理 請求式分頁也稱虛擬頁式存儲管理 與純分頁存儲管理不同 請求式分頁管理系統(tǒng)在進程開始運行之前 不是裝入全部頁面 而是裝入一個或零個頁面 之后根據(jù)進程運行的需要 動態(tài)裝入其它頁面 當內(nèi)存空間已滿 而又需要裝入新的頁面時 則根據(jù)某種算法淘汰某個頁面 以便裝入新的頁面 基本原理 和頁式管理比較 1 首先 物理的內(nèi)存空間被劃分為等長的物理塊 并對塊編號 同時 用戶程序也進行分頁 這些與頁式存儲管理相同 2 在用戶程序開始執(zhí)行前 不將該程序的所有頁都一次性裝入內(nèi)存 而是先放在外存 當程序被調(diào)度投入運行時 系統(tǒng)先將少數(shù)頁裝入內(nèi)存 隨著程序運行 如果所訪問的頁在內(nèi)存中 則對其管理與分頁存儲管理情況相同3 若發(fā)現(xiàn)所要訪問的數(shù)據(jù)或指令不在內(nèi)存中 就會產(chǎn)生缺頁中斷 到外存尋找包含所需數(shù)據(jù)或指令的頁 并將其裝入到內(nèi)存的空閑塊中 4 在裝入一頁的過程中 若發(fā)現(xiàn)內(nèi)存無空閑塊或分配給該進程的物理塊已用完 則需要通過頁面置換功能從已在內(nèi)存的頁中挑選一個將其淘汰 釋放所占用的物理塊后將新的頁面裝入該塊 進程繼續(xù)運行 5 被淘汰的頁面如果剛才被修改過 則還需要將其回寫到外存 以保留其最新內(nèi)容 因此 請求分頁虛擬存儲管理與頁式存儲管理在許多地方相似 區(qū)別是增加了請求調(diào)頁 部分裝入 和頁面置換 部分替換 等功能 需要解決的問題 系統(tǒng)需要解決下面五個問題 1 需要提供一個全新的頁表機制來記錄任一頁是在內(nèi)存或在外存的位置 是否被修改過等信息 2 在請求分頁虛擬存儲管理方式下 內(nèi)存中允許裝入多個進程 每個進程占用一部分物理塊 問題在于 為每個進程分配多少個物理塊才合適 采用何種分配方式才合理 3 進程運行過程中發(fā)現(xiàn)所要訪問的數(shù)據(jù)或指令不在內(nèi)存時 便會產(chǎn)生缺頁中斷 到外存尋找該頁 此時 缺頁中斷如何處理 需要解決的問題 4 一個頁面或者是一開始就裝入內(nèi)存 或者是在運行中被動態(tài)的裝入內(nèi)存 如何進行地址重定位 5 在動態(tài)裝入一個頁面時 若發(fā)現(xiàn)內(nèi)存當前無空閑塊或分配給該進程的物理塊已經(jīng)用完 則需要從已在內(nèi)存的頁面中選出一個將其淘汰 問題在于 在什么范圍內(nèi)選擇要淘汰的頁面 淘汰哪個頁面 這就需要合適的頁面置換算法 請求分頁虛擬存儲管理的硬件支持 1 請求分頁的頁表機制2 缺頁中斷機構(gòu)3 地址轉(zhuǎn)換機構(gòu)4 請求分頁的硬件支撐 MMU 1 請求分頁的頁表機制 在虛擬存儲管理中 頁表除了要完成從邏輯地址到物理地址的轉(zhuǎn)換外 還需要提供頁面置換的相關(guān)信息 因此 頁表中除了有頁號和物理塊號等信息外 還增加了頁的狀態(tài)位 外存地址 修改位 訪問字段等信息 圖3 27頁式虛擬存儲管理的頁表 1 請求分頁的頁表機制 狀態(tài)位 用于標志一頁是否已裝入內(nèi)存 外存地址 頁在外存中的地址 修改位 頁在內(nèi)存中是否被修改過的標志 用來確定如果該頁被換出內(nèi)存時 是否需要再回寫入外存 訪問字段 標志頁在內(nèi)存時是否被訪問過 用于進行頁面置換時考慮是否將該頁換出內(nèi)存 如果該頁被訪問過 在進行頁面置換時 系統(tǒng)會考慮該頁可能以后會被再次訪問而不將其換出 2 缺頁中斷機構(gòu) 在進程運行過程中 當發(fā)現(xiàn)所訪問的頁不在內(nèi)存時 缺頁中斷機構(gòu)便產(chǎn)生一個缺頁 Pagefault 中斷信號 操作系統(tǒng)接到此信號后 就運行缺頁中斷處理程序 將所需要的頁調(diào)入內(nèi)存 缺頁中斷與一般中斷類似 都需要經(jīng)歷保護CPU環(huán)境 分析中斷原因 轉(zhuǎn)入中斷程序處理 中斷處理后恢復(fù)CPU環(huán)境等步驟 2 缺頁中斷機構(gòu) 但缺頁中斷與一般中斷也有不同 1 CPU檢測中斷的時間不同 對一般的中斷信號 CPU是在一條指令執(zhí)行完后檢測其是否存在 檢測時間以一個指令周期為間隔 而對缺頁中斷信號 CPU在一條指令執(zhí)行期間 只要有中斷信息就可檢測 不需要等待一個指令周期 因此 CPU檢測缺頁中斷更及時 2 CPU可以多次處理 如果在一個指令周期中多次檢測到缺頁中斷 CPU都會及時處理 3 地址轉(zhuǎn)換機構(gòu) 請求分頁虛擬存儲技術(shù)是在程序執(zhí)行過程中逐步將程序頁面調(diào)入內(nèi)存的 所以從邏輯地址到物理地址的轉(zhuǎn)換是在程序運行過程中完成的 是動態(tài)重定位裝入 4 請求分頁的硬件支撐 MMU 請求分頁存儲管理需要底層硬件的支撐來完成 即MMU 主存管理部件 負責(zé)地址轉(zhuǎn)換和存儲保護MMU由一組集成電路芯片組成 邏輯地址作為輸入 物理地址作為輸出 直接送達總線 4 請求分頁的硬件支撐 MMU MMU的主要功能 1 管理硬件頁表基址寄存器 2 分解邏輯地址 3 管理快表 4 訪問頁表 5 發(fā)出相應(yīng)中斷 6 管理特征位 請求分頁存儲管理地址變換流程 當進程調(diào)度到CPU上運行時 操作系統(tǒng)自動把此進程PCB中的頁表起始地址裝入硬件頁表基址寄存器進程開始運行 訪問某個虛地址 MMU工作 1 MMU接收CPU傳送過來的邏輯地址并自動按頁面大小把它從某位起分解成頁號和頁內(nèi)位移 2 以頁號為索引查找TLB 請求分頁存儲管理地址變換流程 3 快表不命中 就搜索頁表 4 如果在頁表中找到此頁面 相應(yīng)駐留位為1 送出頁框號 與頁內(nèi)位移拼接成物理地址 并進行訪問權(quán)限檢查 通過即可訪問 并把頁面信息裝入快表 5 如果發(fā)現(xiàn)頁表中的對應(yīng)頁面失效即發(fā)生缺頁中斷 MMU發(fā)出缺頁中斷后就停止工作 由內(nèi)核存儲管理 操作系統(tǒng) 軟件 接收控制 處理缺頁中斷 請求分頁存儲管理地址變換流程 內(nèi)核存儲管理處理缺頁中斷的過程 1 根據(jù)頁號搜索外頁表 找到存放此頁的磁盤物理地址 2 查看主存是否有空閑頁框 如果有則找出 修改主存管理表和相應(yīng)頁表 轉(zhuǎn)5 3 如果主存無空閑頁框 按照替換算法選擇淘汰頁面 檢查其是否被寫過或修改過 若否轉(zhuǎn)5 若是則轉(zhuǎn)44 淘汰頁面被寫過或修改過 將其內(nèi)容寫回磁盤的原先位置5 進行調(diào)頁 把頁面裝入主存所分配的頁框中 同時修改進程頁表項6 返回進程斷點 重新啟動被中斷的指令 查快表 有登記 無登記 查頁表 登記入快表 發(fā)缺頁中斷 在主存 在輔存 形成絕對地址 繼續(xù)執(zhí)行指令 重新執(zhí)行被中斷指令 恢復(fù)現(xiàn)場 調(diào)整頁表和主存分配表 裝入所需頁面 主存有空閑塊 保護現(xiàn)場 有 選擇調(diào)出頁面 該頁是否修改 未修改 已修改 把該頁寫回輔存相應(yīng)位置 操作系統(tǒng) 硬件 邏輯地址 無 請求頁式虛擬存儲系統(tǒng)優(yōu)缺點 優(yōu)點 作業(yè)的程序和數(shù)據(jù)可按頁分散存放在主存中 減少移動開銷 有效解決了碎片問題 既有利于改進主存利用率 又有利于多道程序運行 缺點 要有硬件支持 要進行缺頁中斷處理 機器成本增加 系統(tǒng)開銷加大 這些開銷主要包括 用于地址變換和各種數(shù)據(jù)結(jié)構(gòu)的存儲開銷 執(zhí)行地址變換指令的時間開銷 內(nèi)存與外存之間對換頁面的I O開銷等 3 6 3頁面分配策略與頁面調(diào)度算法 3 6 3頁面分配策略與頁面調(diào)度算法 請求分頁虛擬存儲管理支持多個進程同時裝入內(nèi)存 操作系統(tǒng)為各個進程分別分配部分物理塊 并將各自的部分頁調(diào)入內(nèi)存 在實施中涉及到以下三個策略 1 頁面分配策略 分配策略決定系統(tǒng)應(yīng)該給一個進程分配多少物理塊 進程才能運行 2 頁面調(diào)入策略 頁面調(diào)入策略決定如何將進程所需要的頁面調(diào)入到內(nèi)存 3 頁面置換策略 頁面置換策略決定內(nèi)存中的哪些頁面被換出內(nèi)存 1 頁面分配策略 系統(tǒng)為進程分配主存 需考慮因素 分給進程的空間越小 同一時間處于主存的進程就越多 至少有一個進程處于就緒態(tài)的可能性就越大 如果進程只有小部分在主存里 即使局部性很好 缺頁中斷率還會相當高 因程序的局部性原理 分給進程的主存超過一定限度后 再增加主存空間 不會明顯降低進程的缺頁中斷率 頁面分配策略 固定分配 為每個進程分配固定數(shù)量的物理塊 其數(shù)量在進程創(chuàng)建時 由進程的類型 交互性 批處理或應(yīng)用性 或根據(jù)用戶的要求確定 在進程的整個運行期間都不再改變 具體的分配方式包括 按進程平均分配法 進程按比例分配法和進程優(yōu)先權(quán)分配法等 頁面分配策略 可變分配 可變分配方式是指分配給進程的物理塊數(shù) 在該進程的運行期間可以動態(tài)變化 它用來解決由于事先分配給進程的物理塊太少而導(dǎo)致的頻繁缺頁問題 具體實現(xiàn)時 先為每一進程分配必要數(shù)量的物理塊 使之可以開始運行 系統(tǒng)中余下的空閑物理塊組成一個空閑物理塊隊列 當某一進程在運行過程中發(fā)生缺頁時 系統(tǒng)從空閑物理塊隊列中取出一個空閑塊分配給該進程 只要該空閑隊列中還有物理塊 凡發(fā)生缺頁的進程都可以才該隊列中申請并獲得物理塊 頁面分配策略 可變分配 進程執(zhí)行的某階段缺頁率較高 說明目前局部性較差 系統(tǒng)可多分些頁框以降低缺頁率 反之說明進程目前的局部性較好 可減少分給進程的物理塊數(shù) 2 頁面調(diào)入策略 頁面裝入主存 有兩種策略 1 請求頁調(diào)入 2 預(yù)先頁調(diào)入 1 請求頁調(diào)入策略 請求頁調(diào)入簡稱請調(diào) 是指在CPU需要訪問進程某頁面時 發(fā)現(xiàn)所訪問的頁面不在內(nèi)存 CPU發(fā)出缺頁中斷信號 請求將該頁調(diào)入內(nèi)存 操作系統(tǒng)接收到缺頁中斷請求后 為之分配物理塊并從外存將該頁調(diào)入內(nèi)存 每個進程在剛開始執(zhí)行時 所需的頁面很多 會產(chǎn)生多次缺頁中斷 頁面被逐一調(diào)入內(nèi)存 根據(jù)程序的局部性原理 當進程運行一段時間后 所需要的頁面會逐步減少 缺頁中斷次數(shù)會逐漸下降 最后趨向于很低的水平 進程運行進入相對平穩(wěn)階段 1 請求頁調(diào)入策略 優(yōu)點 只有在需要時才將頁面調(diào)入內(nèi)存 節(jié)省了內(nèi)存空間 缺點 1 在進程初次執(zhí)行時 開始階段會有大量的頁調(diào)入內(nèi)存 這時的進程切換開銷很大 2 發(fā)生缺頁中斷時操作系統(tǒng)會調(diào)入頁面 而每次又僅調(diào)入一個頁面 啟動磁盤作I O的頻率很高 由于每次啟動磁盤時會產(chǎn)生一個時間延遲 因此 會造成系統(tǒng)用于I O的時間增長 系統(tǒng)效率降低 3 對于執(zhí)行順序跳躍性大的程序 缺頁情況變化大 難以趨向穩(wěn)定的水平 從而引起系統(tǒng)不穩(wěn)定 2 預(yù)先頁調(diào)入策略 預(yù)先頁調(diào)入簡稱預(yù)調(diào) 是指由操作系統(tǒng)根據(jù)某種算法 預(yù)先估計進程可能要訪問的頁面 并在處理器需要訪問頁面之前先將頁面預(yù)先調(diào)入內(nèi)存 優(yōu)點 一次可將多個頁面調(diào)入內(nèi)存 減少了缺頁中斷的次數(shù)和I O操作次數(shù) 系統(tǒng)付出的開銷減少 如果預(yù)先動態(tài)估計準確率高 該調(diào)入策略會大大提高系統(tǒng)效率 2 預(yù)先頁調(diào)入策略 缺點 1 如果預(yù)先動態(tài)估計準確率較低 調(diào)入的頁面不被使用的可能性大 系統(tǒng)效率較低 2 如果程序員不能預(yù)先提供所需程序部分的信息 則該調(diào)度策略難以實施 總結(jié) 在實際應(yīng)用中 頁面調(diào)入會將請求頁調(diào)入和預(yù)先頁調(diào)入結(jié)合起來 在進程剛開始執(zhí)行時或每次缺頁中斷時 采用預(yù)先頁調(diào)入 在進程運行穩(wěn)定后 如果發(fā)現(xiàn)缺頁 系統(tǒng)可采用請求頁調(diào)入 3 頁面置換策略 如果頁面替換算法的作用范圍是整個系統(tǒng) 稱全局頁面置換算法 它可以在運行進程間動態(tài)地分配物理塊數(shù) 如果頁面替換算法的作用范圍局限于本進程 稱為局部頁面置換算法 它實際上需要為每個進程分配固定的物理塊 頁面分配和置換策略組合 可組合出以下三種適用的策略 1 固定分配局部置換 FixedAllocation LocalReplacement 2 可變分配全局置換 VariableAllocation GlobalReplacement 3 可變分配局部置換 VariableAllocation LocalReplacemen 1 固定分配局部置換 為每個進程分配固定數(shù)量的物理塊 在進程的整個運行期間都不再改變 當一個進程運行中發(fā)生缺頁中斷時 操作系統(tǒng)只從該進程在內(nèi)存中的頁面中選擇一頁淘汰 該策略不足在于 應(yīng)為每個進程分配多少物理塊數(shù)難以確定 如果分配給進程的物理塊太少 缺頁中斷率高 進而導(dǎo)致整個多道程序系統(tǒng)運行緩慢 給多了 會使內(nèi)存中能同時執(zhí)行的進程數(shù)減少 進而造成處理器空閑和其他設(shè)備空閑 浪費資源 1 固定分配局部置換 采用固定分配算法 系統(tǒng)把物理塊分配給進程 采用 平均分配 按比例分配 優(yōu)先權(quán)分配 2 可變分配全局置換 先為每一進程分配必要數(shù)量的物理塊 使之可以開始運行 系統(tǒng)中余下的空閑物理塊組成一個空閑物理塊隊列 當某一進程在運行中發(fā)生缺頁時 系統(tǒng)從空閑物理塊隊列中取出一個空閑塊分配給該進程 直到系統(tǒng)擁有的空閑物理塊耗盡 才會從內(nèi)存中選擇一頁淘汰 該頁可以是內(nèi)存中任一進程的頁面 該策略易于實現(xiàn) 且可以有效地減少缺頁中斷率 是采用得較多的一種分配和置換策略 3 可變分配局部置換 其實現(xiàn)要點如下 1 新進程裝入主存時 根據(jù)應(yīng)用類型 程序要求 分配給一定數(shù)目物理塊數(shù) 可用請頁式或預(yù)調(diào)式完成這個分配 2 產(chǎn)生缺頁中斷時 從該進程駐留集中選一個頁面替換 3 不時重新評價進程的分配 增加或減少分配給進程的頁框以改善系統(tǒng)性能 3 6 4頁面置換算法 請求分頁虛擬存儲管理規(guī)定 當需要從外存調(diào)入一個新的頁面時 如果此時物理內(nèi)存無空閑塊 系統(tǒng)必須按照一定的算法選擇內(nèi)存中的一些頁面調(diào)出 并將所需的頁面調(diào)入內(nèi)存 這個過程叫頁面置換 頁面置換算法決定從內(nèi)存中置換出哪一個頁面 衡量頁面置換算法的重要的指標是缺頁率 一個進程或一個作業(yè)在運行中成功的頁面訪問次數(shù)為S 即所訪問的頁面在內(nèi)存中 不成功的頁面訪問次數(shù)為F 即訪問的頁面不在內(nèi)存 需要缺頁中斷并調(diào)入內(nèi)存 需要訪問的頁面的總次數(shù)為A S F 則缺頁率f為 f F A 影響缺頁率的因素如下 1 進程分得的內(nèi)存物理塊數(shù)越多 缺頁率越低 2 劃分的頁面越大 缺頁率越低 3 如果程序局部性好 則缺頁率低 4 如果選取的置換算法優(yōu) 則缺頁率低 在進程的內(nèi)存物理塊數(shù)和頁面大小不能改變的情況下 要減少缺頁率 就要考慮選擇合適的頁面置換算法 當要放一頁面到全滿的主存塊時 系統(tǒng)需淘汰一頁 用來選取淘汰哪一頁的規(guī)則 叫替換算法 全局 1先進先出頁面替換算法FIFO2最佳頁面替換算法OPT3最近最少使用頁面替換算法LRU4第二次機會頁面替換算法SCR5時鐘頁面替換算法Clock 1先進先出 FIFO 頁面置換算法 基于程序總是按線性順序來訪問物理空間這一假設(shè) 算法總是淘汰最先調(diào)入主存的那一頁 或者說在主存中駐留時間最長的那一頁 常駐的除外 注意 不考慮剛被訪問 只要是隊列中最先進入的就被淘汰 做題時可按先進先出排好隊 7 7 7 0 0 1 7 0 1 2 0 1 2 0 1 3 2 0 2 3 0 4 3 0 4 3 2 3 0 3 0 4 2 4 2 3 2 3 0 2 1 2 0 1 1 7 0 1 3 0 1 0 1 2 1 2 7 7 0 1 缺頁次數(shù) 15 2 7 0 F F F F 7 S F 0 F 1 F 2 F 3 F 0 F 4 S S F 2 F 3 S S S F 0 F 1 F 2 先進先出頁面置換算法開銷低 容易編程實現(xiàn) 適合于線性順序特性好的程序 但是該算法沒有考慮到頁面的訪問頻率 很可能剛被換出的頁面馬上又要被訪問 使得缺頁率偏高 為了改善FIFO算法 減少缺頁率 科學(xué)家嘗試在進程發(fā)生缺頁時給進程增加物理塊 在實驗中 Belady發(fā)現(xiàn)了一個奇怪的現(xiàn)象 該現(xiàn)象也被稱為Belady異?，F(xiàn)象 即 當頁數(shù)在一定范圍內(nèi)時 缺頁率反而隨分配給進程的物理塊數(shù)的增加而增加 如圖所示 當內(nèi)存物理塊數(shù)從4增加到6時 缺頁率增加了 該現(xiàn)象說明 如果要改善系統(tǒng)性能 不能只靠給進程增加內(nèi)存物理塊 2最佳頁面替換算法OPT 調(diào)入一頁而必須淘汰一個舊頁時 所淘汰的頁應(yīng)該是以后不再訪問的頁或距現(xiàn)在最長時間后再訪問的頁 理論算法 可用來作為衡量各種具體算法的標準 方法 淘汰可選頁面中離當前頁面向后最遠的一頁 表示以后不再訪問或距現(xiàn)在最長時間后再訪問的頁 假定系統(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三個頁面裝入內(nèi)存 以后 當進程要訪問頁面2時 將會產(chǎn)生缺頁中斷 此時OS根據(jù)最佳置換算法 將選擇頁面7予以淘汰 缺頁次數(shù) 9 3最近最少使用 LRU 置換算法 算法淘汰的頁面是在最近一段時間里較久未被訪問的那頁 根據(jù)程序局部性原理 那些剛被使用過的頁面 可能馬上還要被使用 而在較長時間里未被使用的頁面 可能不會馬上使用到 3最近最少使用 LRU 置換算法 舉例 淘汰可選頁面中離當前頁面向前最遠的一頁 表示最近最少使用 缺頁次數(shù) 12 LRU算法的實現(xiàn) 1 隊列中存放當前在主存中的頁號 每當訪問一頁時就調(diào)整一次 使隊列尾總指向最近訪問的頁 隊列頭就是最近最少用的頁 發(fā)生缺頁中斷時總淘汰隊列頭所指示的頁 執(zhí)行一次頁面訪問后 需要從隊列中把該頁調(diào)整到隊列尾 第一 維護一個特殊的隊列 頁面淘汰隊列 LRU算法的實現(xiàn) 1 例子 給某作業(yè)分配了三塊主存 該作業(yè)依次訪問的頁號為 4 3 0 4 1 1 2 3 2 當訪問這些頁時 頁面淘汰序列變化情況如下 訪問頁號頁面淘汰序列被淘汰頁面443430430430410413104124120312342132 隊頭 隊尾 LRU算法的實現(xiàn) 2 標志位法多位計數(shù)器法多位計時器法 第二 需要硬件支持 確定頁面最后訪問以來所經(jīng)歷的時間 標志位法 每頁設(shè)置一個引用標志位R 訪問某頁時 由硬件將頁標志位R置1 隔一定時間t將所有頁的標志R均清0 發(fā)生缺頁中斷時 從標志位R為0的頁中挑選一頁淘汰 挑選到要淘汰的頁后 也將所有頁的標志位R清0 多位計數(shù)器法 每個頁面設(shè)置一個多位計數(shù)器 又叫最不常用頁面替換算法LFU 每當訪問一頁時 就使它對應(yīng)的計數(shù)器加 當發(fā)生缺頁中斷時 可選擇計數(shù)值最小的對應(yīng)頁面淘汰 并將所有計數(shù)器全部清 多位計時器法 為每個頁面設(shè)置一個多位計時器 每當頁面被訪問時 系統(tǒng)的絕對時間記入計時器 比較各頁面的計時器的值 選最小值的未使用的頁面淘汰 因為 它是最 老 的未使用的頁面 4第二次機會頁面替換算法 SCR 改進FIFO算法 把FIFO與頁表中的 引用位 結(jié)合起來使用算法含義 最先進入主存的頁面 如果最近還在被使用的話 仍然有機會作為像一個新調(diào)入頁面一樣留在主存中 4第二次機會頁面替換算法 SCR 實現(xiàn)過程 檢查FIFO中的隊首頁面 最早進入主存的頁面 如果它的 引用位 是0 這個頁面既老又沒有用 選擇該頁面淘汰 如果 引用位 是1 說明它進入主存較早 但最近仍在使用 把它的 引用位 清0 并把這個頁面移到隊尾 把它看作是一個新調(diào)入的頁 5時鐘頁面替換算法 Clock SCR算法采用FIFO隊列可能產(chǎn)生頻繁的出隊和入隊 實現(xiàn)代價高改進 可采用類似鐘表面的環(huán)形表 隊列指針相當于鐘表面上的表針 指向可能要淘汰的頁面 時鐘頁面替換算法 注意 和SCR算法并沒有本質(zhì)區(qū)別 仍需使用引用位 訪問位 5時鐘頁面替換算法 Clock 實現(xiàn)要點 1 一個頁面首次裝入主存 其 引用位 置0 2 主存中的任何頁面被訪問時 引用位 置1 3 淘汰頁面時 從指針當前指向的頁面開始掃描循環(huán)隊列 把遇到的 引用位 是1的頁面的 引用位 清0 跳過這個頁面 把所遇到的 引用位 是0的頁面淘汰掉 指針推進一步 4 掃描循環(huán)隊列時 如果碰到的所有頁面的 引用位 為1 指針就會繞整個循環(huán)隊列一圈 把碰到的所有頁面的 引用位 清0 指針停在起始位置 并淘汰掉這一頁 然后 指針推進一步 時鐘頁面替換改進算法 把 引用位 和 修改位 結(jié)合起來使用 共組合成四種情況 1 最近沒有被引用 沒有被修改 r 0 m 0 2 最近被引用 沒有被修改 r 1 m 0 3 最近沒有被引用 但被修改 r 0 m 1 4 最近被引用過 也被修改過 r 1 m 1 時鐘頁面替換改進算法 步1 選擇最佳淘汰頁面 從指針當前位置開始 掃描循環(huán)隊列 掃描過程中不改變 引用位 把碰到的第一個r 0 m 0的頁面作為淘汰頁面 步2 如果步1失敗 再次從原位置開始 查找r 0且m 1的頁面 把碰到的第一個這樣的頁面作為淘汰頁面 而在掃描過程中把指針所掃過的頁面的 引用位 r置0 步3 如果步2失敗 指針再次回到了起始位置 由于此時所有頁面的 引用位 r均己為0 再轉(zhuǎn)向步1操作 必要時再做步2操作 這次一定可以挑出一個可淘汰的頁面 舉例 假設(shè)采用固定分配策略 進程分得三個頁框 執(zhí)行中按下列次序引用5個獨立的頁面 232152453252 分別用計算OPT LRU FIFO和CLOCK算法中缺頁中斷的次數(shù) 232152453252 232152453252 1 隊首 要淘汰的頁面 隊尾 最近的頁面 232152453252 232152453252 最先進入隊列的頁面 性能比較 OPTF 1 F 2 F 4 3次LRUF 3 F 1 F 2 F 4 3次CLOCKF 2 F 3 F 1 F 5 F 4 3次FIFOF 1 F 3 F 1 F 5 F 2 F 4 3次 可以看出 FIFO算法的性能最差 OPT算法的性能最好 而Clock算法與LRU算法的性能十分接近 3 6 5影響請求頁式存儲管理性能的因素 虛擬存儲技術(shù)以增加進程運行的時間為代價換來系統(tǒng)更多的虛擬內(nèi)存 影響其性能 即缺頁中斷率 的因素有 主存物理塊數(shù) 分得物理塊數(shù)越多f越低頁面大小 頁面越大f越低頁面置換算法程序特性 局部性好 中斷率低 3 6 5影響請求頁式存儲管理性能的因素 1 分配給進程的內(nèi)存塊數(shù)與缺頁率的關(guān)系 分給進程的物理塊數(shù)越多 缺頁率越小 例如 若某進程邏輯地址共需30個頁面 取極端情況 為其分配30個物理塊 則所有頁面全部進入內(nèi)存 缺頁率自然為0 不過此時請求頁式管理已變成了頁式管理 如果取另一個極端 即只分給進程一個物理塊 只能容納下一頁 這種情況下毫無疑問會頻繁地發(fā)生缺頁中斷 缺頁率最大 試驗結(jié)果表明 對每個進程來說 為其分配進程空間頁面數(shù)約一半的物理塊時 請求頁式的效果最好 2 頁面大小對系統(tǒng)性能的影響 1 從頁表大小考慮 如果頁面較小 頁數(shù)就要增加 頁表也隨之擴大 為了控制頁表所占的內(nèi)存空間 應(yīng)選擇較大的頁面尺寸 2 從內(nèi)存利用率考慮 內(nèi)存以塊為單位 一般情況下進程的最后一個頁面總是裝不滿一個物理塊 會產(chǎn)生內(nèi)部碎片 為了減少內(nèi)部碎片 應(yīng)選擇小的頁面尺寸 2 頁面大小對系統(tǒng)性能的影響 3 從讀寫一個頁面所需的時間考慮 頁面需要從外存對換區(qū)讀到內(nèi)存 作業(yè)存放在輔助存儲器上 從磁盤讀入一個頁面的時間包括等待時間 移臂時間 旋轉(zhuǎn)時間 和傳輸時間 通常等待時間遠大于傳輸時間 顯然 加大頁面的尺寸 有利于提高I O的效率 總結(jié) 現(xiàn)代操作系統(tǒng)中 頁面大小大多選擇在512B到4KB之間 頁面長度是由CPU中的MMU規(guī)定的 操作系統(tǒng)通過特定寄存器的指示位來指定當前選用的頁面長度 3 缺頁率對系統(tǒng)性能的影響 頁面替換中的 抖動現(xiàn)象 剛被淘汰的頁面立即又要調(diào)用 而調(diào)入不久隨即被淘汰 淘汰不久又再被調(diào)用 如此反復(fù) 使得整個系統(tǒng)的頁面調(diào)度非常頻繁 以致大部分時間都花費在來回調(diào)度頁面上 而不是執(zhí)行計算任務(wù) 這樣的現(xiàn)象稱作 抖動現(xiàn)象 原因 頁面淘汰算法不合理 分配給進程的物理塊數(shù)太少 注意 采取好的調(diào)度算法可以避免抖動現(xiàn)象 3 7請求分段虛擬存儲管理 請求分段的概念 請求分段虛擬存儲系統(tǒng)把作業(yè)的所有分段的副本都存放在輔助存儲器中 當作業(yè)被調(diào)度投入運行時 首先把當前需要的一段或幾段裝入主存 在執(zhí)行過程中訪問到不在主存的段時再把它們裝入 需要對段表進行擴充 段號 特征位 存儲權(quán)限 擴充位 標志位 主存始址 段長 輔存始址特征位 0 不在主存 1 在主存 存取權(quán)限 00 可執(zhí)行 01 可讀 11 可寫 擴充位 0 固定長 1 可擴充 標志位 00 未修改 01 已修改 11 不可移動 地址轉(zhuǎn)換流程 1 訪問某段 由硬件的地址轉(zhuǎn)換機制查段表 若所需的段在主存 則按分段存儲管理方法進行地址轉(zhuǎn)換得物理地址2 若不在主存 觸發(fā)缺段中斷 由操作系統(tǒng)處理此中斷 查主存分配表 找出一個足夠大的連續(xù)區(qū)域容納此分段 找不到查看空閑區(qū)總和能否滿足此段要求 滿足進行適當移動 若不滿足 需要調(diào)出一個或多個分段到磁盤上 S段在主存 否 是 B S段長度 發(fā)越界中斷 是 否 形成絕對地址 繼續(xù)執(zhí)行指令 操作系統(tǒng) 硬件 符合存取權(quán)限 發(fā)保護中斷 是 否 發(fā)缺段中斷 回顧 段式存儲是基于用戶程序結(jié)構(gòu)的存儲管理技術(shù) 有利于模塊化程序設(shè)計 便于段的擴充 動態(tài)鏈接 共享和保護 但會生成段內(nèi)碎片浪費存儲空間頁式存儲是基于系統(tǒng)存儲器結(jié)構(gòu)的存儲管理技術(shù) 存儲利用率高 便于系統(tǒng)管理 但不易實現(xiàn)存儲共享 保護和動態(tài)擴充把兩者結(jié)合起來就是段頁式存儲管理 請求段頁式的基本原理 1 虛地址以程序的邏輯結(jié)構(gòu)劃分成段 段頁式存儲管理的段式特征 2 實地址劃分成位置固定 大小相等的頁框 段頁式存儲管理的頁式特征 3 將每一段的線性地址空間劃分成與頁框大小相等的頁面 于是形成了段頁式存儲管理的特征 4 邏輯地址形式為 請求段頁式管理的數(shù)據(jù)結(jié)構(gòu) 作業(yè)表 登記進入系統(tǒng)中的所有作業(yè)及該作業(yè)段表的起始地址 段表 至少包含這個段是否在主存 以及該段頁表的起始地址 頁表 包含該頁是否在主存 中斷位 對應(yīng)主存塊號 地址轉(zhuǎn)換 1 從邏輯地址出發(fā) 先以段號s和頁號p作索引去查快表 如果找到 那么立即獲得頁p的頁框號p 并與位移d一起拼裝得到訪問主存的實地址 從而完成了地址轉(zhuǎn)換 地址轉(zhuǎn)換 2 若查快表失敗 就要通過段表和頁表作地址轉(zhuǎn)換了 用段號s作索引 找到相應(yīng)表目 由此得到s段的頁表起址s 再以p作索引得到s段p頁對應(yīng)的表目 得到頁框號p 這時一方面把s段p頁和頁框號p 置換進快表 另一方面用p 和d生成主存實地址 從而完成地址轉(zhuǎn)換 地址轉(zhuǎn)換 3 如查段表時 發(fā)現(xiàn)s段不在主存 產(chǎn)生 缺段中斷 引起系統(tǒng)查找s段在輔存的位置 將該段頁表調(diào)入主存 4 如查頁表時 發(fā)現(xiàn)s段的p頁不在主存 產(chǎn)生 缺頁中斷 引起系統(tǒng)查找s段p頁在輔存的位置 并將該頁調(diào)入主存 當主存已無空閑頁框時 就會導(dǎo)致