【正文】 們將多次執(zhí)行 ?程序中還包括許多對數據結構的處理，如對數組進行操作，它們往往都 局限于很小的范圍內 Operating System Page 88 2022/8/16 虛擬存儲器的引入 ?局限性又表現在下述兩個方面 ?時間局限性 ? 如果程序中的某條指令一旦執(zhí)行， 則不久以后該指令可能再次執(zhí)行 ? 如果某數據被訪問過， 則不久以后該數據可能再次被訪問 ? 典型原因是因在程序中存在著大量 循環(huán)操作 ?空間局限性 ? 一旦程序訪問了某個存儲單元，在不久之后，其附近的存儲單元也將被訪問，即程序在一段時間內所 訪問的地址 ， 可能集中 在一定的范圍之內，其典型情況便是程序的順序執(zhí)行 Operating System Page 89 2022/8/16 2. 早在 1968年 ， ： 程序在執(zhí)行時將呈現出局部性規(guī)律 ， 即在一較短時間內 ， 程序的執(zhí)行僅限于某個部分；相應地 ， 它所訪問的存儲空間也局限于某個區(qū)域 。 基于局部性原理 ， 一個作業(yè)在運行之前 ， 沒有必要全部裝入內存 ， 而僅將那些當前要運行的那部分頁面或段 ，先裝入內存便可啟動運行 ， 其余部分暫時留在磁盤上 。 Operating System Page 90 2022/8/16 虛擬存儲器的引入 ?虛擬存儲器 定義 ?是指具有 請求調入功能 和 置換功能 ， 能從 邏輯上 對內存容量加以擴充的一種存儲器系統 。其邏輯容量由 內存容量和外存容量之和 所決定，其運行 速度 接近于 內存速度，而其 成本卻又接近于外存。 Operating System Page 91 2022/8/16 虛擬存儲器的基本概念 ?交換與覆蓋 ?虛擬存儲器的引入 ?虛擬存儲器的實現方法 ?虛擬存儲器的特征 Operating System Page 92 2022/8/16 虛擬存儲器的實現方法 ?虛擬存儲器的實現都是建立在 離散分配 的存儲管理方式基礎上的 ?主要有 ?請求分頁系統 ?請求分段系統 Operating System Page 93 2022/8/16 虛擬存儲器的基本概念 ?交換與覆蓋 ?虛擬存儲器的引入 ?虛擬存儲器的實現方法 ?虛擬存儲器的特征 Operating System Page 94 2022/8/16 虛擬存儲器的特征 虛擬存儲器最基本的特征是離散性，在此基礎上又形成了多次性及對換性的特征。其所表現出來的最重要的特征是虛擬性。 離散性 多次性 對換性 虛擬性 Operating System Page 95 2022/8/16 第四章 存儲器管理 ?程序的裝入和鏈接 ?連續(xù)分配方式 ?基本分頁存儲管理 ?基本分段存儲管理 ?虛擬存儲器的基本概念 ?請求分頁存儲管理方式 ?頁面置換算法 ?請求分段存儲管理方式 Operating System Page 96 2022/8/16 請求分頁存儲管理方式 ?請求分頁中的硬件支持 ?內存分配策略和分配算法 ?調頁策略 Operating System Page 97 2022/8/16 請求分頁中的硬件支持 ?頁描述子的擴充（頁表機制 ） ?狀態(tài)位 P（中斷位）指示該頁是在內存還是在外存 ?訪問位 A 用于記錄本頁在一段時間內 被訪問的次數 或記錄本頁在最近多長時間 未被訪問 ?修改位 M 表示該頁在內存中是否 被修改過 ?外存地址 該頁在外存上的地址，通常是物理塊號 頁號 物理塊號 狀態(tài)位 P 訪問位 A 修改位 M 外存地址 Operating System Page 98 2022/8/16 請求分頁中的地址變換過程 缺頁中斷處理 保留 CPU 現場 從外存中找到缺頁 內存滿否？ 選擇一頁換出 該頁被修改否？ 將該頁寫回外存 啟動 I/O 硬件 將一頁從外存換入內存 修改頁表 否 是 是 否 頁表項在快表中？ CPU 檢索快表 訪問頁表 否 頁在內存？ 修改訪問位和修改位 形成物理地址 地址變換結束 否 頁號＞頁 表長度 ? 開始 程序請求訪問一頁 產生缺頁中 斷請求調頁 修改快表 是 越界中斷 是 是 OS命令 CPU從外存讀缺頁 Operating System Page 99 2022/8/16 請求分頁存儲管理方式 ?請求分頁中的硬件支持 ?內存分配策略和分配算法 ?調頁策略 Operating System Page 100 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% ?請求調頁策略 ? 當進程在運行中需要訪問某部分程序和數據時，若發(fā)現其所在的頁面不在內存，便提出請求，由 OS將其所需頁面調入內存 ? 目前的虛擬存儲中大多采用此種策略 Operating System Page 104 2022/8/16 2. 從何處調入頁面 在請求分頁系統中的外存分為兩部分： 通常 ， 由于對換區(qū)是采用連續(xù)分配方式 ， 而文件是采用離散分配方式 ， 故對換區(qū)的磁盤 I/O速度比文件區(qū)的高 。 這樣 ， 每當發(fā)生缺頁請求時 ， 系統應從何處將缺頁調入內存 ，可分成如下三種情況 。 文件區(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 最佳置換算法和先進先出置換算法 例：假定系統為某進程分配了三個物理塊 ， 并考慮有以下的頁面號引用串： 7， 0， 1， 2， 0， 3， 0， 4， 2， 3，0， 3， 2， 1， 2， 0， 1， 7， 0， 1進程運行時 ， 先將 7， 0，1三個頁面裝入內存 。 以后 ， 當進程要訪問頁面 2時將會產生缺頁中斷 。 此時 OS根據最佳置換算法 ， 將選擇頁面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)置換算法的描述 選擇 最后一次訪問時間距離當前時間最長 的一頁并淘汰之。即淘汰沒有使用的時間最長的頁。實現代價很高（時間戳或硬件方法） LRU頁面置換算法 引用率 7 0 7 7 0 1 7 0 1 2 2 0 1 0 3 2 0 3 0 4 4 0 3 2 3 0 3 2 1 1 3 2 2 0 1 7 1 0 7 0 1 頁框 4 0 2 4 3 2 0 3 2 1 0 2 9次頁面置換 Operating System Page 112 2022/8/16 2. LRU置換算法的硬件支持 把 LRU算法作為頁面置換算法是比較好的，它對于各種類型的程序都能適用，但實現起來有相當大的難度，因為它要求系統具有較多的支持硬件。所要解決的問題有： ? 一個進程在內存中的各個頁面各有多久時間未被進程訪問； ? 如何快速地知道哪一頁最近最久未使用的頁面。 為此，須利用以下兩類支持硬件： 1．移位寄存器： 定時右移 2．棧： 當進程訪問某頁時，將其移出壓入“棧頂”，“棧底”換出。 Operating System Page 113 2022/8/16 頁面置換算法 ?最佳置換算法和先進先出置換算法 ?最近最久未使用（ LRU）置換算法 ?CLOCK置換算法 ?其它置換算法 Operating System Page 114 2022/8/16 頁號 物理塊號