【正文】 CPU調(diào)用缺頁中斷處理程序 中斷處理程序調(diào)頁 若頁未被修改 ,不必回寫 若頁已被修改 , 必須回寫 若內(nèi)存已滿 ,置換 返回 2022/2/17 157 頁面置換算法 P149 概 述 通常，把選擇換出的算法稱為頁面置換算法。 頁面置換算法影響著系統(tǒng)的性能：盡量減少 系統(tǒng)的 抖動 2022/2/17 158 最近最久未使用 (LRU)置換算法 Clock置換算法 其他置換算法 (LFU)置換算法 本節(jié)主要內(nèi)容： 2022/2/17 159 本節(jié)學(xué)習(xí)目標(biāo)： 理解并熟練掌握 FIFO、 LRU置換算法的思想 和算法的應(yīng)用，會求缺頁次數(shù)和置換次數(shù)； 掌握 CLOCK置換算法的基本思想； 了解其它置換算法 2022/2/17 160 最理想的頁面置換算法是：從內(nèi)存中移出以后不再使用的頁面；如無這樣的頁面，則選擇以后最長時間內(nèi)不需要訪問的頁。這就是最佳算法的思想。 （ Optimal算法） 2022/2/17 161 這種算法本身不是一種實際的方法，因為頁面訪問 的順序是很難預(yù)知的。但是，可把它作為一種評價 標(biāo)準(zhǔn)，比較其他實用方法的優(yōu)劣，所以，最優(yōu)算法 只具有理論上的意義。 2022/2/17 162 假設(shè)系統(tǒng)為某進程分配了 3個物理塊，頁面引用序列如下： 7， 0， 1， 2， 0， 3， 0， 4， 2， 3， 0， 3， 2， 1， 2， 0， 1， 7， 0， 1 進程運行時三個物理塊都是 空閑 的。 例子： 求 :缺頁次數(shù)、缺頁率及置換次數(shù) 2022/2/17 163 最佳（ Optimal）置換算法 發(fā)生了 6次面置換， 9次缺頁中斷 ,。 9/20=45% 2022/2/17 164 (FIFO)頁面置換算法 這種算法的基本思想是：總是先淘汰那些駐留在 內(nèi)存時間最長的頁面，即先進入內(nèi)存的頁面先被 置換掉。理由是：最先進入內(nèi)存的頁面不再被訪 問的可能性最大。 程序執(zhí)行的局部性原理 2022/2/17 165 FIFO算法演示過程（ m=3） 1 2 3 4 1 2 5 1 2 3 4 5 1 約定：每一輪訪存進行排序，將要置換的頁放 在下面 2 2 2 1 1 3 3 3 4 4 4 1 1 1 2 2 5 5 √ √ √ √ √ √ √ 2 1 2 1 5 3 3 4 4 5 5 5 2 3 √ √ 2022/2/17 166 ?主存塊數(shù) m=3， 置換算法采用 FIFO算法 ， 缺頁中斷次數(shù)及缺頁率如圖所示 。 ?在圖中， P行表示頁面走向， M行表示在主存中的頁面號，其中帶有 +的表示新調(diào)入頁面，在 M行的各列按調(diào)入的順序排列，帶有圓圈的數(shù)字表示下一時刻將被淘汰頁面， F行表示是否引起缺頁中斷，帶 √號的表示引起缺頁中斷。 【 例 1】 2022/2/17 167 FIFO算法性能分析（ m=3） 從圖可以看出，缺頁中斷頁數(shù)為 9次，缺頁率 f=9/12=75%。 2022/2/17 168 ?設(shè) m=4， 仍采用 FIFO算法 ， 缺頁中斷次數(shù)及缺頁率 如下圖 所示 。 ?可以算出 ， 在分配給該作業(yè)的內(nèi)存塊數(shù)增加到 4時 ， 缺頁中斷由上圖的 9次反而增加到了 10次 ，缺頁率由 75%增加到 10/12=83%， 這就是 FIFO算法的一種異?，F(xiàn)象 。 隨著分配的主存塊數(shù)的增加 ，缺頁中斷次數(shù)不但沒有降低 ， 反而增加了 。 這與該算法定全不考慮程序的動態(tài)特征有關(guān)。 【 例 2】 2022/2/17 169 圖為 FIFO算法性能分析（ m=4） 2022/2/17 170 最近最久未使用 (LRU)置換算法 這種算法的 基本思想 是 :如果某一頁被訪問了，那么它很可能馬上又被訪問；反之，如果某一頁很長時間沒有被訪問，那么最近也不太可能會被訪問。這種算法考慮了程序設(shè)計的 局部性原理 。其實質(zhì)是，當(dāng)需要置換一頁時，選擇在最近一段時間最久未使用的頁面予以淘汰。 實現(xiàn)這種算法可通過周期性地對“訪問位”進行檢查， 并利用它來記錄一頁面自上次被訪問以來所經(jīng)歷的時間 t， 淘汰時選擇 t最大的頁面。 2022/2/17 171 LRU算法演示過程（ m=3） 約定：每一輪訪存進行排序，將要置換的頁放 在下面 1 2 3 4 1 2 5 1 2 3 4 5 1 2 2 1 3 3 4 4 1 1 1 2 2 5 5 √ √ √ √ √ √ √ 2 1 2 1 5 3 3 4 4 5 2 3 √ √ 1 2 3 4 1 2 √ 2022/2/17 172 ? 【 例 3】 設(shè) m=3， 采用 LRU算法 ， 缺頁中斷次數(shù)及缺頁率如圖所示 。 缺頁次數(shù)： 置換次數(shù)： 10 7 2022/2/17 173 ?【 例 4】 設(shè) m=4，其余同例 3，則缺頁中斷次數(shù)及缺頁率如圖所示。 缺頁次數(shù)： 8 置換次數(shù)： 4 2022/2/17 174 2. LRU置換算法的硬件支持 1)寄存器 R=Rn1…R1R0 說明 :系統(tǒng)為每個在 內(nèi)存 中的頁面配置一個移位寄存器 , 當(dāng)進程訪問某物理塊時 ,將相應(yīng)寄存器的 Rn1位置成 1. 2) 棧 基本思想：每當(dāng)進程訪問某頁時，便將該頁面的頁面號 從棧中移出，將它壓入棧頂。 2022/2/17 175 Clock置換算法 P153 Clock置換算法 (最近未用算法 NRU) 思想 :為每頁設(shè)置一訪問位 ,將內(nèi)存中的所有頁面鏈成 一個循環(huán)隊列 .當(dāng)某頁被訪問時 ,訪問位置 訪問位是 0的置換出 . 2022/2/17 176 2. 改進型 Clock置換算法 四種頁面的組合 : 1類 (A=0,M=0) 2類 (A=0,M=1) 3類 (A=1M=0) 4類 (A=1,M=1) 2022/2/17 177 執(zhí)行步驟 : 第一步 :尋找 A=0且 M=0的第一類頁面 . 在第一次掃描期間不改變訪問位 A. 第二步 :尋找 A=0且 M=1的第二類頁面 . 在第二次掃描期間把所有掃描過的頁面的訪問位 都置 0 . 第三步 :從頭開始 ,將所有的訪問位復(fù) 0,重復(fù)第一步或 第二步 . 2022/2/17 178 其它置換算法 （ LFU)置換算法 基本思想： 為在內(nèi)存中的每個頁面設(shè)置一個移位寄存器，用來 記錄該頁面被訪問的頻率。選擇在最近時期使用最 少的頁面作為淘汰頁。 2022/2/17 179 例子 1：計算缺頁次數(shù) 某程序在內(nèi)存中分配三個頁面，初始為空，頁面走向為 4， 3， 2， 1， 4，3， 5， 4， 3， 2， 1， 5 練習(xí)題： 2022/2/17 180 FIFO 4 3 2 1 4 3 5 4 3 2 1 5 頁 1 4 3 2 1 4 3 5 5 5 2 1 1 頁 2 4 3 2 1 4 3 3 3 5 2 2 頁 3 4 3 2 1 4 4 4 3 5 5 x x x x x x x ? ? x x ? 共缺頁中斷 9次 2022/2/17 181 LRU 4 3 2 1 4 3 5 4 3 2 1 5 頁 1 4 3 2 1 4 3 5 4 3 2 1 5 頁 2 4 3 2 1 4 3 5 4 3 2 1 頁 3 4 3 2 1 4 3 5 4 3 2 x x x x x x x ? ? x x x 共缺頁中斷 10次 2022/2/17 182 OPT 4 3 2 1 4 3 5 4 3 2 1 5 頁 1 4 3 2 1 1 1 5 5 5 2 1 1 頁 2 4 3 3 3 3 3 3 3 5 5 5 頁 3 4 4 4 4 4 4 4 4 4 4 x x x x ? ? x ? ? x x ? 共缺頁中斷 7次 2022/2/17 183 總結(jié)：影響缺頁次數(shù)的因素 (1) 分配給進程的物理頁面數(shù) (2) 頁面本身的大小 (3) 程序的編制方法 (4) 頁面淘汰算法 2022/2/17 184 例子 2：內(nèi)存分配一頁，初始時第一頁在內(nèi)存；頁面大小為 128的整數(shù)；矩陣 A128X128按行存放 程序編制方法 1： For j:=1 to 128 For i:=1 to 128 A[i,j]:=0。 程序編制方法 2： For i:=1 to 128 For j:=1 to 128 A[i,j]:=0。 返回 問題：哪種編制方法能減少缺頁次數(shù) 答案：方法 2 2022/2/17 185 請求分段存儲管理方式 為了能實現(xiàn)虛擬存儲，段式邏輯地址空間中的程序段在運行時并不全部裝入內(nèi)存，而是如同請求式分頁存儲管理，首先調(diào)入一個或若干個程序段運行，在運行過程中調(diào)用到哪段時，就根據(jù)該段長度在內(nèi)存分配一個連續(xù)的分區(qū)給它使用。若內(nèi)存中沒有足夠大的空閑分區(qū)，則考慮進行段的緊湊或?qū)⒛扯位蚰承┒翁蕴鋈ァＯ鄳?yīng)于請求式分頁存儲管理，這種存儲管理技術(shù)稱為請求式分段存儲管理。 思想 : 概 述 2022/2/17 186 本節(jié)主要內(nèi)容： 請求分段中的硬件支持 分段的共享與保護 本節(jié)學(xué)習(xí)目標(biāo)： 了解請求分段中的硬件支持； 了解分段的共享與保護 返回 2022/2/17 187 請求分段中的硬件支持 段名 段長 段的 基址 存取 方式 訪 問 字段 A 修 改 字段 M 存在 位 P 增補位 外存 起址 只執(zhí)行、只讀、讀寫 記錄該段被訪問的頻繁程度 是否被修改過，換頁時參考 指示本段是否已調(diào)入內(nèi)存 在運行過程中是否進行過動態(tài)增長 2022/2/17 188 越界中斷處理 進程在執(zhí)行過程中，有時需要擴大分段，如數(shù)據(jù)段。由于要訪問的地址超出原有的段長，所以發(fā)越界中斷。操作系統(tǒng)處理中斷時 ，首先判斷該段的“擴充位（增補位）”，如可擴充，則增加段的長度；否則按出錯處理 2022/2/17 189 缺段中斷處理 檢查內(nèi)存中是否有足夠的空閑空間 ①若有，則裝入該段，修改有關(guān)數(shù)據(jù)結(jié)構(gòu)，中斷返回 ②若沒有，檢查內(nèi)存中空閑區(qū)的總和是否滿足要求，是則應(yīng)采用緊縮技術(shù)，轉(zhuǎn)① ；否則，淘汰一（些）段，轉(zhuǎn)① 2022/2/17 190 2022/2/17 191 分段的共享與保護 段名 段長 內(nèi)存始址 狀態(tài) 外存始址 共享進程計數(shù) count 狀態(tài) 進程名 進程號 段號 存取控制 … 2022/2/17 192 1)共享段的分配 2)共享段的回收 2022/2/17 193 3. 分段保護 1)越界檢查 2)存取控制檢查 3)環(huán)保護機構(gòu) (1)一個程序可以訪問駐留在相同環(huán)或較低特權(quán)環(huán)中 的數(shù)據(jù) (2)一個程序可以調(diào)用駐留在相同環(huán)或較高特權(quán)環(huán) 中的服務(wù) 返回 2022/2/17 194 本章小結(jié) ? 熟練掌握分區(qū)分配、基本分頁存儲管理方式、常用的頁面置換算法 ? 理解并掌握重定位、對換、虛擬存儲器、置換、頁表、段表、邏輯地址、物理地址、邏輯空間、物理空間等基本概念 2022/2/17 195 本章練習(xí)題