全面了解虛擬內(nèi)存：更好學習Go
導(dǎo)言
計算機存儲器
主存
物理內(nèi)存
虛擬內(nèi)存
虛擬內(nèi)存
頁表
地址翻譯
虛擬內(nèi)存和高速緩存
加速翻譯&優(yōu)化頁表
總結(jié)
參考&延伸閱讀
導(dǎo)言
虛擬內(nèi)存是當今計算機系統(tǒng)中最重要的抽象概念之一，它的提出是為了更加有效地管理內(nèi)存并且降低內(nèi)存出錯的概率。虛擬內(nèi)存影響著計算機的方方面面，包括硬件設(shè)計、文件系統(tǒng)、共享對象和進程/線程調(diào)度等等，每一個致力于編寫高效且出錯概率低的程序的程序員都應(yīng)該深入學習虛擬內(nèi)存。
本文全面而深入地剖析了虛擬內(nèi)存的工作原理，幫助讀者快速而深刻地理解這個重要的概念。
計算機存儲器
存儲器是計算機的核心部件之一，在完全理想的狀態(tài)下，存儲器應(yīng)該要同時具備以下三種特性：
速度足夠快：存儲器的存取速度應(yīng)當快于 CPU 執(zhí)行一條指令，這樣 CPU 的效率才不會受限于存儲器 容量足夠大：容量能夠存儲計算機所需的全部數(shù)據(jù) 價格足夠便宜：價格低廉，所有類型的計算機都能配備
但是現(xiàn)實往往是殘酷的，我們目前的計算機技術(shù)無法同時滿足上述的三個條件，于是現(xiàn)代計算機的存儲器設(shè)計采用了一種分層次的結(jié)構(gòu)：
從頂至底，現(xiàn)代計算機里的存儲器類型分別有：寄存器、高速緩存、主存和磁盤，這些存儲器的速度逐級遞減而容量逐級遞增。存取速度最快的是寄存器，因為寄存器的制作材料和 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 則根據(jù)不同的架構(gòu)設(shè)計會被設(shè)計成獨享或者共享兩種模式之一，比如 Intel 的多核芯片采用的是共享 L2 模式而 AMD 的多核芯片則采用的是獨享 L2 模式。
第三層則是主存，也即主內(nèi)存，通常稱作隨機訪問存儲器（Random Access Memory, RAM）。是與 CPU 直接交換數(shù)據(jù)的內(nèi)部存儲器。它可以隨時讀寫（刷新時除外），而且速度很快，通常作為操作系統(tǒng)或其他正在運行中的程序的臨時資料存儲介質(zhì)。
最后則是磁盤，磁盤和主存相比，每個二進制位的成本低了兩個數(shù)量級，因此容量比之會大得多，動輒上 GB、TB，而缺點則是訪問速度則比主存慢了大概三個數(shù)量級。機械硬盤速度慢主要是因為機械臂需要不斷在金屬盤片之間移動，等待磁盤扇區(qū)旋轉(zhuǎn)至磁頭之下，然后才能進行讀寫操作，因此效率很低。
主存
物理內(nèi)存
我們平時一直提及的物理內(nèi)存就是上文中對應(yīng)的第三種計算機存儲器，RAM 主存，它在計算機中以內(nèi)存條的形式存在，嵌在主板的內(nèi)存槽上，用來加載各式各樣的程序與數(shù)據(jù)以供 CPU 直接運行和使用。
虛擬內(nèi)存
在計算機領(lǐng)域有一句如同摩西十誡般神圣的哲言："計算機科學領(lǐng)域的任何問題都可以通過增加一個間接的中間層來解決"，從內(nèi)存管理、網(wǎng)絡(luò)模型、并發(fā)調(diào)度甚至是硬件架構(gòu)，都能看到這句哲言在閃爍著光芒，而虛擬內(nèi)存則是這一哲言的完美實踐之一。
虛擬內(nèi)存是現(xiàn)代計算機中的一個非常重要的存儲器抽象，主要是用來解決應(yīng)用程序日益增長的內(nèi)存使用需求：現(xiàn)代物理內(nèi)存的容量增長已經(jīng)非?？焖倭耍欢€是跟不上應(yīng)用程序?qū)χ鞔嫘枨蟮脑鲩L速度，對于應(yīng)用程序來說內(nèi)存還是可能會不夠用，因此便需要一種方法來解決這兩者之間的容量差矛盾。為了更高效地管理內(nèi)存并盡可能消除程序錯誤，現(xiàn)代計算機系統(tǒng)對物理主存 RAM 進行抽象，實現(xiàn)了虛擬內(nèi)存 (Virtual Memory, VM) 技術(shù)。
虛擬內(nèi)存
虛擬內(nèi)存的核心原理是：為每個程序設(shè)置一段"連續(xù)"的虛擬地址空間，把這個地址空間分割成多個具有連續(xù)地址范圍的頁 (Page)，并把這些頁和物理內(nèi)存做映射，在程序運行期間動態(tài)映射到物理內(nèi)存。當程序引用到一段在物理內(nèi)存的地址空間時，由硬件立刻執(zhí)行必要的映射；而當程序引用到一段不在物理內(nèi)存中的地址空間時，由操作系統(tǒng)負責將缺失的部分裝入物理內(nèi)存并重新執(zhí)行失敗的指令。
其實虛擬內(nèi)存技術(shù)從某種角度來看的話，很像是糅合了基址寄存器和界限寄存器之后的新技術(shù)。它使得整個進程的地址空間可以通過較小的虛擬單元映射到物理內(nèi)存，而不需要為程序的代碼和數(shù)據(jù)地址進行重定位。
虛擬地址空間按照固定大小劃分成被稱為頁（Page）的若干單元，物理內(nèi)存中對應(yīng)的則是頁框（Page Frame）。這兩者一般來說是一樣的大小，如上圖中的是 4KB，不過實際上計算機系統(tǒng)中一般是 512 字節(jié)到 1 GB，這就是虛擬內(nèi)存的分頁技術(shù)。因為是虛擬內(nèi)存空間，每個進程分配的大小是 4GB (32 位架構(gòu))，而實際上當然不可能給所有在運行中的進程都分配 4GB 的物理內(nèi)存，所以虛擬內(nèi)存技術(shù)還需要利用到一種 交換（swapping）技術(shù)，也就是通常所說的頁面置換算法，在進程運行期間只分配映射當前使用到的內(nèi)存，暫時不使用的數(shù)據(jù)則寫回磁盤作為副本保存，需要用的時候再讀入內(nèi)存，動態(tài)地在磁盤和內(nèi)存之間交換數(shù)據(jù)。
頁表
頁表（Page Table），每次進行虛擬地址到物理地址的映射之時，都需要讀取頁表，從數(shù)學角度來說頁表就是一個函數(shù)，入?yún)⑹翘摂M頁號（Virtual Page Number，簡稱 VPN），輸出是物理頁框號（Physical Page Number，簡稱 PPN，也就是物理地址的基址）。
頁表由多個頁表項（Page Table Entry, 簡稱 PTE）組成，頁表項的結(jié)構(gòu)取決于機器架構(gòu)，不過基本上都大同小異。一般來說頁表項中都會存儲物理頁框號、修改位、訪問位、保護位和 "在/不在" 位（有效位）等信息。
物理頁框號：這是 PTE 中最重要的域值，畢竟頁表存在的意義就是提供 VPN 到 PPN 的映射。 有效位：表示該頁面當前是否存在于主存中，1 表示存在，0 表示缺失，當進程嘗試訪問一個有效位為 0 的頁面時，就會引起一個缺頁中斷。 保護位：指示該頁面所允許的訪問類型，比如 0 表示可讀寫，1 表示只讀。 修改位和訪問位：為了記錄頁面使用情況而引入的，一般是頁面置換算法會使用到。比如當一個內(nèi)存頁面被程序修改過之后，硬件會自動設(shè)置修改位，如果下次程序發(fā)生缺頁中斷需要運行頁面置換算法把該頁面調(diào)出以便為即將調(diào)入的頁面騰出空間之時，就會先去訪問修改位，從而得知該頁面被修改過，也就是臟頁 (Dirty Page)，則需要把最新的頁面內(nèi)容寫回到磁盤保存，否則就表示內(nèi)存和磁盤上的副本內(nèi)容是同步的，無需寫回磁盤；而訪問位同樣也是系統(tǒng)在程序訪問頁面時自動設(shè)置的，它也是頁面置換算法會使用到的一個值，系統(tǒng)會根據(jù)頁面是否正在被訪問來覺得是否要淘汰掉這個頁面，一般來說不再使用的頁面更適合被淘汰掉。 高速緩存禁止位：用于禁止頁面被放入 CPU 高速緩存，這個值主要適用于那些映射到寄存器等實時 I/O 設(shè)備而非普通主存的內(nèi)存頁面，這一類實時 I/O 設(shè)備需要拿到最新的數(shù)據(jù)，而 CPU 高速緩存中的數(shù)據(jù)可能是舊的拷貝。
地址翻譯
進程在運行期間產(chǎn)生的內(nèi)存地址都是虛擬地址，如果計算機沒有引入虛擬內(nèi)存這種存儲器抽象技術(shù)的話，則 CPU 會把這些地址直接發(fā)送到內(nèi)存地址總線上，然后訪問和虛擬地址相同值的物理地址；如果使用虛擬內(nèi)存技術(shù)的話，CPU 則是把這些虛擬地址通過地址總線送到內(nèi)存管理單元（Memory Management Unit，簡稱 MMU），MMU 將虛擬地址翻譯成物理地址之后再通過內(nèi)存總線去訪問物理內(nèi)存：
虛擬地址（比如 16 位地址 8196=0010 000000000100）分為兩部分：虛擬頁號（Virtual Page Number，簡稱 VPN，這里是高 4 位部分）和偏移量（Virtual Page Offset，簡稱 VPO，這里是低 12 位部分），虛擬地址轉(zhuǎn)換成物理地址是通過頁表（page table）來實現(xiàn)的。
這里我們基于一個例子來分析當頁面命中時，計算機各個硬件是如何交互的：
第 1 步：處理器生成一個虛擬地址 VA，通過總線發(fā)送到 MMU；
第 2 步：MMU 通過虛擬頁號得到頁表項的地址 PTEA，通過內(nèi)存總線從 CPU 高速緩存/主存讀取這個頁表項 PTE；
第 3 步：CPU 高速緩存或者主存通過內(nèi)存總線向 MMU 返回頁表項 PTE；
第 4 步：MMU 先把頁表項中的物理頁框號 PPN 復(fù)制到寄存器的高三位中，接著把 12 位的偏移量 VPO 復(fù)制到寄存器的末 12 位構(gòu)成 15 位的物理地址，即可以把該寄存器存儲的物理內(nèi)存地址 PA 發(fā)送到內(nèi)存總線，訪問高速緩存/主存；
第 5 步：CPU 高速緩存/主存返回該物理地址對應(yīng)的數(shù)據(jù)給處理器。
在 MMU 進行地址轉(zhuǎn)換時，如果頁表項的有效位是 0，則表示該頁面并沒有映射到真實的物理頁框號 PPN，則會引發(fā)一個缺頁中斷，CPU 陷入操作系統(tǒng)內(nèi)核，接著操作系統(tǒng)就會通過頁面置換算法選擇一個頁面將其換出 (swap)，以便為即將調(diào)入的新頁面騰出位置，如果要換出的頁面的頁表項里的修改位已經(jīng)被設(shè)置過，也就是被更新過，則這是一個臟頁 (Dirty Page)，需要寫回磁盤更新該頁面在磁盤上的副本，如果該頁面是"干凈"的，也就是沒有被修改過，則直接用調(diào)入的新頁面覆蓋掉被換出的舊頁面即可。
缺頁中斷的具體流程如下：
第 1 步到第 3 步：和前面的頁面命中的前 3 步是一致的； 第 4 步：檢查返回的頁表項 PTE 發(fā)現(xiàn)其有效位是 0，則 MMU 觸發(fā)一次缺頁中斷異常，然后 CPU 轉(zhuǎn)入到操作系統(tǒng)內(nèi)核中的缺頁中斷處理器； 第 5 步：缺頁中斷處理程序檢查所需的虛擬地址是否合法，確認合法后系統(tǒng)則檢查是否有空閑物理頁框號 PPN 可以映射給該缺失的虛擬頁面，如果沒有空閑頁框，則執(zhí)行頁面置換算法尋找一個現(xiàn)有的虛擬頁面淘汰，如果該頁面已經(jīng)被修改過，則寫回磁盤，更新該頁面在磁盤上的副本； 第 6 步：缺頁中斷處理程序從磁盤調(diào)入新的頁面到內(nèi)存，更新頁表項 PTE； 第 7 步：缺頁中斷程序返回到原先的進程，重新執(zhí)行引起缺頁中斷的指令，CPU 將引起缺頁中斷的虛擬地址重新發(fā)送給 MMU，此時該虛擬地址已經(jīng)有了映射的物理頁框號 PPN，因此會按照前面『Page Hit』的流程走一遍，最后主存把請求的數(shù)據(jù)返回給處理器。
虛擬內(nèi)存和高速緩存
前面在分析虛擬內(nèi)存的工作原理之時，談到頁表的存儲位置，為了簡化處理，都是默認把主存和高速緩存放在一起，而實際上更詳細的流程應(yīng)該是如下的原理圖：
如果一臺計算機同時配備了虛擬內(nèi)存技術(shù)和 CPU 高速緩存，那么 MMU 每次都會優(yōu)先嘗試到高速緩存中進行尋址，如果緩存命中則會直接返回，只有當緩存不命中之后才去主存尋址。
通常來說，大多數(shù)系統(tǒng)都會選擇利用物理內(nèi)存地址去訪問高速緩存，因為高速緩存相比于主存要小得多，所以使用物理尋址也不會太復(fù)雜；另外也因為高速緩存容量很小，所以系統(tǒng)需要盡量在多個進程之間共享數(shù)據(jù)塊，而使用物理地址能夠使得多進程同時在高速緩存中存儲數(shù)據(jù)塊以及共享來自相同虛擬內(nèi)存頁的數(shù)據(jù)塊變得更加直觀。
加速翻譯&優(yōu)化頁表
經(jīng)過前面的剖析，相信讀者們已經(jīng)了解了虛擬內(nèi)存及其分頁&地址翻譯的基礎(chǔ)和原理。現(xiàn)在我們可以引入虛擬內(nèi)存中兩個核心的需求，或者說瓶頸：
虛擬地址到物理地址的映射過程必須要非?？欤刂贩g如何加速。 虛擬地址范圍的增大必然會導(dǎo)致頁表的膨脹，形成大頁表。
這兩個因素決定了虛擬內(nèi)存這項技術(shù)能不能真正地廣泛應(yīng)用到計算機中，如何解決這兩個問題呢？
正如文章開頭所說："計算機科學領(lǐng)域的任何問題都可以通過增加一個間接的中間層來解決"。因此，雖然虛擬內(nèi)存本身就已經(jīng)是一個中間層了，但是中間層里的問題同樣可以通過再引入一個中間層來解決。
加速地址翻譯過程的方案目前是通過引入頁表緩存模塊 -- TLB，而大頁表則是通過實現(xiàn)多級頁表或倒排頁表來解決。
TLB 加速
翻譯后備緩沖器（Translation Lookaside Buffer，TLB），也叫快表，是用來加速虛擬地址翻譯的，因為虛擬內(nèi)存的分頁機制，頁表一般是保存在內(nèi)存中的一塊固定的存儲區(qū)，而 MMU 每次翻譯虛擬地址的時候都需要從頁表中匹配一個對應(yīng)的 PTE，導(dǎo)致進程通過 MMU 訪問指定內(nèi)存數(shù)據(jù)的時候比沒有分頁機制的系統(tǒng)多了一次內(nèi)存訪問，一般會多耗費幾十到幾百個 CPU 時鐘周期，性能至少下降一半，如果 PTE 碰巧緩存在 CPU L1 高速緩存中，則開銷可以降低到一兩個周期，但是我們不能寄希望于每次要匹配的 PTE 都剛好在 L1 中，因此需要引入加速機制，即 TLB 快表。
TLB 可以簡單地理解成頁表的高速緩存，保存了最高頻被訪問的頁表項 PTE。由于 TLB 一般是硬件實現(xiàn)的，因此速度極快，MMU 收到虛擬地址時一般會先通過硬件 TLB 并行地在頁表中匹配對應(yīng)的 PTE，若命中且該 PTE 的訪問操作不違反保護位（比如嘗試寫一個只讀的內(nèi)存地址），則直接從 TLB 取出對應(yīng)的物理頁框號 PPN 返回，若不命中則會穿透到主存頁表里查詢，并且會在查詢到最新頁表項之后存入 TLB，以備下次緩存命中，如果 TLB 當前的存儲空間不足則會替換掉現(xiàn)有的其中一個 PTE。
下面來具體分析一下 TLB 命中和不命中。
TLB 命中：
第 1 步：CPU 產(chǎn)生一個虛擬地址 VA； 第 2 步和第 3 步：MMU 從 TLB 中取出對應(yīng)的 PTE； 第 4 步：MMU 將這個虛擬地址 VA 翻譯成一個真實的物理地址 PA，通過地址總線發(fā)送到高速緩存/主存中去； 第 5 步：高速緩存/主存將物理地址 PA 上的數(shù)據(jù)返回給 CPU。
TLB 不命中：
第 1 步：CPU 產(chǎn)生一個虛擬地址 VA； 第 2 步至第 4 步：查詢 TLB 失敗，走正常的主存頁表查詢流程拿到 PTE，然后把它放入 TLB 緩存，以備下次查詢，如果 TLB 此時的存儲空間不足，則這個操作會汰換掉 TLB 中另一個已存在的 PTE； 第 5 步：MMU 將這個虛擬地址 VA 翻譯成一個真實的物理地址 PA，通過地址總線發(fā)送到高速緩存/主存中去； 第 6 步：高速緩存/主存將物理地址 PA 上的數(shù)據(jù)返回給 CPU。
多級頁表
TLB 的引入可以一定程度上解決虛擬地址到物理地址翻譯的開銷問題，接下來還需要解決另一個問題：大頁表。
理論上一臺 32 位的計算機的尋址空間是 4GB，也就是說每一個運行在該計算機上的進程理論上的虛擬尋址范圍是 4GB。到目前為止，我們一直在討論的都是單頁表的情形，如果每一個進程都把理論上可用的內(nèi)存頁都裝載進一個頁表里，但是實際上進程會真正使用到的內(nèi)存其實可能只有很小的一部分，而我們也知道頁表也是保存在計算機主存中的，那么勢必會造成大量的內(nèi)存浪費，甚至有可能導(dǎo)致計算機物理內(nèi)存不足從而無法并行地運行更多進程。
這個問題一般通過多級頁表（Multi-Level Page Tables）來解決，通過把一個大頁表進行拆分，形成多級的頁表，我們具體來看一個二級頁表應(yīng)該如何設(shè)計：假定一個虛擬地址是 32 位，由 10 位的一級頁表索引、10 位的二級頁表索引以及 12 位的地址偏移量，則 PTE 是 4 字節(jié)，頁面 page 大小是 2^12 = 4KB，總共需要 2^20 個 PTE，一級頁表中的每個 PTE 負責映射虛擬地址空間中的一個 4MB 的 chunk，每一個 chunk 都由 1024 個連續(xù)的頁面 Page 組成，如果尋址空間是 4GB，那么一共只需要 1024 個 PTE 就足夠覆蓋整個進程地址空間。二級頁表中的每一個 PTE 都負責映射到一個 4KB 的虛擬內(nèi)存頁面，和單頁表的原理是一樣的。
多級頁表的關(guān)鍵在于，我們并不需要為一級頁表中的每一個 PTE 都分配一個二級頁表，而只需要為進程當前使用到的地址做相應(yīng)的分配和映射。因此，對于大部分進程來說，它們的一級頁表中有大量空置的 PTE，那么這部分 PTE 對應(yīng)的二級頁表也將無需存在，這是一個相當可觀的內(nèi)存節(jié)約，事實上對于一個典型的程序來說，理論上的 4GB 可用虛擬內(nèi)存地址空間絕大部分都會處于這樣一種未分配的狀態(tài)；更進一步，在程序運行過程中，只需要把一級頁表放在主存中，虛擬內(nèi)存系統(tǒng)可以在實際需要的時候才去創(chuàng)建、調(diào)入和調(diào)出二級頁表，這樣就可以確保只有那些最頻繁被使用的二級頁表才會常駐在主存中，此舉亦極大地緩解了主存的壓力。
多級頁表的層級深度可以按照需求不斷擴充，一般來說，級數(shù)越多，靈活性越高。
比如有個一個 k 級頁表，虛擬地址由 k 個 VPN 和 1 個 VPO 組成，每一個 VPN i 都是一個到第 i 級頁表的索引，其中 1 <= i <= k。第 j 級頁表中的每一個 PTE（1 <= j <= k-1）都指向第 j+1 級頁表的基址。第 k 級頁表中的每一個 PTE 都包含一個物理地址的頁框號 PPN，或者一個磁盤塊的地址（該內(nèi)存頁已經(jīng)被頁面置換算法換出到磁盤中）。MMU 每次都需要訪問 k 個 PTE 才能找到物理頁框號 PPN 然后加上虛擬地址中的偏移量 VPO 從而生成一個物理地址。這里讀者可能會對 MMU 每次都訪問 k 個 PTE 表示性能上的擔憂，此時就是 TLB 出場的時候了，計算機正是通過把每一級頁表中的 PTE 緩存在 TLB 中從而讓多級頁表的性能不至于落后單頁表太多。
倒排頁表
另一種針對頁式虛擬內(nèi)存管理大頁表問題的解決方案是倒排頁表（Inverted Page Table，簡稱 IPT）。倒排頁表的原理和搜索引擎的倒排索引相似，都是通過反轉(zhuǎn)映射過程來實現(xiàn)。
在搜索引擎中，有兩個概念：文檔 doc 和 關(guān)鍵詞 keyword，我們的需求是通過 keyword 快速找到對應(yīng)的 doc 列表，如果搜索引擎的存儲結(jié)構(gòu)是正向索引，也即是通過 doc 映射到其中包含的所有 keyword 列表，那么我們要找到某一個指定的 keyword 所對應(yīng)的 doc 列表，那么便需要掃描索引庫中的所有 doc，找到包含該 keyword 的 doc，再根據(jù)打分模型進行打分，排序后返回，這種設(shè)計無疑是低效的；所以我們需要反轉(zhuǎn)一下正向索引從而得到倒排索引，也即通過 keyword 映射到所有包含它的 doc 列表，這樣當我們查詢包含某個指定 keyword 的 doc 列表時，只需要利用倒排索引就可以快速定位到對應(yīng)的結(jié)果，然后還是根據(jù)打分模型進行排序返回。
上面的描述只是搜索引擎倒排索引的簡化原理，實際的倒排索引設(shè)計是要復(fù)雜很多的，有興趣的讀者可以自行查找資料學習，這里就不再展開。
回到虛擬內(nèi)存的倒排頁表，它正是采用了和倒排索引類似的思想，反轉(zhuǎn)了映射過程：前面我們學習到的頁表設(shè)計都是以虛擬地址頁號 VPN 作為頁表項 PTE 索引，映射到物理頁框號 PPN，而在倒排頁表中則是以 PPN 作為 PTE 索引，映射到 (進程號，虛擬頁號 VPN)。
倒排頁表在尋址空間更大的 CPU 架構(gòu)下尤其高效，或者應(yīng)該說更適合那些『虛擬內(nèi)存空間/物理內(nèi)存空間』比例非常大的場景，因為這種設(shè)計是以實際物理內(nèi)存頁框作為 PTE 索引，而不是以遠超物理內(nèi)存的虛擬內(nèi)存作為索引。例如，以 64 位架構(gòu)為例，如果是單頁表結(jié)構(gòu)，還是用 12 位作為頁面地址偏移量，也就是 4KB 的內(nèi)存頁大小，那么以最理論化的方式來計算，則需要 2^52 個 PTE，每個 PTE 占 8 個字節(jié)，那么整個頁表需要 32PB 的內(nèi)存空間，這完全是不可接受的，而如果采用倒排頁表，假定使用 4GB 的 RAM，則只需要 2^20 個 PTE，極大減少內(nèi)存使用量。
倒排頁表雖然在節(jié)省內(nèi)存空間方面效果顯著，但同時卻引入了另一個重大的缺陷：地址翻譯過程變得更加低效。我們都清楚 MMU 的工作就是要把虛擬內(nèi)存地址翻譯成物理內(nèi)存地址，現(xiàn)在索引結(jié)構(gòu)變了，物理頁框號 PPN 作為索引，從原來的 VPN --> PPN 變成了 PPN --> VPN，那么當進程嘗試訪問一個虛擬內(nèi)存地址之時，CPU 在通過地址總線把 VPN 發(fā)送到 MMU 之后，基于倒排頁表的設(shè)計，MMU 并不知道這個 VPN 對應(yīng)的是不是一個缺頁，所以不得不掃描整個倒排頁表來找到該 VPN，而最要命的是就算是一個非缺頁的 VPN，每次內(nèi)存訪問還是需要執(zhí)行這個全表掃描操作，假設(shè)是前面提到的 4GB RAM 的例子，那么相當于每次都要掃描 2^20 個 PTE，相當?shù)托А?/p>
這時候又是我們的老朋友 -- TLB 出場的時候了，我們只需要把高頻使用的頁面緩存在 TLB 中，借助于硬件，在 TLB 緩存命中的情況下虛擬內(nèi)存地址的翻譯過程就可以像普通頁表那樣快速，然而當 TLB 失效的時候，則還是需要通過軟件的方式去掃描整個倒排頁表，線性掃描的方式非常低效，因此一般倒排頁表會基于哈希表來實現(xiàn)，假設(shè)有 1G 的物理內(nèi)存，那么這里就一共有 2^18 個 4KB 大小的頁框，建立一張以 PPN 作為 key 的哈希表，每一個 key 值對應(yīng)的 value 中存儲的是 (VPN, PNN)，那么所有具有相同哈希值的 VPN 會被鏈接在一起形成一個沖突鏈，如果我們把哈希表的槽數(shù)設(shè)置成跟物理頁框數(shù)量一致的話，那么這個倒排哈希表中的沖突鏈的平均長度將會是 1 個 PTE，可以大大提高查詢速度。當 VPN 通過倒排頁表匹配到 PPN 之后，這個 (VPN, PPN) 映射關(guān)系就會馬上被緩存進 TLB，以加速下次虛擬地址翻譯。
倒排頁表在 64 位架構(gòu)的計算機中很常見，因為在 64 位架構(gòu)下，基于分頁的虛擬內(nèi)存中即便把頁面 Page 的大小從一般的 4KB 提升至 4MB，依然需要一個擁有 2^42 個 PTE 的巨型頁表放在主存中（理論上，實際上不會這么實現(xiàn)），極大地消耗內(nèi)存。
總結(jié)
現(xiàn)在讓我們來回顧一下本文的核心內(nèi)容：虛擬內(nèi)存是存在于計算機 CPU 和物理內(nèi)存之間一個中間層，主要作用是高效管理內(nèi)存并減少內(nèi)存出錯。虛擬內(nèi)存的幾個核心概念有：
頁表：從數(shù)學角度來說頁表就是一個函數(shù)，入?yún)⑹翘摂M頁號 VPN，輸出是物理頁框號 PPN，也就是物理地址的基址。頁表由頁表項組成，頁表項中保存了所有用來進行地址翻譯所需的信息，頁表是虛擬內(nèi)存得以正常運作的基礎(chǔ)，每一個虛擬地址要翻譯成物理地址都需要借助它來完成。 TLB：計算機硬件，主要用來解決引入虛擬內(nèi)存之后尋址的性能問題，加速地址翻譯。如果沒有 TLB 來解決虛擬內(nèi)存的性能問題，那么虛擬內(nèi)存將只可能是一個學術(shù)上的理論而無法真正廣泛地應(yīng)用在計算機中。 多級頁表和倒排頁表：用來解決虛擬地址空間爆炸性膨脹而導(dǎo)致的大頁表問題，多級頁表通過將單頁表進行分拆并按需分配虛擬內(nèi)存頁而倒排頁表則是通過反轉(zhuǎn)映射關(guān)系來實現(xiàn)節(jié)省內(nèi)存的效果。
最后，虛擬內(nèi)存技術(shù)中還需要涉及到操作系統(tǒng)的頁面置換機制，由于頁面置換機制也是一個較為龐雜和復(fù)雜的概念，本文便不再繼續(xù)剖析這一部分的原理，我們在以后的文章中再單獨拿來講解。
參考&延伸閱讀
本文的主要參考資料是《現(xiàn)代操作系統(tǒng)》和《深入理解計算機系統(tǒng)》這兩本書的英文原版，如果讀者還想更加深入地學習虛擬內(nèi)存，可以深入閱讀這兩本書并且搜尋其他的論文資料進行學習。
推薦閱讀