在上一篇介紹的幾種多道編程的內(nèi)存管理模式中，以交換內(nèi)存管理最為靈活和先進(jìn)。但是這種策略也存在很多重大問題，而其中最重要的兩個(gè)問題就是空間浪費(fèi)和程序大小受限。那么有什么辦法可以解決交換內(nèi)存存在的這些問題呢？答案是分頁，它是我們解決交換缺陷的“不二法門”。

一、分頁內(nèi)存管理

1.1 解決問題之道

　　為了解決交換系統(tǒng)存在的缺陷，分頁系統(tǒng)橫空出世。分頁系統(tǒng)的核心在于：將虛擬內(nèi)存空間和物理內(nèi)存空間皆劃分為大小相同的頁面，如4KB、8KB或16KB等，并以頁面作為內(nèi)存空間的最小分配單位，一個(gè)程序的一個(gè)頁面可以存放在任意一個(gè)物理頁面里。

　　（1）解決空間浪費(fèi)碎片化問題

　　由于將虛擬內(nèi)存空間和物理內(nèi)存空間按照某種規(guī)定的大小進(jìn)行分配，這里我們稱之為頁（Page），然后按照頁進(jìn)行內(nèi)存分配，也就克服了外部碎片的問題。

　　（2）解決程序大小受限問題

　　程序增長有限是因?yàn)橐粋€(gè)程序需要全部加載到內(nèi)存才能運(yùn)行，因此解決的辦法就是使得一個(gè)程序無須全部加載就可以運(yùn)行。使用分頁也可以解決這個(gè)問題，只需將當(dāng)前需要的頁面放在內(nèi)存里，其他暫時(shí)不用的頁面放在磁盤上，這樣一個(gè)程序同時(shí)占用內(nèi)存和磁盤，其增長空間就大大增加了。而且，分頁之后，如果一個(gè)程序需要更多的空間，給其分配一個(gè)新頁即可（而無需將程序倒出倒進(jìn)從而提高空間增長效率）。

1.2 虛擬地址的構(gòu)成與地址翻譯

　　（1）虛擬地址的構(gòu)成

　　在分頁系統(tǒng)下，一個(gè)程序發(fā)出的虛擬地址由兩部分組成：頁面號(hào)和頁內(nèi)偏移值，如下圖所示：

　　例如，對于32位尋址的系統(tǒng)，如果頁面大小為4KB，則頁面號(hào)占20位，頁內(nèi)偏移值占12位。

　　（2）地址翻譯：虛擬地址→物理地址

　　分頁系統(tǒng)的核心是頁面的翻譯，即從虛擬頁面到物理頁面的映射（Mapping）。該翻譯過程如下偽代碼所示：

if(虛擬頁面非法、不在內(nèi)存中或被保護(hù))
{
    陷入到操作系統(tǒng)錯(cuò)誤服務(wù)程序
}
else
{
    將虛擬頁面號(hào)轉(zhuǎn)換為物理頁面號(hào)
    根據(jù)物理頁面號(hào)產(chǎn)生最終物理地址
}

　　而這個(gè)翻譯過程由內(nèi)存管理單元（MMU）完成，MMU接收CPU發(fā)出的虛擬地址，將其翻譯為物理地址后發(fā)送給內(nèi)存。內(nèi)存管理單元按照該物理地址進(jìn)行相應(yīng)訪問后讀出或?qū)懭胂嚓P(guān)數(shù)據(jù)，如下圖所示：

　　那么，這個(gè)翻譯是怎么實(shí)現(xiàn)的呢？答案是查頁表，對于每個(gè)程序，內(nèi)存管理單元MMU都為其保存一個(gè)頁表，該頁表中存放的是虛擬頁面到物理頁面的映射。每當(dāng)為一個(gè)虛擬頁面尋找到一個(gè)物理頁面之后，就在頁表里增加一條記錄來保留該映射關(guān)系。當(dāng)然，隨著虛擬頁面進(jìn)出物理內(nèi)存，頁表的內(nèi)容也會(huì)不斷更新變化。

1.3 頁表

　　頁表的根本功能是提供從虛擬頁面到物理頁面的映射。因此，頁表的記錄條數(shù)與虛擬頁面數(shù)相同。此外，內(nèi)存管理單元依賴于頁表來進(jìn)行一切與頁面有關(guān)的管理活動(dòng)，這些活動(dòng)包括判斷某一頁面號(hào)是否在內(nèi)存里，頁面是否受到保護(hù)，頁面是否非法空間等等。

　　頁表的一個(gè)記錄所包括的內(nèi)容如下圖所示：

　　由于頁表的特殊地位，決定了它是由硬件直接提供支持，即頁表是一個(gè)硬件數(shù)據(jù)結(jié)構(gòu)。

1.4 分頁系統(tǒng)的優(yōu)缺點(diǎn)

　　優(yōu)點(diǎn)：

　　（1）分頁系統(tǒng)不會(huì)產(chǎn)生外部碎片，一個(gè)進(jìn)程占用的內(nèi)存空間可以不是連續(xù)的，并且一個(gè)進(jìn)程的虛擬頁面在不需要的時(shí)候可以放在磁盤中。

　　（2）分頁系統(tǒng)可以共享小的地址，即頁面共享。只需要在對應(yīng)給定頁面的頁表項(xiàng)里做一個(gè)相關(guān)的記錄即可。

　　缺點(diǎn)：頁表很大，占用了大量的內(nèi)存空間。

1.5 缺頁中斷處理

　　在分頁系統(tǒng)中，一個(gè)虛擬頁面既有可能在物理內(nèi)存，也有可能保存在磁盤上。如果CPU發(fā)出的虛擬地址對應(yīng)的頁面不在物理內(nèi)存，就將產(chǎn)生一個(gè)缺頁中斷，而缺頁中斷服務(wù)程序負(fù)責(zé)將需要的虛擬頁面找到并加載到內(nèi)存。缺頁中斷的處理步驟如下，省略了中間很多的步驟，只保留最核心的幾個(gè)步驟：

二、頁面置換算法

　　如果發(fā)生了缺頁中斷，就需要從磁盤上將需要的頁面調(diào)入內(nèi)存。如果內(nèi)存沒有多余的空間，就需要在現(xiàn)有的頁面中選擇一個(gè)頁面進(jìn)行替換。使用不同的頁面置換算法，頁面更換的順序也會(huì)各不相同。如果挑選的頁面是之后很快又要被訪問的頁面，那么系統(tǒng)將很開再次產(chǎn)生缺頁中斷，因?yàn)榇疟P訪問速度遠(yuǎn)遠(yuǎn)內(nèi)存訪問速度，缺頁中斷的代價(jià)是非常大的。因此，挑選哪個(gè)頁面進(jìn)行置換不是隨隨便便的事情，而是有要求的。

2.1 頁面置換的目標(biāo)

　　頁面置換時(shí)挑選頁面的目標(biāo)主要在于降低隨后發(fā)生缺頁中斷的次數(shù)或概率。

　　因此，挑選的頁面應(yīng)當(dāng)是隨后相當(dāng)長時(shí)間內(nèi)不會(huì)被訪問的頁面，最好是再也不會(huì)被訪問的頁面。BTW，如果可能，最好選擇一個(gè)沒有修改過的頁面，這樣替換時(shí)就無須將被替換頁面的內(nèi)容寫回磁盤，從而進(jìn)一步加快缺頁中斷的響應(yīng)速度。

　　所以，為了達(dá)到這個(gè)目的，先驅(qū)們設(shè)計(jì)出了各種各樣的頁面置換算法，下面就來看看這些算法。

2.2 隨機(jī)更換算法

　　在需要替換頁面的時(shí)候，產(chǎn)生一個(gè)隨機(jī)頁面號(hào)，從而替換與該頁面號(hào)對應(yīng)的物理頁面。遺憾的是，隨機(jī)選出的被替換的頁面不太可能是隨后相當(dāng)長時(shí)間內(nèi)不會(huì)被訪問的頁面。也就是說，這種算法難以保證最小化隨后的缺頁中斷次數(shù)。事實(shí)上，這種算法的效果相當(dāng)差。

2.3 先進(jìn)先出算法

　　顧名思義，先進(jìn)先出（FIFO，F(xiàn)irst In First Out）算法的核心是更換最早進(jìn)入內(nèi)存的頁面，其實(shí)現(xiàn)機(jī)制是使用鏈表將所有在內(nèi)存中的頁面按照進(jìn)入時(shí)間的早晚鏈接起來，然后每次置換鏈表頭上的頁面就行了，而新加進(jìn)來的頁面則掛在鏈表的末端，如下圖所示：

　　FIFO的優(yōu)點(diǎn)是簡單且容易實(shí)現(xiàn)，缺點(diǎn)是如果最先加載進(jìn)來的頁面是經(jīng)常被訪問的頁面，那么就可能造成被訪問的頁面替換到磁盤上，導(dǎo)致很快就需要再次發(fā)生缺頁中斷，從而降低效率。

2.4 第二次機(jī)會(huì)算法

　　由于FIFO只考慮進(jìn)入內(nèi)存的時(shí)間，不關(guān)心一個(gè)頁面被訪問的頻率，從而有可能造成替換掉一個(gè)被經(jīng)常訪問的頁面而造成效率低下。那么，可以對FIFO進(jìn)行改進(jìn)：在使用FIFO更換一個(gè)頁面時(shí)，需要看一下該頁面是否在最近被訪問過，如果沒有被訪問過，則替換該頁面。反之，如果最近被訪問過（通過檢查其訪問位的取值），則不替換該頁面，而是將該頁面掛到鏈表末端，并將該頁面進(jìn)入內(nèi)存的時(shí)間設(shè)置為當(dāng)前時(shí)間，并將其訪問位清零。這樣，對于最近被訪問過的頁面來說，相當(dāng)于給了它第二次機(jī)會(huì)。

　　例如，當(dāng)A頁面最近被訪問過，即其訪問位R的值為1，則使用第二次機(jī)會(huì)算法之后，鏈表的格局如下圖所示：

　　第二次機(jī)會(huì)算法簡單、公平且容易實(shí)現(xiàn)。但是，每次給予一個(gè)頁面第二次機(jī)會(huì)時(shí)，將其移動(dòng)到鏈表末端需要耗費(fèi)時(shí)間。此外，頁面的訪問位只在頁面替換進(jìn)行掃描時(shí)才可能清零，所以其時(shí)間局域性體現(xiàn)得不好，訪問位為1的頁面可能是很久以前訪問的，時(shí)間上的分辨粒度太粗，從而影響頁面替換的效果。

2.5 時(shí)鐘算法

　　為了改善第二次機(jī)會(huì)算法的缺點(diǎn)，先驅(qū)們提出了時(shí)鐘算法。時(shí)鐘算法的核心思想是：將頁面排成一個(gè)時(shí)鐘的形狀，該時(shí)鐘有一個(gè)針臂，每次需要更換頁面時(shí)，我們從針臂所指的頁面開始檢查。如果當(dāng)前頁面的訪問位為0，即從上次檢查到這次，該頁面沒有被訪問過，將該頁面替換。反之，就將其訪問位清零，并順時(shí)針移動(dòng)指針到下一個(gè)頁面。重復(fù)這些步驟，直到找到一個(gè)訪問位為0的頁面。

　　例如下圖所示的一個(gè)時(shí)鐘，指針指向的頁面是F，因此第一個(gè)被考慮替換的頁面是F。如果頁面F的訪問位為0，F(xiàn)將被替換。如果F的訪問位為1，則F的訪問位清零，指針移動(dòng)到頁面G。

　　從表面上看，它和第二次機(jī)會(huì)算法類似，都是訪問位為0就更換，反之則再給一次機(jī)會(huì)。但是，它和第二次機(jī)會(huì)算法還是有幾點(diǎn)不同：

　　（1）他們的數(shù)據(jù)結(jié)構(gòu)不一樣，第二次機(jī)會(huì)使用的是鏈表，時(shí)鐘算法使用的是索引（整數(shù)指針）。這樣，其使用的內(nèi)存空間不一樣。

　　（2）第二次機(jī)會(huì)需要使用額外的內(nèi)存，而時(shí)鐘算法可以直接使用頁表。使用頁表的好處是無需額外的空間，更大的好處是頁面的訪問位會(huì)定期自動(dòng)清零，這樣將使得時(shí)鐘算法的時(shí)間分辨粒度較第二次機(jī)會(huì)算法高，從而取得更好的頁面替換效果。

　　時(shí)鐘算法的精髓是第二次機(jī)會(huì)，其缺點(diǎn)也就和第二次機(jī)會(huì)算法一樣：過于公平，沒有考慮到不同頁面調(diào)用頻率的不同，有可能換出不應(yīng)該或不能換出的頁面，還可能造成無限循環(huán)。

PS：至此，隨機(jī)、FIFO、第二次機(jī)會(huì)與時(shí)鐘算法的介紹就到此結(jié)束，這四種算法都是屬于“公平算法”，即所有的頁面都或多或少地給予公平待遇，沒有頁面獲得特殊待遇。但是這種公平實(shí)現(xiàn)方式，會(huì)使效率受到一定影響，這時(shí)因?yàn)閭€(gè)體對于整個(gè)系統(tǒng)的貢獻(xiàn)沒有被區(qū)別對待，造成貢獻(xiàn)大的和貢獻(xiàn)小的待遇一樣，自然會(huì)影響整個(gè)系統(tǒng)的效率。

2.6 最優(yōu)更換算法

　　我們知道，最理想的頁面替換算法是選擇一個(gè)再也不會(huì)被訪問的頁面進(jìn)行替換。如果不存在這樣的頁面，那至少選擇一個(gè)在隨后最長時(shí)間內(nèi)不會(huì)被訪問的頁面進(jìn)行替換。這樣，我們就可以保證在隨后發(fā)生缺頁中斷的次數(shù)最小或概率最低，這種算法就是最有替換算法。

　　但是，我們沒法知道一個(gè)頁面隨后多長時(shí)間不會(huì)被訪問，因此最優(yōu)更換算法在實(shí)際中沒法實(shí)現(xiàn)，那么為什么要介紹最有更換算法呢？這是為了定義一個(gè)標(biāo)桿，以此來評(píng)判其他算法的優(yōu)劣。

2.7 NRU（最近未被使用）算法

　　顧名思義，NRU就是選擇一個(gè)在最近一段時(shí)間內(nèi)沒有被訪問過的頁面進(jìn)行替換，這是基于程序訪問的時(shí)空局域性。因?yàn)楦鶕?jù)時(shí)空局域性原理，一個(gè)最近沒有被訪問的頁面，在隨后的時(shí)間里也不太可能被訪問，而NRU的實(shí)現(xiàn)方式就是利用頁面的訪問和修改位。

　　每個(gè)頁面都有一個(gè)訪問位和一個(gè)修改位，凡是對頁面進(jìn)行讀寫操作時(shí)，訪問位被設(shè)置為1。當(dāng)進(jìn)程對頁面進(jìn)行讀寫操作時(shí)，修改位設(shè)置為1。根據(jù)這兩個(gè)位的狀態(tài)來對頁面進(jìn)行分類的話，可以分成以下四種頁面類型：1、2、3、4。

　　有了這個(gè)分類，NRU算法就按照這四類頁面的順序依次尋找可以替換的頁面。如果所有頁面皆被訪問和修改過，那也只能從中替換掉一個(gè)頁面，因此NRU算法總是會(huì)終結(jié)的。

　　當(dāng)然，這種分類比較籠統(tǒng)，在同一類頁面里，我們沒有辦法分辨出哪一類被訪問的時(shí)間更近一些。即在某些情況下，我們替換的可能并不是最近沒有被使用的頁面。

2.8 LRU（最近最少使用）算法

　　與NRU算法相比，LRU算法不僅考慮最近是否用過，還要考慮最近使用的頻率。這里是基于過去的數(shù)據(jù)預(yù)測未來：如果一個(gè)頁面被訪問的頻率低，那么以后很可能也用不到。

　　LRU算法的實(shí)現(xiàn)必須以某種方式記錄每個(gè)頁面被訪問的次數(shù)，這是個(gè)相當(dāng)大的工作量。最簡單的方式就是在頁表的記錄項(xiàng)里增加一個(gè)計(jì)數(shù)域，一個(gè)頁面被訪問一次，這個(gè)計(jì)數(shù)器的值就增加1。于是，當(dāng)需要更換頁面時(shí)，只需要找到計(jì)數(shù)域值最小的頁面替換即可，該頁面即是最近最少使用的頁面。另一種簡單實(shí)現(xiàn)方式就是用一個(gè)鏈表將所有頁面鏈接起來，最近被使用的頁面在鏈表頭，最近未被使用的放在鏈表尾。在每次頁面訪問時(shí)對這個(gè)鏈表進(jìn)行更新，使其保持最近被使用的頁面在鏈表頭。

　　LRU算法雖然很好，但是實(shí)現(xiàn)成本高（需要分辨出不同頁面中哪個(gè)頁面時(shí)最近最少使用的），并且時(shí)間代價(jià)大（每次頁面訪問發(fā)生時(shí)都需要更新記錄）。因此，一般的商業(yè)操作系統(tǒng)都沒有采納LRU頁面更新算法。

2.9 工作集算法

　　由于不可能精確地確定那個(gè)頁面是最近最少使用的，那就干脆不花費(fèi)這個(gè)力氣，只維持少量的信息使得我們選出的替換頁面不太可能是馬上又會(huì)使用的頁面即可。這種少量的信息就是工作集信息。

　　工作集概念來源于程序訪問的時(shí)空局限性，即在一段時(shí)間內(nèi)，程序訪問的頁面將局限在一組頁面集合上。例如，最近k次訪問均發(fā)生在某m個(gè)頁面上，那么m就是參數(shù)為k時(shí)的工作集。我們用w(k,t)來表示在時(shí)間t時(shí)k次訪問所涉及的頁面數(shù)量。

　　顯然，隨著k的增長，w(k,t)的值也隨之增長；但是當(dāng)k增長到某個(gè)數(shù)值之后，w(k,t)的值將增長極其緩慢甚至接近停滯，并維持一段時(shí)間的穩(wěn)定，如下圖所示：

　　由上圖可以看出，如果一個(gè)程序在內(nèi)存里面的頁面數(shù)與其工作集大小相等或者超過工作集，則該程序可在一段時(shí)間內(nèi)不會(huì)發(fā)生缺頁中斷。如果其在內(nèi)存的頁面數(shù)小于工作集，則發(fā)生缺頁中斷的頻率將增加，甚至發(fā)生內(nèi)存抖動(dòng)。

　　因此，工作計(jì)算法的目標(biāo)就是維持當(dāng)前的工作集的頁面在物理內(nèi)存里面。每次頁面更換時(shí)，尋找一個(gè)不屬于當(dāng)前工作集的頁面替換即可。這樣，我們再尋找頁面時(shí)只需要將頁面分離為兩大類即可：當(dāng)前工作集內(nèi)頁面和當(dāng)前工作集外頁面。如此，只要找到一個(gè)飛當(dāng)前工作集的頁面，將其替換即可。

　　工作集算法的優(yōu)點(diǎn)：實(shí)現(xiàn)簡單，只需要在頁表的每個(gè)記錄增加一個(gè)虛擬時(shí)間域即可。而且，這個(gè)時(shí)間域不是每次發(fā)生訪問時(shí)都需要更新，而是在需要更換頁面時(shí)，頁面更換算法對其進(jìn)行修改，因此時(shí)間成本也不大。

　　工作集算法的缺點(diǎn)：每次掃描頁面進(jìn)行替換時(shí)，有可能需要掃描整個(gè)頁表。然而，并不是所有頁面都內(nèi)存里，因此掃描過程中的一大部分時(shí)間將是無用功。另外，由于其數(shù)據(jù)結(jié)構(gòu)是線性的，會(huì)造成每次都按同樣的順序進(jìn)行掃描，顯得不太公平。

2.10 工作集時(shí)鐘算法

　　鑒于工作集算法的缺點(diǎn)，先驅(qū)們將工作集算法與時(shí)鐘算法結(jié)合起來，設(shè)計(jì)出了工作集時(shí)鐘算法，即使用工作集算法的原理，但是將頁面的掃描順序按照時(shí)鐘的形式組織起來。這樣每次需要替換頁面時(shí)，從指針指向的頁面開始掃描，從而達(dá)到更加公平的狀態(tài)。而且，按時(shí)鐘組織的頁面只是在內(nèi)存里面的頁面，在內(nèi)存外的頁面不放在時(shí)鐘圈里，從而提高實(shí)現(xiàn)效率。

　　鑒于其時(shí)間與空間上的優(yōu)勢，工作集時(shí)鐘算法被大多商業(yè)操作系統(tǒng)所采納。

參考資料

鄒恒明，《操作系統(tǒng)之哲學(xué)原理》，機(jī)械工業(yè)出版社