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

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

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

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

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

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

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

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

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

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

分段帶來(lái)一些新的問(wèn)題。

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

第二個(gè)也是更重要的問(wèn)題是分段會(huì)帶來(lái)外部碎片?？臻e空間被分割成不同大小的小塊，成為碎片，后續(xù)的請(qǐng)求可能會(huì)失敗，因?yàn)闆](méi)有一塊足夠大的連續(xù)空閑空間，即使這時(shí)總的空閑空間超出了請(qǐng)求的大小。

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

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

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

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

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

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

通過(guò)虛擬頁(yè)號(hào)，我們現(xiàn)在可以檢索頁(yè)表，找到虛擬頁(yè)所在的物理頁(yè)面。因此，我們可以通過(guò)用物理幀號(hào)替換虛擬頁(yè)號(hào)來(lái)轉(zhuǎn)換此虛擬地址，然后將載入發(fā)送給物理內(nèi)存。偏移量保持不變，因?yàn)槠屏恐皇歉嬖V我們頁(yè)面中的哪個(gè)字節(jié)是我們想要的。如下圖所示：

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

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

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

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

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

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

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

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

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

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

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

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

如果仔細(xì)構(gòu)建，頁(yè)表的每個(gè)部分都可以整齊的放入一頁(yè)中，從而更容易管理內(nèi)存。有了多級(jí)頁(yè)表，我們?cè)黾恿艘粋€(gè)間接層，使用了頁(yè)目錄，指向頁(yè)表的各個(gè)部分，這種間接方式，讓我們能夠?qū)㈨?yè)表頁(yè)放在物理內(nèi)存的任何地方。

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

另一個(gè)明顯的缺點(diǎn)是復(fù)雜性。無(wú)論是硬件還是操作系統(tǒng)來(lái)處理頁(yè)表查找，這樣做無(wú)疑都比簡(jiǎn)單的線性頁(yè)表查找更復(fù)雜。

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

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

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

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

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

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

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

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

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

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

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

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

處理頁(yè)錯(cuò)誤的流程：

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

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

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

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

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

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

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

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

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

LRU 策略是替換最近最少使用的頁(yè)。

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

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

過(guò)程：

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

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