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

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

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

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

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

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