目錄

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

1. 分頁

1.1 地址轉(zhuǎn)換

1.2 頁表存在哪里

1.3 列表中究竟有什么

1.4?分頁的優(yōu)缺點

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

2.1?TLB 的基本算法

2.2 誰來處理 TLB 未命中

2.2.1 硬件處理

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

2.3?TLB 的內(nèi)容

2.4?上下文切換時對 TLB 的處理

2.4.1?清空 TLB

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

2.5?TLB 替換策略

3. 較小的頁表

3.1 簡單的解決方案：更大的頁

3.2 混合方法：分頁和分段

3.2.1 雜合方式的原理

3.2.2 雜合方式存在的問題

3.3 多級頁表

3.3.1 多級頁表的原理

3.3.2 多級頁表的成本

3.3.3 兩級頁表示例

3.4 反向頁表

3.5 將頁表交換到磁盤

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

4.1 交換空間

4.2 存在位

4.3 頁錯誤

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

4.4.1 緩存管理

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

4.4.3 簡單策略：FIFO、隨機

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

4.4.5 近似 LRU

4.4.6 考慮臟頁

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

---

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

1. 分頁

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

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

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

1.1 地址轉(zhuǎn)換

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

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

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

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

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

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

1.2 頁表存在哪里

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

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

1.3 列表中究竟有什么

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

每個 PTE 包含許多不同的位:

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

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

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

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

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

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

1.4?分頁的優(yōu)缺點

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

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

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

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

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

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

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

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

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

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

2.1?TLB 的基本算法

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

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

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

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

2.2 誰來處理 TLB 未命中 2.2.1 硬件處理

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

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

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

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

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

2.3?TLB 的內(nèi)容

VPN ｜ PFN ｜ 其他位

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

2.4?上下文切換時對 TLB 的處理

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

這個問題有一些可能的解決方案。

2.4.1?清空 TLB

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

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

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

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

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

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

2.5?TLB 替換策略

緩存替換（cache replacement）-->向 TLB 中插入新項時，會替換（replace）一個舊項，這樣問題就來了：應(yīng)該替換那一個？

（1）替換最近最少使用（least-recently-used，LRU）的項。

（2）另一 種典型策略就是隨機（random）策略，即隨機選擇一項換出去。

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

3. 較小的頁表

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

3.1 簡單的解決方案：更大的頁

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

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

一種簡單的減小頁表大小的方法：使用更大的頁

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

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

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

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

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

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

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

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

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

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

3.2.2 雜合方式存在的問題

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

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

3.3 多級頁表 3.3.1 多級頁表的原理

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

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

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

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

在一個簡單的兩級頁表中，頁目錄為每頁頁表包含了一項。它由多個頁目錄項（Page Directory Entries，PDE）組成。PDE 至少擁有有效位（valid bit）和頁幀號（page frame number， PFN），類似于 PTE。如果 PDE 項的有效位為1，則意味著該項指向的頁表（通過 PFN）中至少有一頁是有效的，即在該 PDE 所 指向的頁中，至少一個 PTE。如果 PDE 項無效，則 PDE 的其余部分沒有定義。?

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

3.3.2 多級頁表的成本

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

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

3.3.3 兩級頁表示例

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

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

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

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

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

這個例子中的頁表很小：256 個項，分布在 16 個頁上。頁目錄需要為頁表的每頁提供一個項，所以需要 4 位 VPN 來索引目錄。我們使用 VPN 的前 4 位，如下所示：

PDIndex?頁目錄索引

PTIndex?頁表索引

PDE 頁目錄項

PTE 頁表項

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

3.4 反向頁表

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

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

3.5 將頁表交換到磁盤

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

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

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

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

4.1 交換空間

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

4.2 存在位

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

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

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

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

4.3 頁錯誤

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

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

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

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

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

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

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

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

4.4.1 緩存管理

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

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

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

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

如果不得不踢出一些頁，為什么不踢出在最遠(yuǎn)將來才會訪問的頁呢？

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

前 3 個訪問是未命中，因為緩存開始是空的。這種未命中有時也稱作冷啟動未命中（cold-start miss，或強制未命中，compulsory miss）。

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

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

4.4.3 簡單策略：FIFO、隨機

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

任何像 FIFO 或隨機這樣簡單的策略都可能會有一個共同的問題：它可能會踢出一個重要的頁，而這個頁馬上要被引用。

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

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

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

4.4.5 近似 LRU

從計算開銷的角度來看，近似 LRU 更為可行。這個想法需要硬件增加一個使用位（use bit，有時稱為引用位， reference bit）。

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

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

4.4.6 考慮臟頁

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

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

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

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

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

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

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

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

廣告

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