第二十七課虛擬內(nèi)存Virtual Memory一、什么是虛擬內(nèi)存一句話虛擬內(nèi)存是一種讓程序感覺自己擁有比實際內(nèi)存更大空間的技術(shù)。例如你的電腦實際8GB RAM但是程序看到幾十GB地址空間為什么因為操作系統(tǒng)把一部分內(nèi)容放內(nèi)存。一部分內(nèi)容放硬盤。需要時再調(diào)入。類似你的書桌。桌子只能放10本書。但是你有100本書。怎么辦不會把100本全部攤桌上。而是桌上放正在看的10本。其他放書柜。需要再換。對應(yīng)書桌 內(nèi)存 書柜 外存硬盤 換書 頁面調(diào)入調(diào)出二、為什么需要虛擬內(nèi)存主要有三個原因。1. 運行大程序以前程序必須全部裝入內(nèi)存?，F(xiàn)在不用。例如大型軟件100GB。電腦16GB內(nèi)存。仍然可以運行。因為只加載當(dāng)前需要部分。2. 提高內(nèi)存利用率如果10個程序。每個只用20%。以前全部加載浪費。現(xiàn)在只加載需要部分?？梢赃\行更多程序。3. 保護進程每個程序擁有自己的虛擬地址空間?；ゲ挥绊?。三、虛擬內(nèi)存的核心思想記住一句話離散裝入按需調(diào)入。什么意思離散裝入程序不用連續(xù)放。還是分頁。按需調(diào)入需要哪一頁。才加載哪一頁。所以虛擬內(nèi)存建立在分頁基礎(chǔ)上。四、請求分頁系統(tǒng)★★★★★現(xiàn)代操作系統(tǒng)主要使用請求分頁存儲管理。名字拆開請求需要時才加載。分頁程序分成頁面。系統(tǒng)開始運行只加載部分頁面。例如程序有100頁。啟動只加載10頁。其他不加載。運行訪問第50頁。發(fā)現(xiàn)沒有。怎么辦產(chǎn)生缺頁中斷五、什么是缺頁中斷重點缺頁意思當(dāng)前需要的頁面不在內(nèi)存。例如程序訪問頁20。頁表發(fā)現(xiàn)頁20 × 不在內(nèi)存于是發(fā)生缺頁中斷。流程CPU訪問頁面 ↓ 檢查頁表 ↓ 發(fā)現(xiàn)頁面不在內(nèi)存 ↓ 缺頁中斷 ↓ 操作系統(tǒng)處理 ↓ 從硬盤調(diào)入頁面 ↓ 更新頁表 ↓ 繼續(xù)執(zhí)行六、缺頁中斷為什么特殊普通中斷例如鍵盤輸入。CPU暫停。處理。缺頁中斷更復(fù)雜。因為它需要訪問外存。外存很慢。所以缺頁代價很高。七、頁表中的關(guān)鍵位為了支持虛擬內(nèi)存頁表增加一些信息。① 狀態(tài)位存在位表示頁面是否在內(nèi)存。例如1在內(nèi)存 0不在內(nèi)存② 訪問字段記錄頁面最近是否被訪問。后面頁面置換算法會使用。③ 修改位表示頁面是否被修改。為什么重要因為如果頁面沒修改。換出去不用寫回硬盤。八、虛擬內(nèi)存工作流程完整過程程序運行 ↓ CPU產(chǎn)生邏輯地址 ↓ 查頁表 ↓ 頁面存在 ↓ 是 ↓ 訪問內(nèi)存 否 ↓ 缺頁中斷 ↓ 尋找空閑頁框 ↓ 調(diào)入頁面 ↓ 更新頁表 ↓ 繼續(xù)運行九、局部性原理★★★★★為什么虛擬內(nèi)存有效因為程序運行有規(guī)律。這個規(guī)律叫局部性原理。分兩種1. 時間局部性意思最近訪問過的數(shù)據(jù)很可能馬上再次訪問。例如循環(huán)for(i0;i100;i){sum;}sum一直使用。2. 空間局部性意思當(dāng)前訪問附近的數(shù)據(jù)也可能被訪問。例如數(shù)組a[0]a[1]a[2]通常連續(xù)訪問。因為存在局部性。所以不用一次加載全部程序。十、虛擬內(nèi)存的問題虛擬內(nèi)存很好。但是有一個風(fēng)險。如果內(nèi)存太小。程序頻繁換入換出。會發(fā)生什么CPU大部分時間不是運行程序。而是在搬頁面。這種現(xiàn)象叫抖動Thrashing例如學(xué)生桌子太小。一本書剛拿出來。馬上又放回去。換另一本。一直整理。沒有學(xué)習(xí)。計算機也是一樣。十一、本課重點總結(jié)★★★★★必須掌握虛擬內(nèi)存定義讓程序邏輯上擁有比物理內(nèi)存更大的空間。核心思想按需調(diào)入 離散存儲請求分頁需要哪頁加載哪頁。缺頁中斷頁面不在內(nèi)存。產(chǎn)生中斷。局部性原理為什么虛擬內(nèi)存有效時間局部性空間局部性抖動頻繁頁面交換。導(dǎo)致系統(tǒng)性能下降。十二、口訣虛擬內(nèi)存程序不用全裝入需要哪頁調(diào)哪頁。缺頁頁不在產(chǎn)生中斷調(diào)入后繼續(xù)干。局部性剛用還會用附近也可能用。第二十八課頁面置換算法Page Replacement Algorithm一、為什么需要頁面置換假設(shè)內(nèi)存只有3個頁框?，F(xiàn)在已經(jīng)裝入頁1 頁2 頁3來了頁4。怎么辦內(nèi)存滿了。必須選擇一個頁面換出去。這個過程叫頁面置換Page Replacement二、頁面置換的目標(biāo)目標(biāo)很簡單盡量減少缺頁次數(shù)。為什么因為缺頁需要訪問硬盤。而硬盤非常慢。所以好的算法應(yīng)該預(yù)測哪個頁面以后最不需要。三、算法一最佳置換算法 OPT★★★★★OPTOptimal。中文最佳置換。思想淘汰未來最長時間不會被訪問的頁面。注意關(guān)鍵詞未來。例如當(dāng)前內(nèi)存1 2 3下一次訪問4未來訪問序列1 2 5 1 3 4問換誰看三個頁面未來什么時候再次出現(xiàn)。頁1馬上出現(xiàn)。頁2后面出現(xiàn)。頁3較晚出現(xiàn)。所以淘汰頁3。四、OPT的特點優(yōu)點理論上最好。缺頁次數(shù)最低。缺點現(xiàn)實中無法實現(xiàn)。為什么因為操作系統(tǒng)不知道未來。所以O(shè)PT主要用于比較其他算法?？荚嚱?jīng)常問哪個算法缺頁最少答案OPT。五、算法二FIFO★★★★★FIFOFirst In First Out。中文先進先出。思想誰最早進入內(nèi)存就淘汰誰。類似排隊買票。最早排隊的人先離開。例如三個頁框。訪問1 2 3 4過程開始空。訪問1[1]訪問2[1 2]訪問3[1 2 3]訪問4滿了。誰最早頁1。淘汰頁1。結(jié)果[4 2 3]六、FIFO的問題Belady異?！铩铩铩铩镞@是考試重點。正常想內(nèi)存越大。缺頁越少。但是FIFO可能反而更多。這叫Belady異常。例如3個頁框缺頁9次。增加到4個頁框缺頁10次。反而增加。為什么因為FIFO只看進入時間。不看使用情況。七、算法三LRU★★★★★L(fēng)RULeast Recently Used。中文最近最久未使用。思想淘汰最長時間沒有被使用的頁面。它比FIFO聰明。因為利用局部性原理。例如當(dāng)前內(nèi)存1 2 3訪問頁4?？醋罱褂们闆r。如果頁1很久沒訪問。頁2剛訪問。頁3也剛訪問。淘汰頁1。八、LRU為什么有效因為程序具有時間局部性。如果一個頁面很久沒使用。那么近期大概率也不會使用。所以LRU性能接近OPT。九、三種算法比較★★★★★算法依據(jù)優(yōu)點缺點OPT未來訪問最好無法實現(xiàn)FIFO進入時間簡單可能Belady異常LRU過去訪問效果好實現(xiàn)復(fù)雜口訣OPT看未來 FIFO看年齡 LRU看最近十、缺頁次數(shù)計算方法重點考試通常給訪問序列。例如頁訪問7 0 1 2 0 3 0 4頁框3個。問FIFO缺頁次數(shù)。步驟畫表。例如訪問 7 0 1 2 0 3 框1 7 7 7 2 2 2 框2 0 0 0 0 3 框3 1 1 1 1每次新頁面進入算一次缺頁。十一、一個簡單例子頁面1 2 3 1 4三個頁框。訪問1缺頁。內(nèi)存1訪問2缺頁。1 2訪問3缺頁。1 2 3訪問1已經(jīng)存在。不缺頁。訪問4沒有。缺頁?？?cè)表?次。十二、LRU和FIFO容易混這是很多人的坑。FIFO問誰進去最早例如進入順序 1 2 3換1。LRU問誰最近最久沒用例如最近3剛用 2剛用 1很久沒用換1?？赡芙Y(jié)果一樣。但是判斷方法不同。十三、Clock算法了解真實系統(tǒng)很少直接使用純LRU。因為記錄訪問時間成本高。所以出現(xiàn)Clock算法。思想模擬LRU。每個頁面有一個訪問位0 / 1訪問設(shè)置1。置換尋找訪問位為0的頁面。408一般重點OPT、FIFO、LRU。十四、本課重點總結(jié)★★★★★必須掌握OPT淘汰未來最長時間不用。理論最優(yōu)。FIFO淘汰最早進入內(nèi)存頁面?？赡墚a(chǎn)生Belady異常。LRU淘汰最近最長時間沒使用頁面。利用局部性。缺頁次數(shù)計算畫表模擬。十五、最終口訣頁面置換最佳看未來 先進看進入 最近看過去