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

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