操作系統(tǒng)內(nèi)存的詳細(xì)資料講解分析

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

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

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

操作系統(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)行探討，從簡(jiǎn)單到復(fù)雜，由于最低級(jí)別的緩存是由硬件進(jìn)行管理的，所以我們主要探討主存模型和如何對(duì)主存進(jìn)行管理。

無(wú)存儲(chǔ)器抽象

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

MOV REGISTER1， 1000

計(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ì)立刻崩潰。

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

運(yùn)行多個(gè)程序

但是，即便沒有存儲(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)程如果訪問(wèn)鍵與其 PSW 中保存的碼不同，360 硬件會(huì)捕獲這種情況。因?yàn)橹挥胁僮飨到y(tǒng)可以修改保護(hù)鍵，這樣就可以防止進(jìn)程之間、用戶進(jìn)程和操作系統(tǒng)之間的干擾。

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

從圖上可以看出，這是兩個(gè)不同的 16KB 程序的裝載過(guò)程，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，由于這種不正確訪問(wèn)，可能會(huì)造成程序崩潰。

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

一種存儲(chǔ)器抽象：地址空間

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

第二點(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)用程序可以通過(guò)鼠標(biāo)來(lái)喚醒。在系統(tǒng)中沒有物理內(nèi)存的情況下很難實(shí)現(xiàn)。

地址空間的概念

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

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

基址寄存器和變址寄存器

最簡(jiǎn)單的辦法是使用動(dòng)態(tài)重定位（dynamic relocation）技術(shù)，它就是通過(guò)一種簡(jiǎn)單的方式將每個(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ù)位置并且在裝載期間無(wú)需重定位。當(dāng)一個(gè)進(jìn)程運(yùn)行時(shí)，程序的起始物理地址裝載到基址寄存器中，程序的長(zhǎng)度則裝載到變址寄存器中。在上圖 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)用程序的長(zhǎng)度。

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

使用基址寄存器和變址寄存器是給每個(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)，在每次訪問(wèn)內(nèi)存時(shí)，都會(huì)進(jìn)行 ADD 和 CMP 運(yùn)算。CMP 指令可以執(zhí)行的很快，但是加法就會(huì)相對(duì)慢一些，除非使用特殊的加法電路，否則加法因進(jìn)位傳播時(shí)間而變慢。

交換技術(shù)

如果計(jì)算機(jī)的物理內(nèi)存足夠大來(lá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è)簡(jiǎn)單的應(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 來(lái)啟動(dòng)，但是一旦它們開始處理數(shù)據(jù)就需要許多 GB 來(lái)處理。從結(jié)果上來(lái)看，將所有進(jìn)程始終保持在內(nèi)存中需要大量?jī)?nèi)存，如果內(nèi)存不足，則無(wú)法完成。

所以針對(duì)上面內(nèi)存不足的問(wèn)題，提出了兩種處理方式：最簡(jiǎn)單的一種方式就是交換（swapping）技術(shù)，即把一個(gè)進(jìn)程完整的調(diào)入內(nèi)存，然后再內(nèi)存中運(yùn)行一段時(shí)間，再把它放回磁盤。空閑進(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)存中。下面我們首先先探討一下交換

交換過(guò)程

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

剛開始的時(shí)候，只有進(jìn)程 A 在內(nèi)存中，然后從創(chuàng)建進(jìn)程 B 和進(jìn)程 C 或者從磁盤中把它們換入內(nèi)存，然后在圖 d 中，A 被換出內(nèi)存到磁盤中，最后 A 重新進(jìn)來(lái)。因?yàn)閳D g 中的進(jìn)程 A 現(xiàn)在到了不同的位置，所以在裝載過(guò)程中需要被重新定位，或者在交換程序時(shí)通過(guò)軟件來(lái)執(zhí)行；或者在程序執(zhí)行期間通過(guò)硬件來(lái)重定位?；芳拇嫫骱妥冎芳拇嫫骶瓦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è)值得注意的問(wèn)題是，當(dāng)進(jìn)程被創(chuàng)建或者換入內(nèi)存時(shí)應(yīng)該為它分配多大的內(nèi)存。如果進(jìn)程被創(chuàng)建后它的大小是固定的并且不再改變，那么分配策略就比較簡(jiǎn)單：操作系統(tǒng)會(huì)準(zhǔn)確的按其需要的大小進(jìn)行分配。

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

代碼段（codesegment/textsegment）：

又稱文本段，用來(lái)存放指令，運(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 語(yǔ)句中的格式字符串和開關(guān)語(yǔ)句的跳轉(zhuǎn)表。也就是常量區(qū)。例如，全局作用域中的 const int ival = 10，ival 存放在 .rodata 段；再如，函數(shù)局部作用域中的 printf（“Hello world %d ”， c）; 語(yǔ)句中的格式字符串 “Hello world %d ”，也存放在 .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++ 編譯過(guò)后的結(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 ） 是用來(lái)區(qū)分或者劃分范圍區(qū)域的意思。匯編語(yǔ)言的 segment 偽指令表示段定義的起始，ends 偽指令表示段定義的結(jié)束。段定義是一段連續(xù)的內(nèi)存空間

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

如果一個(gè)進(jìn)程與空閑區(qū)相鄰，那么可把該空閑區(qū)分配給進(jìn)程以供其增大。

如果進(jìn)程相鄰的是另一個(gè)進(jìn)程，就會(huì)有兩種處理方式：要么把需要增長(zhǎng)的進(jìn)程移動(dòng)到一個(gè)內(nèi)存中空閑區(qū)足夠大的區(qū)域，要么把一個(gè)或多個(gè)進(jìn)程交換出去，已變成生成一個(gè)大的空閑區(qū)。

如果一個(gè)進(jìn)程在內(nèi)存中不能增長(zhǎng)，而且磁盤上的交換區(qū)也滿了，那么這個(gè)進(jìn)程只有掛起一些空閑空間（或者可以結(jié)束該進(jìn)程）

上面只針對(duì)單個(gè)或者一小部分需要增長(zhǎng)的進(jìn)程采用的方式，如果大部分進(jìn)程都要在運(yùn)行時(shí)增長(zhǎng)，為了減少因內(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)程分配了增長(zhǎng)空間的內(nèi)存配置。

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

空閑內(nèi)存管理

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

位圖（bitmap）

空閑列表（free lists）

下面我們就來(lái)探討一下這兩種使用方式

使用位圖的存儲(chǔ)管理

使用位圖方法時(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)。

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

使用鏈表進(jìn)行管理

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

在這個(gè)例子中，段鏈表（segment list）是按照地址排序的。這種方式的優(yōu)點(diǎn)是，當(dāng)進(jìn)程終止或被交換時(shí)，更新列表很簡(jiǎn)單。一個(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)存，最簡(jiǎn)單的算法是使用 首次適配（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)生大量無(wú)用的小緩沖區(qū)，首次匹配算法生成的空閑區(qū)會(huì)更大一些。

最佳適配的空閑區(qū)會(huì)分裂出很多非常小的緩沖區(qū)，為了避免這一問(wèn)題，可以考慮使用 最差適配（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í)，首次適配算法與最佳適配算法一樣快，而下次適配算法在這里毫無(wú)意義。

另一種分配算法是 快速適配（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í)，尋找它的相鄰塊并查看是否可以合并的過(guò)程都是非常耗時(shí)的。如果不進(jìn)行合并，內(nèi)存將會(huì)很快分裂出大量進(jìn)程無(wú)法利用的小空閑區(qū)。

虛擬內(nèi)存

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

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

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

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

在某種意義上來(lái)說(shuō)，虛擬地址是對(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)程使用。

分頁(yè)

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

MOV REG，1000

這條指令時(shí)，它會(huì)把內(nèi)存地址為 1000 的內(nèi)存單元的內(nèi)容復(fù)制到 REG 中（或者相反，這取決于計(jì)算機(jī)）。地址可以通過(guò)索引、基址寄存器、段寄存器或其他方式產(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)存地址，像下圖這樣

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

頁(yè)表給出虛擬地址與物理內(nèi)存地址之間的映射關(guān)系。每一頁(yè)起始于 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 的程序，但是程序無(wú)法全部調(diào)入內(nèi)存運(yùn)行，在磁盤上必須有一個(gè)最多 64 KB 的程序核心映像的完整副本，以保證程序片段在需要時(shí)被調(diào)入內(nèi)存。

存在映射的頁(yè)如何映射

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

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

MOV REG， 0

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

MOV REG， 8192

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

MOV REG， 24576

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

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

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

未映射的頁(yè)如何映射

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

MOV REG， 32780

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

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

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

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

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

頁(yè)表

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

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

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

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

頁(yè)表項(xiàng)的結(jié)構(gòu)

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

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

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

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

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

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

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

加速分頁(yè)過(guò)程

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

虛擬地址到物理地址的映射速度必須要快

如果虛擬地址空間足夠大，那么頁(yè)表也會(huì)足夠大

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

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

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

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

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

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

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

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

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

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

1-byte：1 字節(jié)的操作數(shù)和操作碼共同以 1 字節(jié)表示；操作數(shù)是內(nèi)部寄存器，并被編碼到指令中；指令需要一個(gè)存儲(chǔ)位置來(lái)將單個(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ì)少量頁(yè)面進(jìn)行多次訪問(wèn)，而不是對(duì)大量頁(yè)面進(jìn)行少量訪問(wèn)。因此，只有很少的頁(yè)面能夠被再次訪問(wèn)，而其他的頁(yè)表項(xiàng)很少被訪問(wèn)。

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

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

TLB 加速分頁(yè)

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

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

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

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

軟件 TLB 管理

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

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

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

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

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

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

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

所需的頁(yè)面就在內(nèi)存中，但是卻沒有記錄在進(jìn)程的頁(yè)表中，這種情況可能是由其他進(jìn)程從磁盤掉入內(nèi)存，這種情況只需要把頁(yè)正確映射就可以了，而不需要在從硬盤調(diào)入，這是一種軟失效，稱為 次要缺頁(yè)錯(cuò)誤（minor page fault）。

基于上述情況，如果需要從硬盤直接調(diào)入頁(yè)面，這就是嚴(yán)重缺頁(yè)錯(cuò)誤（major page falut）。

還有一種情況是，程序可能訪問(wèn)了一個(gè)非法地址，根本無(wú)需向 TLB 中增加映射。此時(shí)，操作系統(tǒng)會(huì)報(bào)告一個(gè) 段錯(cuò)誤（segmentation fault） 來(lái)終止程序。只有第三種缺頁(yè)屬于程序錯(cuò)誤，其他缺頁(yè)情況都會(huì)被硬件或操作系統(tǒng)以降低程序性能為代價(jià)來(lái)修復(fù)

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

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

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

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

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

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

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

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

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

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

倒排頁(yè)表

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

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

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

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

頁(yè)面置換算法

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

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

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

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

下面我們就來(lái)探討一下有哪些頁(yè)面置換算法。

最優(yōu)頁(yè)面置換算法

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

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

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

最近未使用頁(yè)面置換算法

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

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

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

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

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

第 0 類：沒有引用 R，沒有修改 M

第 1 類：沒有引用 R，已修改 M

第 2 類：引用 R ，沒有修改 M

第 3 類：已被訪問(wèn) R，已被修改 M

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

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

先進(jìn)先出頁(yè)面置換算法

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

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

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

初始化的時(shí)候，沒有任何頁(yè)面，所以第一次的時(shí)候會(huì)檢查頁(yè)面 1 是否位于鏈表中，沒有在鏈表中，那么就是 MISS，頁(yè)面1 進(jìn)入鏈表，鏈表的先進(jìn)先出的方向如圖所示。

類似的，第二次會(huì)先檢查頁(yè)面 2 是否位于鏈表中，沒有在鏈表中，那么頁(yè)面 2 進(jìn)入鏈表，狀態(tài)為 MISS，依次類推。

我們來(lái)看第四次，此時(shí)的鏈表為 1 2 3，第四次會(huì)檢查頁(yè)面 2 是否位于鏈表中，經(jīng)過(guò)檢索后，發(fā)現(xiàn) 2 在鏈表中，那么狀態(tài)就是 HIT，并不會(huì)再進(jìn)行入隊(duì)和出隊(duì)操作，第五次也是一樣的。

下面來(lái)看第六次，此時(shí)的鏈表還是 1 2 3，因?yàn)橹皼]有執(zhí)行進(jìn)入鏈表操作，頁(yè)面 5 會(huì)首先進(jìn)行檢查，發(fā)現(xiàn)鏈表中沒有頁(yè)面 5 ，則執(zhí)行頁(yè)面 5 的進(jìn)入鏈表操作，頁(yè)面 2 執(zhí)行出鏈表的操作，執(zhí)行完成后的鏈表順序?yàn)?2 3 5。

第二次機(jī)會(huì)頁(yè)面置換算法

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

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

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

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

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

時(shí)鐘頁(yè)面置換算法

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

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

最近最少使用頁(yè)面置換算法

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

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

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

用軟件模擬 LRU

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

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

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

首先，在 R 位被添加進(jìn)來(lái)之前先把計(jì)數(shù)器右移一位；

第二步，R 位被添加到最左邊的位而不是最右邊的位。

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

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

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

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

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

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

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

工作集頁(yè)面置換算法

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

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

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

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

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

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

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

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

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

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

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

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

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

工作集時(shí)鐘頁(yè)面置換算法

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

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

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

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

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

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

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

至少調(diào)度了一次寫操作

沒有調(diào)度過(guò)寫操作

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

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

頁(yè)面置換算法小結(jié)

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

最優(yōu)算法在當(dāng)前頁(yè)面中置換最后要訪問(wèn)的頁(yè)面。不幸的是，沒有辦法來(lái)判定哪個(gè)頁(yè)面是最后一個(gè)要訪問(wèn)的，因此實(shí)際上該算法不能使用。然而，它可以作為衡量其他算法的標(biāo)準(zhǔn)。

NRU 算法根據(jù) R 位和 M 位的狀態(tài)將頁(yè)面氛圍四類。從編號(hào)最小的類別中隨機(jī)選擇一個(gè)頁(yè)面。NRU 算法易于實(shí)現(xiàn)，但是性能不是很好。存在更好的算法。

FIFO 會(huì)跟蹤頁(yè)面加載進(jìn)入內(nèi)存中的順序，并把頁(yè)面放入一個(gè)鏈表中。有可能刪除存在時(shí)間最長(zhǎng)但是還在使用的頁(yè)面，因此這個(gè)算法也不是一個(gè)很好的選擇。

第二次機(jī)會(huì)算法是對(duì) FIFO 的一個(gè)修改，它會(huì)在刪除頁(yè)面之前檢查這個(gè)頁(yè)面是否仍在使用。如果頁(yè)面正在使用，就會(huì)進(jìn)行保留。這個(gè)改進(jìn)大大提高了性能。

時(shí)鐘 算法是第二次機(jī)會(huì)算法的另外一種實(shí)現(xiàn)形式，時(shí)鐘算法和第二次算法的性能差不多，但是會(huì)花費(fèi)更少的時(shí)間來(lái)執(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è)可能是最重要的。