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