[[317518]]

虛擬內(nèi)存

盡管基址寄存器和變址寄存器用來創(chuàng)建地址空間的抽象，但是這有一個其他的問題需要解決：管理軟件的膨脹(managing bloatware)。雖然內(nèi)存的大小增長迅速，但是軟件的大小增長的要比內(nèi)存還要快。在 1980 年的時候，許多大學用一臺 4 MB 的 VAX 計算機運行分時操作系統(tǒng)，供十幾個用戶同時運行?，F(xiàn)在微軟公司推薦的 64 位 Windows 8 系統(tǒng)至少需要 2 GB 內(nèi)存，而許多多媒體的潮流則進一步推動了對內(nèi)存的需求。

這一發(fā)展的結(jié)果是，需要運行的程序往往大到內(nèi)存無法容納，而且必然需要系統(tǒng)能夠支持多個程序同時運行，即使內(nèi)存可以滿足其中單獨一個程序的需求，但是從總體上來看內(nèi)存仍然滿足不了日益增長的軟件的需求(感覺和xxx和xxx 的矛盾很相似)。而交換技術(shù)并不是一個很有效的方案，在一些中小應用程序尚可使用交換，如果應用程序過大，難道還要每次交換幾 GB 的內(nèi)存?這顯然是不合適的，一個典型的 SATA 磁盤的峰值傳輸速度高達幾百兆/秒，這意味著需要好幾秒才能換出或者換入一個 1 GB 的程序。

SATA(Serial ATA)硬盤，又稱串口硬盤，是未來 PC 機硬盤的趨勢，已基本取代了傳統(tǒng)的 PATA 硬盤。

那么還有沒有一種有效的方式來應對呢?有，那就是使用 虛擬內(nèi)存(virtual memory)，虛擬內(nèi)存的基本思想是，每個程序都有自己的地址空間，這個地址空間被劃分為多個稱為頁面(page)的塊。每一頁都是連續(xù)的地址范圍。這些頁被映射到物理內(nèi)存，但并不是所有的頁都必須在內(nèi)存中才能運行程序。當程序引用到一部分在物理內(nèi)存中的地址空間時，硬件會立刻執(zhí)行必要的映射。當程序引用到一部分不在物理內(nèi)存中的地址空間時，由操作系統(tǒng)負責將缺失的部分裝入物理內(nèi)存并重新執(zhí)行失敗的指令。

在某種意義上來說，虛擬地址是對基址寄存器和變址寄存器的一種概述。8088 有分離的基址寄存器(但不是變址寄存器)用于放入 text 和 data 。

使用虛擬內(nèi)存，可以將整個地址空間以很小的單位映射到物理內(nèi)存中，而不是僅僅針對 text 和 data 區(qū)進行重定位。下面我們會探討虛擬內(nèi)存是如何實現(xiàn)的。

虛擬內(nèi)存很適合在多道程序設計系統(tǒng)中使用，許多程序的片段同時保存在內(nèi)存中，當一個程序等待它的一部分讀入內(nèi)存時，可以把 CPU 交給另一個進程使用。

分頁

大部分使用虛擬內(nèi)存的系統(tǒng)中都會使用一種 分頁(paging) 技術(shù)。在任何一臺計算機上，程序會引用使用一組內(nèi)存地址。當程序執(zhí)行

MOV REG,1000

這條指令時，它會把內(nèi)存地址為 1000 的內(nèi)存單元的內(nèi)容復制到 REG 中(或者相反，這取決于計算機)。地址可以通過索引、基址寄存器、段寄存器或其他方式產(chǎn)生。

這些程序生成的地址被稱為 虛擬地址(virtual addresses) 并形成虛擬地址空間(virtual address space)，在沒有虛擬內(nèi)存的計算機上，系統(tǒng)直接將虛擬地址送到內(nèi)存中線上，讀寫操作都使用同樣地址的物理內(nèi)存。在使用虛擬內(nèi)存時，虛擬地址不會直接發(fā)送到內(nèi)存總線上。相反，會使用 MMU(Memory Management Unit) 內(nèi)存管理單元把虛擬地址映射為物理內(nèi)存地址，像下圖這樣：

下面這幅圖展示了這種映射是如何工作的。

頁表給出虛擬地址與物理內(nèi)存地址之間的映射關(guān)系。每一頁起始于 4096 的倍數(shù)位置，結(jié)束于 4095 的位置，所以 4K 到 8K 實際為 4096 - 8191 ，8K - 12K 就是 8192 - 12287

在這個例子中，我們可能有一個 16 位地址的計算機，地址從 0 - 64 K - 1，這些是虛擬地址。然而只有 32 KB 的物理地址。所以雖然可以編寫 64 KB 的程序，但是程序無法全部調(diào)入內(nèi)存運行，在磁盤上必須有一個最多 64 KB 的程序核心映像的完整副本，以保證程序片段在需要時被調(diào)入內(nèi)存。

存在映射的頁如何映射

虛擬地址空間由固定大小的單元組成，這種固定大小的單元稱為 頁(pages)。而相對的，物理內(nèi)存中也有固定大小的物理單元，稱為 頁框(page frames)。頁和頁框的大小一樣。在上面這個例子中，頁的大小為 4KB ，但是實際的使用過程中頁的大小范圍可能是 512 字節(jié) - 1G 字節(jié)的大小。對應于 64 KB 的虛擬地址空間和 32 KB 的物理內(nèi)存，可得到 16 個虛擬頁面和 8 個頁框。RAM 和磁盤之間的交換總是以整個頁為單元進行交換的。

程序試圖訪問地址時，例如執(zhí)行下面這條指令：

MOV REG, 0

會將虛擬地址 0 送到 MMU。MMU 看到虛擬地址落在頁面 0 (0 - 4095)，根據(jù)其映射結(jié)果，這一頁面對應的頁框 2 (8192 - 12287)，因此 MMU 把地址變換為 8192 ，并把地址 8192 送到總線上。內(nèi)存對 MMU 一無所知，它只看到一個對 8192 地址的讀寫請求并執(zhí)行它。MMU 從而有效的把所有虛擬地址 0 - 4095 映射到了 8192 - 12287 的物理地址。同樣的，指令

MOV REG, 8192

也被有效的轉(zhuǎn)換為

MOV REG, 24576

虛擬地址 8192(在虛擬頁 2 中)被映射到物理地址 24576(在物理頁框 6 中)上。

通過恰當?shù)脑O置 MMU，可以把 16 個虛擬頁面映射到 8 個頁框中的任何一個。但是這并沒有解決虛擬地址空間比物理內(nèi)存大的問題。

上圖中有 8 個物理頁框，于是只有 8 個虛擬頁被映射到了物理內(nèi)存中，在上圖中用 X 號表示的其他頁面沒有被映射。在實際的硬件中，會使用一個 在/不在(Present/absent bit)位記錄頁面在內(nèi)存中的實際存在情況。

未映射的頁如何映射

當程序訪問一個未映射的頁面，如執(zhí)行指令：

MOV REG, 32780

將會發(fā)生什么情況呢?虛擬頁面 8 (從 32768 開始)的第 12 個字節(jié)所對應的物理地址是什么?MMU 注意到該頁面沒有被映射(在圖中用 X 號表示)，于是 CPU 會陷入(trap)到操作系統(tǒng)中。這個陷入稱為 缺頁中斷(page fault) 或者是 缺頁錯誤。操作系統(tǒng)會選擇一個很少使用的頁并把它的內(nèi)容寫入磁盤(如果它不在磁盤上)。隨后把需要訪問的頁面讀到剛才回收的頁框中，修改映射關(guān)系，然后重新啟動引起陷入的指令。有點不太好理解，舉個例子來看一下。

例如，如果操作系統(tǒng)決定放棄頁框 1，那么它將把虛擬機頁面 8 裝入物理地址 4096，并對 MMU 映射做兩處修改。首先，它要將虛擬頁中的 1 表項標記為未映射，使以后任何對虛擬地址 4096 - 8191 的訪問都將導致陷入。隨后把虛擬頁面 8 的表項的叉號改為 1，因此在引起陷阱的指令重新啟動時，它將把虛擬地址 32780 映射為物理地址(4096 + 12)。

下面查看一下 MMU 的內(nèi)部構(gòu)造以便了解它們是如何工作的，以及了解為什么我們選用的頁大小都是 2 的整數(shù)次冪。下圖我們可以看到一個虛擬地址的例子。

虛擬地址 8196 (二進制 0010000000000100)用上面的頁表映射圖所示的 MMU 映射機制進行映射，輸入的 16 位虛擬地址被分為 4 位的頁號和 12 位的偏移量。4 位的頁號可以表示 16 個頁面，12 位的偏移可以為一頁內(nèi)的全部 4096 個字節(jié)。

可用頁號作為頁表(page table) 的索引，以得出對應于該虛擬頁面的頁框號。如果在/不在位則是 0 ，則引起一個操作系統(tǒng)陷入。如果該位是 1，則將在頁表中查到的頁框號復制到輸出寄存器的高 3 位中，再加上輸入虛擬地址中的低 12 位偏移量。如此就構(gòu)成了 15 位的物理地址。輸出寄存器的內(nèi)容隨即被作為物理地址送到總線。

頁表

在上面這個簡單的例子中，虛擬地址到物理地址的映射可以總結(jié)如下：虛擬地址被分為虛擬頁號(高位部分)和偏移量(低位部分)。例如，對于 16 位地址和 4 KB 的頁面大小，高 4 位可以指定 16 個虛擬頁面中的一頁，而低 12 位接著確定了所選頁面中的偏移量(0-4095)。

虛擬頁號可作為頁表的索引用來找到虛擬頁中的內(nèi)容。由頁表項可以找到頁框號(如果有的話)。然后把頁框號拼接到偏移量的高位端，以替換掉虛擬頁號，形成物理地址。

因此，頁表的目的是把虛擬頁映射到頁框中。從數(shù)學上說，頁表是一個函數(shù)，它的參數(shù)是虛擬頁號，結(jié)果是物理頁框號。

通過這個函數(shù)可以把虛擬地址中的虛擬頁轉(zhuǎn)換為頁框，從而形成物理地址。

頁表項的結(jié)構(gòu)

下面我們探討一下頁表項的具體結(jié)構(gòu)，上面你知道了頁表項的大致構(gòu)成，是由頁框號和在/不在位構(gòu)成的，現(xiàn)在我們來具體探討一下頁表項的構(gòu)成。

頁表項的結(jié)構(gòu)是與機器相關(guān)的，但是不同機器上的頁表項大致相同。上面是一個頁表項的構(gòu)成，不同計算機的頁表項可能不同，但是一般來說都是 32 位的。頁表項中最重要的字段就是頁框號(Page frame number)。畢竟，頁表到頁框最重要的一步操作就是要把此值映射過去。下一個比較重要的就是在/不在位，如果此位上的值是 1，那么頁表項是有效的并且能夠被使用。如果此值是 0 的話，則表示該頁表項對應的虛擬頁面不在內(nèi)存中，訪問該頁面會引起一個缺頁異常(page fault)。

保護位(Protection) 告訴我們哪一種訪問是允許的，啥意思呢?最簡單的表示形式是這個域只有一位，0 表示可讀可寫，1 表示的是只讀。

修改位(Modified) 和 訪問位(Referenced) 會跟蹤頁面的使用情況。當一個頁面被寫入時，硬件會自動的設置修改位。修改位在頁面重新分配頁框時很有用。如果一個頁面已經(jīng)被修改過(即它是 臟 的)，則必須把它寫回磁盤。如果一個頁面沒有被修改過(即它是 干凈的)，那么重新分配時這個頁框會被直接丟棄，因為磁盤上的副本仍然是有效的。這個位有時也叫做 臟位(dirty bit)，因為它反映了頁面的狀態(tài)。

訪問位(Referenced) 在頁面被訪問時被設置，不管是讀還是寫。這個值能夠幫助操作系統(tǒng)在發(fā)生缺頁中斷時選擇要淘汰的頁。不再使用的頁要比正在使用的頁更適合被淘汰。這個位在后面要討論的頁面置換算法中作用很大。

最后一位用于禁止該頁面被高速緩存，這個功能對于映射到設備寄存器還是內(nèi)存中起到了關(guān)鍵作用。通過這一位可以禁用高速緩存。具有獨立的 I/O 空間而不是用內(nèi)存映射 I/O 的機器來說，并不需要這一位。

在深入討論下面問題之前，需要強調(diào)一下：虛擬內(nèi)存本質(zhì)上是用來創(chuàng)造一個地址空間的抽象，可以把它理解成為進程是對 CPU 的抽象，虛擬內(nèi)存的實現(xiàn)，本質(zhì)是將虛擬地址空間分解成頁，并將每一項映射到物理內(nèi)存的某個頁框。因為我們的重點是如何管理這個虛擬內(nèi)存的抽象。

加速分頁過程

到現(xiàn)在我們已經(jīng)虛擬內(nèi)存(virtual memory) 和 分頁(paging) 的基礎，現(xiàn)在我們可以把目光放在具體的實現(xiàn)上面了。在任何帶有分頁的系統(tǒng)中，都會需要面臨下面這兩個主要問題：

• 虛擬地址到物理地址的映射速度必須要快
• 如果虛擬地址空間足夠大，那么頁表也會足夠大

第一個問題是由于每次訪問內(nèi)存都需要進行虛擬地址到物理地址的映射，所有的指令最終都來自于內(nèi)存，并且很多指令也會訪問內(nèi)存中的操作數(shù)。

操作數(shù)：操作數(shù)是計算機指令中的一個組成部分，它規(guī)定了指令中進行數(shù)字運算的量 。操作數(shù)指出指令執(zhí)行的操作所需要數(shù)據(jù)的來源。操作數(shù)是匯編指令的一個字段。比如，MOV、ADD 等。

因此，每條指令可能會多次訪問頁表，如果執(zhí)行一條指令需要 1 ns，那么頁表查詢需要在 0.2 ns 之內(nèi)完成，以避免映射成為一個主要性能瓶頸。

第二個問題是所有的現(xiàn)代操作系統(tǒng)都會使用至少 32 位的虛擬地址，并且 64 位正在變得越來越普遍。假設頁大小為 4 KB，32 位的地址空間將近有 100 萬頁，而 64 位地址空間簡直多到無法想象。

對大而且快速的頁映射的需要成為構(gòu)建計算機的一個非常重要的約束。就像上面頁表中的圖一樣，每一個表項對應一個虛擬頁面，虛擬頁號作為索引。在啟動一個進程時，操作系統(tǒng)會把保存在內(nèi)存中進程頁表讀副本放入寄存器中。

最后一句話是不是不好理解?還記得頁表是什么嗎?它是虛擬地址到內(nèi)存地址的映射頁表。頁表是虛擬地址轉(zhuǎn)換的關(guān)鍵組成部分，它是訪問內(nèi)存中數(shù)據(jù)所必需的。在進程啟動時，執(zhí)行很多次虛擬地址到物理地址的轉(zhuǎn)換，會把物理地址的副本從內(nèi)存中讀入到寄存器中，再執(zhí)行這一轉(zhuǎn)換過程。

所以，在進程的運行過程中，不必再為頁表而訪問內(nèi)存。使用這種方法的優(yōu)勢是簡單而且映射過程中不需要訪問內(nèi)存。缺點是 頁表太大時，代價高昂，而且每次上下文切換的時候都必須裝載整個頁表，這樣會造成性能的降低。鑒于此，我們討論一下加速分頁機制和處理大的虛擬地址空間的實現(xiàn)方案。

轉(zhuǎn)換檢測緩沖區(qū)

我們首先先來一起探討一下加速分頁的問題。大部分優(yōu)化方案都是從內(nèi)存中的頁表開始的。這種設計對效率有著巨大的影響?？紤]一下，例如，假設一條 1 字節(jié)的指令要把一個寄存器中的數(shù)據(jù)復制到另一個寄存器。在不分頁的情況下，這條指令只訪問一次內(nèi)存，即從內(nèi)存取出指令。有了分頁機制后，會因為要訪問頁表而需要更多的內(nèi)存訪問。由于執(zhí)行速度通常被 CPU 從內(nèi)存中取指令和數(shù)據(jù)的速度所限制，這樣的話，兩次訪問才能實現(xiàn)一次的訪問效果，所以內(nèi)存訪問的性能會下降一半。在這種情況下，根本不會采用分頁機制。

什么是 1 字節(jié)的指令?我們以 8085 微處理器為例來說明一下，在 8085 微處理中，一共有 3 種字節(jié)指令，它們分別是 1-byte(1 字節(jié))、2-byte(2 字節(jié))、3-byte(3 字節(jié))，我們分別來說一下。

1-byte：1 字節(jié)的操作數(shù)和操作碼共同以 1 字節(jié)表示;操作數(shù)是內(nèi)部寄存器，并被編碼到指令中;指令需要一個存儲位置來將單個寄存器存儲在存儲位置中。沒有操作數(shù)的指令也是 1-byte 指令。

例如：MOV B,C 、LDAX B、NOP、HLT(這塊不明白的讀者可以自行查閱)。

2-byte: 2 字節(jié)包括：第一個字節(jié)指定的操作碼;第二個字節(jié)指定操作數(shù);指令需要兩個存儲器位置才能存儲在存儲器中。

例如 MVI B, 26 H、IN 56 H

3-byte: 在 3 字節(jié)指令中，第一個字節(jié)指定操作碼;后面兩個字節(jié)指定 16 位的地址;第二個字節(jié)保存低位地址;第三個字節(jié)保存 高位地址。指令需要三個存儲器位置才能將單個字節(jié)存儲在存儲器中。

例如 LDA 2050 H、JMP 2085 H

大多數(shù)程序總是對少量頁面進行多次訪問，而不是對大量頁面進行少量訪問。因此，只有很少的頁面能夠被再次訪問，而其他的頁表項很少被訪問。

頁表項一般也被稱為 Page Table Entry(PTE)。

基于這種設想，提出了一種方案，即從硬件方面來解決這個問題，為計算機設置一個小型的硬件設備，能夠?qū)⑻摂M地址直接映射到物理地址，而不必再訪問頁表。這種設備被稱為轉(zhuǎn)換檢測緩沖區(qū)(Translation Lookaside Buffer, TLB)，有時又被稱為 相聯(lián)存儲器(associate memory) 。

TLB 通常位于 MMU 中，包含少量的表項，每個表項都記錄了頁面的相關(guān)信息，除了虛擬頁號外，其他表項都和頁表是一一對應的。

是不是你到現(xiàn)在還是有點不理解什么是 TLB，TLB 其實就是一種內(nèi)存緩存，用于減少訪問內(nèi)存所需要的時間，它就是 MMU 的一部分，TLB 會將虛擬地址到物理地址的轉(zhuǎn)換存儲起來，通?？梢苑Q為地址翻譯緩存(address-translation cache)。TLB 通常位于 CPU 和 CPU 緩存之間，它與 CPU 緩存是不同的緩存級別。下面我們來看一下 TLB 是如何工作的。

當一個 MMU 中的虛擬地址需要進行轉(zhuǎn)換時，硬件首先檢查虛擬頁號與 TLB 中所有表項進行并行匹配，判斷虛擬頁是否在 TLB 中。如果找到了有效匹配項，并且要進行的訪問操作沒有違反保護位的話，則將頁框號直接從 TLB 中取出而不用再直接訪問頁表。如果虛擬頁在 TLB 中但是違反了保護位的權(quán)限的話(比如只允許讀但是是一個寫指令)，則會生成一個保護錯誤(protection fault) 返回。

上面探討的是虛擬地址在 TLB 中的情況，那么如果虛擬地址不再 TLB 中該怎么辦?如果 MMU 檢測到?jīng)]有有效的匹配項，就會進行正常的頁表查找，然后從 TLB 中逐出一個表項然后把從頁表中找到的項放在 TLB 中。當一個表項被從 TLB 中清除出，將修改位復制到內(nèi)存中頁表項，除了訪問位之外，其他位保持不變。當頁表項從頁表裝入 TLB 中時，所有的值都來自于內(nèi)存。

軟件 TLB 管理

直到現(xiàn)在，我們假設每臺電腦都有可以被硬件識別的頁表，外加一個 TLB。在這個設計中，TLB 管理和處理 TLB 錯誤完全由硬件來完成。僅僅當頁面不在內(nèi)存中時，才會發(fā)生操作系統(tǒng)的陷入(trap)。

在以前，我們上面的假設通常是正確的。但是，許多現(xiàn)代的 RISC 機器，包括 SPARC、MIPS 和 HP PA，幾乎所有的頁面管理都是在軟件中完成的。

精簡指令集計算機或 RISC 是一種計算機指令集，它使計算機的微處理器的每條指令(CPI)周期比復雜指令集計算機(CISC)少。

在這些計算機上，TLB 條目由操作系統(tǒng)顯示加載。當發(fā)生 TLB 訪問丟失時，不再是由 MMU 到頁表中查找并取出需要的頁表項，而是生成一個 TLB 失效并將問題交給操作系統(tǒng)解決。操作系統(tǒng)必須找到該頁，把它從 TLB 中移除(移除頁表中的一項)，然后把新找到的頁放在 TLB 中，最后再執(zhí)行先前出錯的指令。然而，所有這些操作都必須通過少量指令完成，因為 TLB 丟失的發(fā)生率要比出錯率高很多。

無論是用硬件還是用軟件來處理 TLB 失效，常見的方式都是找到頁表并執(zhí)行索引操作以定位到將要訪問的頁面，在軟件中進行搜索的問題是保存頁表的頁可能不在 TLB 中，這將在處理過程中導致其他 TLB 錯誤。改善方法是可以在內(nèi)存中的固定位置維護一個大的 TLB 表項的高速緩存來減少 TLB 失效。通過首先檢查軟件的高速緩存，操作系統(tǒng) 能夠有效的減少 TLB 失效問題。

TLB 軟件管理會有兩種 TLB 失效問題，當一個頁訪問在內(nèi)存中而不在 TLB 中時，將產(chǎn)生 軟失效(soft miss)，那么此時要做的就是把頁表更新到 TLB 中(我們上面探討的過程)，而不會產(chǎn)生磁盤 I/O，處理僅僅需要一些機器指令在幾納秒的時間內(nèi)完成。然而，當頁本身不在內(nèi)存中時，將會產(chǎn)生硬失效(hard miss)，那么此時就需要從磁盤中進行頁表提取，硬失效的處理時間通常是軟失效的百萬倍。在頁表結(jié)構(gòu)中查找映射的過程稱為 頁表遍歷(page table walk)。

上面的這兩種情況都是理想情況下出現(xiàn)的現(xiàn)象，但是在實際應用過程中情況會更加復雜，未命中的情況可能既不是硬失效又不是軟失效。一些未命中可能更軟或更硬(偷笑)。比如，如果頁表遍歷的過程中沒有找到所需要的頁，那么此時會出現(xiàn)三種情況：

• 所需的頁面就在內(nèi)存中，但是卻沒有記錄在進程的頁表中，這種情況可能是由其他進程從磁盤掉入內(nèi)存，這種情況只需要把頁正確映射就可以了，而不需要在從硬盤調(diào)入，這是一種軟失效，稱為 次要缺頁錯誤(minor page fault)。
• 基于上述情況，如果需要從硬盤直接調(diào)入頁面，這就是嚴重缺頁錯誤(major page falut)。
• 還有一種情況是，程序可能訪問了一個非法地址，根本無需向 TLB 中增加映射。此時，操作系統(tǒng)會報告一個 段錯誤(segmentation fault) 來終止程序。只有第三種缺頁屬于程序錯誤，其他缺頁情況都會被硬件或操作系統(tǒng)以降低程序性能為代價來修復。

針對大內(nèi)存的頁表

還記得我們討論的是什么問題嗎?(捂臉)，可能討論的太多你有所不知道了，我再提醒你一下，上面加速分頁過程討論的是虛擬地址到物理地址的映射速度必須要快的問題，還有一個問題是 如果虛擬地址空間足夠大，那么頁表也會足夠大的問題，如何處理巨大的虛擬地址空間，下面展開我們的討論。

多級頁表

第一種方案是使用多級頁表(multi)，下面是一個例子。

32 位的虛擬地址被劃分為 10 位的 PT1 域，10 位的 PT2 域，還有 12 位的 Offset 域。因為偏移量是 12 位，所以頁面大小是 4KB，共有 2^20 次方個頁面。

引入多級頁表的原因是避免把全部頁表一直保存在內(nèi)存中。不需要的頁表就不應該保留。

多級頁表是一種分頁方案，它由兩個或多個層次的分頁表組成，也稱為分層分頁。級別1(level 1)頁面表的條目是指向級別 2(level 2) 頁面表的指針，級別2頁面表的條目是指向級別 3(level 3) 頁面表的指針，依此類推。最后一級頁表存儲的是實際的信息。

下面是一個二級頁表的工作過程：

在最左邊是頂級頁表，它有 1024 個表項，對應于 10 位的 PT1 域。當一個虛擬地址被送到 MMU 時，MMU 首先提取 PT1 域并把該值作為訪問頂級頁表的索引。因為整個 4 GB (即 32 位)虛擬地址已經(jīng)按 4 KB 大小分塊，所以頂級頁表中的 1024 個表項的每一個都表示 4M 的塊地址范圍。

由索引頂級頁表得到的表項中含有二級頁表的地址或頁框號。頂級頁表的表項 0 指向程序正文的頁表，表項 1 指向含有數(shù)據(jù)的頁表，表項 1023 指向堆棧的頁表，其他的項(用陰影表示)表示沒有使用?，F(xiàn)在把 PT2 域作為訪問選定的二級頁表的索引，以便找到虛擬頁面的對應頁框號。

倒排頁表

針對分頁層級結(jié)構(gòu)中不斷增加的替代方法是使用 倒排頁表(inverted page tables)。采用這種解決方案的有 PowerPC、UltraSPARC 和 Itanium。在這種設計中，實際內(nèi)存中的每個頁框?qū)粋€表項，而不是每個虛擬頁面對應一個表項。

雖然倒排頁表節(jié)省了大量的空間，但是它也有自己的缺陷：那就是從虛擬地址到物理地址的轉(zhuǎn)換會變得很困難。當進程 n 訪問虛擬頁面 p 時，硬件不能再通過把 p 當作指向頁表的一個索引來查找物理頁。而是必須搜索整個倒排表來查找某個表項。另外，搜索必須對每一個內(nèi)存訪問操作都執(zhí)行一次，而不是在發(fā)生缺頁中斷時執(zhí)行。

解決這一問題的方式是使用 TLB。當發(fā)生 TLB 失效時，需要用軟件搜索整個倒排頁表。一個可行的方式是建立一個散列表，用虛擬地址來散列。當前所有內(nèi)存中的具有相同散列值的虛擬頁面被鏈接在一起。如下圖所示：

如果散列表中的槽數(shù)與機器中物理頁面數(shù)一樣多，那么散列表的沖突鏈的長度將會是 1 個表項的長度，這將會大大提高映射速度。一旦頁框被找到，新的(虛擬頁號，物理頁框號)就會被裝在到 TLB 中。

刊誤

P115 頁，兩條線位置畫反，根據(jù)下面的描述很容易誤導他人，望修正。

文章參考：

https://www.geeksforgeeks.org/multilevel-paging-in-operating-system/

https://en.wikipedia.org/wiki/Translation_lookaside_buffer

https://electricalvoice.com/instruction-word-size-8085-microprocessor/

https://en.wikipedia.org/wiki/Page_table

https://www.javatpoint.com/os-page-table

https://baike.baidu.com/item/內(nèi)存/103614?fr=aladdin

https://baike.baidu.com/item/數(shù)據(jù)段/5136260?fromtitle=data%20segment&fromid=18082638&fr=aladdin

https://blog.csdn.net/One_L_Star/article/details/81901186

《現(xiàn)代操作系統(tǒng)》第四版

《Modern Operation System》fourth

https://baike.baidu.com/item/SATA硬盤/3947233?fr=aladdin

https://baike.baidu.com/item/虛擬地址/1329947?fr=aladdin