虛擬內存精粹

導言

虛擬內存是當今計算機系統中最重要的抽象概念之一，它的提出是爲了更加有效地管理內存並且降低內存出錯的概率。虛擬內存影響着計算機的方方面面，包括硬件設計、文件系統、共享對象和進程 / 線程調度等等，每一個致力於編寫高效且出錯概率低的程序的程序員都應該深入學習虛擬內存。

本文全面而深入地剖析了虛擬內存的工作原理，幫助讀者快速而深刻地理解這個重要的概念。

計算機存儲器

存儲器是計算機的核心部件之一，在完全理想的狀態下，存儲器應該要同時具備以下三種特性：

  1. 速度足夠快：存儲器的存取速度應當快於 CPU 執行一條指令，這樣 CPU 的效率纔不會受限於存儲器

  2. 容量足夠大：容量能夠存儲計算機所需的全部數據

  3. 價格足夠便宜：價格低廉，所有類型的計算機都能配備

但是現實往往是殘酷的，我們目前的計算機技術無法同時滿足上述的三個條件，於是現代計算機的存儲器設計採用了一種分層次的結構：

從頂至底，現代計算機裏的存儲器類型分別有：寄存器、高速緩存、主存和磁盤，這些存儲器的速度逐級遞減而容量逐級遞增。存取速度最快的是寄存器，因爲寄存器的製作材料和 CPU 是相同的，所以速度和 CPU 一樣快，CPU 訪問寄存器是沒有時延的，然而因爲價格昂貴，因此容量也極小，一般 32 位的 CPU 配備的寄存器容量是 32✖️32 Bit，64 位的 CPU 則是 64✖️64 Bit，不管是 32 位還是 64 位，寄存器容量都小於 1 KB，且寄存器也必須通過軟件自行管理。

第二層是高速緩存，也即我們平時瞭解的 CPU 高速緩存 L1、L2、L3，一般 L1 是每個 CPU 獨享，L3 是全部 CPU 共享，而 L2 則根據不同的架構設計會被設計成獨享或者共享兩種模式之一，比如 Intel 的多核芯片採用的是共享 L2 模式而 AMD 的多核芯片則採用的是獨享 L2 模式。

第三層則是主存，也即主內存，通常稱作隨機訪問存儲器（Random Access Memory, RAM）。是與 CPU 直接交換數據的內部存儲器。它可以隨時讀寫（刷新時除外），而且速度很快，通常作爲操作系統或其他正在運行中的程序的臨時資料存儲介質。

最後則是磁盤，磁盤和主存相比，每個二進制位的成本低了兩個數量級，因此容量比之會大得多，動輒上 GB、TB，而缺點則是訪問速度則比主存慢了大概三個數量級。機械硬盤速度慢主要是因爲機械臂需要不斷在金屬盤片之間移動，等待磁盤扇區旋轉至磁頭之下，然後才能進行讀寫操作，因此效率很低。

主存

物理內存

我們平時一直提及的物理內存就是上文中對應的第三種計算機存儲器，RAM 主存，它在計算機中以內存條的形式存在，嵌在主板的內存槽上，用來加載各式各樣的程序與數據以供 CPU 直接運行和使用。

虛擬內存

在計算機領域有一句如同摩西十誡般神聖的哲言：" 計算機科學領域的任何問題都可以通過增加一個間接的中間層來解決 "，從內存管理、網絡模型、併發調度甚至是硬件架構，都能看到這句哲言在閃爍着光芒，而虛擬內存則是這一哲言的完美實踐之一。

虛擬內存是現代計算機中的一個非常重要的存儲器抽象，主要是用來解決應用程序日益增長的內存使用需求：現代物理內存的容量增長已經非常快速了，然而還是跟不上應用程序對主存需求的增長速度，對於應用程序來說內存還是可能會不夠用，因此便需要一種方法來解決這兩者之間的容量差矛盾。爲了更高效地管理內存並儘可能消除程序錯誤，現代計算機系統對物理主存 RAM 進行抽象，實現了_**虛擬內存 (Virtual Memory, VM) **_技術。

虛擬內存

虛擬內存的核心原理是：爲每個程序設置一段 "連續" 的虛擬地址空間，把這個地址空間分割成多個具有連續地址範圍的頁 (Page)，並把這些頁和物理內存做映射，在程序運行期間動態映射到物理內存。當程序引用到一段在物理內存的地址空間時，由硬件立刻執行必要的映射；而當程序引用到一段不在物理內存中的地址空間時，由操作系統負責將缺失的部分裝入物理內存並重新執行失敗的指令。

其實虛擬內存技術從某種角度來看的話，很像是糅合了基址寄存器和界限寄存器之後的新技術。它使得整個進程的地址空間可以通過較小的虛擬單元映射到物理內存，而不需要爲程序的代碼和數據地址進行重定位。

虛擬地址空間按照固定大小劃分成被稱爲頁（Page）的若干單元，物理內存中對應的則是頁框（Page Frame）。這兩者一般來說是一樣的大小，如上圖中的是 4KB，不過實際上計算機系統中一般是 512 字節到 1 GB，這就是虛擬內存的分頁技術。因爲是虛擬內存空間，每個進程分配的大小是 4GB (32 位架構)，而實際上當然不可能給所有在運行中的進程都分配 4GB 的物理內存，所以虛擬內存技術還需要利用到一種 交換（swapping）技術，也就是通常所說的頁面置換算法，在進程運行期間只分配映射當前使用到的內存，暫時不使用的數據則寫回磁盤作爲副本保存，需要用的時候再讀入內存，動態地在磁盤和內存之間交換數據。

頁表

頁表（Page Table），每次進行虛擬地址到物理地址的映射之時，都需要讀取頁表，從數學角度來說頁表就是一個函數，入參是虛擬頁號（Virtual Page Number，簡稱 VPN），輸出是物理頁框號（Physical Page Number，簡稱 PPN，也就是物理地址的基址）。

頁表由多個頁表項（Page Table Entry, 簡稱 PTE）組成，頁表項的結構取決於機器架構，不過基本上都大同小異。一般來說頁表項中都會存儲物理頁框號、修改位、訪問位、保護位和 "在 / 不在" 位（有效位）等信息。

地址翻譯

進程在運行期間產生的內存地址都是虛擬地址，如果計算機沒有引入虛擬內存這種存儲器抽象技術的話，則 CPU 會把這些地址直接發送到內存地址總線上，然後訪問和虛擬地址相同值的物理地址；如果使用虛擬內存技術的話，CPU 則是把這些虛擬地址通過地址總線送到內存管理單元（Memory Management Unit，簡稱 MMU），MMU 將虛擬地址翻譯成物理地址之後再通過內存總線去訪問物理內存：

虛擬地址（比如 16 位地址 8196=0010 000000000100）分爲兩部分：虛擬頁號（Virtual Page Number，簡稱 VPN，這裏是高 4 位部分）和偏移量（Virtual Page Offset，簡稱 VPO，這裏是低 12 位部分），虛擬地址轉換成物理地址是通過頁表（page table）來實現的。

這裏我們基於一個例子來分析當頁面命中時，計算機各個硬件是如何交互的：

在 MMU 進行地址轉換時，如果頁表項的有效位是 0，則表示該頁面並沒有映射到真實的物理頁框號 PPN，則會引發一個缺頁中斷，CPU 陷入操作系統內核，接着操作系統就會通過頁面置換算法選擇一個頁面將其換出 (swap)，以便爲即將調入的新頁面騰出位置，如果要換出的頁面的頁表項裏的修改位已經被設置過，也就是被更新過，則這是一個髒頁 (Dirty Page)，需要寫回磁盤更新該頁面在磁盤上的副本，如果該頁面是 "乾淨" 的，也就是沒有被修改過，則直接用調入的新頁面覆蓋掉被換出的舊頁面即可。

缺頁中斷的具體流程如下：

虛擬內存和高速緩存

前面在分析虛擬內存的工作原理之時，談到頁表的存儲位置，爲了簡化處理，都是默認把主存和高速緩存放在一起，而實際上更詳細的流程應該是如下的原理圖：

如果一臺計算機同時配備了虛擬內存技術和 CPU 高速緩存，那麼 MMU 每次都會優先嚐試到高速緩存中進行尋址，如果緩存命中則會直接返回，只有當緩存不命中之後纔去主存尋址。

通常來說，大多數系統都會選擇利用物理內存地址去訪問高速緩存，因爲高速緩存相比於主存要小得多，所以使用物理尋址也不會太複雜；另外也因爲高速緩存容量很小，所以系統需要儘量在多個進程之間共享數據塊，而使用物理地址能夠使得多進程同時在高速緩存中存儲數據塊以及共享來自相同虛擬內存頁的數據塊變得更加直觀。

加速翻譯 & 優化頁表

經過前面的剖析，相信讀者們已經瞭解了虛擬內存及其分頁 & 地址翻譯的基礎和原理。現在我們可以引入虛擬內存中兩個核心的需求，或者說瓶頸：

這兩個因素決定了虛擬內存這項技術能不能真正地廣泛應用到計算機中，如何解決這兩個問題呢？

正如文章開頭所說：" 計算機科學領域的任何問題都可以通過增加一個間接的中間層來解決 "。因此，雖然虛擬內存本身就已經是一箇中間層了，但是中間層裏的問題同樣可以通過再引入一箇中間層來解決。

加速地址翻譯過程的方案目前是通過引入頁表緩存模塊 -- TLB，而大頁表則是通過實現多級頁表或倒排頁表來解決。

TLB 加速

翻譯後備緩衝器（Translation Lookaside Buffer，TLB），也叫快表，是用來加速虛擬地址翻譯的，因爲虛擬內存的分頁機制，頁表一般是保存在內存中的一塊固定的存儲區，而 MMU 每次翻譯虛擬地址的時候都需要從頁表中匹配一個對應的 PTE，導致進程通過 MMU 訪問指定內存數據的時候比沒有分頁機制的系統多了一次內存訪問，一般會多耗費幾十到幾百個 CPU 時鐘週期，性能至少下降一半，如果 PTE 碰巧緩存在 CPU L1 高速緩存中，則開銷可以降低到一兩個週期，但是我們不能寄希望於每次要匹配的 PTE 都剛好在 L1 中，因此需要引入加速機制，即 TLB 快表。

TLB 可以簡單地理解成頁表的高速緩存，保存了最高頻被訪問的頁表項 PTE。由於 TLB 一般是硬件實現的，因此速度極快，MMU 收到虛擬地址時一般會先通過硬件 TLB 並行地在頁表中匹配對應的 PTE，若命中且該 PTE 的訪問操作不違反保護位（比如嘗試寫一個只讀的內存地址），則直接從 TLB 取出對應的物理頁框號 PPN 返回，若不命中則會穿透到主存頁表裏查詢，並且會在查詢到最新頁表項之後存入 TLB，以備下次緩存命中，如果 TLB 當前的存儲空間不足則會替換掉現有的其中一個 PTE。

下面來具體分析一下 TLB 命中和不命中。

TLB 命中：

TLB 不命中：

多級頁表

TLB 的引入可以一定程度上解決虛擬地址到物理地址翻譯的開銷問題，接下來還需要解決另一個問題：大頁表。

理論上一臺 32 位的計算機的尋址空間是 4GB，也就是說每一個運行在該計算機上的進程理論上的虛擬尋址範圍是 4GB。到目前爲止，我們一直在討論的都是單頁表的情形，如果每一個進程都把理論上可用的內存頁都裝載進一個頁表裏，但是實際上進程會真正使用到的內存其實可能只有很小的一部分，而我們也知道頁表也是保存在計算機主存中的，那麼勢必會造成大量的內存浪費，甚至有可能導致計算機物理內存不足從而無法並行地運行更多進程。

這個問題一般通過多級頁表（Multi-Level Page Tables）來解決，通過把一個大頁表進行拆分，形成多級的頁表，我們具體來看一個二級頁表應該如何設計：假定一個虛擬地址是 32 位，由 10 位的一級頁表索引、10 位的二級頁表索引以及 12 位的地址偏移量，則 PTE 是 4 字節，頁面 page 大小是 2^12 = 4KB，總共需要 2^20 個 PTE，一級頁表中的每個 PTE 負責映射虛擬地址空間中的一個 4MB 的 chunk，每一個 chunk 都由 1024 個連續的頁面 Page 組成，如果尋址空間是 4GB，那麼一共只需要 1024 個 PTE 就足夠覆蓋整個進程地址空間。二級頁表中的每一個 PTE 都負責映射到一個 4KB 的虛擬內存頁面，和單頁表的原理是一樣的。

多級頁表的關鍵在於，我們並不需要爲一級頁表中的每一個 PTE 都分配一個二級頁表，而只需要爲進程當前使用到的地址做相應的分配和映射。因此，對於大部分進程來說，它們的一級頁表中有大量空置的 PTE，那麼這部分 PTE 對應的二級頁表也將無需存在，這是一個相當可觀的內存節約，事實上對於一個典型的程序來說，理論上的 4GB 可用虛擬內存地址空間絕大部分都會處於這樣一種未分配的狀態；更進一步，在程序運行過程中，只需要把一級頁表放在主存中，虛擬內存系統可以在實際需要的時候纔去創建、調入和調出二級頁表，這樣就可以確保只有那些最頻繁被使用的二級頁表纔會常駐在主存中，此舉亦極大地緩解了主存的壓力。

多級頁表的層級深度可以按照需求不斷擴充，一般來說，級數越多，靈活性越高。

比如有個一個 k 級頁表，虛擬地址由 k 個 VPN 和 1 個 VPO 組成，每一個 VPN i 都是一個到第 i 級頁表的索引，其中 1 <= i <= k。第 j 級頁表中的每一個 PTE（1 <= j <= k-1）都指向第 j+1 級頁表的基址。第 k 級頁表中的每一個 PTE 都包含一個物理地址的頁框號 PPN，或者一個磁盤塊的地址（該內存頁已經被頁面置換算法換出到磁盤中）。MMU 每次都需要訪問 k 個 PTE 才能找到物理頁框號 PPN 然後加上虛擬地址中的偏移量 VPO 從而生成一個物理地址。這裏讀者可能會對 MMU 每次都訪問 k 個 PTE 表示性能上的擔憂，此時就是 TLB 出場的時候了，計算機正是通過把每一級頁表中的 PTE 緩存在 TLB 中從而讓多級頁表的性能不至於落後單頁表太多。

倒排頁表

另一種針對頁式虛擬內存管理大頁表問題的解決方案是倒排頁表（Inverted Page Table，簡稱 IPT）。倒排頁表的原理和搜索引擎的倒排索引相似，都是通過反轉映射過程來實現。

在搜索引擎中，有兩個概念：文檔 doc 和 關鍵詞 keyword，我們的需求是通過 keyword 快速找到對應的 doc 列表，如果搜索引擎的存儲結構是正向索引，也即是通過 doc 映射到其中包含的所有 keyword 列表，那麼我們要找到某一個指定的 keyword 所對應的 doc 列表，那麼便需要掃描索引庫中的所有 doc，找到包含該 keyword 的 doc，再根據打分模型進行打分，排序後返回，這種設計無疑是低效的；所以我們需要反轉一下正向索引從而得到倒排索引，也即通過 keyword 映射到所有包含它的 doc 列表，這樣當我們查詢包含某個指定 keyword 的 doc 列表時，只需要利用倒排索引就可以快速定位到對應的結果，然後還是根據打分模型進行排序返回。

上面的描述只是搜索引擎倒排索引的簡化原理，實際的倒排索引設計是要複雜很多的，有興趣的讀者可以自行查找資料學習，這裏就不再展開。

回到虛擬內存的倒排頁表，它正是採用了和倒排索引類似的思想，反轉了映射過程：前面我們學習到的頁表設計都是以虛擬地址頁號 VPN 作爲頁表項 PTE 索引，映射到物理頁框號 PPN，而在倒排頁表中則是以 PPN 作爲 PTE 索引，映射到 (進程號，虛擬頁號 VPN)。

倒排頁表在尋址空間更大的 CPU 架構下尤其高效，或者應該說更適合那些『虛擬內存空間 / 物理內存空間』比例非常大的場景，因爲這種設計是以實際物理內存頁框作爲 PTE 索引，而不是以遠超物理內存的虛擬內存作爲索引。例如，以 64 位架構爲例，如果是單頁表結構，還是用 12 位作爲頁面地址偏移量，也就是 4KB 的內存頁大小，那麼以最理論化的方式來計算，則需要 2^52 個 PTE，每個 PTE 佔 8 個字節，那麼整個頁表需要 32PB 的內存空間，這完全是不可接受的，而如果採用倒排頁表，假定使用 4GB 的 RAM，則只需要 2^20 個 PTE，極大減少內存使用量。

倒排頁表雖然在節省內存空間方面效果顯著，但同時卻引入了另一個重大的缺陷：地址翻譯過程變得更加低效。我們都清楚 MMU 的工作就是要把虛擬內存地址翻譯成物理內存地址，現在索引結構變了，物理頁框號 PPN 作爲索引，從原來的 VPN --> PPN 變成了 PPN --> VPN，那麼當進程嘗試訪問一個虛擬內存地址之時，CPU 在通過地址總線把 VPN 發送到 MMU 之後，基於倒排頁表的設計，MMU 並不知道這個 VPN 對應的是不是一個缺頁，所以不得不掃描整個倒排頁表來找到該 VPN，而最要命的是就算是一個非缺頁的 VPN，每次內存訪問還是需要執行這個全表掃描操作，假設是前面提到的 4GB RAM 的例子，那麼相當於每次都要掃描 2^20 個 PTE，相當低效。

這時候又是我們的老朋友 -- TLB 出場的時候了，我們只需要把高頻使用的頁面緩存在 TLB 中，藉助於硬件，在 TLB 緩存命中的情況下虛擬內存地址的翻譯過程就可以像普通頁表那樣快速，然而當 TLB 失效的時候，則還是需要通過軟件的方式去掃描整個倒排頁表，線性掃描的方式非常低效，因此一般倒排頁表會基於哈希表來實現，假設有 1G 的物理內存，那麼這裏就一共有 2^18 個 4KB 大小的頁框，建立一張以 PPN 作爲 key 的哈希表，每一個 key 值對應的 value 中存儲的是 (VPN, PNN)，那麼所有具有相同哈希值的 VPN 會被鏈接在一起形成一個衝突鏈，如果我們把哈希表的槽數設置成跟物理頁框數量一致的話，那麼這個倒排哈希表中的衝突鏈的平均長度將會是 1 個 PTE，可以大大提高查詢速度。當 VPN 通過倒排頁表匹配到 PPN 之後，這個 (VPN, PPN) 映射關係就會馬上被緩存進 TLB，以加速下次虛擬地址翻譯。

倒排頁表在 64 位架構的計算機中很常見，因爲在 64 位架構下，基於分頁的虛擬內存中即便把頁面 Page 的大小從一般的 4KB 提升至 4MB，依然需要一個擁有 2^42 個 PTE 的巨型頁表放在主存中（理論上，實際上不會這麼實現），極大地消耗內存。

總結

現在讓我們來回顧一下本文的核心內容：虛擬內存是存在於計算機 CPU 和物理內存之間一箇中間層，主要作用是高效管理內存並減少內存出錯。虛擬內存的幾個核心概念有：

  1. 頁表：從數學角度來說頁表就是一個函數，入參是虛擬頁號 VPN，輸出是物理頁框號 PPN，也就是物理地址的基址。頁表由頁表項組成，頁表項中保存了所有用來進行地址翻譯所需的信息，頁表是虛擬內存得以正常運作的基礎，每一個虛擬地址要翻譯成物理地址都需要藉助它來完成。

  2. TLB：計算機硬件，主要用來解決引入虛擬內存之後尋址的性能問題，加速地址翻譯。如果沒有 TLB 來解決虛擬內存的性能問題，那麼虛擬內存將只可能是一個學術上的理論而無法真正廣泛地應用在計算機中。

  3. 多級頁表和倒排頁表：用來解決虛擬地址空間爆炸性膨脹而導致的大頁表問題，多級頁表通過將單頁表進行分拆並按需分配虛擬內存頁而倒排頁表則是通過反轉映射關係來實現節省內存的效果。

最後，虛擬內存技術中還需要涉及到操作系統的頁面置換機制，由於頁面置換機制也是一個較爲龐雜和複雜的概念，本文便不再繼續剖析這一部分的原理，我們在以後的文章中再單獨拿來講解。

參考 & 延伸閱讀

本文的主要參考資料是《現代操作系統》和《深入理解計算機系統》這兩本書的英文原版，如果讀者還想更加深入地學習虛擬內存，可以深入閱讀這兩本書並且搜尋其他的論文資料進行學習。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/Ghu-0Qc9PyEHHmIaRVtMyA

猜你喜歡