虛擬內(nèi)存管理.虛擬內(nèi)存技術(shù)的引入內(nèi)存空間大小的問(wèn)題內(nèi)存空間問(wèn)題的解決辦法軟件解決方案的基礎(chǔ)操作系統(tǒng)的解決辦法2內(nèi)存空間大小的問(wèn)題每個(gè)程序運(yùn)行所需空間不能超過(guò)可用內(nèi)存程序會(huì)因不能裝入內(nèi)存而無(wú)法運(yùn)行程序的功能越來(lái)越復(fù)雜、代碼越來(lái)越長(zhǎng)采用覆蓋技術(shù)限制太大程序員在寫程序時(shí)要考慮內(nèi)存大小、考慮覆蓋3內(nèi)存空間問(wèn)題的解決辦法硬件：增加內(nèi)存軟件：改變程序的要求問(wèn)題關(guān)鍵：如果程序可以不用全部放在內(nèi)存中就能夠執(zhí)行4軟件解決方案的基礎(chǔ)并不需要所有代碼和數(shù)據(jù)都放到內(nèi)存中一個(gè)CPU在某個(gè)時(shí)刻只能訪問(wèn)一條語(yǔ)句或者一個(gè)數(shù)據(jù)有成熟的地址重定向技術(shù)允許程序在內(nèi)存中的位置不連續(xù)且可以變化5操作系統(tǒng)的解決辦法不再一次把一個(gè)進(jìn)程的全部信息都裝入到內(nèi)存中只是裝入一部分然后調(diào)度進(jìn)程運(yùn)行其他部分等到需要時(shí)再裝入6操作系統(tǒng)的解決辦法多大的程序都可以在有限的內(nèi)存中運(yùn)行程序員寫程序時(shí)再不用考慮內(nèi)存的大小程序員可以編寫使用任意大內(nèi)存空間的程序1G的程序，編譯程序編址地址空間從0到1G，程序可在只有256M內(nèi)存的計(jì)算機(jī)上運(yùn)行程序員感覺(jué)他有1G大的內(nèi)存空間，而不是256M7虛擬內(nèi)存技術(shù)虛擬內(nèi)存空間程序員寫程序時(shí)使用的地址空間虛擬內(nèi)存技術(shù)采用虛擬空間獨(dú)立編址、操作系統(tǒng)負(fù)責(zé)把一個(gè)大的虛擬空間的內(nèi)容分階段裝入實(shí)際內(nèi)存中運(yùn)行的技術(shù)程序員以為自己有一很大內(nèi)存空間，且獨(dú)享虛擬空間受限于地址寬度32位虛擬地址，虛擬空間上限4G8虛擬內(nèi)存技術(shù)的實(shí)現(xiàn)內(nèi)存分配訪問(wèn)內(nèi)存淘汰9內(nèi)存分配先把程序分成若干部分選擇把一部分裝載到內(nèi)存中記錄信息哪些部分裝載到內(nèi)存中，哪些沒(méi)有裝載到內(nèi)存中的部分放在什么位置可采用頁(yè)式、段式、段頁(yè)式10內(nèi)存分配頁(yè)式虛擬空間仍然分成頁(yè)在頁(yè)表中增加一個(gè)標(biāo)志，表示這個(gè)頁(yè)是否在內(nèi)存中如果在內(nèi)存中，頁(yè)表中記錄相應(yīng)頁(yè)框號(hào)11訪問(wèn)內(nèi)存查找頁(yè)表或者段表，判斷內(nèi)容是否在內(nèi)存中已經(jīng)被裝入到內(nèi)存中利用頁(yè)表或者段表中的信息，把虛擬地址轉(zhuǎn)換成對(duì)應(yīng)的物理地址未裝入到內(nèi)存在內(nèi)存中找一塊空閑空間分配給進(jìn)程把要訪問(wèn)的內(nèi)容從外存讀取到內(nèi)存修改頁(yè)表或者段表12淘汰如果內(nèi)存中沒(méi)有空閑空間，或者空閑空間低于限定值選擇內(nèi)存中一些正被使用的單元把里面的內(nèi)容寫回到外存把這些空間釋放出來(lái)分配給需要的進(jìn)程13淘汰抖動(dòng)選擇今后不會(huì)或者最近不會(huì)用到的內(nèi)容換出局部性原理一般情況下一個(gè)進(jìn)程在一段時(shí)間內(nèi)要訪問(wèn)的指令和數(shù)據(jù)都集中在一起14虛擬內(nèi)存技術(shù)實(shí)現(xiàn)的基礎(chǔ)局部性原理地址重定向技術(shù)使程序在一定程度上不再受物理內(nèi)存大小的限制15分頁(yè)技術(shù)實(shí)現(xiàn)的虛擬內(nèi)存內(nèi)存分配虛擬空間的管理物理內(nèi)存空間分成與頁(yè)面大小相同頁(yè)框空閑頁(yè)框管理頁(yè)表內(nèi)存訪問(wèn)缺頁(yè)中斷頁(yè)面淘汰16虛擬空間的管理地址長(zhǎng)度確定虛擬空間的大小如32位的Linux操作系統(tǒng)的虛擬空間大小4G分為系統(tǒng)空間和用戶空間17空閑頁(yè)框管理鏈表位圖18頁(yè)表創(chuàng)建新進(jìn)程時(shí)，在內(nèi)存中為進(jìn)程創(chuàng)建一個(gè)頁(yè)表為進(jìn)程分配內(nèi)存，填寫頁(yè)表相關(guān)內(nèi)容19頁(yè)表表項(xiàng)結(jié)構(gòu)頁(yè)面訪問(wèn)位A{0

頁(yè)面不在內(nèi)存1頁(yè)面在內(nèi)存0

頁(yè)面未被訪問(wèn)1頁(yè)面已被訪問(wèn)0

頁(yè)面未被修改1頁(yè)面已被修改判斷缺頁(yè)中斷影響頁(yè)面置換策略是否重寫外存

頁(yè)面存在位P{

頁(yè)面修改位M{頁(yè)號(hào)頁(yè)框號(hào)

存取控制頁(yè)面存在P頁(yè)面訪問(wèn)A頁(yè)面修改M外存地址20頁(yè)表大小4GB虛擬空間分成512字節(jié)大小的頁(yè)，共有4*230/29=4*221=8M個(gè)頁(yè)每個(gè)頁(yè)的頁(yè)表項(xiàng)占4個(gè)字節(jié)進(jìn)程頁(yè)表大小為8M*4B=32MB21解決辦法把頁(yè)表看作是在虛擬空間中整個(gè)頁(yè)表也被分頁(yè)頁(yè)表不全部放在內(nèi)存中每次系統(tǒng)只裝載頁(yè)表的一部分放在內(nèi)存中的頁(yè)表頁(yè)也不再連續(xù)存放22多級(jí)頁(yè)表頁(yè)目錄表描述哪些頁(yè)表頁(yè)已經(jīng)在內(nèi)存中、哪些還不在在內(nèi)存中的頁(yè)表頁(yè)放在什么地方23多級(jí)頁(yè)表24兩級(jí)頁(yè)表結(jié)構(gòu)的地址轉(zhuǎn)換25倒排頁(yè)表按頁(yè)框號(hào)排序每個(gè)頁(yè)框占有一個(gè)表項(xiàng)每個(gè)表項(xiàng)存放在該頁(yè)框中頁(yè)面的虛擬頁(yè)號(hào)擁有該頁(yè)面的進(jìn)程標(biāo)識(shí)符26倒排頁(yè)表27倒排頁(yè)表節(jié)省空間虛擬空間很大，如64位頁(yè)表大小（頁(yè)面大小為4KB，每個(gè)頁(yè)表項(xiàng)8個(gè)字節(jié)）8*264/212=255=235*220=235G查找費(fèi)時(shí)按照虛擬頁(yè)號(hào)查找整個(gè)頁(yè)表解決辦法散列頁(yè)表快表TLB28散列頁(yè)表以頁(yè)號(hào)作為參數(shù)形成散列值散列表中每一項(xiàng)有一個(gè)鏈表把有相同散列值的元素鏈接起來(lái)每個(gè)鏈表元素由三部分組成頁(yè)號(hào)對(duì)應(yīng)的內(nèi)存塊號(hào)指向鏈表中下一個(gè)元素的指針29散列頁(yè)表30關(guān)聯(lián)高速緩存TLB實(shí)現(xiàn)虛擬內(nèi)存引入時(shí)間開銷地址轉(zhuǎn)換的時(shí)間開銷讀取進(jìn)程的頁(yè)表、頁(yè)面目錄一次訪存變成兩次、三次訪存動(dòng)作CPU內(nèi)部設(shè)置專門用來(lái)存放頁(yè)表的緩存放置最近經(jīng)常用到的頁(yè)表項(xiàng)31高速關(guān)聯(lián)緩存提高查找頁(yè)表項(xiàng)的速度以其中某一存儲(chǔ)項(xiàng)內(nèi)容作為地址來(lái)存取的存儲(chǔ)器也稱TLB，TranslationLookasideBuffer（轉(zhuǎn)換檢測(cè)緩沖區(qū)）

32高速關(guān)聯(lián)緩存33單元訪問(wèn)訪問(wèn)虛擬地址單元的內(nèi)容按照頁(yè)面的大小計(jì)算頁(yè)號(hào)查詢頁(yè)表檢查該頁(yè)表項(xiàng)中“存在”標(biāo)志位如果存在標(biāo)志位被設(shè)置按頁(yè)表項(xiàng)中的頁(yè)框號(hào)計(jì)算物理地址；如果存在標(biāo)志位未被設(shè)置缺頁(yè)異常34缺頁(yè)異常異常與中斷異常也稱為同步中斷在處理器執(zhí)行到由于編程失誤而導(dǎo)致的錯(cuò)誤指令時(shí)，或者在執(zhí)行期間出現(xiàn)特殊情況（如缺頁(yè)），必須靠?jī)?nèi)核處理時(shí)，處理器就會(huì)產(chǎn)生一個(gè)異常中斷外部硬件產(chǎn)生的一個(gè)電信號(hào)，從CPU的中斷引腳進(jìn)入，打斷當(dāng)前CPU的運(yùn)行把需要的內(nèi)容裝入到內(nèi)存中并設(shè)置相應(yīng)的頁(yè)表項(xiàng)35缺頁(yè)中斷36多級(jí)頁(yè)表的使用計(jì)算出頁(yè)表項(xiàng)位于哪個(gè)頁(yè)表頁(yè)中根據(jù)頁(yè)表頁(yè)號(hào)查找頁(yè)目錄如果頁(yè)表項(xiàng)在內(nèi)存中得到頁(yè)表項(xiàng)在內(nèi)存中的位置，讀取頁(yè)表項(xiàng)、找到頁(yè)框號(hào)、計(jì)算出物理地址、訪問(wèn)物理單元如果頁(yè)表項(xiàng)未在內(nèi)存中，缺頁(yè)異常異常處理程序創(chuàng)建一個(gè)新的頁(yè)表頁(yè)37頁(yè)面的裝入預(yù)裝入訪問(wèn)速度很快浪費(fèi)空間按需裝入不浪費(fèi)空間浪費(fèi)時(shí)間38頁(yè)面的裝入通常操作系統(tǒng)會(huì)綜合利用這兩種方式創(chuàng)建進(jìn)程時(shí)，為每個(gè)進(jìn)程預(yù)裝入一定數(shù)量的頁(yè)面當(dāng)進(jìn)程執(zhí)行到一定階段，需要新頁(yè)面時(shí)，再按需要裝入裝入要訪問(wèn)的頁(yè)時(shí)捎帶把后面的頁(yè)也預(yù)裝入一些局部性原理39頁(yè)面的淘汰盡量減少缺頁(yè)異常的發(fā)生選擇以后再也不會(huì)用到的頁(yè)面淘汰選擇那些再次使用的時(shí)間距離現(xiàn)在最遠(yuǎn)的頁(yè)面淘汰40淘汰算法最優(yōu)策略（OPT）先進(jìn)先出法（FIFO）第二次機(jī)會(huì)置換法（SCR）最近最少訪問(wèn)的策略（LRU）簡(jiǎn)化形式的LRU工作集算法工作集時(shí)鐘算法41最優(yōu)策略（OPT）選擇以后再也不會(huì)用到的頁(yè)面淘汰選擇那些再次使用的時(shí)間距離現(xiàn)在最遠(yuǎn)的頁(yè)面淘汰42最優(yōu)策略（OPT）43最優(yōu)策略（OPT）操作系統(tǒng)需要知道將來(lái)要使用的頁(yè)面順序作為一個(gè)最好的標(biāo)準(zhǔn)用在理想的實(shí)驗(yàn)環(huán)境下評(píng)測(cè)其他實(shí)用的淘汰策略44先進(jìn)先出（FIFO）法直接換出最早裝入的頁(yè)面容易理解方便程序設(shè)計(jì)45先進(jìn)先出（FIFO）法46先進(jìn)先出（FIFO）法性能并不很好缺點(diǎn)存在Belady異?，F(xiàn)象，即缺頁(yè)率隨內(nèi)存塊增加而增加反常的現(xiàn)象：內(nèi)存中可裝入頁(yè)面數(shù)增加了，缺頁(yè)異常數(shù)反而也增加了淘汰的是常用頁(yè)面47第二次機(jī)會(huì)置換法（SCR）SecondChancePageReplacement,SCR對(duì)FIFO算法的改進(jìn)避免把經(jīng)常使用的頁(yè)面置換出去按時(shí)間順序檢查設(shè)置頁(yè)面訪問(wèn)位，檢查隊(duì)首頁(yè)面的訪問(wèn)位0：淘汰該頁(yè)；1：轉(zhuǎn)移到隊(duì)尾，給第二次機(jī)會(huì)48時(shí)鐘置換法（Clock）將頁(yè)面保存在環(huán)形鏈表中避免SCR法在鏈表中移動(dòng)頁(yè)面49最近最少訪問(wèn)的策略LRU，LeastRecentlyUsed猜測(cè)將來(lái)可能訪問(wèn)的頁(yè)面序列如果一個(gè)頁(yè)面很久沒(méi)有被訪問(wèn)，根據(jù)局部性原理，將來(lái)被訪問(wèn)的可能性也比較小選擇未被訪問(wèn)時(shí)間最長(zhǎng)的那些頁(yè)面換出50LRU策略51最近最少訪問(wèn)的策略為每個(gè)在內(nèi)存中的頁(yè)面維持一個(gè)計(jì)時(shí)器頁(yè)面被訪問(wèn)時(shí)，計(jì)時(shí)器清0，否則隨時(shí)間增長(zhǎng)操作系統(tǒng)要淘汰頁(yè)面時(shí)，比較頁(yè)面計(jì)時(shí)器，選出時(shí)間最長(zhǎng)的頁(yè)面實(shí)驗(yàn)表明LRU的效果比FIFO要好52簡(jiǎn)化形式的LRULRU策略的實(shí)現(xiàn)開銷非常大為每個(gè)頁(yè)設(shè)置一個(gè)標(biāo)志位，表示這個(gè)頁(yè)面最近是否被訪問(wèn)過(guò)，稱為訪問(wèn)位通常設(shè)置在每個(gè)頁(yè)的頁(yè)表項(xiàng)中頁(yè)面被訪問(wèn)時(shí)，訪問(wèn)位設(shè)置為1操作系統(tǒng)定期將所有頁(yè)面的訪問(wèn)位清0當(dāng)操作系統(tǒng)需要挑選頁(yè)面換出時(shí)，選擇訪問(wèn)位為0的頁(yè)面使用最多的策略53工作集替換算法工作集一個(gè)進(jìn)程當(dāng)前正在使用的頁(yè)面的集合workingset若整個(gè)工作集都被裝入內(nèi)存，進(jìn)程在運(yùn)行到下一運(yùn)行階段前，不會(huì)產(chǎn)生很多缺頁(yè)中斷找出一個(gè)不在工作集中的頁(yè)面并淘汰它工作集w(k,t)在任一時(shí)刻t，包含所有最近k次內(nèi)存訪問(wèn)所訪問(wèn)過(guò)的頁(yè)面的一個(gè)集合54工作集替換算法工作集模型設(shè)法跟蹤進(jìn)程的工作集，以確保在讓進(jìn)程運(yùn)行以前，它的工作集就已在內(nèi)存中了跟蹤進(jìn)程的工作集用長(zhǎng)度為k的移位寄存器，每次內(nèi)存訪問(wèn)把寄存器左移一位，在最右端插入剛訪問(wèn)的頁(yè)面號(hào)缺頁(yè)時(shí)，讀出移位寄存器內(nèi)容并排序，刪除重復(fù)的頁(yè)面，即得到工作集維護(hù)移位寄存器并在缺頁(yè)中斷時(shí)處理它所需的開銷很大，從未被用過(guò)55工作集替換算法頁(yè)表設(shè)置“訪問(wèn)位”、上次訪問(wèn)近似時(shí)間定期的時(shí)鐘中斷用軟件方法清除訪問(wèn)位替換算法過(guò)程檢查頁(yè)面的訪問(wèn)位，若訪問(wèn)位1：把當(dāng)前實(shí)際時(shí)間寫進(jìn)頁(yè)表項(xiàng)的“上次使用時(shí)間”域，以表示缺頁(yè)中斷發(fā)生時(shí)該頁(yè)面正在被使用該頁(yè)面在當(dāng)前時(shí)鐘滴答中已經(jīng)被訪問(wèn)過(guò)，在工作集中，不應(yīng)該被刪除若所有頁(yè)面都被訪問(wèn)過(guò)，則隨機(jī)選擇56工作集替換算法替換算法過(guò)程檢查頁(yè)面的訪問(wèn)位，若訪問(wèn)位0：當(dāng)前時(shí)鐘滴答中，該頁(yè)面還沒(méi)有被訪問(wèn)過(guò)，可以作為候選者被置換需要計(jì)算生存時(shí)間（即當(dāng)前實(shí)際運(yùn)行時(shí)間減去上次使用時(shí)間）若生存時(shí)間大于t，則不在工作集，置換若不大于t，則在工作集，不能置換若全在工作集中，選擇生存時(shí)間最長(zhǎng)的比較費(fèi)時(shí)57工作集時(shí)鐘算法以頁(yè)框?yàn)樵氐难h(huán)表58頁(yè)面淘汰：其他考慮盡量選擇那些沒(méi)有被改動(dòng)的頁(yè)面操作系統(tǒng)需要把選定淘汰頁(yè)面寫回到外存如果頁(yè)面沒(méi)有被改寫，和外存中原來(lái)的頁(yè)面是一樣的，沒(méi)有必要再重寫回外存換出沒(méi)有被改動(dòng)的頁(yè)面，只要改動(dòng)該頁(yè)的頁(yè)表項(xiàng)，并在系統(tǒng)中標(biāo)記這個(gè)頁(yè)沒(méi)有被使用每個(gè)頁(yè)的頁(yè)表項(xiàng)中增加一個(gè)標(biāo)志位，稱為“修改位”，表示頁(yè)面是否被修改過(guò)59頁(yè)表表項(xiàng)結(jié)構(gòu)頁(yè)面訪問(wèn)位A{0

頁(yè)面不在內(nèi)存1