程序自身并不需要關心自己的數據及代碼存在哪，并且對程序來說，內存看上去是連續且獨占的。當然事實肯定不是如此，而這背后就是操作系統的功勞 —— 內存虛擬化。本篇文章就介紹操作系統是如何實現虛擬內存系統的。

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

一個進程的地址空間包含運行的程序的所有內存狀態。每次內存引用時，硬件都會進行地址轉換，將應用程序的內存引用重定向到內存中實際的位置。

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

界限寄存器的作用在于，確保了進程產生的所有地址都在進程的地址 “界限” 中。

操作系統和硬件支持結合，實現了虛擬內存，而為了實現虛擬內存，操作系統所需要做的工作如下：

為了解決連續內存的浪費問題，操作系統引入了分段。

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

分段機制使得操作系統能夠將不同的段放入不同的物理內存區域，從而避免了虛擬地址空間中的未使用部分占用物理內存。如下圖所示：

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

分段帶來一些新的問題。

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

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

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

還有一些改進策略：

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

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

操作系統為每個進程保存一個數據結構，稱為頁表。主要用來為地址空間的每個虛擬頁面保存地址轉換，從而讓我們知道每個頁在物理內存中的位置。

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

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

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

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

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

為了解決頁表內存開銷過多的問題，Multics 的創造者提出了分頁和分段結合的想法。解決方法是，不是為進程的整個地址空間提供單個頁表，而是為每個邏輯分擔提供一個頁表。

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

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

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

多級頁表也是用來解決頁表占用太多內存的問題，去掉頁表中的所有無效區域，而不是將它們全部保留在內存中。多級頁表將線性頁表變成了樹。

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

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

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

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

如果仔細構建，頁表的每個部分都可以整齊的放入一頁中，從而更容易管理內存。有了多級頁表，我們增加了一個間接層，使用了頁目錄，指向頁表的各個部分，這種間接方式，讓我們能夠將頁表頁放在物理內存的任何地方。

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

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

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

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

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

如果沒有 (TLB 未命中)，在不同的系統中表現不一樣：

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

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

但該方法有一定開銷：每次進程運行，當它訪問數據和代碼頁時，都會觸發 TLB 未命中，如果操作系統頻繁切換進程，這種開銷會很高。

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

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

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

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

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

處理頁錯誤的流程：

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

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

最后的重試操作會在 TLB 中找到轉換映射，從已轉換的內存物理地址，獲取所需的數據或指令。

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

原理是：當操作系統發現有少于 LW 個頁可用時，后臺負責釋放內存的線程會開始運行，直到有 HW 個可用的物理頁。這個后臺線程有時稱為交換守護進程 (swap daemon) 或頁守護進程 (page daemon)，然后會進入休眠狀態。

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

最優替換策略能達到總體未命中數量最少，即替換內存中在最遠將來才會被訪問到的頁，可以達到緩存未命中率最低。但很難實現。

FIFO 策略，即頁在進入系統時，簡單地放入一個隊列，當發生替換時，隊列尾部的頁被踢出。

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

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

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

Clock 算法是近似 LRU 的一種算法，也是許多現代系統的做法。該算法需要硬件增加一個使用位。

過程：

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

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