主存(RAM) 是一件非常重要的資源，必須要認(rèn)真對(duì)待內(nèi)存。雖然目前大多數(shù)內(nèi)存的增長速度要比 IBM 7094 要快的多，但是，程序大小的增長要比內(nèi)存的增長還快很多。不管存儲(chǔ)器有多大，程序大小的增長速度比內(nèi)存容量的增長速度要快的多。下面我們就來探討一下操作系統(tǒng)是如何創(chuàng)建內(nèi)存并管理他們的。

經(jīng)過多年的研究發(fā)現(xiàn)，科學(xué)家提出了一種 分層存儲(chǔ)器體系(memory hierarchy)，下面是分層體系的分類

位于頂層的存儲(chǔ)器速度最快，但是相對(duì)容量最小，成本非常高。層級(jí)結(jié)構(gòu)向下，其訪問速度會(huì)變慢，但是容量會(huì)變大，相對(duì)造價(jià)也就越便宜。（所以個(gè)人感覺相對(duì)存儲(chǔ)容量來說，訪問速度是更重要的）

操作系統(tǒng)中管理內(nèi)存層次結(jié)構(gòu)的部分稱為內(nèi)存管理器(memory manager)，它的主要工作是有效的管理內(nèi)存，記錄哪些內(nèi)存是正在使用的，在進(jìn)程需要時(shí)分配內(nèi)存以及在進(jìn)程完成時(shí)回收內(nèi)存。所有現(xiàn)代操作系統(tǒng)都提供內(nèi)存管理。

下面我們會(huì)對(duì)不同的內(nèi)存管理模型進(jìn)行探討，從簡單到復(fù)雜，由于最低級(jí)別的緩存是由硬件進(jìn)行管理的，所以我們主要探討主存模型和如何對(duì)主存進(jìn)行管理。

最簡單的存儲(chǔ)器抽象是無存儲(chǔ)器。早期大型計(jì)算機(jī)（20 世紀(jì) 60 年代之前），小型計(jì)算機(jī)（20 世紀(jì) 70 年代之前）和個(gè)人計(jì)算機(jī)（20 世紀(jì) 80 年代之前）都沒有存儲(chǔ)器抽象。每一個(gè)程序都直接訪問物理內(nèi)存。當(dāng)一個(gè)程序執(zhí)行如下命令：

計(jì)算機(jī)會(huì)把位置為 1000 的物理內(nèi)存中的內(nèi)容移到 REGISTER1 中。因此呈現(xiàn)給程序員的內(nèi)存模型就是物理內(nèi)存，內(nèi)存地址從 0 開始到內(nèi)存地址的最大值中，每個(gè)地址中都會(huì)包含一個(gè) 8 位位數(shù)的內(nèi)存單元。

所以這種情況下的計(jì)算機(jī)不可能會(huì)有兩個(gè)應(yīng)用程序同時(shí)在內(nèi)存中。如果第一個(gè)程序向內(nèi)存地址 2000 的這個(gè)位置寫入了一個(gè)值，那么此值將會(huì)替換第二個(gè)程序 2000 位置上的值，所以，同時(shí)運(yùn)行兩個(gè)應(yīng)用程序是行不通的，兩個(gè)程序會(huì)立刻崩潰。

不過即使存儲(chǔ)器模型就是物理內(nèi)存，還是存在一些可變體的。下面展示了三種變體

在上圖 a 中，操作系統(tǒng)位于 RAM(Random Access Memory) 的底部，或像是圖 b 一樣位于 ROM(Read-Only Memory) 頂部；而在圖 c 中，設(shè)備驅(qū)動(dòng)程序位于頂端的 ROM 中，而操作系統(tǒng)位于底部的 RAM 中。圖 a 的模型以前用在大型機(jī)和小型機(jī)上，但現(xiàn)在已經(jīng)很少使用了；圖 b 中的模型一般用于掌上電腦或者是嵌入式系統(tǒng)中。第三種模型就應(yīng)用在早期個(gè)人計(jì)算機(jī)中了。ROM 系統(tǒng)中的一部分成為 BIOS (Basic Input Output System)。模型 a 和 c 的缺點(diǎn)是用戶程序中的錯(cuò)誤可能會(huì)破壞操作系統(tǒng)，可能會(huì)導(dǎo)致災(zāi)難性的后果。

按照這種方式組織系統(tǒng)時(shí)，通常同一個(gè)時(shí)刻只能有一個(gè)進(jìn)程正在運(yùn)行。一旦用戶鍵入了一個(gè)命令，操作系統(tǒng)就把需要的程序從磁盤復(fù)制到內(nèi)存中并執(zhí)行；當(dāng)進(jìn)程運(yùn)行結(jié)束后，操作系統(tǒng)在用戶終端顯示提示符并等待新的命令。收到新的命令后，它把新的程序裝入內(nèi)存，覆蓋前一個(gè)程序。

在沒有存儲(chǔ)器抽象的系統(tǒng)中實(shí)現(xiàn)并行性一種方式是使用多線程來編程。由于同一進(jìn)程中的多線程內(nèi)部共享同一內(nèi)存映像，那么實(shí)現(xiàn)并行也就不是問題了。但是這種方式卻并沒有被廣泛采納，因?yàn)槿藗兺ǔＯＭ軌蛟谕粫r(shí)間內(nèi)運(yùn)行沒有關(guān)聯(lián)的程序，而這正是線程抽象所不能提供的。

但是，即便沒有存儲(chǔ)器抽象，同時(shí)運(yùn)行多個(gè)程序也是有可能的。操作系統(tǒng)只需要把當(dāng)前內(nèi)存中所有內(nèi)容保存到磁盤文件中，然后再把程序讀入內(nèi)存即可。只要某一時(shí)刻內(nèi)存只有一個(gè)程序在運(yùn)行，就不會(huì)有沖突的情況發(fā)生。

在額外特殊硬件的幫助下，即使沒有交換功能，也可以并行的運(yùn)行多個(gè)程序。IBM 360 的早期模型就是這樣解決的

System/360是 IBM 在1964年4月7日，推出的劃時(shí)代的大型電腦，這一系列是世界上首個(gè)指令集可兼容計(jì)算機(jī)。

在 IBM 360 中，內(nèi)存被劃分為 2KB 的區(qū)域塊，每塊區(qū)域被分配一個(gè) 4 位的保護(hù)鍵，保護(hù)鍵存儲(chǔ)在 CPU 的特殊寄存器(SFR)中。一個(gè)內(nèi)存為 1 MB 的機(jī)器只需要 512 個(gè)這樣的 4 位寄存器，容量總共為 256 字節(jié) (這個(gè)會(huì)算吧) PSW(Program Status Word, 程序狀態(tài)字) 中有一個(gè) 4 位碼。一個(gè)運(yùn)行中的進(jìn)程如果訪問鍵與其 PSW 中保存的碼不同，360 硬件會(huì)捕獲這種情況。因?yàn)橹挥胁僮飨到y(tǒng)可以修改保護(hù)鍵，這樣就可以防止進(jìn)程之間、用戶進(jìn)程和操作系統(tǒng)之間的干擾。

這種解決方式是有一個(gè)缺陷。如下所示，假設(shè)有兩個(gè)程序，每個(gè)大小各為 16 KB

從圖上可以看出，這是兩個(gè)不同的 16KB 程序的裝載過程，a 程序首先會(huì)跳轉(zhuǎn)到地址 24，那里是一條 MOV 指令，然而 b 程序會(huì)首先跳轉(zhuǎn)到地址 28，地址 28 是一條 CMP 指令。這是兩個(gè)程序被先后加載到內(nèi)存中的情況，假如這兩個(gè)程序被同時(shí)加載到內(nèi)存中并且從 0 地址處開始執(zhí)行，內(nèi)存的狀態(tài)就如上面 c 圖所示，程序裝載完成開始運(yùn)行，第一個(gè)程序首先從 0 地址處開始運(yùn)行，執(zhí)行 JMP 24 指令，然后依次執(zhí)行后面的指令（許多指令沒有畫出），一段時(shí)間后第一個(gè)程序執(zhí)行完畢，然后開始執(zhí)行第二個(gè)程序。第二個(gè)程序的第一條指令是 28，這條指令會(huì)使程序跳轉(zhuǎn)到第一個(gè)程序的 ADD 處，而不是事先設(shè)定好的跳轉(zhuǎn)指令 CMP，由于這種不正確訪問，可能會(huì)造成程序崩潰。

上面兩個(gè)程序的執(zhí)行過程中有一個(gè)核心問題，那就是都引用了絕對(duì)物理地址，這不是我們想要看到的。我們想要的是每一個(gè)程序都會(huì)引用一個(gè)私有的本地地址。IBM 360 在第二個(gè)程序裝載到內(nèi)存中的時(shí)候會(huì)使用一種稱為 靜態(tài)重定位(static relocation) 的技術(shù)來修改它。它的工作流程如下：當(dāng)一個(gè)程序被加載到 16384 地址時(shí)，常數(shù) 16384 被加到每一個(gè)程序地址上（所以 JMP 28會(huì)變?yōu)镴MP 16412 ）。雖然這個(gè)機(jī)制在不出錯(cuò)誤的情況下是可行的，但這不是一種通用的解決辦法，同時(shí)會(huì)減慢裝載速度。更近一步來講，它需要所有可執(zhí)行程序中的額外信息，以指示哪些包含（可重定位）地址，哪些不包含（可重定位）地址。畢竟，上圖 b 中的 JMP 28 可以被重定向（被修改），而類似 MOV REGISTER1,28 會(huì)把數(shù)字 28 移到 REGISTER 中則不會(huì)重定向。所以，裝載器(loader)需要一定的能力來辨別地址和常數(shù)。

把物理內(nèi)存暴露給進(jìn)程會(huì)有幾個(gè)主要的缺點(diǎn)：第一個(gè)問題是，如果用戶程序可以尋址內(nèi)存的每個(gè)字節(jié)，它們就可以很容易的破壞操作系統(tǒng)，從而使系統(tǒng)停止運(yùn)行（除非使用 IBM 360 那種 lock-and-key 模式或者特殊的硬件進(jìn)行保護(hù)）。即使在只有一個(gè)用戶進(jìn)程運(yùn)行的情況下，這個(gè)問題也存在。

第二點(diǎn)是，這種模型想要運(yùn)行多個(gè)程序是很困難的（如果只有一個(gè) CPU 那就是順序執(zhí)行）。在個(gè)人計(jì)算機(jī)上，一般會(huì)打開很多應(yīng)用程序，比如輸入法、電子郵件、瀏覽器，這些進(jìn)程在不同時(shí)刻會(huì)有一個(gè)進(jìn)程正在運(yùn)行，其他應(yīng)用程序可以通過鼠標(biāo)來喚醒。在系統(tǒng)中沒有物理內(nèi)存的情況下很難實(shí)現(xiàn)。

如果要使多個(gè)應(yīng)用程序同時(shí)運(yùn)行在內(nèi)存中，必須要解決兩個(gè)問題：保護(hù)和 重定位。我們來看 IBM 360 是如何解決的：第一種解決方式是用保護(hù)密鑰標(biāo)記內(nèi)存塊，并將執(zhí)行過程的密鑰與提取的每個(gè)存儲(chǔ)字的密鑰進(jìn)行比較。這種方式只能解決第一種問題（破壞操作系統(tǒng)），但是不能解決多進(jìn)程在內(nèi)存中同時(shí)運(yùn)行的問題。

還有一種更好的方式是創(chuàng)造一個(gè)存儲(chǔ)器抽象：地址空間(the address space)。就像進(jìn)程的概念創(chuàng)建了一種抽象的 CPU 來運(yùn)行程序，地址空間也創(chuàng)建了一種抽象內(nèi)存供程序使用。地址空間是進(jìn)程可以用來尋址內(nèi)存的地址集。每個(gè)進(jìn)程都有它自己的地址空間，獨(dú)立于其他進(jìn)程的地址空間，但是某些進(jìn)程會(huì)希望可以共享地址空間。

最簡單的辦法是使用動(dòng)態(tài)重定位(dynamic relocation)技術(shù)，它就是通過一種簡單的方式將每個(gè)進(jìn)程的地址空間映射到物理內(nèi)存的不同區(qū)域。從 CDC 6600(世界上最早的超級(jí)計(jì)算機(jī))到 Intel 8088(原始 IBM PC 的核心)所使用的經(jīng)典辦法是給每個(gè) CPU 配置兩個(gè)特殊硬件寄存器，通常叫做基址寄存器(basic register)和變址寄存器(limit register)。當(dāng)使用基址寄存器和變址寄存器時(shí)，程序會(huì)裝載到內(nèi)存中的連續(xù)位置并且在裝載期間無需重定位。當(dāng)一個(gè)進(jìn)程運(yùn)行時(shí)，程序的起始物理地址裝載到基址寄存器中，程序的長度則裝載到變址寄存器中。在上圖 c 中，當(dāng)一個(gè)程序運(yùn)行時(shí)，裝載到這些硬件寄存器中的基址和變址寄存器的值分別是 0 和 16384。當(dāng)?shù)诙€(gè)程序運(yùn)行時(shí)，這些值分別是 16384 和 32768。如果第三個(gè) 16 KB 的程序直接裝載到第二個(gè)程序的地址之上并且運(yùn)行，這時(shí)基址寄存器和變址寄存器的值會(huì)是 32768 和 16384。那么我們可以總結(jié)下

• 基址寄存器：存儲(chǔ)數(shù)據(jù)內(nèi)存的起始位置
• 變址寄存器：存儲(chǔ)應(yīng)用程序的長度。

每當(dāng)進(jìn)程引用內(nèi)存以獲取指令或讀取、寫入數(shù)據(jù)時(shí)，CPU 都會(huì)自動(dòng)將基址值添加到進(jìn)程生成的地址中，然后再將其發(fā)送到內(nèi)存總線上。同時(shí)，它檢查程序提供的地址是否大于或等于變址寄存器 中的值。如果程序提供的地址要超過變址寄存器的范圍，那么會(huì)產(chǎn)生錯(cuò)誤并中止訪問。這樣，對(duì)上圖 c 中執(zhí)行 JMP 28 這條指令后，硬件會(huì)把它解釋為 JMP 16412，所以程序能夠跳到 CMP 指令，過程如下

使用基址寄存器和變址寄存器是給每個(gè)進(jìn)程提供私有地址空間的一種非常好的方法，因?yàn)槊總€(gè)內(nèi)存地址在送到內(nèi)存之前，都會(huì)先加上基址寄存器的內(nèi)容。在很多實(shí)際系統(tǒng)中，對(duì)基址寄存器和變址寄存器都會(huì)以一定的方式加以保護(hù)，使得只有操作系統(tǒng)可以修改它們。在 CDC 6600 中就提供了對(duì)這些寄存器的保護(hù)，但在 Intel 8088 中則沒有，甚至沒有變址寄存器。但是，Intel 8088 提供了許多基址寄存器，使程序的代碼和數(shù)據(jù)可以被獨(dú)立的重定位，但是對(duì)于超出范圍的內(nèi)存引用沒有提供保護(hù)。

所以你可以知道使用基址寄存器和變址寄存器的缺點(diǎn)，在每次訪問內(nèi)存時(shí)，都會(huì)進(jìn)行 ADD 和 CMP 運(yùn)算。CMP 指令可以執(zhí)行的很快，但是加法就會(huì)相對(duì)慢一些，除非使用特殊的加法電路，否則加法因進(jìn)位傳播時(shí)間而變慢。

如果計(jì)算機(jī)的物理內(nèi)存足夠大來容納所有的進(jìn)程，那么之前提及的方案或多或少是可行的。但是實(shí)際上，所有進(jìn)程需要的 RAM 總?cè)萘恳h(yuǎn)遠(yuǎn)高于內(nèi)存的容量。在 Windows、OS X、或者 Linux 系統(tǒng)中，在計(jì)算機(jī)完成啟動(dòng)（Boot）后，大約有 50 - 100 個(gè)進(jìn)程隨之啟動(dòng)。例如，當(dāng)一個(gè) Windows 應(yīng)用程序被安裝后，它通常會(huì)發(fā)出命令，以便在后續(xù)系統(tǒng)啟動(dòng)時(shí)，將啟動(dòng)一個(gè)進(jìn)程，這個(gè)進(jìn)程除了檢查應(yīng)用程序的更新外不做任何操作。一個(gè)簡單的應(yīng)用程序可能會(huì)占用 5 - 10MB 的內(nèi)存。其他后臺(tái)進(jìn)程會(huì)檢查電子郵件、網(wǎng)絡(luò)連接以及許多其他諸如此類的任務(wù)。這一切都會(huì)發(fā)生在第一個(gè)用戶啟動(dòng)之前。如今，像是 Photoshop 這樣的重要用戶應(yīng)用程序僅僅需要 500 MB 來啟動(dòng)，但是一旦它們開始處理數(shù)據(jù)就需要許多 GB 來處理。從結(jié)果上來看，將所有進(jìn)程始終保持在內(nèi)存中需要大量內(nèi)存，如果內(nèi)存不足，則無法完成。

所以針對(duì)上面內(nèi)存不足的問題，提出了兩種處理方式：最簡單的一種方式就是交換(swapping)技術(shù)，即把一個(gè)進(jìn)程完整的調(diào)入內(nèi)存，然后再內(nèi)存中運(yùn)行一段時(shí)間，再把它放回磁盤?？臻e進(jìn)程會(huì)存儲(chǔ)在磁盤中，所以這些進(jìn)程在沒有運(yùn)行時(shí)不會(huì)占用太多內(nèi)存。另外一種策略叫做虛擬內(nèi)存(virtual memory)，虛擬內(nèi)存技術(shù)能夠允許應(yīng)用程序部分的運(yùn)行在內(nèi)存中。下面我們首先先探討一下交換

下面是一個(gè)交換過程

剛開始的時(shí)候，只有進(jìn)程 A 在內(nèi)存中，然后從創(chuàng)建進(jìn)程 B 和進(jìn)程 C 或者從磁盤中把它們換入內(nèi)存，然后在圖 d 中，A 被換出內(nèi)存到磁盤中，最后 A 重新進(jìn)來。因?yàn)閳D g 中的進(jìn)程 A 現(xiàn)在到了不同的位置，所以在裝載過程中需要被重新定位，或者在交換程序時(shí)通過軟件來執(zhí)行；或者在程序執(zhí)行期間通過硬件來重定位?；芳拇嫫骱妥冎芳拇嫫骶瓦m用于這種情況。

交換在內(nèi)存創(chuàng)建了多個(gè) 空閑區(qū)(hole)，內(nèi)存會(huì)把所有的空閑區(qū)盡可能向下移動(dòng)合并成為一個(gè)大的空閑區(qū)。這項(xiàng)技術(shù)稱為內(nèi)存緊縮(memory compaction)。但是這項(xiàng)技術(shù)通常不會(huì)使用，因?yàn)檫@項(xiàng)技術(shù)回消耗很多 CPU 時(shí)間。例如，在一個(gè) 16GB 內(nèi)存的機(jī)器上每 8ns 復(fù)制 8 字節(jié)，它緊縮全部的內(nèi)存大約要花費(fèi) 16s。

有一個(gè)值得注意的問題是，當(dāng)進(jìn)程被創(chuàng)建或者換入內(nèi)存時(shí)應(yīng)該為它分配多大的內(nèi)存。如果進(jìn)程被創(chuàng)建后它的大小是固定的并且不再改變，那么分配策略就比較簡單：操作系統(tǒng)會(huì)準(zhǔn)確的按其需要的大小進(jìn)行分配。

但是如果進(jìn)程的 data segment 能夠自動(dòng)增長，例如，通過動(dòng)態(tài)分配堆中的內(nèi)存，肯定會(huì)出現(xiàn)問題。這里還是再提一下什么是 data segment 吧。從邏輯層面操作系統(tǒng)把數(shù)據(jù)分成不同的段(不同的區(qū)域)來存儲(chǔ)：

• 代碼段（codesegment/textsegment）：

又稱文本段，用來存放指令，運(yùn)行代碼的一塊內(nèi)存空間

此空間大小在代碼運(yùn)行前就已經(jīng)確定

內(nèi)存空間一般屬于只讀，某些架構(gòu)的代碼也允許可寫

在代碼段中，也有可能包含一些只讀的常數(shù)變量，例如字符串常量等。

• 數(shù)據(jù)段（datasegment）：

可讀可寫

存儲(chǔ)初始化的全局變量和初始化的 static 變量

數(shù)據(jù)段中數(shù)據(jù)的生存期是隨程序持續(xù)性（隨進(jìn)程持續(xù)性）隨進(jìn)程持續(xù)性：進(jìn)程創(chuàng)建就存在，進(jìn)程死亡就消失

• bss段（bsssegment）：

可讀可寫

存儲(chǔ)未初始化的全局變量和未初始化的 static 變量

bss 段中數(shù)據(jù)的生存期隨進(jìn)程持續(xù)性

bss 段中的數(shù)據(jù)一般默認(rèn)為0

• rodata段：

只讀數(shù)據(jù)比如 printf 語句中的格式字符串和開關(guān)語句的跳轉(zhuǎn)表。也就是常量區(qū)。例如，全局作用域中的 const int ival = 10，ival 存放在 .rodata 段；再如，函數(shù)局部作用域中的 printf('Hello world %d\n', c); 語句中的格式字符串 'Hello world %d\n'，也存放在 .rodata 段。

• 棧（stack）：

可讀可寫

存儲(chǔ)的是函數(shù)或代碼中的局部變量(非 static 變量)

棧的生存期隨代碼塊持續(xù)性，代碼塊運(yùn)行就給你分配空間，代碼塊結(jié)束，就自動(dòng)回收空間

• 堆（heap）：

可讀可寫

存儲(chǔ)的是程序運(yùn)行期間動(dòng)態(tài)分配的 malloc/realloc 的空間

堆的生存期隨進(jìn)程持續(xù)性，從 malloc/realloc 到 free 一直存在

下面是我們用 Borland C++ 編譯過后的結(jié)果

_TEXT   segment dword public use32 'CODE'_TEXT   ends_DATA   segment dword public use32 'DATA'_DATA   ends_BSS    segment dword public use32 'BSS'_BSS    ends

段定義( segment ) 是用來區(qū)分或者劃分范圍區(qū)域的意思。匯編語言的 segment 偽指令表示段定義的起始，ends 偽指令表示段定義的結(jié)束。段定義是一段連續(xù)的內(nèi)存空間

所以內(nèi)存針對(duì)自動(dòng)增長的區(qū)域，會(huì)有三種處理方式

• 如果一個(gè)進(jìn)程與空閑區(qū)相鄰，那么可把該空閑區(qū)分配給進(jìn)程以供其增大。
• 如果進(jìn)程相鄰的是另一個(gè)進(jìn)程，就會(huì)有兩種處理方式：要么把需要增長的進(jìn)程移動(dòng)到一個(gè)內(nèi)存中空閑區(qū)足夠大的區(qū)域，要么把一個(gè)或多個(gè)進(jìn)程交換出去，已變成生成一個(gè)大的空閑區(qū)。
• 如果一個(gè)進(jìn)程在內(nèi)存中不能增長，而且磁盤上的交換區(qū)也滿了，那么這個(gè)進(jìn)程只有掛起一些空閑空間（或者可以結(jié)束該進(jìn)程）

上面只針對(duì)單個(gè)或者一小部分需要增長的進(jìn)程采用的方式，如果大部分進(jìn)程都要在運(yùn)行時(shí)增長，為了減少因內(nèi)存區(qū)域不夠而引起的進(jìn)程交換和移動(dòng)所產(chǎn)生的開銷，一種可用的方法是，在換入或移動(dòng)進(jìn)程時(shí)為它分配一些額外的內(nèi)存。然而，當(dāng)進(jìn)程被換出到磁盤上時(shí)，應(yīng)該只交換實(shí)際上使用的內(nèi)存，將額外的內(nèi)存交換也是一種浪費(fèi)，下面是一種為兩個(gè)進(jìn)程分配了增長空間的內(nèi)存配置。

如果進(jìn)程有兩個(gè)可增長的段，例如，供變量動(dòng)態(tài)分配和釋放的作為堆(全局變量)使用的一個(gè)數(shù)據(jù)段(data segment)，以及存放局部變量與返回地址的一個(gè)堆棧段(stack segment)，就如圖 b 所示。在圖中可以看到所示進(jìn)程的堆棧段在進(jìn)程所占內(nèi)存的頂端向下增長，緊接著在程序段后的數(shù)據(jù)段向上增長。當(dāng)增長預(yù)留的內(nèi)存區(qū)域不夠了，處理方式就如上面的流程圖(data segment 自動(dòng)增長的三種處理方式)一樣了。

在進(jìn)行內(nèi)存動(dòng)態(tài)分配時(shí)，操作系統(tǒng)必須對(duì)其進(jìn)行管理。大致上說，有兩種監(jiān)控內(nèi)存使用的方式

• 位圖(bitmap)
• 空閑列表(free lists)

下面我們就來探討一下這兩種使用方式

使用位圖方法時(shí)，內(nèi)存可能被劃分為小到幾個(gè)字或大到幾千字節(jié)的分配單元。每個(gè)分配單元對(duì)應(yīng)于位圖中的一位，0 表示空閑， 1 表示占用（或者相反）。一塊內(nèi)存區(qū)域和其對(duì)應(yīng)的位圖如下

圖 a 表示一段有 5 個(gè)進(jìn)程和 3 個(gè)空閑區(qū)的內(nèi)存，刻度為內(nèi)存分配單元，陰影區(qū)表示空閑（在位圖中用 0 表示）；圖 b 表示對(duì)應(yīng)的位圖；圖 c 表示用鏈表表示同樣的信息

分配單元的大小是一個(gè)重要的設(shè)計(jì)因素，分配單位越小，位圖越大。然而，即使只有 4 字節(jié)的分配單元，32 位的內(nèi)存也僅僅只需要位圖中的 1 位。32n 位的內(nèi)存需要 n 位的位圖，所以1 個(gè)位圖只占用了 1/32 的內(nèi)存。如果選擇更大的內(nèi)存單元，位圖應(yīng)該要更小。如果進(jìn)程的大小不是分配單元的整數(shù)倍，那么在最后一個(gè)分配單元中會(huì)有大量的內(nèi)存被浪費(fèi)。

位圖提供了一種簡單的方法在固定大小的內(nèi)存中跟蹤內(nèi)存的使用情況，因?yàn)?strong>位圖的大小取決于內(nèi)存和分配單元的大小。這種方法有一個(gè)問題是，當(dāng)決定為把具有 k 個(gè)分配單元的進(jìn)程放入內(nèi)存時(shí)，內(nèi)容管理器(memory manager) 必須搜索位圖，在位圖中找出能夠運(yùn)行 k 個(gè)連續(xù) 0 位的串。在位圖中找出制定長度的連續(xù) 0 串是一個(gè)很耗時(shí)的操作，這是位圖的缺點(diǎn)。（可以簡單理解為在雜亂無章的數(shù)組中，找出具有一大長串空閑的數(shù)組單元）

另一種記錄內(nèi)存使用情況的方法是，維護(hù)一個(gè)記錄已分配內(nèi)存段和空閑內(nèi)存段的鏈表，段會(huì)包含進(jìn)程或者是兩個(gè)進(jìn)程的空閑區(qū)域?？捎蒙厦娴膱D c 來表示內(nèi)存的使用情況。鏈表中的每一項(xiàng)都可以代表一個(gè) 空閑區(qū)(H) 或者是進(jìn)程(P)的起始標(biāo)志，長度和下一個(gè)鏈表項(xiàng)的位置。

在這個(gè)例子中，段鏈表(segment list)是按照地址排序的。這種方式的優(yōu)點(diǎn)是，當(dāng)進(jìn)程終止或被交換時(shí)，更新列表很簡單。一個(gè)終止進(jìn)程通常有兩個(gè)鄰居（除了內(nèi)存的頂部和底部外）。相鄰的可能是進(jìn)程也可能是空閑區(qū)，它們有四種組合方式。

當(dāng)按照地址順序在鏈表中存放進(jìn)程和空閑區(qū)時(shí)，有幾種算法可以為創(chuàng)建的進(jìn)程（或者從磁盤中換入的進(jìn)程）分配內(nèi)存。我們先假設(shè)內(nèi)存管理器知道應(yīng)該分配多少內(nèi)存，最簡單的算法是使用 首次適配(first fit)。內(nèi)存管理器會(huì)沿著段列表進(jìn)行掃描，直到找個(gè)一個(gè)足夠大的空閑區(qū)為止。除非空閑區(qū)大小和要分配的空間大小一樣，否則將空閑區(qū)分為兩部分，一部分供進(jìn)程使用；一部分生成新的空閑區(qū)。首次適配算法是一種速度很快的算法，因?yàn)樗鼤?huì)盡可能的搜索鏈表。

首次適配的一個(gè)小的變體是 下次適配(next fit)。它和首次匹配的工作方式相同，只有一個(gè)不同之處那就是下次適配在每次找到合適的空閑區(qū)時(shí)就會(huì)記錄當(dāng)時(shí)的位置，以便下次尋找空閑區(qū)時(shí)從上次結(jié)束的地方開始搜索，而不是像首次匹配算法那樣每次都會(huì)從頭開始搜索。Bays(1997) 證明了下次算法的性能略低于首次匹配算法。

另外一個(gè)著名的并且廣泛使用的算法是 最佳適配(best fit)。最佳適配會(huì)從頭到尾尋找整個(gè)鏈表，找出能夠容納進(jìn)程的最小空閑區(qū)。最佳適配算法會(huì)試圖找出最接近實(shí)際需要的空閑區(qū)，以最好的匹配請(qǐng)求和可用空閑區(qū)，而不是先一次拆分一個(gè)以后可能會(huì)用到的大的空閑區(qū)。比如現(xiàn)在我們需要一個(gè)大小為 2 的塊，那么首次匹配算法會(huì)把這個(gè)塊分配在位置 5 的空閑區(qū)，而最佳適配算法會(huì)把該塊分配在位置為 18 的空閑區(qū)，如下

那么最佳適配算法的性能如何呢？最佳適配會(huì)遍歷整個(gè)鏈表，所以最佳適配算法的性能要比首次匹配算法差。但是令人想不到的是，最佳適配算法要比首次匹配和下次匹配算法浪費(fèi)更多的內(nèi)存，因?yàn)樗鼤?huì)產(chǎn)生大量無用的小緩沖區(qū)，首次匹配算法生成的空閑區(qū)會(huì)更大一些。

最佳適配的空閑區(qū)會(huì)分裂出很多非常小的緩沖區(qū)，為了避免這一問題，可以考慮使用 最差適配(worst fit) 算法。即總是分配最大的內(nèi)存區(qū)域（所以你現(xiàn)在明白為什么最佳適配算法會(huì)分裂出很多小緩沖區(qū)了吧），使新分配的空閑區(qū)比較大從而可以繼續(xù)使用。仿真程序表明最差適配算法也不是一個(gè)好主意。

如果為進(jìn)程和空閑區(qū)維護(hù)各自獨(dú)立的鏈表，那么這四個(gè)算法的速度都能得到提高。這樣，這四種算法的目標(biāo)都是為了檢查空閑區(qū)而不是進(jìn)程。但這種分配速度的提高的一個(gè)不可避免的代價(jià)是增加復(fù)雜度和減慢內(nèi)存釋放速度，因?yàn)楸仨殞⒁粋€(gè)回收的段從進(jìn)程鏈表中刪除并插入空閑鏈表區(qū)。

如果進(jìn)程和空閑區(qū)使用不同的鏈表，那么可以按照大小對(duì)空閑區(qū)鏈表排序，以便提高最佳適配算法的速度。在使用最佳適配算法搜索由小到大排列的空閑區(qū)鏈表時(shí)，只要找到一個(gè)合適的空閑區(qū)，則這個(gè)空閑區(qū)就是能容納這個(gè)作業(yè)的最小空閑區(qū)，因此是最佳匹配。因?yàn)榭臻e區(qū)鏈表以單鏈表形式組織，所以不需要進(jìn)一步搜索?？臻e區(qū)鏈表按大小排序時(shí)，首次適配算法與最佳適配算法一樣快，而下次適配算法在這里毫無意義。

另一種分配算法是 快速適配(quick fit) 算法，它為那些常用大小的空閑區(qū)維護(hù)單獨(dú)的鏈表。例如，有一個(gè) n 項(xiàng)的表，該表的第一項(xiàng)是指向大小為 4 KB 的空閑區(qū)鏈表表頭指針，第二項(xiàng)是指向大小為 8 KB 的空閑區(qū)鏈表表頭指針，第三項(xiàng)是指向大小為 12 KB 的空閑區(qū)鏈表表頭指針，以此類推。比如 21 KB 這樣的空閑區(qū)既可以放在 20 KB 的鏈表中，也可以放在一個(gè)專門存放大小比較特別的空閑區(qū)鏈表中。

快速匹配算法尋找一個(gè)指定代銷的空閑區(qū)也是十分快速的，但它和所有將空閑區(qū)按大小排序的方案一樣，都有一個(gè)共同的缺點(diǎn)，即在一個(gè)進(jìn)程終止或被換出時(shí)，尋找它的相鄰塊并查看是否可以合并的過程都是非常耗時(shí)的。如果不進(jìn)行合并，內(nèi)存將會(huì)很快分裂出大量進(jìn)程無法利用的小空閑區(qū)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

MOV REG, 0

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

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

MOV REG, 24576

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

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

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

當(dāng)程序訪問一個(gè)未映射的頁面，如執(zhí)行指令

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

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

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

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

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

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

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

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

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

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

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

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

修改位(Modified) 和 訪問位(Referenced) 會(huì)跟蹤頁面的使用情況。當(dāng)一個(gè)頁面被寫入時(shí)，硬件會(huì)自動(dòng)的設(shè)置修改位。修改位在頁面重新分配頁框時(shí)很有用。如果一個(gè)頁面已經(jīng)被修改過（即它是 臟 的），則必須把它寫回磁盤。如果一個(gè)頁面沒有被修改過（即它是 干凈的），那么重新分配時(shí)這個(gè)頁框會(huì)被直接丟棄，因?yàn)榇疟P上的副本仍然是有效的。這個(gè)位有時(shí)也叫做 臟位(dirty bit)，因?yàn)樗从沉隧撁娴臓顟B(tài)。

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

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

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

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

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

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

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

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

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

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

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

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

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

什么是 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)部寄存器，并被編碼到指令中；指令需要一個(gè)存儲(chǔ)位置來將單個(gè)寄存器存儲(chǔ)在存儲(chǔ)位置中。沒有操作數(shù)的指令也是 1-byte 指令。

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

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

例如 MVI B, 26 H、IN 56 H

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

例如 LDA 2050 H、JMP 2085 H

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

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

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

TLB 通常位于 MMU 中，包含少量的表項(xiàng)，每個(gè)表項(xiàng)都記錄了頁面的相關(guān)信息，除了虛擬頁號(hào)外，其他表項(xiàng)都和頁表是一一對(duì)應(yīng)的

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

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

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

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

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

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

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

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

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

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

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

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

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

32 位的虛擬地址被劃分為 10 位的 PT1 域，10 位的 PT2 域，還有 12 位的 Offset 域。因?yàn)槠屏渴?12 位，所以頁面大小是 4KB，公有 2^20 次方個(gè)頁面。

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

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

下面是一個(gè)二級(jí)頁表的工作過程

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

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

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

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

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

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

當(dāng)發(fā)生缺頁異常時(shí)，操作系統(tǒng)會(huì)選擇一個(gè)頁面進(jìn)行換出從而為新進(jìn)來的頁面騰出空間。如果要換出的頁面在內(nèi)存中已經(jīng)被修改，那么必須將其寫到磁盤中以使磁盤副本保持最新狀態(tài)。如果頁面沒有被修改過，并且磁盤中的副本也已經(jīng)是最新的，那么就不需要進(jìn)行重寫。那么就直接使用調(diào)入的頁面覆蓋需要移除的頁面就可以了。

當(dāng)發(fā)生缺頁中斷時(shí)，雖然可以隨機(jī)的選擇一個(gè)頁面進(jìn)行置換，但是如果每次都選擇一個(gè)不常用的頁面會(huì)提升系統(tǒng)的性能。如果一個(gè)經(jīng)常使用的頁面被換出，那么這個(gè)頁面在短時(shí)間內(nèi)又可能被重復(fù)使用，那么就可能會(huì)造成額外的性能開銷。在關(guān)于頁面的主題上有很多頁面置換算法(page replacement algorithms)，這些已經(jīng)從理論上和實(shí)踐上得到了證明。

需要指出的是，頁面置換問題在計(jì)算機(jī)的其他領(lǐng)域中也會(huì)出現(xiàn)。例如，多數(shù)計(jì)算機(jī)把最近使用過的 32 字節(jié)或者 64 字節(jié)的存儲(chǔ)塊保存在一個(gè)或多個(gè)高速緩存中。當(dāng)緩存滿的時(shí)候，一些塊就被選擇和移除。這些塊的移除除了花費(fèi)時(shí)間較短外，這個(gè)問題同頁面置換問題完全一樣。之所以花費(fèi)時(shí)間較短，是因?yàn)閬G掉的高速緩存可以從內(nèi)存中獲取，而內(nèi)存沒有尋找磁道的時(shí)間也不存在旋轉(zhuǎn)延遲。

第二個(gè)例子是 Web 服務(wù)器。服務(wù)器會(huì)在內(nèi)存中緩存一些經(jīng)常使用到的 Web 頁面。然而，當(dāng)緩存滿了并且已經(jīng)引用了新的頁面，那么必須決定退出哪個(gè) Web 頁面。在高速緩存中的 Web 頁面不會(huì)被修改。因此磁盤中的 Web 頁面經(jīng)常是最新的，同樣的考慮也適用在虛擬內(nèi)存中。在虛擬系統(tǒng)中，內(nèi)存中的頁面可能會(huì)修改也可能不會(huì)修改。

下面我們就來探討一下有哪些頁面置換算法。

最優(yōu)的頁面置換算法很容易描述但在實(shí)際情況下很難實(shí)現(xiàn)。它的工作流程如下：在缺頁中斷發(fā)生時(shí)，這些頁面之一將在下一條指令（包含該指令的頁面）上被引用。其他頁面則可能要到 10、100 或者 1000 條指令后才會(huì)被訪問。每個(gè)頁面都可以用在該頁首次被訪問前所要執(zhí)行的指令數(shù)作為標(biāo)記。

最優(yōu)化的頁面算法表明應(yīng)該標(biāo)記最大的頁面。如果一個(gè)頁面在 800 萬條指令內(nèi)不會(huì)被使用，另外一個(gè)頁面在 600 萬條指令內(nèi)不會(huì)被使用，則置換前一個(gè)頁面，從而把需要調(diào)入這個(gè)頁面而發(fā)生的缺頁中斷推遲。計(jì)算機(jī)也像人類一樣，會(huì)把不愿意做的事情盡可能的往后拖。

這個(gè)算法最大的問題時(shí)無法實(shí)現(xiàn)。當(dāng)缺頁中斷發(fā)生時(shí)，操作系統(tǒng)無法知道各個(gè)頁面的下一次將在什么時(shí)候被訪問。這種算法在實(shí)際過程中根本不會(huì)使用。

為了能夠讓操作系統(tǒng)收集頁面使用信息，大部分使用虛擬地址的計(jì)算機(jī)都有兩個(gè)狀態(tài)位，R 和 M，來和每個(gè)頁面進(jìn)行關(guān)聯(lián)。每當(dāng)引用頁面（讀入或?qū)懭耄r(shí)都設(shè)置 R，寫入（即修改）頁面時(shí)設(shè)置 M，這些位包含在每個(gè)頁表項(xiàng)中，就像下面所示

因?yàn)槊看卧L問時(shí)都會(huì)更新這些位，因此由硬件來設(shè)置它們非常重要。一旦某個(gè)位被設(shè)置為 1，就會(huì)一直保持 1 直到操作系統(tǒng)下次來修改此位。

如果硬件沒有這些位，那么可以使用操作系統(tǒng)的缺頁中斷和時(shí)鐘中斷機(jī)制來進(jìn)行模擬。當(dāng)啟動(dòng)一個(gè)進(jìn)程時(shí)，將其所有的頁面都標(biāo)記為不在內(nèi)存；一旦訪問任何一個(gè)頁面就會(huì)引發(fā)一次缺頁中斷，此時(shí)操作系統(tǒng)就可以設(shè)置 R 位(在它的內(nèi)部表中)，修改頁表項(xiàng)使其指向正確的頁面，并設(shè)置為 READ ONLY 模式，然后重新啟動(dòng)引起缺頁中斷的指令。如果頁面隨后被修改，就會(huì)發(fā)生另一個(gè)缺頁異常。從而允許操作系統(tǒng)設(shè)置 M 位并把頁面的模式設(shè)置為 READ/WRITE。

可以用 R 位和 M 位來構(gòu)造一個(gè)簡單的頁面置換算法：當(dāng)啟動(dòng)一個(gè)進(jìn)程時(shí)，操作系統(tǒng)將其所有頁面的兩個(gè)位都設(shè)置為 0。R 位定期的被清零（在每個(gè)時(shí)鐘中斷）。用來將最近未引用的頁面和已引用的頁面分開。

當(dāng)出現(xiàn)缺頁中斷后，操作系統(tǒng)會(huì)檢查所有的頁面，并根據(jù)它們的 R 位和 M 位將當(dāng)前值分為四類：

• 第 0 類：沒有引用 R，沒有修改 M
• 第 1 類：沒有引用 R，已修改 M
• 第 2 類：引用 R ，沒有修改 M
• 第 3 類：已被訪問 R，已被修改 M

盡管看起來好像無法實(shí)現(xiàn)第一類頁面，但是當(dāng)?shù)谌愴撁娴?R 位被時(shí)鐘中斷清除時(shí)，它們就會(huì)發(fā)生。時(shí)鐘中斷不會(huì)清除 M 位，因?yàn)樾枰@個(gè)信息才能知道是否寫回磁盤中。清除 R 但不清除 M 會(huì)導(dǎo)致出現(xiàn)一類頁面。

NRU(Not Recently Used) 算法從編號(hào)最小的非空類中隨機(jī)刪除一個(gè)頁面。此算法隱含的思想是，在一個(gè)時(shí)鐘內(nèi)（約 20 ms）淘汰一個(gè)已修改但是沒有被訪問的頁面要比一個(gè)大量引用的未修改頁面好，NRU 的主要優(yōu)點(diǎn)是易于理解并且能夠有效的實(shí)現(xiàn)。

另一種開銷較小的方式是使用 FIFO(First-In,First-Out) 算法，這種類型的數(shù)據(jù)結(jié)構(gòu)也適用在頁面置換算法中。由操作系統(tǒng)維護(hù)一個(gè)所有在當(dāng)前內(nèi)存中的頁面的鏈表，最早進(jìn)入的放在表頭，最新進(jìn)入的頁面放在表尾。在發(fā)生缺頁異常時(shí)，會(huì)把頭部的頁移除并且把新的頁添加到表尾。

還記得缺頁異常什么時(shí)候發(fā)生嗎？我們知道應(yīng)用程序訪問內(nèi)存會(huì)進(jìn)行虛擬地址到物理地址的映射，缺頁異常就發(fā)生在虛擬地址無法映射到物理地址的時(shí)候。因?yàn)閷?shí)際的物理地址要比虛擬地址小很多（參考上面的虛擬地址和物理地址映射圖），所以缺頁經(jīng)常會(huì)發(fā)生。

先進(jìn)先出頁面可能是最簡單的頁面替換算法了。在這種算法中，操作系統(tǒng)會(huì)跟蹤鏈表中內(nèi)存中的所有頁。下面我們舉個(gè)例子看一下（這個(gè)算法我剛開始看的時(shí)候有點(diǎn)懵逼，后來才看懂，我還是很菜）

• 初始化的時(shí)候，沒有任何頁面，所以第一次的時(shí)候會(huì)檢查頁面 1 是否位于鏈表中，沒有在鏈表中，那么就是 MISS，頁面1 進(jìn)入鏈表，鏈表的先進(jìn)先出的方向如圖所示。
• 類似的，第二次會(huì)先檢查頁面 2 是否位于鏈表中，沒有在鏈表中，那么頁面 2 進(jìn)入鏈表，狀態(tài)為 MISS，依次類推。
• 我們來看第四次，此時(shí)的鏈表為 1 2 3，第四次會(huì)檢查頁面 2 是否位于鏈表中，經(jīng)過檢索后，發(fā)現(xiàn) 2 在鏈表中，那么狀態(tài)就是 HIT，并不會(huì)再進(jìn)行入隊(duì)和出隊(duì)操作，第五次也是一樣的。
• 下面來看第六次，此時(shí)的鏈表還是 1 2 3，因?yàn)橹皼]有執(zhí)行進(jìn)入鏈表操作，頁面 5 會(huì)首先進(jìn)行檢查，發(fā)現(xiàn)鏈表中沒有頁面 5 ，則執(zhí)行頁面 5 的進(jìn)入鏈表操作，頁面 2 執(zhí)行出鏈表的操作，執(zhí)行完成后的鏈表順序?yàn)?2 3 5。

我們上面學(xué)到的 FIFO 鏈表頁面有個(gè)缺陷，那就是出鏈和入鏈并不會(huì)進(jìn)行 check 檢查，這樣就會(huì)容易把經(jīng)常使用的頁面置換出去，為了避免這一問題，我們對(duì)該算法做一個(gè)簡單的修改：我們檢查最老頁面的 R 位，如果是 0 ，那么這個(gè)頁面就是最老的而且沒有被使用，那么這個(gè)頁面就會(huì)被立刻換出。如果 R 位是 1，那么就清除此位，此頁面會(huì)被放在鏈表的尾部，修改它的裝入時(shí)間就像剛放進(jìn)來的一樣。然后繼續(xù)搜索。

這種算法叫做 第二次機(jī)會(huì)(second chance)算法，就像下面這樣，我們看到頁面 A 到 H 保留在鏈表中，并按到達(dá)內(nèi)存的時(shí)間排序。

a）按照先進(jìn)先出的方法排列的頁面；b）在時(shí)刻 20 處發(fā)生缺頁異常中斷并且 A 的 R 位已經(jīng)設(shè)置時(shí)的頁面鏈表。

假設(shè)缺頁異常發(fā)生在時(shí)刻 20 處，這時(shí)最老的頁面是 A ，它是在 0 時(shí)刻到達(dá)的。如果 A 的 R 位是 0，那么它將被淘汰出內(nèi)存，或者把它寫回磁盤（如果它已經(jīng)被修改過），或者只是簡單的放棄（如果它是未被修改過）。另一方面，如果它的 R 位已經(jīng)設(shè)置了，則將 A 放到鏈表的尾部并且重新設(shè)置裝入時(shí)間為當(dāng)前時(shí)刻（20 處），然后清除 R 位。然后從 B 頁面開始繼續(xù)搜索合適的頁面。

尋找第二次機(jī)會(huì)的是在最近的時(shí)鐘間隔中未被訪問過的頁面。如果所有的頁面都被訪問過，該算法就會(huì)被簡化為單純的 FIFO 算法。具體來說，假設(shè)圖 a 中所有頁面都設(shè)置了 R 位。操作系統(tǒng)將頁面依次移到鏈表末尾，每次都在添加到末尾時(shí)清除 R 位。最后，算法又會(huì)回到頁面 A，此時(shí)的 R 位已經(jīng)被清除，那么頁面 A 就會(huì)被執(zhí)行出鏈處理，因此算法能夠正常結(jié)束。

即使上面提到的第二次頁面置換算法也是一種比較合理的算法，但它經(jīng)常要在鏈表中移動(dòng)頁面，既降低了效率，而且這種算法也不是必須的。一種比較好的方式是把所有的頁面都保存在一個(gè)類似鐘面的環(huán)形鏈表中，一個(gè)表針指向最老的頁面。如下圖所示

當(dāng)缺頁錯(cuò)誤出現(xiàn)時(shí)，算法首先檢查表針指向的頁面，如果它的 R 位是 0 就淘汰該頁面，并把新的頁面插入到這個(gè)位置，然后把表針向前移動(dòng)一位；如果 R 位是 1 就清除 R 位并把表針前移一個(gè)位置。重復(fù)這個(gè)過程直到找到了一個(gè) R 位為 0 的頁面位置。了解這個(gè)算法的工作方式，就明白為什么它被稱為 時(shí)鐘(clokc)算法了。

最近最少使用頁面置換算法的一個(gè)解釋會(huì)是下面這樣：在前面幾條指令中頻繁使用的頁面和可能在后面的幾條指令中被使用。反過來說，已經(jīng)很久沒有使用的頁面有可能在未來一段時(shí)間內(nèi)仍不會(huì)被使用。這個(gè)思想揭示了一個(gè)可以實(shí)現(xiàn)的算法：在缺頁中斷時(shí)，置換未使用時(shí)間最長的頁面。這個(gè)策略稱為 LRU(Least Recently Used) ，最近最少使用頁面置換算法。

雖然 LRU 在理論上是可以實(shí)現(xiàn)的，但是從長遠(yuǎn)看來代價(jià)比較高。為了完全實(shí)現(xiàn) LRU，會(huì)在內(nèi)存中維護(hù)一個(gè)所有頁面的鏈表，最頻繁使用的頁位于表頭，最近最少使用的頁位于表尾。困難的是在每次內(nèi)存引用時(shí)更新整個(gè)鏈表。在鏈表中找到一個(gè)頁面，刪除它，然后把它移動(dòng)到表頭是一個(gè)非常耗時(shí)的操作，即使使用硬件來實(shí)現(xiàn)也是一樣的費(fèi)時(shí)。

然而，還有其他方法可以通過硬件實(shí)現(xiàn) LRU。讓我們首先考慮最簡單的方式。這個(gè)方法要求硬件有一個(gè) 64 位的計(jì)數(shù)器，它在每條指令執(zhí)行完成后自動(dòng)加 1，每個(gè)頁表必須有一個(gè)足夠容納這個(gè)計(jì)數(shù)器值的域。在每次訪問內(nèi)存后，將當(dāng)前的值保存到被訪問頁面的頁表項(xiàng)中。一旦發(fā)生缺頁異常，操作系統(tǒng)就檢查所有頁表項(xiàng)中計(jì)數(shù)器的值，找到值最小的一個(gè)頁面，這個(gè)頁面就是最少使用的頁面。

盡管上面的 LRU 算法在原則上是可以實(shí)現(xiàn)的，但是很少有機(jī)器能夠擁有那些特殊的硬件。上面是硬件的實(shí)現(xiàn)方式，那么現(xiàn)在考慮要用軟件來實(shí)現(xiàn) LRU 。一種可以實(shí)現(xiàn)的方案是 NFU(Not Frequently Used，最不常用)算法。它需要一個(gè)軟件計(jì)數(shù)器來和每個(gè)頁面關(guān)聯(lián)，初始化的時(shí)候是 0 。在每個(gè)時(shí)鐘中斷時(shí)，操作系統(tǒng)會(huì)瀏覽內(nèi)存中的所有頁，會(huì)將每個(gè)頁面的 R 位（0 或 1）加到它的計(jì)數(shù)器上。這個(gè)計(jì)數(shù)器大體上跟蹤了各個(gè)頁面訪問的頻繁程度。當(dāng)缺頁異常出現(xiàn)時(shí)，則置換計(jì)數(shù)器值最小的頁面。

NFU 最主要的問題是它不會(huì)忘記任何東西，想一下是不是這樣？例如，在一個(gè)多次（掃描）的編譯器中，在第一遍掃描中頻繁使用的頁面會(huì)在后續(xù)的掃描中也有較高的計(jì)數(shù)。事實(shí)上，如果第一次掃描的執(zhí)行時(shí)間恰好是各次掃描中最長的，那么后續(xù)遍歷的頁面的統(tǒng)計(jì)次數(shù)總會(huì)比第一次頁面的統(tǒng)計(jì)次數(shù)小。結(jié)果是操作系統(tǒng)將置換有用的頁面而不是不再使用的頁面。

幸運(yùn)的是只需要對(duì) NFU 做一個(gè)簡單的修改就可以讓它模擬 LRU，這個(gè)修改有兩個(gè)步驟

• 首先，在 R 位被添加進(jìn)來之前先把計(jì)數(shù)器右移一位；
• 第二步，R 位被添加到最左邊的位而不是最右邊的位。

修改以后的算法稱為 老化(aging) 算法，下圖解釋了老化算法是如何工作的。

我們假設(shè)在第一個(gè)時(shí)鐘周期內(nèi)頁面 0 - 5 的 R 位依次是 1，0，1，0，1，1，（也就是頁面 0 是 1，頁面 1 是 0，頁面 2 是 1 這樣類推）。也就是說，在 0 個(gè)時(shí)鐘周期到 1 個(gè)時(shí)鐘周期之間，0，2，4，5 都被引用了，從而把它們的 R 位設(shè)置為 1，剩下的設(shè)置為 0 。在相關(guān)的六個(gè)計(jì)數(shù)器被右移之后 R 位被添加到 左側(cè) ，就像上圖中的 a。剩下的四列顯示了接下來的四個(gè)時(shí)鐘周期內(nèi)的六個(gè)計(jì)數(shù)器變化。

CPU正在以某個(gè)頻率前進(jìn)，該頻率的周期稱為時(shí)鐘滴答或時(shí)鐘周期。一個(gè) 100Mhz 的處理器每秒將接收100,000,000個(gè)時(shí)鐘滴答。

當(dāng)缺頁異常出現(xiàn)時(shí)，將置換（就是移除）計(jì)數(shù)器值最小的頁面。如果一個(gè)頁面在前面 4 個(gè)時(shí)鐘周期內(nèi)都沒有被訪問過，那么它的計(jì)數(shù)器應(yīng)該會(huì)有四個(gè)連續(xù)的 0 ，因此它的值肯定要比前面 3 個(gè)時(shí)鐘周期內(nèi)都沒有被訪問過的頁面的計(jì)數(shù)器小。

這個(gè)算法與 LRU 算法有兩個(gè)重要的區(qū)別：看一下上圖中的 e，第三列和第五列

它們?cè)趦蓚€(gè)時(shí)鐘周期內(nèi)都沒有被訪問過，在此之前的時(shí)鐘周期內(nèi)都引用了兩個(gè)頁面。根據(jù) LRU 算法，如果需要置換的話，那么應(yīng)該在這兩個(gè)頁面中選擇一個(gè)。那么問題來了，我萌應(yīng)該選擇哪個(gè)？現(xiàn)在的問題是我們不知道時(shí)鐘周期 1 到時(shí)鐘周期 2 內(nèi)它們中哪個(gè)頁面是后被訪問到的。因?yàn)樵诿總€(gè)時(shí)鐘周期內(nèi)只記錄了一位，所以無法區(qū)分在一個(gè)時(shí)鐘周期內(nèi)哪個(gè)頁面最早被引用，哪個(gè)頁面是最后被引用的。因此，我們能做的就是置換頁面3，因?yàn)轫撁?3 在周期 0 - 1 內(nèi)都沒有被訪問過，而頁面 5 卻被引用過。

LRU 與老化之前的第 2 個(gè)區(qū)別是，在老化期間，計(jì)數(shù)器具有有限數(shù)量的位（這個(gè)例子中是 8 位），這就限制了以往的訪問記錄。如果兩個(gè)頁面的計(jì)數(shù)器都是 0 ，那么我們可以隨便選擇一個(gè)進(jìn)行置換。實(shí)際上，有可能其中一個(gè)頁面的訪問次數(shù)實(shí)在 9 個(gè)時(shí)鐘周期以前，而另外一個(gè)頁面是在 1000 個(gè)時(shí)鐘周期之前，但是我們卻無法看到這些。在實(shí)際過程中，如果時(shí)鐘周期是 20 ms，8 位一般是夠用的。所以我們經(jīng)常拿 20 ms 來舉例。

在最單純的分頁系統(tǒng)中，剛啟動(dòng)進(jìn)程時(shí)，在內(nèi)存中并沒有頁面。此時(shí)如果 CPU 嘗試匹配第一條指令，就會(huì)得到一個(gè)缺頁異常，使操作系統(tǒng)裝入含有第一條指令的頁面。其他的錯(cuò)誤比如 全局變量和 堆棧 引起的缺頁異常通常會(huì)緊接著發(fā)生。一段時(shí)間以后，進(jìn)程需要的大部分頁面都在內(nèi)存中了，此時(shí)進(jìn)程開始在較少的缺頁異常環(huán)境中運(yùn)行。這個(gè)策略稱為 請(qǐng)求調(diào)頁(demand paging)，因?yàn)轫撁媸歉鶕?jù)需要被調(diào)入的，而不是預(yù)先調(diào)入的。

在一個(gè)大的地址空間中系統(tǒng)的讀所有的頁面，將會(huì)造成很多缺頁異常，因此會(huì)導(dǎo)致沒有足夠的內(nèi)存來容納這些頁面。不過幸運(yùn)的是，大部分進(jìn)程不是這樣工作的，它們都會(huì)以局部性方式(locality of reference) 來訪問，這意味著在執(zhí)行的任何階段，程序只引用其中的一小部分。

一個(gè)進(jìn)程當(dāng)前正在使用的頁面的集合稱為它的 工作集(working set)，如果整個(gè)工作集都在內(nèi)存中，那么進(jìn)程在運(yùn)行到下一運(yùn)行階段（例如，編譯器的下一遍掃面）之前，不會(huì)產(chǎn)生很多缺頁中斷。如果內(nèi)存太小從而無法容納整個(gè)工作集，那么進(jìn)程的運(yùn)行過程中會(huì)產(chǎn)生大量的缺頁中斷，會(huì)導(dǎo)致運(yùn)行速度也會(huì)變得緩慢。因?yàn)橥ǔＶ恍枰獛准{秒就能執(zhí)行一條指令，而通常需要十毫秒才能從磁盤上讀入一個(gè)頁面。如果一個(gè)程序每 10 ms 只能執(zhí)行一到兩條指令，那么它將需要很長時(shí)間才能運(yùn)行完。如果只是執(zhí)行幾條指令就會(huì)產(chǎn)生中斷，那么就稱作這個(gè)程序產(chǎn)生了 顛簸(thrashing)。

在多道程序的系統(tǒng)中，通常會(huì)把進(jìn)程移到磁盤上（即從內(nèi)存中移走所有的頁面），這樣可以讓其他進(jìn)程有機(jī)會(huì)占用 CPU 。有一個(gè)問題是，當(dāng)進(jìn)程想要再次把之前調(diào)回磁盤的頁面調(diào)回內(nèi)存怎么辦？從技術(shù)的角度上來講，并不需要做什么，此進(jìn)程會(huì)一直產(chǎn)生缺頁中斷直到它的工作集 被調(diào)回內(nèi)存。然后，每次裝入一個(gè)進(jìn)程需要 20、100 甚至 1000 次缺頁中斷，速度顯然太慢了，并且由于 CPU 需要幾毫秒時(shí)間處理一個(gè)缺頁中斷，因此由相當(dāng)多的 CPU 時(shí)間也被浪費(fèi)了。

因此，不少分頁系統(tǒng)中都會(huì)設(shè)法跟蹤進(jìn)程的工作集，確保這些工作集在進(jìn)程運(yùn)行時(shí)被調(diào)入內(nèi)存。這個(gè)方法叫做 工作集模式(working set model)。它被設(shè)計(jì)用來減少缺頁中斷的次數(shù)的。在進(jìn)程運(yùn)行前首先裝入工作集頁面的這一個(gè)過程被稱為 預(yù)先調(diào)頁(prepaging)，工作集是隨著時(shí)間來變化的。

根據(jù)研究表明，大多數(shù)程序并不是均勻的訪問地址空間的，而訪問往往是集中于一小部分頁面。一次內(nèi)存訪問可能會(huì)取出一條指令，也可能會(huì)取出數(shù)據(jù)，或者是存儲(chǔ)數(shù)據(jù)。在任一時(shí)刻 t，都存在一個(gè)集合，它包含所喲歐最近 k 次內(nèi)存訪問所訪問過的頁面。這個(gè)集合 w(k,t) 就是工作集。因?yàn)樽罱?k = 1次訪問肯定會(huì)訪問最近 k > 1 次訪問所訪問過的頁面，所以 w(k,t) 是 k 的單調(diào)遞減函數(shù)。隨著 k 的增大，w(k,t) 是不會(huì)無限變大的，因?yàn)槌绦虿豢赡茉L問比所能容納頁面數(shù)量上限還多的頁面。

事實(shí)上大多數(shù)應(yīng)用程序只會(huì)任意訪問一小部分頁面集合，但是這個(gè)集合會(huì)隨著時(shí)間而緩慢變化，所以為什么一開始曲線會(huì)快速上升而 k 較大時(shí)上升緩慢。為了實(shí)現(xiàn)工作集模型，操作系統(tǒng)必須跟蹤哪些頁面在工作集中。一個(gè)進(jìn)程從它開始執(zhí)行到當(dāng)前所實(shí)際使用的 CPU 時(shí)間總數(shù)通常稱作 當(dāng)前實(shí)際運(yùn)行時(shí)間。進(jìn)程的工作集可以被稱為在過去的 t 秒實(shí)際運(yùn)行時(shí)間中它所訪問過的頁面集合。

下面來簡單描述一下工作集的頁面置換算法，基本思路就是找出一個(gè)不在工作集中的頁面并淘汰它。下面是一部分機(jī)器頁表

因?yàn)橹挥心切┰趦?nèi)存中的頁面才可以作為候選者被淘汰，所以該算法忽略了那些不在內(nèi)存中的頁面。每個(gè)表項(xiàng)至少包含兩條信息：上次使用該頁面的近似時(shí)間和 R（訪問）位?？瞻椎木匦伪硎驹撍惴ú恍枰渌侄危珥摽驍?shù)量、保護(hù)位、修改位。

算法的工作流程如下，假設(shè)硬件要設(shè)置 R 和 M 位。同樣的，在每個(gè)時(shí)鐘周期內(nèi)，一個(gè)周期性的時(shí)鐘中斷會(huì)使軟件清除 Referenced(引用)位。在每個(gè)缺頁異常，頁表會(huì)被掃描以找出一個(gè)合適的頁面把它置換。

隨著每個(gè)頁表項(xiàng)的處理，都需要檢查 R 位。如果 R 位是 1，那么就會(huì)將當(dāng)前時(shí)間寫入頁表項(xiàng)的 上次使用時(shí)間域，表示的意思就是缺頁異常發(fā)生時(shí)頁面正在被使用。因?yàn)轫撁嬖诋?dāng)前時(shí)鐘周期內(nèi)被訪問過，那么它應(yīng)該出現(xiàn)在工作集中而不是被刪除（假設(shè) t 是橫跨了多個(gè)時(shí)鐘周期）。

如果 R 位是 0 ，那么在當(dāng)前的時(shí)鐘周期內(nèi)這個(gè)頁面沒有被訪問過，應(yīng)該作為被刪除的對(duì)象。為了查看是否應(yīng)該將其刪除，會(huì)計(jì)算其使用期限（當(dāng)前虛擬時(shí)間 - 上次使用時(shí)間），來用這個(gè)時(shí)間和 t 進(jìn)行對(duì)比。如果使用期限大于 t，那么這個(gè)頁面就不再工作集中，而使用新的頁面來替換它。然后繼續(xù)掃描更新剩下的表項(xiàng)。

然而，如果 R 位是 0 但是使用期限小于等于 t，那么此頁應(yīng)該在工作集中。此時(shí)就會(huì)把頁面臨時(shí)保存起來，但是會(huì)記生存時(shí)間最長（即上次使用時(shí)間的最小值）的頁面。如果掃描完整個(gè)頁表卻沒有找到適合被置換的頁面，也就意味著所有的頁面都在工作集中。在這種情況下，如果找到了一個(gè)或者多個(gè) R = 0 的頁面，就淘汰生存時(shí)間最長的頁面。最壞的情況下是，在當(dāng)前時(shí)鐘周期內(nèi)，所有的頁面都被訪問過了（也就是都有 R = 1），因此就隨機(jī)選擇一個(gè)頁面淘汰，如果有的話最好選一個(gè)未被訪問的頁面，也就是干凈的頁面。

當(dāng)缺頁異常發(fā)生后，需要掃描整個(gè)頁表才能確定被淘汰的頁面，因此基本工作集算法還是比較浪費(fèi)時(shí)間的。一個(gè)對(duì)基本工作集算法的提升是基于時(shí)鐘算法但是卻使用工作集的信息，這種算法稱為WSClock(工作集時(shí)鐘)。由于它的實(shí)現(xiàn)簡單并且具有高性能，因此在實(shí)踐中被廣泛應(yīng)用。

與時(shí)鐘算法一樣，所需的數(shù)據(jù)結(jié)構(gòu)是一個(gè)以頁框?yàn)樵氐难h(huán)列表，就像下面這樣

最初的時(shí)候，該表是空的。當(dāng)裝入第一個(gè)頁面后，把它加載到該表中。隨著更多的頁面的加入，它們形成一個(gè)環(huán)形結(jié)構(gòu)。每個(gè)表項(xiàng)包含來自基本工作集算法的上次使用時(shí)間，以及 R 位（已標(biāo)明）和 M 位（未標(biāo)明）。

與時(shí)鐘算法一樣，在每個(gè)缺頁異常時(shí)，首先檢查指針指向的頁面。如果 R 位被是設(shè)置為 1，該頁面在當(dāng)前時(shí)鐘周期內(nèi)就被使用過，那么該頁面就不適合被淘汰。然后把該頁面的 R 位置為 0，指針指向下一個(gè)頁面，并重復(fù)該算法。該事件序列化后的狀態(tài)參見圖 b。

現(xiàn)在考慮指針指向的頁面 R = 0 時(shí)會(huì)發(fā)生什么，參見圖 c，如果頁面的使用期限大于 t 并且頁面為被訪問過，那么這個(gè)頁面就不會(huì)在工作集中，并且在磁盤上會(huì)有一個(gè)此頁面的副本。申請(qǐng)重新調(diào)入一個(gè)新的頁面，并把新的頁面放在其中，如圖 d 所示。另一方面，如果頁面被修改過，就不能重新申請(qǐng)頁面，因?yàn)檫@個(gè)頁面在磁盤上沒有有效的副本。為了避免由于調(diào)度寫磁盤操作引起的進(jìn)程切換，指針繼續(xù)向前走，算法繼續(xù)對(duì)下一個(gè)頁面進(jìn)行操作。畢竟，有可能存在一個(gè)老的，沒有被修改過的頁面可以立即使用。

原則上來說，所有的頁面都有可能因?yàn)榇疟PI/O 在某個(gè)時(shí)鐘周期內(nèi)被調(diào)度。為了降低磁盤阻塞，需要設(shè)置一個(gè)限制，即最大只允許寫回 n 個(gè)頁面。一旦達(dá)到該限制，就不允許調(diào)度新的寫操作。

那么就有個(gè)問題，指針會(huì)繞一圈回到原點(diǎn)的，如果回到原點(diǎn)，它的起始點(diǎn)會(huì)發(fā)生什么？這里有兩種情況：

• 至少調(diào)度了一次寫操作
• 沒有調(diào)度過寫操作

在第一種情況中，指針僅僅是不停的移動(dòng)，尋找一個(gè)未被修改過的頁面。由于已經(jīng)調(diào)度了一個(gè)或者多個(gè)寫操作，最終會(huì)有某個(gè)寫操作完成，它的頁面會(huì)被標(biāo)記為未修改。置換遇到的第一個(gè)未被修改過的頁面，這個(gè)頁面不一定是第一個(gè)被調(diào)度寫操作的頁面，因?yàn)橛脖P驅(qū)動(dòng)程序?yàn)榱藘?yōu)化性能可能會(huì)把寫操作重排序。

對(duì)于第二種情況，所有的頁面都在工作集中，否則將至少調(diào)度了一個(gè)寫操作。由于缺乏額外的信息，最簡單的方法就是置換一個(gè)未被修改的頁面來使用，掃描中需要記錄未被修改的頁面的位置，如果不存在未被修改的頁面，就選定當(dāng)前頁面并把它寫回磁盤。

我們到現(xiàn)在已經(jīng)研究了各種頁面置換算法，現(xiàn)在我們來一個(gè)簡單的總結(jié)，算法的總結(jié)歸納如下

• 最優(yōu)算法在當(dāng)前頁面中置換最后要訪問的頁面。不幸的是，沒有辦法來判定哪個(gè)頁面是最后一個(gè)要訪問的，因此實(shí)際上該算法不能使用。然而，它可以作為衡量其他算法的標(biāo)準(zhǔn)。
• NRU 算法根據(jù) R 位和 M 位的狀態(tài)將頁面氛圍四類。從編號(hào)最小的類別中隨機(jī)選擇一個(gè)頁面。NRU 算法易于實(shí)現(xiàn)，但是性能不是很好。存在更好的算法。
• FIFO 會(huì)跟蹤頁面加載進(jìn)入內(nèi)存中的順序，并把頁面放入一個(gè)鏈表中。有可能刪除存在時(shí)間最長但是還在使用的頁面，因此這個(gè)算法也不是一個(gè)很好的選擇。
• 第二次機(jī)會(huì)算法是對(duì) FIFO 的一個(gè)修改，它會(huì)在刪除頁面之前檢查這個(gè)頁面是否仍在使用。如果頁面正在使用，就會(huì)進(jìn)行保留。這個(gè)改進(jìn)大大提高了性能。
• 時(shí)鐘 算法是第二次機(jī)會(huì)算法的另外一種實(shí)現(xiàn)形式，時(shí)鐘算法和第二次算法的性能差不多，但是會(huì)花費(fèi)更少的時(shí)間來執(zhí)行算法。
• LRU 算法是一個(gè)非常優(yōu)秀的算法，但是沒有特殊的硬件(TLB)很難實(shí)現(xiàn)。如果沒有硬件，就不能使用 LRU 算法。
• NFU 算法是一種近似于 LRU 的算法，它的性能不是非常好。
• 老化 算法是一種更接近 LRU 算法的實(shí)現(xiàn)，并且可以更好的實(shí)現(xiàn)，因此是一個(gè)很好的選擇
• 最后兩種算法都使用了工作集算法。工作集算法提供了合理的性能開銷，但是它的實(shí)現(xiàn)比較復(fù)雜。WSClock 是另外一種變體，它不僅能夠提供良好的性能，而且可以高效地實(shí)現(xiàn)。

總之，最好的算法是老化算法和WSClock算法。他們分別是基于 LRU 和工作集算法。他們都具有良好的性能并且能夠被有效的實(shí)現(xiàn)。還存在其他一些好的算法，但實(shí)際上這兩個(gè)可能是最重要的。