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

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

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

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

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

5、中分配三個(gè)頁(yè)框頁(yè)面訪問序列為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頁(yè)框1 4 2頁(yè)框2 3 1頁(yè)框3 2 1 5 x x x x x x x 缺頁(yè)7次典型的頁(yè)面置換算法FIFO頁(yè)面置換算法頁(yè)面置換算法3選擇內(nèi)存中駐留時(shí)間最長(zhǎng)的頁(yè)面并淘汰之部分程序總體按線性順序來訪問物理空間優(yōu)點(diǎn): 直觀，實(shí)現(xiàn)簡(jiǎn)單缺點(diǎn): 與進(jìn)程實(shí)際運(yùn)行的規(guī)律不相適應(yīng)，性能較差，可能出現(xiàn)分配頁(yè)框數(shù)增加、缺頁(yè)次數(shù)反而增加的異?，F(xiàn)象典型的頁(yè)面置換算法FIFO頁(yè)面置換算法頁(yè)面置換算法3系統(tǒng)為進(jìn)程P在內(nèi)存中分配三個(gè)頁(yè)框頁(yè)面訪問序列為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 頁(yè)框1 4 1 5頁(yè)框2 3 4 2 頁(yè)框3 2 3 1 x x x x x x x x x 缺頁(yè)中斷9次典型的頁(yè)面置換算法最近最少用頁(yè)面置換算法最近最少用頁(yè)面置換算法4淘汰的頁(yè)面是在最近較久未被訪問或訪問次數(shù)最少的頁(yè)面基于程序局部性原理，剛被訪問過的頁(yè)面，馬上再被訪問的概率將會(huì)較高典型的頁(yè)面置換算法最近最少用頁(yè)面置換算法最近最少用頁(yè)面置換算法4設(shè)置一個(gè)隊(duì)列，存放當(dāng)前在主存中的頁(yè)號(hào)頁(yè)面訪問后，需要從隊(duì)列中把該頁(yè)調(diào)整到隊(duì)列尾隊(duì)列尾總指向最近訪問的頁(yè)，隊(duì)列頭就是最近最少用的頁(yè)面缺頁(yè)中斷時(shí)，總淘汰隊(duì)列頭所指示的頁(yè)面典型的頁(yè)面置換算法最近最少用

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

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