虛擬內存管理

北京工業大學軟件學院張麗1整理ppt主要內容虛擬內存技術的引入虛擬內存技術概念虛擬內存的實現分頁技術實現的虛擬內存2整理ppt虛擬內存技術的引入內存空間大小的問題內存空間問題的解決方法軟件解決方案的根底操作系統的解決方法3整理ppt內存空間大小的問題每個程序運行所需空間不能超過可用內存程序會因不能裝入內存而無法運行程序的功能越來越復雜、代碼越來越長采用覆蓋技術限制太大程序員在寫程序時要考慮內存大小、考慮覆蓋4整理ppt內存空間問題的解決方法硬件：增加內存軟件：改變程序的要求問題關鍵：如果程序可以不用全部放在內存中就能夠執行5整理ppt軟件解決方案的根底并不需要所有代碼和數據都放到內存中一個CPU在某個時刻只能訪問一條語句或者一個數據有成熟的地址重定向技術允許程序在內存中的位置不連續且可以變化6整理ppt操作系統的解決方法不再一次把一個進程的全部信息都裝入到內存中只是裝入一局部然后調度進程運行其他局部等到需要時再裝入7整理ppt操作系統的解決方法多大的程序都可以在有限的內存中運行程序員寫程序時再不用考慮內存的大小程序員可以編寫使用任意大內存空間的程序1G的程序，編譯程序編址地址空間從0到1G，程序可在只有256M內存的計算機上運行程序員感覺他有1G大的內存空間，而不是256M8整理ppt虛擬內存技術虛擬內存空間程序員寫程序時使用的地址空間虛擬內存技術采用虛擬空間獨立編址、操作系統負責把一個大的虛擬空間的內容分階段裝入實際內存中運行的技術程序員以為自己有一很大內存空間，且獨享虛擬空間受限于地址寬度32位虛擬地址，虛擬空間上限4G9整理ppt虛擬內存技術的實現內存分配訪問內存淘汰10整理ppt內存分配先把程序分成假設干局部選擇把一局部裝載到內存中記錄信息哪些局部裝載到內存中，哪些沒有裝載到內存中的局部放在什么位置可采用頁式、段式、段頁式11整理ppt內存分配頁式虛擬空間仍然分成頁在頁表中增加一個標志，表示這個頁是否在內存中如果在內存中，頁表中記錄相應頁框號12整理ppt訪問內存查找頁表或者段表，判斷內容是否在內存中已經被裝入到內存中利用頁表或者段表中的信息，把虛擬地址轉換成對應的物理地址未裝入到內存在內存中找一塊空閑空間分配給進程把要訪問的內容從外存讀取到內存修改頁表或者段表13整理ppt淘汰如果內存中沒有空閑空間，或者空閑空間低于限定值選擇內存中一些正被使用的單元把里面的內容寫回到外存把這些空間釋放出來分配給需要的進程14整理ppt淘汰抖動選擇今后不會或者最近不會用到的內容換出局部性原理一般情況下一個進程在一段時間內要訪問的指令和數據都集中在一起15整理ppt虛擬內存技術實現的根底局部性原理地址重定向技術使程序在一定程度上不再受物理內存大小的限制16整理ppt分頁技術實現的虛擬內存內存分配虛擬空間的管理物理內存空間分成與頁面大小相同頁框空閑頁框管理頁表內存訪問缺頁中斷頁面淘汰17整理ppt虛擬空間的管理地址長度確定虛擬空間的大小如32位的Linux操作系統的虛擬空間大小4G分為系統空間和用戶空間18整理ppt空閑頁框管理鏈表位圖19整理ppt頁表創立新進程時，在內存中為進程創立一個頁表為進程分配內存，填寫頁表相關內容20整理ppt頁表表項結構頁面訪問位A{0

頁面不在內存1頁面在內存0

頁面未被訪問1頁面已被訪問0

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

頁面存在位P{

頁面修改位M{頁號頁框號

存取控制頁面存在P頁面訪問A頁面修改M外存地址21整理ppt頁表大小4GB虛擬空間分成512字節大小的頁，共有4*230/29=4*221=8M個頁每個頁的頁表項占4個字節進程頁表大小為8M*4B=32MB22整理ppt解決方法把頁表看作是在虛擬空間中整個頁表也被分頁頁表不全部放在內存中每次系統只裝載頁表的一局部放在內存中的頁表頁也不再連續存放23整理ppt多級頁表頁目錄表描述哪些頁表頁已經在內存中、哪些還不在在內存中的頁表頁放在什么地方24整理ppt多級頁表25整理ppt兩級頁表結構的地址轉換26整理ppt倒排頁表按頁框號排序每個頁框占有一個表項每個表項存放在該頁框中頁面的虛擬頁號擁有該頁面的進程標識符27整理ppt倒排頁表28整理ppt倒排頁表節省空間虛擬空間很大，如64位頁表大小〔頁面大小為4KB，每個頁表項8個字節〕8*264/212=255=235*220=235G查找費時按照虛擬頁號查找整個頁表解決方法散列頁表快表TLB29整理ppt散列頁表以頁號作為參數形成散列值散列表中每一項有一個鏈表把有相同散列值的元素鏈接起來每個鏈表元素由三局部組成頁號對應的內存塊號指向鏈表中下一個元素的指針30整理ppt散列頁表31整理ppt關聯高速緩存TLB實現虛擬內存引入時間開銷地址轉換的時間開銷讀取進程的頁表、頁面目錄一次訪存變成兩次、三次訪存動作CPU內部設置專門用來存放頁表的緩存放置最近經常用到的頁表項32整理ppt高速關聯緩存提高查找頁表項的速度以其中某一存儲項內容作為地址來存取的存儲器也稱TLB，TranslationLookasideBuffer〔轉換檢測緩沖區〕33整理ppt高速關聯緩存34整理ppt單元訪問訪問虛擬地址單元的內容按照頁面的大小計算頁號查詢頁表檢查該頁表項中“存在〞標志位如果存在標志位被設置按頁表項中的頁框號計算物理地址；如果存在標志位未被設置缺頁異常35整理ppt缺頁異常異常與中斷異常也稱為同步中斷在處理器執行到由于編程失誤而導致的錯誤指令時，或者在執行期間出現特殊情況〔如缺頁〕，必須靠內核處理時，處理器就會產生一個異常中斷外部硬件產生的一個電信號，從CPU的中斷引腳進入，打斷當前CPU的運行把需要的內容裝入到內存中并設置相應的頁表項36整理ppt缺頁中斷37整理ppt多級頁表的使用計算出頁表項位于哪個頁表頁中根據頁表頁號查找頁目錄如果頁表項在內存中得到頁表項在內存中的位置，讀取頁表項、找到頁框號、計算出物理地址、訪問物理單元如果頁表項未在內存中，缺頁異常異常處理程序創立一個新的頁表頁38整理ppt頁面的裝入預裝入訪問速度很快浪費空間按需裝入不浪費空間浪費時間39整理ppt頁面的裝入通常操作系統會綜合利用這兩種方式創立進程時，為每個進程預裝入一定數量的頁面當進程執行到一定階段，需要新頁面時，再按需要裝入裝入要訪問的頁時捎帶把后面的頁也預裝入一些局部性原理40整理ppt頁面的淘汰盡量減少缺頁異常的發生選擇以后再也不會用到的頁面淘汰選擇那些再次使用的時間距離現在最遠的頁面淘汰41整理ppt淘汰算法最優策略〔OPT〕先進先出法〔FIFO〕第二次時機置換法〔SCR〕最近最少訪問的策略〔LRU〕簡化形式的LRU工作集算法工作集時鐘算法42整理ppt最優策略〔OPT〕選擇以后再也不會用到的頁面淘汰選擇那些再次使用的時間距離現在最遠的頁面淘汰43整理ppt最優策略〔OPT〕44整理ppt最優策略〔OPT〕操作系統需要知道將來要使用的頁面順序作為一個最好的標準用在理想的實驗環境下評測其他實用的淘汰策略45整理ppt先進先出〔FIFO〕法直接換出最早裝入的頁面容易理解方便程序設計46整理ppt先進先出〔FIFO〕法47整理ppt先進先出〔FIFO〕法性能并不很好缺點存在Belady異常現象，即缺頁率隨內存塊增加而增加反常的現象：內存中可裝入頁面數增加了，缺頁異常數反而也增加了淘汰的是常用頁面48整理ppt第二次時機置換法〔SCR〕SecondChancePageReplacement,SCR對FIFO算法的改進防止把經常使用的頁面置換出去按時間順序檢查設置頁面訪問位，檢查隊首頁面的訪問位0：淘汰該頁；1：轉移到隊尾，給第二次時機49整理ppt時鐘置換法〔Clock〕將頁面保存在環形鏈表中防止SCR法在鏈表中移動頁面50整理ppt最近最少訪問的策略LRU，LeastRecentlyUsed猜測將來可能訪問的頁面序列如果一個頁面很久沒有被訪問，根據局部性原理，將來被訪問的可能性也比較小選擇未被訪問時間最長的那些頁面換出51整理pptLRU策略52整理ppt最近最少訪問的策略為每個在內存中的頁面維持一個計時器頁面被訪問時，計時器清0，否那么隨時間增長操作系統要淘汰頁面時，比較頁面計時器，選出時間最長的頁面實驗說明LRU的效果比FIFO要好53整理ppt簡化形式的LRULRU策略的實現開銷非常大為每個頁設置一個標志位，表示這個頁面最近是否被訪問過，稱為訪問位通常設置在每個頁的頁表項中頁面被訪問時，訪問位設置為1操作系統定期將所有頁面的訪問位清0當操作系統需要挑選頁面換出時，選擇訪問位為0的頁面使用最多的策略54整理ppt工作集替換算法工作集一個進程當前正在使用的頁面的集合workingset假設整個工作集都被裝入內存，進程在運行到下一運行階段前，不會產生很多缺頁中斷找出一個不在工作集中的頁面并淘汰它工作集w(k,t)在任一時刻t，包含所有最近k次內存訪問所訪問過的頁面的一個集合55整理ppt工作集替換算法工作集模型設法跟蹤進程的工作集，以確保在讓進程運行以前，它的工作集就已在內存中了跟蹤進程的工作集用長度為k的移位存放器，每次內存訪問把存放器左移一位，在最右端插入剛訪問的頁面號缺頁時，讀出移位存放器內容并排序，刪除重復的頁面，即得到工作集維護移位存放器并在缺頁中斷時處理它所需的開銷很大，從未被用過56整理ppt工作集替換算法頁表設置“訪問位〞、上次訪問近似時間定期的時鐘中斷用軟件方法去除訪問位替換算法過程檢查頁面的訪問位，假設訪問位1：把當前實際時間寫進頁表項的“上次使用時間〞域，以表示缺頁中斷發生時該頁面正在被使用該頁面在當前時鐘滴答中已經被訪問過，在工作集中，不應該被刪除假設所有頁面都被訪問過，那么隨機選擇57整理ppt工作集替換算法替換算法過程檢查頁面的訪問位，假設訪問位0：當前時鐘滴答中，該頁面還沒有被訪問過，可以作為候選者被置換需要計算生存時間〔即當前實際運行時間減去上次使用時間〕假設生存時間大于t，那么不在工作集，置換假設不大于t，那么在工作集，不能置換假設全在工作集中，選擇生存時間最長的比較費時58整理ppt工作集時鐘算法以頁框為元素的循環表59整理ppt頁面淘汰：其他考慮盡量選擇那些沒有被改動的頁面操作系統需要把選定淘汰頁面寫回到外存如果頁面沒有被改寫，和外存中原來的頁面是一樣的，沒有必要再重寫回外存換出沒有被改動的頁面，只要改動該頁的頁表項，并在系統中標記這個頁沒有被使用每個頁的頁表項中增加一個標志位，稱為“修改位〞，表示頁面是否被修改正