操作系統(tǒng)筆記：內(nèi)存虛擬化

程序自身并不需要關(guān)心自己的數(shù)據(jù)及代碼存在哪，并且對程序來說，內(nèi)存看上去是連續(xù)且獨占的。當(dāng)然事實肯定不是如此，而這背后就是操作系統(tǒng)的功勞 —— 內(nèi)存虛擬化。本篇文章就介紹操作系統(tǒng)是如何實現(xiàn)虛擬內(nèi)存系統(tǒng)的。

操作系統(tǒng)提供了一個易用的物理內(nèi)存抽象：地址空間。地址空間是運行的程序看到的系統(tǒng)中的內(nèi)存。

一個進(jìn)程的地址空間包含運行的程序的所有內(nèi)存狀態(tài)。每次內(nèi)存引用時，硬件都會進(jìn)行地址轉(zhuǎn)換，將應(yīng)用程序的內(nèi)存引用重定向到內(nèi)存中實際的位置。

為了完成地址轉(zhuǎn)換，每個 CPU 需要兩個硬件寄存器：基址 (base) 寄存器和界限 (bound) 寄存器。程序的起始地址存放在基址寄存器。進(jìn)程產(chǎn)生的所有內(nèi)存引用，都會被處理器通過以下方式轉(zhuǎn)換成物理地址：

界限寄存器的作用在于，確保了進(jìn)程產(chǎn)生的所有地址都在進(jìn)程的地址 “界限” 中。

操作系統(tǒng)和硬件支持結(jié)合，實現(xiàn)了虛擬內(nèi)存，而為了實現(xiàn)虛擬內(nèi)存，操作系統(tǒng)所需要做的工作如下：

為了解決連續(xù)內(nèi)存的浪費問題，操作系統(tǒng)引入了分段。

具體來說，在 MMU 中引入不止一個基址和界限寄存器對，而是給地址空間內(nèi)的每個邏輯段一對。一個段只是地址空間里的一個連續(xù)定長的區(qū)域，在典型的地址空間里有 3 個邏輯不同的段：代碼、棧和堆。

分段機(jī)制使得操作系統(tǒng)能夠?qū)⒉煌亩畏湃氩煌奈锢韮?nèi)存區(qū)域，從而避免了虛擬地址空間中的未使用部分占用物理內(nèi)存。如下圖所示：

而如何從一個虛擬地址中識別出對應(yīng)的段是哪一個，主要有兩個方法：

分段帶來一些新的問題。

第一個是段寄存器的值必須被保存和恢復(fù)。每個進(jìn)程都有自己獨立的虛擬地址空間，操作系統(tǒng)必須在進(jìn)程運行前，確保這些寄存器被正確的賦值。

第二個也是更重要的問題是分段會帶來外部碎片?？臻e空間被分割成不同大小的小塊，成為碎片，后續(xù)的請求可能會失敗，因為沒有一塊足夠大的連續(xù)空閑空間，即使這時總的空閑空間超出了請求的大小。

解決外部碎片的一種方法是緊湊物理內(nèi)存，重新安排原有的段，但內(nèi)存緊湊成本很高；另一種簡單的方法是使用空閑列表（free-list）管理算法，試圖保留大額內(nèi)存用于分配。目前已經(jīng)有數(shù)百種方法，包括經(jīng)典算法：

還有一些改進(jìn)策略：

然而不管算法多么精妙，外部碎片仍然存在，無法完全消除。唯一真正解決的辦法就是完全避免這個問題，永遠(yuǎn)不要分配不同大小的內(nèi)存塊，這也是分頁被引入的原因。

分頁不是將一個進(jìn)程的地址空間分割成幾個不同長度的邏輯段 (即代碼、堆、段)，而是分割成固定大小的單元，每個單元稱為一頁。相應(yīng)的，我們把物理內(nèi)存看成是定長槽塊的陣列，叫做頁幀。每個頁幀包含一個虛擬內(nèi)存頁。

操作系統(tǒng)為每個進(jìn)程保存一個數(shù)據(jù)結(jié)構(gòu)，稱為頁表。主要用來為地址空間的每個虛擬頁面保存地址轉(zhuǎn)換，從而讓我們知道每個頁在物理內(nèi)存中的位置。

虛擬地址分成兩個組件：虛擬頁號（VPN）和頁內(nèi)的偏移量（offset）

通過虛擬頁號，我們現(xiàn)在可以檢索頁表，找到虛擬頁所在的物理頁面。因此，我們可以通過用物理幀號替換虛擬頁號來轉(zhuǎn)換此虛擬地址，然后將載入發(fā)送給物理內(nèi)存。偏移量保持不變，因為偏移量只是告訴我們頁面中的哪個字節(jié)是我們想要的。如下圖所示：

簡言之，頁表就是一種數(shù)據(jù)結(jié)構(gòu)，用于將虛擬地址 (或者實際上，是虛擬頁號) 映射到物理地址 (物理幀號)。因此任何數(shù)據(jù)結(jié)構(gòu)都可以采用，最簡單的形式成為線性頁表，就是一個數(shù)組。操作系統(tǒng)通過虛擬頁號 (VPN) 檢索該數(shù)組，并在該索引處查找頁表項 (PTE) ，以找到期望的物理幀號 (PFN)。

對于每個內(nèi)存引用，分頁都需要我們執(zhí)行一個額外的內(nèi)存引用，以便首先從頁表中獲取地址轉(zhuǎn)換。額外的內(nèi)存引用開銷很大，而且在這種情況下，可能會使進(jìn)程減慢兩倍或更多。

分頁雖然看起來是內(nèi)存虛擬化需求的一個很好的解決方案，但這兩個關(guān)鍵問題必須先克服。

為了解決頁表內(nèi)存開銷過多的問題，Multics 的創(chuàng)造者提出了分頁和分段結(jié)合的想法。解決方法是，不是為進(jìn)程的整個地址空間提供單個頁表，而是為每個邏輯分擔(dān)提供一個頁表。

在分段中，有一個基址寄存器用來存放每個段在物理內(nèi)存中的位置，還有一個界限寄存器用來存放該段的大小。在這里依然使用這些結(jié)構(gòu)，不過，基址不是指向段本身，而是保存該段的頁表的物理地址；界限寄存器用來指示頁表的結(jié)尾（即它有多少有效位）。

這種雜合方案的關(guān)鍵區(qū)別在于，每個分段都有界限寄存器，每個界限寄存器保存了段中最大有效頁的值。例如，如果代碼段使用前3個頁，則代碼段頁表將只有3個項分配給它，并且界限寄存器將被設(shè)置為3。與線性頁表相比，雜合方法實現(xiàn)了顯著的內(nèi)存節(jié)省，棧和堆之間未分配的頁不再占用頁表中的空間 (僅將其標(biāo)記為無效)。

而這種方法的弊端在于，一是它仍然要求使用分段，如果有一個大而稀疏的堆，仍然可能導(dǎo)致大量的頁表浪費；二是外部碎片再次出現(xiàn)，盡管大部分內(nèi)存是以頁表大小單位管理的，但頁表現(xiàn)在可以是任意大小 (PTE 的倍數(shù))。

多級頁表也是用來解決頁表占用太多內(nèi)存的問題，去掉頁表中的所有無效區(qū)域，而不是將它們?nèi)勘Ａ粼趦?nèi)存中。多級頁表將線性頁表變成了樹。

首先，將頁表分成頁大小的單元；然后，如果整頁的頁表項 (PTE) 無效，就完全不分配該頁的頁表。為了追蹤頁表的也是否有效 (以及如果有效，它在內(nèi)存中的位置)，使用了名為頁目錄的新結(jié)構(gòu)。頁目錄可以告訴你頁表的頁在哪里，或者頁表的整個頁不包含有效頁。

下面的圖展示了一個例子，左邊是經(jīng)典的線性頁表，即使地址空間的大部分中間區(qū)域無效 (即頁表的中間兩頁)，我們?nèi)匀恍枰獮檫@些區(qū)域分配頁表空間；右邊是一個多級頁表，頁目錄僅將這些區(qū)域分配頁表空間 (即第一個和最后一個)，頁表的這兩頁就駐留在內(nèi)存中。因此，我們可以形象地看到多級頁表的工作方式：只是讓線性頁表的一部分消失 (釋放這些幀用作其他用途)，并用頁目錄記錄頁表的哪些頁也被分配。

在一個簡單的兩級頁表中，頁目錄為每頁頁表包含了一項。由多個頁目錄項 (PDE) 組成，PDE 至少擁有有效位 (valid bit) 和頁幀號 (PFN)，類似于 PTE。但這個有效位的含義稍有不同：如果 PDE 項是有效的，則意味著該項指向的頁表 (通過 PTE) 中至少有一頁是有效的，即在該 PDE 所指向的頁中，至少一個 PTE，其有效位被設(shè)置為 1。如果 PDE 項無效，則 PDE 的其余部分沒有定義。

多級頁表分配的頁表空間，與你正在使用的地址空間內(nèi)存量成比例，因此通常很緊湊，并且支持稀疏的地址空間。

如果仔細(xì)構(gòu)建，頁表的每個部分都可以整齊的放入一頁中，從而更容易管理內(nèi)存。有了多級頁表，我們增加了一個間接層，使用了頁目錄，指向頁表的各個部分，這種間接方式，讓我們能夠?qū)㈨摫眄摲旁谖锢韮?nèi)存的任何地方。

多級頁表是有成本的，在 TLB 未命中時，需要從內(nèi)存加載兩次，才能從頁表中獲取正確的地址轉(zhuǎn)換信息 (一次用于頁目錄，另一次用于 PTE 本身)，而用線性頁表只需要一次加載。

另一個明顯的缺點是復(fù)雜性。無論是硬件還是操作系統(tǒng)來處理頁表查找，這樣做無疑都比簡單的線性頁表查找更復(fù)雜。

為了解決分頁所帶來的額外內(nèi)存訪問的問題，操作系統(tǒng)需要一些額外的幫助，因此引入了地址轉(zhuǎn)換旁路緩沖寄存器 (TLB)，就是頻繁發(fā)生的虛擬到物理地址轉(zhuǎn)換的硬件緩存。

首先從虛擬地址中提取頁號 (VPN)，然后檢查 TLB 是否有該 VPN 的轉(zhuǎn)換映射；

如果有，我們就有了 TLB 命中，意味著 TLB 有該頁的轉(zhuǎn)換映射，就可以從相關(guān)的 TLB 項中取出頁診號 (PFN) 與原來虛擬地址中的偏移量組合成期望的物理地址；

如果沒有 (TLB 未命中)，在不同的系統(tǒng)中表現(xiàn)不一樣：

TLB 中包含的虛擬到物理地址映射只對當(dāng)前進(jìn)程有效，對其他進(jìn)程是沒有意義的。所以在上下文切換時，TLB 的管理有兩種方法。

如果是軟件管理 TLB 的系統(tǒng)，可以在發(fā)生上下文切換時，通過一條顯式指令來完成；如果是硬件管理 TLB 系統(tǒng)，則可以在頁表基址寄存器內(nèi)容發(fā)生變化時清空 TLB。不論哪種情況，情況操作都是把全部有效位置為 0，本質(zhì)上清空了 TLB。

但該方法有一定開銷：每次進(jìn)程運行，當(dāng)它訪問數(shù)據(jù)和代碼頁時，都會觸發(fā) TLB 未命中，如果操作系統(tǒng)頻繁切換進(jìn)程，這種開銷會很高。

增加硬件支持，實現(xiàn)跨上下文切換的 TLB 共享。比如有的系統(tǒng)在 TLB 中添加一個地址空間標(biāo)識符 (ASID)，可以把 ASID 看做是進(jìn)程標(biāo)識符，但通常比 PID 位數(shù)少一位。TLB 因此可以同時緩存不同進(jìn)程的地址空間映射，沒有任何沖突。

為了支持更大的地址空間，操作系統(tǒng)需要把當(dāng)前沒有在用的那部分地址空間找個地方存儲起來。硬盤通常能夠滿足這個需求，在我們的存儲層級結(jié)構(gòu)中，大而慢的硬盤位于底層，內(nèi)存之上。增加交換空間讓操作系統(tǒng)為多個并發(fā)運行的進(jìn)程都提供巨大地址空間的假象。

在硬盤上開辟一部分空間用于物理頁的移入和移出，在操作系統(tǒng)中這樣的空間稱為交換空間，因為我們將內(nèi)存中的頁交換到其中，并在需要的時候又交換回去。因此，我們會假設(shè)操作系統(tǒng)能夠以頁為大小為單元讀取或者寫入交換空間，為了達(dá)到這個目的。

硬件通過頁表中的存在位，來判斷是否在內(nèi)存中。如果存在位設(shè)置為1，則表示該頁存在于物理內(nèi)存中，并且所有內(nèi)容都正常進(jìn)行；如果存在位設(shè)置為0，則頁不在內(nèi)存中，而在硬盤上。

訪問不在物理內(nèi)存中的頁，這種行為通常被稱為頁錯誤。這時 “頁錯誤處理程序” 被執(zhí)行，處理頁錯誤。

處理頁錯誤的流程：

如上圖所示，當(dāng)操作系統(tǒng)接收到頁錯誤時，會先找可用的物理幀，如果找不到，操作系統(tǒng)會執(zhí)行交換算法，踢出一些頁，釋放物理幀，并將請求發(fā)送到硬盤，將頁讀取到內(nèi)存中。

當(dāng)硬盤 I/O 完成時，操作系統(tǒng)會更新頁表，將此頁標(biāo)記為存在，更新頁表項的 PFN 字段以記錄新獲取頁的內(nèi)存位置，并重試指令。下一次重新訪問 TLB 還是未命中，然而這次因為頁在內(nèi)存中，因此會將頁表中的地址更新到 TLB 中。

最后的重試操作會在 TLB 中找到轉(zhuǎn)換映射，從已轉(zhuǎn)換的內(nèi)存物理地址，獲取所需的數(shù)據(jù)或指令。

為了保證有少量的空閑內(nèi)存，大多數(shù)操作系統(tǒng)會設(shè)置高水位線 (HW) 和低水位線 (LW)。

原理是：當(dāng)操作系統(tǒng)發(fā)現(xiàn)有少于 LW 個頁可用時，后臺負(fù)責(zé)釋放內(nèi)存的線程會開始運行，直到有 HW 個可用的物理頁。這個后臺線程有時稱為交換守護(hù)進(jìn)程 (swap daemon) 或頁守護(hù)進(jìn)程 (page daemon)，然后會進(jìn)入休眠狀態(tài)。

當(dāng)內(nèi)存不夠時，由于內(nèi)存壓力迫使操作系統(tǒng)換出一些頁，為常用的頁騰出空間，確定要踢出哪些頁封裝在操作系統(tǒng)的替換策略中。交換策略有很多，如下：

最優(yōu)替換策略能達(dá)到總體未命中數(shù)量最少，即替換內(nèi)存中在最遠(yuǎn)將來才會被訪問到的頁，可以達(dá)到緩存未命中率最低。但很難實現(xiàn)。

FIFO 策略，即頁在進(jìn)入系統(tǒng)時，簡單地放入一個隊列，當(dāng)發(fā)生替換時，隊列尾部的頁被踢出。

FIFO 有個很大的優(yōu)勢：實現(xiàn)相當(dāng)簡單。但其根本無法確定頁的重要性，即使頁 0 已被多次訪問， FIFO 仍然會將其踢出。且 FIFO 會引起 Belady 異常。

LRU 策略是替換最近最少使用的頁。

LRU 目前看來優(yōu)于 FIFO 策略及隨機(jī)策略，但隨著系統(tǒng)中頁的數(shù)量的增長，掃描所有頁的時間字段只是為了找到最精確最少使用的頁，這個代價太大。

Clock 算法是近似 LRU 的一種算法，也是許多現(xiàn)代系統(tǒng)的做法。該算法需要硬件增加一個使用位。

過程：

考慮到內(nèi)存中的頁是否被修改，硬件增加一個修改位。每次寫入頁時都會設(shè)置此位，因此可以將其合并到頁面替換算法中。如果頁已被修改并因此變臟，則提出就必須將它寫回磁盤，這很昂貴；如果沒有被修改，踢出就沒有成本。因此，一些虛擬系統(tǒng)更傾向于踢出干凈頁，而不是臟頁。

本文就操作系統(tǒng)的內(nèi)存虛擬化部分做了簡單總結(jié)，包括分段、分頁、TLB 以及交換空間。通過這些，操作系統(tǒng)實現(xiàn)了虛擬內(nèi)存系統(tǒng)，從而保證內(nèi)存對程序的透明，程序訪問內(nèi)存的高效，以及進(jìn)程之間的相互隔離。