操作系統(tǒng)課件(3.4 虛擬存儲管理機制)

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

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

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

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

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選擇內存中駐留時間最長的頁面并淘汰之部分程序總體按線性順序來訪問物理空間優(yōu)點: 直觀，實現(xiàn)簡單缺點: 與進程實際運行的規(guī)律不相適應，性能較差，可能出現(xiàn)分配頁框數(shù)增加、缺頁次數(shù)反而增加的異常現(xiàn)象典型的頁面置換算法FIFO頁面置換算法頁面置換算法3系統(tǒng)為進程P在內存中分配三個頁框頁面訪問序列為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設置一個隊列，存放當前在主存中的頁號頁面訪問后，需要從隊列中把該頁調整到隊列尾隊列尾總指向最近訪問的頁，隊列頭就是最近最少用的頁面缺頁中斷時，總淘汰隊列頭所指示的頁面典型的頁面置換算法最近最少用

7、頁面置換算法最近最少用頁面置換算法4系統(tǒng)為進程P在內存中分配三個頁框頁面訪問序列為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頁框虛擬存儲管理機制本講內容1. 程序訪問局部性原理2. 虛擬存儲器基本原理3. 分頁式虛擬存儲管理4. 典型的頁