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