目錄

安龍ssl適用于網(wǎng)站、小程序/APP、API接口等需要進(jìn)行數(shù)據(jù)傳輸應(yīng)用場(chǎng)景，ssl證書未來(lái)市場(chǎng)廣闊！成為創(chuàng)新互聯(lián)公司的ssl證書銷售渠道，可以享受市場(chǎng)價(jià)格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：028-86922220（備注：SSL證書合作）期待與您的合作！

1. 分頁(yè)

1.1 地址轉(zhuǎn)換

1.2 頁(yè)表存在哪里

1.3 列表中究竟有什么

1.4?分頁(yè)的優(yōu)缺點(diǎn)

2. 快速地址轉(zhuǎn)換（TLB）

2.1?TLB 的基本算法

2.2 誰(shuí)來(lái)處理 TLB 未命中

2.2.1 硬件處理

2.2.2 軟件（操作系統(tǒng)）處理

2.3?TLB 的內(nèi)容

2.4?上下文切換時(shí)對(duì) TLB 的處理

2.4.1?清空 TLB

2.4.2 地址空間標(biāo)識(shí)符

2.5?TLB 替換策略

3. 較小的頁(yè)表

3.1 簡(jiǎn)單的解決方案：更大的頁(yè)

3.2 混合方法：分頁(yè)和分段

3.2.1 雜合方式的原理

3.2.2 雜合方式存在的問(wèn)題

3.3 多級(jí)頁(yè)表

3.3.1 多級(jí)頁(yè)表的原理

3.3.2 多級(jí)頁(yè)表的成本

3.3.3 兩級(jí)頁(yè)表示例

3.4 反向頁(yè)表

3.5 將頁(yè)表交換到磁盤

4.超越物理內(nèi)存

4.1 交換空間

4.2 存在位

4.3 頁(yè)錯(cuò)誤

4.4 內(nèi)存滿了怎么辦

4.4.1 緩存管理

4.4.2 最優(yōu)替換策略

4.4.3 簡(jiǎn)單策略：FIFO、隨機(jī)

4.4.4 利用歷史數(shù)據(jù)：LRU

4.4.5 近似 LRU

4.4.6 考慮臟頁(yè)

4.5 交換何時(shí)真正發(fā)生

---

Operating Systems: Three Easy Pieces 筆記
第18章 分頁(yè)：介紹
第19章 分頁(yè)：快速地址轉(zhuǎn)換（TLB）
第20章 分頁(yè)：較小的表
第 21 章 超越物理內(nèi)存：機(jī)制
第 22 章 超越物理內(nèi)存：策略

1. 分頁(yè)

操作系統(tǒng)解決空間管理的兩種方法

（1）將空間分割成不同長(zhǎng)度的分片，就像虛擬內(nèi)存管理中的分段。但是，這個(gè)解決方法存在固有的問(wèn)題 -->空間本身會(huì)碎片化（fragmented）， 隨著時(shí)間推移，分配內(nèi)存會(huì)變得比較困難。

（2）將空間分割成固定長(zhǎng)度的分片，在虛擬內(nèi)存中，我們稱這種思想為分頁(yè)。將一個(gè)進(jìn)程的地址空間分割成固定大小的單元，每個(gè)單元稱為一頁(yè)。相應(yīng)地，我們把物理內(nèi)存看成是定長(zhǎng)槽塊的陣列，叫作頁(yè)幀（page frame）。每個(gè)這樣的頁(yè)幀包含一個(gè)虛擬內(nèi)存頁(yè)。

1.1 地址轉(zhuǎn)換

圖 18.1 展示了一個(gè)只有 64 字節(jié)的小地址空間，有 4 個(gè) 16 字節(jié)的頁(yè)（虛擬頁(yè) 0、1、2、3）。真實(shí)的地址空間肯定大得 多，通常 32 位有 4GB 的地址空間，甚至有 64 位。

圖 18.2 展示了對(duì)應(yīng)的物理內(nèi)存，由一組固定大小的槽塊組成。在這個(gè)例子中，有 8 個(gè)頁(yè)幀（由 128 字節(jié)物理內(nèi)存構(gòu)成，也是極小的）。從圖中可以看出，虛擬地址空間的頁(yè)放在物理內(nèi)存的不同位置。圖中還顯示，操作系統(tǒng)自己用了一些物理內(nèi)存。

為了記錄地址空間的每個(gè)虛擬頁(yè)放在物理內(nèi)存中的位置，操作系統(tǒng)通常為每個(gè)進(jìn)程保存一個(gè)數(shù)據(jù)結(jié)構(gòu)，稱為頁(yè)表（page table）。示例中，頁(yè)表具有以下 4 個(gè)條目：（VP 0→物理幀 3）、（VP 1→PF 7）、 （VP 2→PF 5）和（VP 3→PF 2）。

頁(yè)表是一個(gè)每進(jìn)程的數(shù)據(jù)結(jié)構(gòu)。如果在上面的示例中運(yùn)行另一個(gè)進(jìn)程，操作系統(tǒng)將不得不為它管理不同的頁(yè)表，因?yàn)樗奶摂M頁(yè)顯 然映射到不同的物理頁(yè)面（除了共享之外）。

為了轉(zhuǎn)換該過(guò)程生成的虛擬地址，首先將其分成兩個(gè)組件：虛擬頁(yè)面號(hào)（virtual page number，VPN）和頁(yè)內(nèi)的偏移量（offset）。對(duì)于這個(gè)例子，因?yàn)檫M(jìn)程的虛擬地址空間是 64 字節(jié)，我們的虛擬地址總共需要 6 位（2^6 = 64）；頁(yè)的大小為16 字節(jié)（2^4 ），因此我們有一個(gè) 2 位（64字節(jié)/16字節(jié) = 2^2）的虛擬頁(yè)號(hào)（VPN）；位于 64 字節(jié)的地址空間，因此我們需要能夠選擇 4 個(gè)頁(yè)。虛擬地址表示如下：

假設(shè)上面的加載是虛擬地址 21，其二進(jìn)制形式是 010101。虛擬地址“21”在虛擬頁(yè)“01”（或 1）的第 5 個(gè)（“0101”）字節(jié)處。我們的最終物理地址是 1110101（十進(jìn)制 117），正是我們希望加載指令（見(jiàn)圖 18.2）獲取數(shù)據(jù)的地方。

1.2 頁(yè)表存在哪里

頁(yè)表可以變得非常大，例如，想象一個(gè)典型的 32 位地址空間，帶有 4KB（2^12）的頁(yè)。這個(gè)虛擬地址分成 20 位的 VPN 和 12 位的偏移量（1KB 的頁(yè)面大小需要 10 位，只需增加兩位即可達(dá)到 4KB）。 一個(gè) 20 位的 VPN 意味著，操作系統(tǒng)必須為每個(gè)進(jìn)程管理 2^20個(gè)地址轉(zhuǎn)換（大約一百萬(wàn)）。 假設(shè)每個(gè)頁(yè)表格條目（PTE）需要 4 個(gè)字節(jié)，來(lái)保存物理地址轉(zhuǎn)換和任何其他有用的東西， 每個(gè)頁(yè)表就需要巨大的 4MB 內(nèi)存！這非常大?，F(xiàn)在想象一下有 100 個(gè)進(jìn)程在運(yùn)行：這意味 著操作系統(tǒng)會(huì)需要 400MB 內(nèi)存，只是為了所有這些地址轉(zhuǎn)換！

由于頁(yè)表如此之大，我們沒(méi)有在 MMU 中利用任何特殊的片上硬件，而是將每個(gè)進(jìn)程的頁(yè)表存儲(chǔ)在內(nèi)存中。

1.3 列表中究竟有什么

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

每個(gè) PTE 包含許多不同的位:

有效位（valid bit） 通常用于指示特定地址轉(zhuǎn)換是否有效。例如，當(dāng)一個(gè)程序開(kāi)始運(yùn)行時(shí)，它的代碼和堆在其 地址空間的一端，棧在另一端。所有未使用的中間空間都將被標(biāo)記為無(wú)效（invalid），如果進(jìn)程嘗試訪問(wèn)這種內(nèi)存，就會(huì)陷入操作系統(tǒng)，可能會(huì)導(dǎo)致該進(jìn)程終止。因此，有效位對(duì)于支持稀疏地址空間至關(guān)重要。通過(guò)簡(jiǎn)單地將地址空間中所有未使用的頁(yè)面標(biāo)記為無(wú)效，我們不再需要為這些頁(yè)面分配物理幀，從而節(jié)省大量?jī)?nèi)存。

保護(hù)位（protection bit），表明頁(yè)是否可以讀取、寫入或執(zhí)行。同樣，以這些位不允許的方式訪問(wèn)頁(yè)，會(huì)陷入操作系統(tǒng)。

存在位（present bit）表示該頁(yè)是在物理存儲(chǔ)器還是在磁盤上（即它已被換出，swapped out）。當(dāng)我們研究如何將部分地址空間交換（swap）到磁盤，從而支持大于物理內(nèi)存的地址空間時(shí)，我們將進(jìn)一步理解這一 機(jī)制。交換允許操作系統(tǒng)將很少使用的頁(yè)面移到磁盤，從而釋放物理內(nèi)存。

臟位（dirty bit） 表明頁(yè)面被帶入內(nèi)存后是否被修改過(guò)。

參考位（reference bit / 訪問(wèn)位 accessed bit）有時(shí)用于追蹤頁(yè)是否被訪問(wèn)，也用于確定哪些頁(yè)很受歡迎，因此應(yīng)該保留在內(nèi)存中。

圖 18.5 顯示了來(lái)自 x86 架構(gòu)的示例頁(yè)表項(xiàng)[I09]。它包含一個(gè)存在位（P），確定是否允許寫入該頁(yè)面的讀/寫位（R/W），?確定用戶模式進(jìn)程是否可以訪問(wèn)該頁(yè)面的用戶/超級(jí)用戶位 （U/S），有幾位（PWT、PCD、PAT 和 G）確定硬件緩存如何為這些頁(yè)面工作，一個(gè)訪問(wèn)位 （A）和一個(gè)臟位（D），最后是頁(yè)幀號(hào)（PFN）本身。

1.4?分頁(yè)的優(yōu)缺點(diǎn)

與分段相比，分頁(yè)有許多優(yōu)點(diǎn)：

首先，它不會(huì)導(dǎo)致外部碎片，因?yàn)榉猪?yè)將內(nèi)存劃分為固定大小的單元。

其次，它非常靈活，支持稀疏虛擬地址空間。

然而，實(shí)現(xiàn)分頁(yè)支持而不小心考慮，會(huì)導(dǎo)致 / 缺點(diǎn)：

較慢的機(jī)器（有許多額外的內(nèi)存訪問(wèn)來(lái)訪問(wèn)頁(yè)表）-->映射信息一般存儲(chǔ)在物理內(nèi)存中，所以在轉(zhuǎn)換虛擬地址時(shí)，每次指令獲取、顯式加載或保存，都要額外讀一次內(nèi)存以得到轉(zhuǎn)換信息

內(nèi)存浪費(fèi)（內(nèi)存被頁(yè)表塞滿而不是有用的應(yīng)用程序數(shù)據(jù)）

2. 快速地址轉(zhuǎn)換（TLB）

如何加速地址轉(zhuǎn)換 -->硬件

地址轉(zhuǎn)換旁路緩沖存儲(chǔ)器（translation-lookaside buffer，TLB）/ 地址轉(zhuǎn)換緩存（address-translation cache），即頻繁發(fā)生的虛擬到物理地址轉(zhuǎn)換的硬件緩存（cache） -->

對(duì)每次內(nèi)存訪問(wèn)，硬件先檢查 TLB，看看其中是否有期望的轉(zhuǎn)換映射，如果有，就完成轉(zhuǎn)換（很快），不用訪問(wèn)頁(yè)表 （其中有全部的轉(zhuǎn)換映射）。

2.1?TLB 的基本算法

硬件算法的大體流程如下：

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

如果有，我們有了 TLB 命中（TLB hit）， 這意味著 TLB 有該頁(yè)的轉(zhuǎn)換映射。成功！接下來(lái)我們就可以從相關(guān)的 TLB 項(xiàng)中取出頁(yè)幀號(hào) （PFN），與原來(lái)虛擬地址中的偏移量組合形成期望的物理地址（PA），并訪問(wèn)內(nèi)（第 5～7 行），假定保護(hù)檢查沒(méi)有失敗。

如果 CPU 沒(méi)有在 TLB 中找到轉(zhuǎn)換映射（TLB 未命中），硬件訪問(wèn)頁(yè)表來(lái)尋找轉(zhuǎn)換映射，并用該轉(zhuǎn)換映射更新 TLB， 假設(shè)該虛擬地址有效，而且我們有相關(guān)的訪問(wèn)權(quán)限。最后，當(dāng) TLB 更新成功后，系統(tǒng)會(huì)重新嘗試該指令，這時(shí) TLB 中有了這個(gè)轉(zhuǎn)換映射，內(nèi)存引用得到很快處理。

2.2 誰(shuí)來(lái)處理 TLB 未命中 2.2.1 硬件處理

以前的硬件有復(fù)雜的指令集，有時(shí)稱為復(fù)雜指令集計(jì)算機(jī)（Complex-Instruction Set Computer，CISC），一個(gè)例子是 x86 架構(gòu)，硬件全權(quán)處理 TLB 未命中。為了做到這一點(diǎn)，硬件必須知道頁(yè)表在內(nèi)存中的確切位置（通過(guò)頁(yè)表基址寄存器， page-table base register），以及頁(yè)表的確切格式。發(fā)生未命中時(shí)， 硬件會(huì)“遍歷”頁(yè)表，找到正確的頁(yè)表項(xiàng)，取出想要的轉(zhuǎn)換映射，用它更新 TLB，并重試該指令。

2.2.2 軟件（操作系統(tǒng)）處理

更現(xiàn)代的體系結(jié)構(gòu)，都是精簡(jiǎn)指令集計(jì)算機(jī)（Reduced-Instruction Set Computer，RISC），有所謂的軟件管理 TLB（softwaremanaged TLB）。發(fā)生 TLB 未命中時(shí)，硬件系統(tǒng)會(huì)拋出一個(gè)異常，這會(huì)暫停當(dāng)前的指令流，將特權(quán)級(jí)提升至內(nèi)核模式，跳轉(zhuǎn)至陷阱處理程序（trap handler）。這個(gè)陷阱處理程序是操作系統(tǒng)的一段代碼，用于處理 TLB 未命中。 這段代碼會(huì)查找頁(yè)表中的轉(zhuǎn)換映射，然后用特別的“特權(quán)”指令更新 TLB，并從陷阱返回。然后，硬件重試該指令， TLB 命中。

注意兩個(gè)重要的細(xì)節(jié)。
第一，這里的從陷阱返回指令稍稍不同于之前提到的服務(wù)于系統(tǒng)調(diào)用的從陷阱返回。
在后一種情況下，從陷阱返回應(yīng)該繼續(xù)執(zhí)行陷入操作系統(tǒng)之后那條指令，就像從函數(shù)調(diào)用返回后，會(huì)繼續(xù)執(zhí)行此次調(diào)用之后的語(yǔ)句。
在前一種情況下，從 TLB 未命中的陷阱返回后，硬件必須從導(dǎo)致陷阱的指令繼續(xù)執(zhí)行。這次重試再次執(zhí)行該指令，但這次會(huì)命中 TLB。
因此，根據(jù)陷阱或異常的原因，系統(tǒng)在陷入內(nèi)核時(shí)必須保存不同的程序計(jì)數(shù)器，以便將來(lái)能夠正確地繼續(xù)執(zhí)行。

第二，在運(yùn)行 TLB 未命中處理代碼時(shí)，操作系統(tǒng)需要避免TLB 未命中的無(wú)限遞歸。有很多解決方案，例如，可以把 TLB 未命中陷阱處理程序直接放到物理內(nèi)存中 （它們沒(méi)有映射過(guò)，不用經(jīng)過(guò)地址轉(zhuǎn)換）?；蛘咴?TLB 中保留一些項(xiàng)，記錄永久有效的地址轉(zhuǎn)換，并將其中一些永久地址轉(zhuǎn)換槽塊留給處理代碼本身，這些被監(jiān)聽(tīng)的地址轉(zhuǎn)換總是會(huì)命中 TLB。

2.3?TLB 的內(nèi)容

VPN ｜ PFN ｜ 其他位

“其他位”，例如，TLB 通常有一個(gè)有效（valid）位，用來(lái)標(biāo)識(shí)該項(xiàng)是不是 有效地轉(zhuǎn)換映射。通常還有一些保護(hù)（protection）位，用來(lái)標(biāo)識(shí)該頁(yè)是否有訪問(wèn)權(quán)限。例如，代碼頁(yè)被標(biāo)識(shí)為可讀和可執(zhí)行，而堆的頁(yè)被標(biāo)識(shí)為可讀和可寫。還有其他一些位，包括地址空間標(biāo)識(shí)符（address-space identifier）、臟位（dirty bit）等。

2.4?上下文切換時(shí)對(duì) TLB 的處理

TLB 中包含的虛擬到物理的地址映射只對(duì)當(dāng)前進(jìn)程有效，所以在發(fā)生進(jìn)程切換時(shí)，硬件或操作系統(tǒng)（或二者）必須注意確保即將運(yùn)行的進(jìn)程不要誤讀了之前進(jìn)程的地址映射。

這個(gè)問(wèn)題有一些可能的解決方案。

2.4.1?清空 TLB

一種方法是在上下文切換時(shí)，簡(jiǎn)單地清空（flush）TLB， 這樣在新進(jìn)程運(yùn)行前 TLB 就變成了空的。進(jìn)程不會(huì)再讀到錯(cuò)誤的地址映射。但是，有一定開(kāi)銷：每次進(jìn)程運(yùn)行，當(dāng)它訪問(wèn)數(shù)據(jù)和代碼頁(yè)時(shí)，都會(huì)觸發(fā) TLB 未命中。

如果是軟件管理 TLB 的系統(tǒng)，可以在發(fā)生上下文切換時(shí)，通過(guò)一條顯式（特權(quán)）指令來(lái)完成。

如果是硬件管理 TLB，則可以在頁(yè)表基址寄存器內(nèi)容發(fā)生變化時(shí)清空 TLB。

不論哪種情況，清空操作都是把全部有效位（valid）置為 0，本質(zhì)上清空了 TLB。

2.4.2 地址空間標(biāo)識(shí)符

如果操作系統(tǒng)頻繁地切換進(jìn)程，這種開(kāi)銷會(huì)很高。 為了減少這種開(kāi)銷，一些系統(tǒng)增加了硬件支持，實(shí)現(xiàn)跨上下文切換的 TLB 共享。比如，有的系統(tǒng)在 TLB 中添加了一個(gè)地址空間標(biāo)識(shí)符（Address Space Identifier，ASID）。可以把 ASID 看作是進(jìn)程標(biāo)識(shí)符（Process Identifier，PID），但通常比 PID 位數(shù)少（PID 一般 32 位， ASID 一般是 8 位）。有了地址空間標(biāo)識(shí)符，TLB 可以同時(shí)緩存不同進(jìn)程的地址空間映。

2.5?TLB 替換策略

緩存替換（cache replacement）-->向 TLB 中插入新項(xiàng)時(shí)，會(huì)替換（replace）一個(gè)舊項(xiàng)，這樣問(wèn)題就來(lái)了：應(yīng)該替換那一個(gè)？

（1）替換最近最少使用（least-recently-used，LRU）的項(xiàng)。

（2）另一 種典型策略就是隨機(jī)（random）策略，即隨機(jī)選擇一項(xiàng)換出去。

這種策略很簡(jiǎn)單，并且可以避免一種極端情況。例如，一個(gè)程序循環(huán)訪問(wèn) n+1 個(gè)頁(yè)，但 TLB 大小只能存放 n 個(gè)頁(yè)。 這時(shí)之前看似“合理”的 LRU 策略就會(huì)表現(xiàn)得不可理喻，因?yàn)槊看卧L問(wèn)內(nèi)存都會(huì)觸發(fā) TLB 未命中。

3. 較小的頁(yè)表

現(xiàn)在來(lái)解決分頁(yè)引入的第二個(gè)問(wèn)題：頁(yè)表太大，因此消耗的內(nèi)存太多。

3.1 簡(jiǎn)單的解決方案：更大的頁(yè)

從線性頁(yè)表開(kāi)始，假設(shè)有一個(gè) 32 位地址空間（2^32 字節(jié)），頁(yè)表項(xiàng)4 字節(jié)

4KB的頁(yè)（2^12 字節(jié)） -->約一百萬(wàn)個(gè)虛擬頁(yè)面 （2^32/2^12=1M），頁(yè)表大小為 4MB

一種簡(jiǎn)單的減小頁(yè)表大小的方法：使用更大的頁(yè)

16KB 的頁(yè) -->18 位的 VPN +14 位的偏移量 -->現(xiàn)在線性頁(yè)表中有 2^18（256K個(gè)虛擬頁(yè)面）個(gè)項(xiàng)，頁(yè)表大小為 1MB（256K*4B），頁(yè)表縮到四分之一

存在的問(wèn)題：大內(nèi)存頁(yè)會(huì)導(dǎo)致每頁(yè)內(nèi)的浪費(fèi)，浪費(fèi)在分配單元內(nèi)部，稱為內(nèi)部碎片（internal fragmentation）問(wèn)題。因此，大多數(shù)系統(tǒng)在常見(jiàn)的情況下使用相對(duì)較小的頁(yè)大?。?KB（如 x86）或 8KB（如 SPARCv9）。

3.2 混合方法：分頁(yè)和分段 3.2.1 雜合方式的原理

假設(shè)我們有一個(gè)地址空間，其中 堆和棧的使用部分很小。例如，我們使用一個(gè) 16KB 的小地址空間和 1KB 的頁(yè)（見(jiàn)圖 20.1）。該地址空間的頁(yè)表如表 20.1 所示。

這個(gè)例子假定單個(gè)代碼頁(yè)（VPN 0）映射到物理 頁(yè) 10，單個(gè)堆頁(yè)（VPN 4）映射到物理頁(yè) 23，以及 地址空間另一端的兩個(gè)棧頁(yè)（VPN 14 和 15）被分別 映射到物理頁(yè) 28 和 4。從圖 20.1 中可以看到，大部 分頁(yè)表都沒(méi)有使用，充滿了無(wú)效的（invalid）項(xiàng)，十分浪費(fèi)。

因此，我們的雜合方式為每個(gè)邏輯分段提供一個(gè)頁(yè)表。在這個(gè)例子中，我們可能有 3 個(gè)頁(yè)表，地址空間的代碼、堆和棧部分各有一個(gè)。

分段中有一個(gè)基址（base）寄存器，存放每個(gè)段在物理內(nèi)存中的位置，還有一個(gè)界限（bound）或限制（limit）寄存器，存放該段的大小。在雜合方案中也有這些結(jié)構(gòu)。不同的是，使用基址寄存器保存該段頁(yè)表的物理地址；界限寄存器用于指示頁(yè)表的結(jié)尾（即它有多少有效頁(yè)）。

假設(shè) 32 位虛擬地址空間包含 4KB 頁(yè)面，且地址空間分為 4 個(gè)段。本例中，我們只使用 3 個(gè)段：一個(gè)用于代碼，另一個(gè)用于堆，還有 一個(gè)用于棧。 用地址空間的前兩位確定地址引用的是哪個(gè)段。假設(shè) 00 是未使用的段，01 是代 碼段，10 是堆段，11 是棧段。因此，虛擬地址如下所示：

在硬件中，假設(shè)有 3 個(gè)基本/界限對(duì)，代碼、堆和棧各一個(gè)。當(dāng)進(jìn)程正在運(yùn)行時(shí)，每個(gè)段的基址寄存器都包含該段的線性頁(yè)表的物理地址。因此，系統(tǒng)中的每個(gè)進(jìn)程現(xiàn)在都有 3 個(gè)與其關(guān)聯(lián)的頁(yè)表。在上下文切換時(shí)，必須更改這些寄存器，以反映新運(yùn)行進(jìn)程的頁(yè)表的位置。 在 TLB 未命中時(shí)（假設(shè)硬件負(fù)責(zé)處理 TLB 未命中），硬件使用分段位（SN）來(lái)確定要用哪個(gè)基址和界限對(duì)。然后硬件將其中的物理地址與 VPN 結(jié)合起來(lái)， 形成頁(yè)表項(xiàng)（PTE）的地址。

例如，如果代碼段使用它的前 3 個(gè)頁(yè)（0、1 和 2），則代碼段頁(yè)表將只有 3 個(gè)項(xiàng)分配給它，并且界限寄存器將被設(shè)置為 3。內(nèi)存訪問(wèn)超出段的末尾將產(chǎn)生一個(gè)異常，并可能導(dǎo)致進(jìn)程終止。以這種方式，與線性頁(yè)表相比，雜合方法實(shí)現(xiàn)了顯著的內(nèi)存節(jié)省。棧和堆之間未分配的頁(yè)不再占用頁(yè)表中的空間（僅將其標(biāo)記為無(wú)效）。

3.2.2 雜合方式存在的問(wèn)題

首先，仍然要求使用分段。如果有一個(gè)大而稀疏的堆，仍然可能導(dǎo)致大量的頁(yè)表浪費(fèi)。

其次，這種雜合導(dǎo)致外部碎片再次出現(xiàn)。盡管大部分內(nèi)存是以頁(yè)面大小單位管理的，但頁(yè)表現(xiàn)在可以是任意大?。ㄊ?PTE 的倍數(shù)）。因此，在內(nèi)存中為它們尋找自由空間更為復(fù)雜。

3.3 多級(jí)頁(yè)表 3.3.1 多級(jí)頁(yè)表的原理

如何去掉頁(yè)表中的所有無(wú)效區(qū)域，而不是將它們?nèi)勘Ａ粼趦?nèi)存中？

使用多級(jí)頁(yè)表（multi-level page table）將線性頁(yè)表變成了類似樹(shù)的東西，eg：x86系統(tǒng)。

多級(jí)頁(yè)表的基本思想：讓線性頁(yè)表的一部分消失（釋放這些幀用于其他用途），并用頁(yè)目錄來(lái)記錄頁(yè)表的哪些頁(yè)被分配。

首先，將頁(yè)表分成頁(yè)大小的單元。然后，如果整頁(yè)的頁(yè)表項(xiàng)（PTE）無(wú)效，就完全不分配該頁(yè)的頁(yè)表。使用名為頁(yè)目錄（page directory）的新結(jié)構(gòu)追蹤頁(yè)表的頁(yè)是否有效，以及（如果有效）它在內(nèi)存中的位置。圖 20.2 的左邊是經(jīng)典的線性頁(yè)表。即使地址空間的大部分中間區(qū)域無(wú)效，我們?nèi)匀恍枰獮檫@些區(qū)域分配頁(yè)表空間（即頁(yè)表的中間兩頁(yè)）。右側(cè)是一個(gè)多級(jí)頁(yè)表。頁(yè)目錄僅將頁(yè)表的兩頁(yè)標(biāo)記為有效（第一個(gè)和最后一個(gè)）；因此，頁(yè)表的這兩頁(yè)就駐留在內(nèi)存中。

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

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

3.3.2 多級(jí)頁(yè)表的成本

在任何復(fù)雜的多級(jí)頁(yè)表訪問(wèn)發(fā)生之前，硬件首先檢查 TLB。在命中時(shí)，物理地址直接形成，而不像之前一樣訪問(wèn)頁(yè)表。只有在 TLB 未命中時(shí)，硬件才需要執(zhí) 行完整的多級(jí)查找。

以兩級(jí)頁(yè)表為例，在 TLB 未命中時(shí)，需要從內(nèi)存加載兩次，才能從頁(yè)表中獲取正確的地址轉(zhuǎn)換信息（一次用于頁(yè)目錄，另一次用于 PTE 本身），而用線性頁(yè)表只需加載一次。因此，多級(jí)表是一個(gè)時(shí)間-空間折中（time-space trade-off）的例子。在TLB 命中的情況下，性能和線性頁(yè)表相同，但 TLB 未命中時(shí)，則會(huì)因較小的表而導(dǎo)致較高的成本。 另一個(gè)明顯的缺點(diǎn)是復(fù)雜性。在 TLB 未命中時(shí)，無(wú)論是硬件還是操作系統(tǒng)來(lái)處理頁(yè)表查找，無(wú)疑都比簡(jiǎn)單的線性頁(yè)表查找更復(fù)雜。

3.3.3 兩級(jí)頁(yè)表示例

設(shè)想一個(gè)大小為 16KB 的小地址空間，其中包含 64 個(gè)字節(jié)的頁(yè)，具體信息整理如下

地址空間	16KB, 14位
頁(yè)大小	64字節(jié)，6位 ->偏移量6位
VPN	8位
線性頁(yè)表	2^8 = 256項(xiàng)
現(xiàn)在將將完整的線性頁(yè)表?分解成 頁(yè)大小的單元??
PTE 的大小	4字節(jié) ->頁(yè)表大小1KB（4 字節(jié)×256項(xiàng)） -> 1KB 頁(yè)表可以分為 16 個(gè) 64 字節(jié)的頁(yè)（1024字節(jié)/64字節(jié)） 每個(gè)頁(yè)可以容納 16 個(gè) PTE（64字節(jié)/4字節(jié)）
頁(yè)目錄需要幾位來(lái)索引頁(yè)表項(xiàng)所在的頁(yè)	256 個(gè)項(xiàng)，分布在 16 (2^4)個(gè)頁(yè)上 -> 需要 4 位 VPN 來(lái)索引目錄

圖 20.3 展示了這種地址空間的一個(gè)例子。

在這個(gè)例子中，虛擬頁(yè) 0 和 1 用于代碼，虛擬頁(yè) 4 和 5 用 于堆，虛擬頁(yè) 254 和 255 用于棧。地址空間的其余頁(yè)未被使用。 要為這個(gè)地址空間構(gòu)建一個(gè)兩級(jí)頁(yè)表，我們從完整的線性頁(yè)表開(kāi)始，將它分解成頁(yè)大小的單元。

在這個(gè)例子中，完整頁(yè)表有 256 個(gè)項(xiàng)；假設(shè)每個(gè) PTE 的大小是 4 個(gè)字節(jié)。因此，我們的完整頁(yè)表大小為 1KB（256×4 字節(jié)）。頁(yè)的大小為64 字節(jié)，1KB 頁(yè)表可以分為 16 個(gè) 64 字節(jié)的頁(yè)，每個(gè)頁(yè)可以容納 16 個(gè) PTE。

這個(gè)例子中的頁(yè)表很?。?56 個(gè)項(xiàng)，分布在 16 個(gè)頁(yè)上。頁(yè)目錄需要為頁(yè)表的每頁(yè)提供一個(gè)項(xiàng)，所以需要 4 位 VPN 來(lái)索引目錄。我們使用 VPN 的前 4 位，如下所示：

PDIndex?頁(yè)目錄索引

PTIndex?頁(yè)表索引

PDE 頁(yè)目錄項(xiàng)

PTE 頁(yè)表項(xiàng)

從 VPN 中提取?PDIndex ->索引到頁(yè)目錄 ->如果 PDE 標(biāo)記為無(wú)效則引發(fā)異常 (End)??如果 PDE 有效 ->從頁(yè)目錄項(xiàng)指向的頁(yè)表的頁(yè)中獲取 PTE ->獲取頁(yè)

3.4 反向頁(yè)表

不同于上述，系統(tǒng)的每個(gè)進(jìn)程一個(gè)頁(yè)表，有許多頁(yè)表。反向頁(yè)表，只保留一個(gè)頁(yè)表。

反向頁(yè)表（inverted page table）的頁(yè)表項(xiàng)代表系統(tǒng)的每個(gè)物理頁(yè)，告訴我們哪個(gè)進(jìn)程正在使用此頁(yè)，以及該進(jìn)程的哪個(gè)虛擬頁(yè)映射到此物理頁(yè)。 現(xiàn)在，要找到正確的項(xiàng)，就是要搜索這個(gè)數(shù)據(jù)結(jié)構(gòu)。線性掃描是昂貴的，因此通常在此基礎(chǔ)結(jié)構(gòu)上建立散列表，以加速查找。

3.5 將頁(yè)表交換到磁盤

到目前為止，我們一直假設(shè)頁(yè)表位于內(nèi)核擁有的物理內(nèi)存中。即使我們有很多技巧來(lái)減小頁(yè)表的大小，但是它仍然有可能是太大而無(wú)法一 次裝入內(nèi)存。因此，一些系統(tǒng)將這樣的頁(yè)表放入內(nèi)核虛擬內(nèi)存（kernel virtual memory），從而允許系統(tǒng)在內(nèi)存壓力較大時(shí)，將這些頁(yè)表中的一部分交換（swap）到磁盤。

4.超越物理內(nèi)存

為了支持更大的地址空間，操作系統(tǒng)需要把當(dāng)前沒(méi)有在用的那部分地址空間找個(gè)地方存儲(chǔ)起來(lái)。

比內(nèi)存有更大的容量，所以一般來(lái)說(shuō)也更慢 -->硬盤（hard disk drive）

4.1 交換空間

我們將內(nèi)存中的頁(yè)交換到 交換空間（swap space），并在需要的時(shí)候又交換回去。因此，我們會(huì)假設(shè)操作系統(tǒng)能夠以頁(yè)大小為單元讀取或者寫入交換空間。為了達(dá)到這個(gè)目的，操作系統(tǒng)需要記住給定頁(yè)的硬盤地址（disk address）。使用交換空間可以讓系統(tǒng)假裝內(nèi)存比實(shí)際物理內(nèi)存更大。

4.2 存在位

假設(shè)有一個(gè)硬件管理 TLB 的系統(tǒng)。 硬件首先從虛擬地址獲得 VPN，檢查 TLB 是否匹配，

如果命中，則獲得最終的物理地址并從內(nèi)存中取回。

如果 TLB 未命中，則硬件在內(nèi)存中查找頁(yè)表（使用頁(yè)表基址寄存器），并使用 VPN 查找該頁(yè)的頁(yè)表項(xiàng)（PTE）作為索引。如果頁(yè)有效且存在于物理內(nèi)存中，則硬件從 PTE 中獲得 PFN，將其插入 TLB，并重試該指令，這次 TLB 命中。不過(guò)，硬件在 PTE 中查找的頁(yè)，有可能不在物理內(nèi)存中。

硬件（或操作系統(tǒng)，在軟件管理 TLB 時(shí)）判斷是否在內(nèi)存中的方法，是通過(guò)頁(yè)表項(xiàng)中的一條新信息，即存在位（present bit）。如果存在位設(shè)置為 1，則表示該頁(yè)存在于物理內(nèi)存中。如果存在位設(shè)置為 零，則頁(yè)不在內(nèi)存中，而在硬盤上。訪問(wèn)不在物理內(nèi)存中的頁(yè)，這種行為通常被稱為頁(yè)錯(cuò) 誤（page fault）。

4.3 頁(yè)錯(cuò)誤

在 TLB 未命中的情況下，如果頁(yè)不存在，由操作系統(tǒng)負(fù)責(zé)處理頁(yè)錯(cuò)誤，將該頁(yè)交換到內(nèi)存中。

當(dāng)硬盤 I/O 完成時(shí)，操作系統(tǒng)會(huì)更新頁(yè)表，將此頁(yè)標(biāo)記為存在，更新頁(yè)表項(xiàng)（PTE）的 PFN 字段以記錄新獲取頁(yè)的內(nèi)存位置，并重試指令。再次重新訪問(wèn) TLB 還是未命中，但這次頁(yè)在內(nèi)存中，因此會(huì)將頁(yè)表中的地址更新到 TLB 中（也可以在處理頁(yè)錯(cuò)誤時(shí)更新 TLB 以避免此步驟）。最后的重試操作會(huì)在 TLB 中找到轉(zhuǎn)換映射，從已轉(zhuǎn)換的內(nèi)存物理地址，獲取所需的數(shù)據(jù)或指令。

當(dāng) TLB 未命中發(fā)生的時(shí)候有 3 種重要情景：

第一種情況，該頁(yè)有效且存在。在這種情況下，TLB 未命中處理程序可以簡(jiǎn)單地從 PTE 中獲取 PFN，然后重試指令（這次 TLB 會(huì)命中）。

第二種情況，該頁(yè)有效但不存在，頁(yè)錯(cuò)誤處理程序需要運(yùn)行。雖然這是進(jìn)程可以訪問(wèn)的合法頁(yè)，但它并不在物理內(nèi)存中。

第三種情況，訪問(wèn)的是一個(gè)無(wú)效頁(yè)，可能由于程序中的錯(cuò)誤。在這種情況下，PTE 中的其他位都 不重要了。硬件捕獲這個(gè)非法訪問(wèn)，操作系統(tǒng)陷阱處理程序運(yùn)行，可能會(huì)殺死非法進(jìn)程。?

4.4 內(nèi)存滿了怎么辦

在上面的描述中，我們假設(shè)有足夠的空閑內(nèi)存來(lái)從存儲(chǔ)交換空間換入（page in）的頁(yè)。但是，內(nèi)存可能已滿（或接近滿了）。因此，操作系統(tǒng)可能希望先交換出（page out）一個(gè)或多個(gè)頁(yè)，以便為操作系統(tǒng)即將交換入的新頁(yè)留出空間。選擇哪些頁(yè)被交換出或被替換（replace）的過(guò)程，被稱為頁(yè)交換策略（page-replacement policy）。

4.4.1 緩存管理

由于內(nèi)存只包含系統(tǒng)中所有頁(yè)的子集，因此可以將其視為系統(tǒng)中虛擬內(nèi)存頁(yè)的緩存（cache）。

因此，在為這個(gè)緩存選擇替換策略時(shí)，我們的目標(biāo)是讓緩存未命中（cache miss）最少，即從磁盤獲取頁(yè)的次數(shù)最少?；蛘撸尵彺婷校╟ache hit）最多，即在內(nèi)存中找到待訪問(wèn)頁(yè)的次數(shù)最多。

平均內(nèi)存訪問(wèn)時(shí)間（Average Memory Access Time，AMAT）

4.4.2 最優(yōu)替換策略

如果不得不踢出一些頁(yè)，為什么不踢出在最遠(yuǎn)將來(lái)才會(huì)訪問(wèn)的頁(yè)呢？

假設(shè)一個(gè)程序按照以下順序訪問(wèn) 虛擬頁(yè)：0，1，2，0，1，3，0，3，1，2，1。表 22.1 展示了最優(yōu)的策略，這里假設(shè)緩存可以存 3 個(gè)頁(yè)。

前 3 個(gè)訪問(wèn)是未命中，因?yàn)榫彺骈_(kāi)始是空的。這種未命中有時(shí)也稱作冷啟動(dòng)未命中（cold-start miss，或強(qiáng)制未命中，compulsory miss）。

計(jì)算緩存命中率：有 6 次命中和 5 次未命中，那么緩存命中率?54.5%。也可以計(jì)算命中率中除去強(qiáng)制未命中（即忽略頁(yè)的第一次未命中），那么緩存命中率為 81.8%。

但是未來(lái)的訪問(wèn)是無(wú)法知道的，所以無(wú)法為通用操作系統(tǒng)實(shí)現(xiàn)最優(yōu)策略。因此，最優(yōu)策略只能作為比較，知道我們的策略有多接近“完美”。

4.4.3 簡(jiǎn)單策略：FIFO、隨機(jī)

FIFO 命中率只有 36.4%（不包括強(qiáng) 制性未命中為 57.1%）。

任何像 FIFO 或隨機(jī)這樣簡(jiǎn)單的策略都可能會(huì)有一個(gè)共同的問(wèn)題：它可能會(huì)踢出一個(gè)重要的頁(yè)，而這個(gè)頁(yè)馬上要被引用。

4.4.4 利用歷史數(shù)據(jù)：LRU

頁(yè)替換策略可以使用的一個(gè)歷史信息是頻率（frequency）。如果一個(gè)頁(yè)被訪問(wèn)了很多次， 也許它不應(yīng)該被替換，因?yàn)樗@然更有價(jià)值。頁(yè)更常用的屬性是訪問(wèn)的近期性（recency）， 越近被訪問(wèn)過(guò)的頁(yè)，也許再次訪問(wèn)的可能性也就越大。

最不經(jīng)常使用（Least-Frequently-Used， LFU）策略會(huì)替換最不經(jīng)常使用的頁(yè)。同樣，最少最近使用（Least-Recently-Used，LRU） 策略替換最近最少使用的頁(yè)面。

4.4.5 近似 LRU

從計(jì)算開(kāi)銷的角度來(lái)看，近似 LRU 更為可行。這個(gè)想法需要硬件增加一個(gè)使用位（use bit，有時(shí)稱為引用位， reference bit）。

系統(tǒng)的每個(gè)頁(yè)有一個(gè)使用位，存儲(chǔ)在某個(gè)地方（例如，它們可能在每個(gè)進(jìn)程的頁(yè)表中，或者只在某個(gè)數(shù)組中）。每當(dāng)頁(yè)被引用（即讀或?qū)懀r(shí)，硬件將使用位設(shè)置為 1。 但是，硬件不會(huì)清除該位（即將其設(shè)置為 0），這由操作系統(tǒng)負(fù)責(zé)。

有一個(gè)簡(jiǎn)單的實(shí)現(xiàn)近似 LRU方法稱作 時(shí)鐘算法（clock algorithm）?？紤]系統(tǒng)中的所有頁(yè)都放在一個(gè)循環(huán)列表中。時(shí)鐘指針（clock hand）開(kāi)始時(shí)指向某個(gè)特定的頁(yè)（哪個(gè)頁(yè)不重要）。當(dāng)必須進(jìn)行頁(yè)替換時(shí)，操作系統(tǒng)檢查當(dāng)前指向的頁(yè) P 的使用位是 1 還是 0。如果是 1，則意味著頁(yè)面 P 最近被使用， 因此不適合被替換。然后，P 的使用位設(shè)置為 0，時(shí)鐘指針遞增到下一頁(yè)（P + 1）。該算法 一直持續(xù)到找到一個(gè)使用位為 0 的頁(yè)（在最壞的情況下，所有的頁(yè)都已經(jīng)被使用了，那么就將所有頁(yè)的使用位都設(shè)置為 0）。

4.4.6 考慮臟頁(yè)

時(shí)鐘算法的一個(gè)小修改是對(duì)內(nèi)存中的頁(yè)是否被修改的額外考慮。這樣做的原因是：如果頁(yè)已被修改（modified）并因此變臟（dirty），則踢出它就必須將它寫回磁盤，這很昂貴。如果它沒(méi)有被修改（因此是干凈的，clean），踢出就沒(méi)成本。物理幀可以簡(jiǎn)單地重用于其他目的而無(wú)須額外的 I/O。

因此，一些虛擬機(jī)系統(tǒng)更傾向于踢出干凈頁(yè)，而不是臟頁(yè)。 為了支持這種行為，硬件應(yīng)該包括一個(gè)修改位（modified bit，又名臟位，dirty bit）。每次 寫入頁(yè)時(shí)都會(huì)設(shè)置此位，因此可以將其合并到頁(yè)面替換算法中。例如，時(shí)鐘算法可以被改變， 以掃描既未使用又干凈的頁(yè)先踢出。無(wú)法找到這種頁(yè)時(shí)，再查找臟的未使用頁(yè)面。

4.5 交換何時(shí)真正發(fā)生

為了保證有少量的空閑內(nèi)存，大多數(shù)操作系統(tǒng)會(huì)設(shè)置高水位線（High Watermark，HW） 和低水位線（Low Watermark，LW），來(lái)幫助決定何時(shí)從內(nèi)存中清除頁(yè)。原理 -->

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

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

文章標(biāo)題：內(nèi)存分頁(yè)、交換空間-創(chuàng)新互聯(lián)
本文URL：http://jinyejixie.com/article26/ccjjjg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信公眾號(hào)、商城網(wǎng)站、Google、關(guān)鍵詞優(yōu)化、定制網(wǎng)站、自適應(yīng)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)