1、徐小龍/WindowsLinuxMac OSOpenStackAndroidLinux虛擬存儲管理機制本講內(nèi)容1. 程序訪問局部性原理2. 虛擬存儲器基本原理3. 分頁式虛擬存儲管理4. 典型的頁面置換算法5. 分段式虛擬存儲管理程序訪問局部性原理基本思想基本思想1P.Denning研究了程序執(zhí)行時的局部性原理一段時間內(nèi)程序的執(zhí)行呈現(xiàn)出高度局部性程序訪問局部性原理兩個局部性兩個局部性 2某條指令被執(zhí)行或某個數(shù)據(jù)結(jié)構(gòu)被訪問，則近期該指令可能再次執(zhí)行，該數(shù)據(jù)結(jié)構(gòu)可能再次被訪問若某個存儲單元被訪問，則其附近的存儲單元也可能被訪問，一段時間內(nèi)訪問可能集中在一定范圍內(nèi)虛擬存儲管理機制本講內(nèi)容1. 程序訪

2、問局部性原理2. 虛擬存儲器基本原理3. 分頁式虛擬存儲管理4. 典型的頁面置換算法5. 分段式虛擬存儲管理虛擬存儲空間虛擬存儲空間1虛擬存儲器基本原理虛擬存儲器是由操作系統(tǒng)提供的假想存儲器，它不是實際內(nèi)存，而是系統(tǒng)對物理內(nèi)存的邏輯擴充。程序、數(shù)據(jù)、堆?？梢猿^內(nèi)存的大小，系統(tǒng)把當前使用的部分保留在內(nèi)存，而把其它部分保存在輔存上，需要時在內(nèi)存和輔存之間動態(tài)交換虛擬存儲空間受限于系統(tǒng)地址結(jié)構(gòu)、內(nèi)存大小及可用的輔存容量虛擬存儲系統(tǒng)虛擬存儲系統(tǒng)2虛擬存儲器基本原理虛擬地址空間處理器虛地址存儲管理部件實地址主存輔存物理地址空間虛擬存儲管理機制本講內(nèi)容1. 程序訪問局部性原理2. 虛擬存儲器基本原理3.

3、 分頁式虛擬存儲管理4. 典型的頁面置換算法5. 分段式虛擬存儲管理分頁式虛擬存儲管理基本原理基本原理1進程運行前，不裝入全部頁面，而是裝入一個或數(shù)個頁面根據(jù)進程運行的需要，動態(tài)裝入其它頁面內(nèi)存空間已滿，又需要裝入新頁面時，則淘汰內(nèi)存部分頁面，裝入新的頁面分頁式虛擬存儲管理關(guān)鍵問題關(guān)鍵問題2系統(tǒng)如何獲知進程當前所需頁面不在內(nèi)存中發(fā)現(xiàn)缺頁時，如何把所缺頁面調(diào)入內(nèi)存需要淘汰頁面時，根據(jù)什么策略選擇淘汰頁面分頁式虛擬存儲管理頁表擴充頁表擴充3頁號和頁框號其作用與分頁存儲管理相同中斷位指示頁面是否在內(nèi)存中，若不在內(nèi)存，則產(chǎn)生缺頁中斷訪問位記錄該頁是否被訪問或者訪問次數(shù)修改位指示頁面在調(diào)入內(nèi)存后是否被修

4、改過輔存地址指出該頁在輔存上的地址虛擬存儲管理機制本講內(nèi)容1. 程序訪問局部性原理2. 虛擬存儲器基本原理3. 分頁式虛擬存儲管理4. 典型的頁面置換算法5. 分段式虛擬存儲管理典型的頁面置換算法性能指標性能指標1進程P在運行中成功的內(nèi)存訪問次數(shù)為S，不成功的訪問次數(shù)為F，則缺頁中斷率為：R=F/(S+F)頁面置換算法分配進程頁框數(shù)頁框本身大小程序的編制方法典型的頁面置換算法理想理想頁面置換算法頁面置換算法2調(diào)入新的一頁面而必須淘汰一個舊頁時，淘汰頁是以后不再訪問或最長時間以后再訪問的頁面可作為衡量各種實用頁面置換算法的標準典型的頁面置換算法理想理想頁面置換算法頁面置換算法2系統(tǒng)為進程P在內(nèi)存

5、中分配三個頁框頁面訪問序列為4，3，2，1，4，3，5，4，3，2，1，5 OPT 4 3 2 1 4 3 5 4 3 2 1 5頁框1 4 2頁框2 3 1頁框3 2 1 5 x x x x x x x 缺頁7次典型的頁面置換算法FIFO頁面置換算法頁面置換算法3選擇內(nèi)存中駐留時間最長的頁面并淘汰之部分程序總體按線性順序來訪問物理空間優(yōu)點: 直觀，實現(xiàn)簡單缺點: 與進程實際運行的規(guī)律不相適應(yīng)，性能較差，可能出現(xiàn)分配頁框數(shù)增加、缺頁次數(shù)反而增加的異?，F(xiàn)象典型的頁面置換算法FIFO頁面置換算法頁面置換算法3系統(tǒng)為進程P在內(nèi)存中分配三個頁框頁面訪問序列為4，3，2，1，4，3，5，4，3，2，1，

6、5 FIFO 4 3 2 1 4 3 5 4 3 2 1 頁框1 4 1 5頁框2 3 4 2 頁框3 2 3 1 x x x x x x x x x 缺頁中斷9次典型的頁面置換算法最近最少用頁面置換算法最近最少用頁面置換算法4淘汰的頁面是在最近較久未被訪問或訪問次數(shù)最少的頁面基于程序局部性原理，剛被訪問過的頁面，馬上再被訪問的概率將會較高典型的頁面置換算法最近最少用頁面置換算法最近最少用頁面置換算法4設(shè)置一個隊列，存放當前在主存中的頁號頁面訪問后，需要從隊列中把該頁調(diào)整到隊列尾隊列尾總指向最近訪問的頁，隊列頭就是最近最少用的頁面缺頁中斷時，總淘汰隊列頭所指示的頁面典型的頁面置換算法最近最少用

7、頁面置換算法最近最少用頁面置換算法4系統(tǒng)為進程P在內(nèi)存中分配三個頁框頁面訪問序列為4，3，2，1，4，3，5，4，3，2，1，5 LRU 4 3 2 1 4 3 5 4 3 2 1 5頁框1 4 1 5 2頁框2 3 4 1 頁框3 2 3 5 x x x x x x x x x x缺頁中斷10次典型的頁面置換算法時鐘頁面時鐘頁面置換算法置換算法5一個頁面首次裝入主存，“訪問位”置1主存中的任何頁面被訪問時，“訪問位”置1Page9 use=1Page19Use=1Page1Use=0Page45Use=1Page191Use=1Page556Use=0Page13Use=0Page67Use

8、=1Page33Use=1Page222Use=0下一個幀指針n012345678第1頁框典型的頁面置換算法時鐘頁面時鐘頁面置換算法置換算法5淘汰頁面時，從指針當前指向的頁面開始掃描循環(huán)隊列遇到的“訪問位”是1的頁面的“訪問位”清0，跳過這個頁面把所遇到的“訪問位”是0的頁面置換掉，指針推進一步Page9 use=1Page19Use=1Page1Use=0Page45Use=1Page191Use=1Page556Use=0Page13Use=0Page67Use=1Page33Use=1Page222Use=0下一個幀指針n012345678第1頁框典型的頁面置換算法時鐘頁面時鐘頁面置換算法置換算法5如果遇到的所有頁面的“訪問位”為1，指針就會繞整個循環(huán)隊列一圈把 碰 到 的 所 有 頁 面 的“訪問位”清0指針回到起始位置，并淘汰掉這一頁，指針推進一步Page9 use=1Page19Use=1Page1Use=0Page45Use=1Page191Use=1Page556Use=0Page13Use=0Page67Use=1Page33Use=1Page222Use=0下一個幀指針n012345678第1頁框虛擬存儲管理機制本講內(nèi)容1. 程序訪問局部性原理2. 虛擬存儲器基本原理3. 分頁式虛擬存儲管理4. 典型的頁