在當(dāng)今數(shù)字化時(shí)代，隨著軟件應(yīng)用的不斷發(fā)展和功能的日益強(qiáng)大，它們對(duì)內(nèi)存的需求也在持續(xù)攀升。無(wú)論是運(yùn)行大型數(shù)據(jù)庫(kù)管理系統(tǒng)、進(jìn)行復(fù)雜的數(shù)據(jù)分析和人工智能模型訓(xùn)練，還是暢玩精美的 3A 游戲，內(nèi)存的重要性愈發(fā)凸顯。就拿一款熱門(mén)的 3A 游戲來(lái)說(shuō)，在高畫(huà)質(zhì)和高分辨率的設(shè)置下，其運(yùn)行時(shí)所占用的內(nèi)存輕松就能達(dá)到十幾 GB。而對(duì)于那些進(jìn)行大數(shù)據(jù)分析的專(zhuān)業(yè)軟件，在處理海量數(shù)據(jù)時(shí)，對(duì)內(nèi)存的渴望更是強(qiáng)烈，幾十 GB 的內(nèi)存占用也并不罕見(jiàn)。

在 Linux 操作系統(tǒng)中，內(nèi)存管理是一項(xiàng)至關(guān)重要的任務(wù)，而其中的頁(yè)交換算法則是內(nèi)存管理的核心關(guān)鍵。它就像是一位精明的管家，在物理內(nèi)存資源有限的情況下，巧妙地協(xié)調(diào)內(nèi)存的使用，確保系統(tǒng)能夠高效穩(wěn)定地運(yùn)行。當(dāng)系統(tǒng)內(nèi)存緊張時(shí)，頁(yè)交換算法能夠精準(zhǔn)地決定哪些內(nèi)存頁(yè)面需要被暫時(shí)轉(zhuǎn)移到磁盤(pán)的交換空間中，以便為更急需內(nèi)存的程序騰出空間。而當(dāng)這些被轉(zhuǎn)移的頁(yè)面再次被需要時(shí)，它又能迅速將其從交換空間中取回，重新加載到物理內(nèi)存里。

頁(yè)交換算法的優(yōu)劣，直接關(guān)系到整個(gè)系統(tǒng)的性能表現(xiàn)。一個(gè)高效的頁(yè)交換算法，能夠讓系統(tǒng)在內(nèi)存緊張的情況下依然保持流暢的運(yùn)行，大大減少程序的卡頓現(xiàn)象，提升用戶的使用體驗(yàn)。相反，如果頁(yè)交換算法不夠理想，系統(tǒng)可能會(huì)頻繁地進(jìn)行頁(yè)面交換操作，導(dǎo)致磁盤(pán) I/O 負(fù)載過(guò)高，進(jìn)而使系統(tǒng)運(yùn)行變得遲緩，甚至出現(xiàn)死機(jī)的情況。在服務(wù)器環(huán)境中，這可能會(huì)導(dǎo)致服務(wù)中斷，給企業(yè)帶來(lái)嚴(yán)重的損失；在個(gè)人電腦上，也會(huì)讓用戶感到煩躁和不滿。那么，Linux 內(nèi)核中的頁(yè)交換算法究竟是如何工作的呢？它又有著怎樣的奧秘和獨(dú)特之處？接下來(lái)，就讓我們一同深入探索 Linux 內(nèi)核頁(yè)交換算法的奇妙世界，揭開(kāi)它神秘的面紗。

一、頁(yè)交換算法概述

在Linux操作系統(tǒng)中，當(dāng)內(nèi)存充足時(shí)，內(nèi)核會(huì)盡量多地使用內(nèi)存作為文件緩存（page cache）， 從而提高系統(tǒng)的性能。文件緩存頁(yè)面會(huì)添加到文件類(lèi)型的LRU鏈表中；當(dāng)內(nèi)存緊張時(shí)，文件緩存頁(yè)面會(huì)被丟棄，或者把修改的文件緩存頁(yè)面回寫(xiě)到存儲(chǔ)設(shè)備中，與塊設(shè)備同步之后便可釋放出物理內(nèi)存?，F(xiàn)在的應(yīng)用程序轉(zhuǎn)向內(nèi)存密集型，無(wú)論系統(tǒng)中有多少物理內(nèi)存都是不夠用的，因此Linux操作系統(tǒng)會(huì)使用存儲(chǔ)設(shè)備作為交換分區(qū)，內(nèi)核將很少使用的內(nèi)存換出到交換分區(qū)，以便釋放出物理內(nèi)存，這個(gè)機(jī)制稱(chēng)為頁(yè)交換（swapping），這些處理機(jī)制統(tǒng)稱(chēng)為頁(yè)面回收（page reclaim）。

在最近幾十年操作系統(tǒng)的發(fā)展過(guò)程中，出現(xiàn)了很多頁(yè)面交換算法，其中每個(gè)算法都有各自的優(yōu)點(diǎn)和缺點(diǎn)。Linux內(nèi)核中采用的頁(yè)交換算法主要是經(jīng)典LRU鏈表算法和第二次機(jī)會(huì)（second chance）法。

(1)頁(yè)面置換過(guò)程——頁(yè)面置換的工作流程如圖所示，主要包括以下4個(gè)步驟：

• 第1步：找出所需頁(yè)面在磁盤(pán)上的位置。
• 第2步：找出一個(gè)空閑內(nèi)存塊。如果有空閑塊，就用它；如果沒(méi)有空閑塊，就用頁(yè)面置換算法選擇一個(gè)可置換的內(nèi)存塊，把該頁(yè)寫(xiě)到磁盤(pán)上，并相應(yīng)地修改頁(yè)表和存儲(chǔ)塊表。
• 第3步：把所需頁(yè)面讀入剛剛得到的內(nèi)存空閑塊，修改頁(yè)表和存儲(chǔ)塊表。
• 第4步：重新啟動(dòng)該用戶進(jìn)程。

(2)頁(yè)面走向

置換算法的好壞直接影響系統(tǒng)的性能。若采用的置換算法不合適，可能出現(xiàn)這樣的現(xiàn)象：剛被換出的頁(yè)，很快又被訪問(wèn)，為把它調(diào)入而換出另一頁(yè)，之后又訪問(wèn)剛被換出的頁(yè)，……如此頻繁地更換頁(yè)面，以致系統(tǒng)的大部分時(shí)間花費(fèi)在頁(yè)面的調(diào)度和傳輸上。此時(shí)，系統(tǒng)好像很忙，但實(shí)際效率卻很低。這種現(xiàn)象稱(chēng)為“抖動(dòng)”。

好的頁(yè)面置換算法能夠適當(dāng)降低頁(yè)面更換頻率（減少缺頁(yè)率），盡量避免系統(tǒng)“抖動(dòng)”。

為評(píng)價(jià)一個(gè)算法的優(yōu)劣，可將該算法應(yīng)用于一個(gè)特定的存儲(chǔ)訪問(wèn)序列（也叫頁(yè)面走向）上，并且計(jì)算缺頁(yè)數(shù)量。

二、Linux 內(nèi)存管理基礎(chǔ)

2.1內(nèi)存管理的重要性

內(nèi)存管理，作為操作系統(tǒng)的關(guān)鍵核心功能，對(duì)于系統(tǒng)的穩(wěn)定高效運(yùn)行而言，有著舉足輕重的意義，其主要任務(wù)涵蓋內(nèi)存分配、回收、保護(hù)等多個(gè)重要方面。

在內(nèi)存分配方面，當(dāng)一個(gè)新的程序啟動(dòng)時(shí)，操作系統(tǒng)需要為其精準(zhǔn)地分配足夠的內(nèi)存空間，以確保程序能夠順利加載并運(yùn)行。這就好比在一座大型寫(xiě)字樓里，為每一家新入駐的公司合理分配辦公場(chǎng)地，讓它們能夠正常開(kāi)展業(yè)務(wù)。如果內(nèi)存分配不合理，比如分配的內(nèi)存過(guò)小，程序可能無(wú)法完整加載，導(dǎo)致運(yùn)行出錯(cuò)；而分配過(guò)大，則會(huì)造成內(nèi)存資源的浪費(fèi)，就像給一家小型創(chuàng)業(yè)公司分配了一個(gè)超大的辦公區(qū)域，卻有大量空間閑置。

內(nèi)存回收同樣不可或缺。當(dāng)程序運(yùn)行結(jié)束或者不再需要某些內(nèi)存空間時(shí)，操作系統(tǒng)必須及時(shí)將這些內(nèi)存回收，以便重新分配給其他有需求的程序。這類(lèi)似于寫(xiě)字樓里的公司退租后，物業(yè)要及時(shí)清理場(chǎng)地，重新出租給新的租戶。若內(nèi)存回收不及時(shí)，就會(huì)出現(xiàn)內(nèi)存泄漏的問(wèn)題，隨著時(shí)間的推移，系統(tǒng)可用內(nèi)存會(huì)越來(lái)越少，最終導(dǎo)致系統(tǒng)性能?chē)?yán)重下降，甚至崩潰。

內(nèi)存保護(hù)則是保障系統(tǒng)安全穩(wěn)定運(yùn)行的重要防線。它能防止不同程序之間的內(nèi)存相互干擾和非法訪問(wèn)，確保每個(gè)程序只能在自己被分配的內(nèi)存空間內(nèi)進(jìn)行操作。這就如同寫(xiě)字樓里的每家公司都有自己獨(dú)立的辦公區(qū)域，彼此之間不能隨意闖入和破壞，保證了各個(gè)公司的正常運(yùn)作和數(shù)據(jù)安全。如果沒(méi)有內(nèi)存保護(hù)機(jī)制，一個(gè)惡意程序可能會(huì)隨意修改其他程序的內(nèi)存數(shù)據(jù)，導(dǎo)致其他程序運(yùn)行出錯(cuò)，甚至整個(gè)系統(tǒng)癱瘓。

2.2Linux 內(nèi)存管理的特點(diǎn)

與其他操作系統(tǒng)相比，Linux 內(nèi)存管理在靈活性、高效性和對(duì)硬件的適應(yīng)性等方面展現(xiàn)出了顯著的特點(diǎn) 。

Linux 內(nèi)存管理的靈活性體現(xiàn)在多個(gè)方面。它支持多種內(nèi)存分配策略，能夠根據(jù)不同的應(yīng)用場(chǎng)景和需求，選擇最合適的分配方式。在一些對(duì)內(nèi)存使用效率要求極高的科學(xué)計(jì)算應(yīng)用中，Linux 可以采用特定的內(nèi)存分配策略，減少內(nèi)存碎片的產(chǎn)生，提高內(nèi)存的利用率。同時(shí)，Linux 還允許用戶根據(jù)自己的需求對(duì)內(nèi)存管理進(jìn)行定制和優(yōu)化，用戶可以通過(guò)修改內(nèi)核參數(shù)等方式，調(diào)整內(nèi)存管理的行為，以滿足特定的業(yè)務(wù)需求。

高效性也是 Linux 內(nèi)存管理的一大亮點(diǎn)。它采用了先進(jìn)的內(nèi)存管理算法，能夠快速地進(jìn)行內(nèi)存分配和回收操作，減少系統(tǒng)的開(kāi)銷(xiāo)。在處理大量并發(fā)進(jìn)程時(shí)，Linux 的內(nèi)存管理系統(tǒng)能夠迅速為每個(gè)進(jìn)程分配所需的內(nèi)存，并且在進(jìn)程結(jié)束后及時(shí)回收內(nèi)存，使得系統(tǒng)能夠高效地處理多任務(wù)。Linux 還通過(guò)內(nèi)存緩存等技術(shù)，提高了數(shù)據(jù)的訪問(wèn)速度，進(jìn)一步提升了系統(tǒng)的整體性能。例如，它會(huì)將經(jīng)常訪問(wèn)的數(shù)據(jù)緩存到內(nèi)存中，當(dāng)再次訪問(wèn)這些數(shù)據(jù)時(shí)，就可以直接從內(nèi)存中讀取，而無(wú)需從速度較慢的磁盤(pán)中讀取，大大提高了數(shù)據(jù)的讀取效率。

Linux 內(nèi)存管理對(duì)硬件的適應(yīng)性也非常出色，它能夠很好地支持各種不同類(lèi)型的硬件平臺(tái)，無(wú)論是常見(jiàn)的 x86 架構(gòu)，還是 ARM、PowerPC 等架構(gòu)，Linux 都能充分發(fā)揮硬件的性能優(yōu)勢(shì)，實(shí)現(xiàn)高效的內(nèi)存管理。在嵌入式設(shè)備中，由于硬件資源有限，Linux 可以根據(jù)設(shè)備的具體硬件配置，靈活地調(diào)整內(nèi)存管理策略，確保系統(tǒng)在有限的內(nèi)存條件下穩(wěn)定運(yùn)行。對(duì)于具有不同內(nèi)存大小和特性的硬件，Linux 能夠自動(dòng)識(shí)別并進(jìn)行優(yōu)化，以達(dá)到最佳的內(nèi)存使用效果。

2.3頁(yè)交換算法原理

頁(yè)交換算法的設(shè)計(jì)和實(shí)現(xiàn)，緊密依賴于局部性原理。局部性原理包含時(shí)間局部性和空間局部性兩個(gè)重要方面 。

時(shí)間局部性指的是，在程序運(yùn)行過(guò)程中，如果一個(gè)數(shù)據(jù)項(xiàng)在某個(gè)時(shí)刻被訪問(wèn)，那么在不久的將來(lái)，它很可能會(huì)再次被訪問(wèn)。例如，在一個(gè)循環(huán)結(jié)構(gòu)的程序中，循環(huán)變量會(huì)在每次循環(huán)時(shí)被頻繁訪問(wèn)，這就體現(xiàn)了時(shí)間局部性。假設(shè)一個(gè)程序中有一個(gè)循環(huán)，用于計(jì)算數(shù)組中所有元素的總和，循環(huán)變量 i 在每次循環(huán)中都會(huì)被訪問(wèn)，而且在整個(gè)循環(huán)執(zhí)行期間，i 會(huì)被多次重復(fù)訪問(wèn)，這就是時(shí)間局部性的典型表現(xiàn)。

空間局部性則是說(shuō)，如果一個(gè)數(shù)據(jù)項(xiàng)的地址被訪問(wèn)，那么與它在空間位置上臨近的數(shù)據(jù)項(xiàng)的地址，很可能也會(huì)在不久之后被訪問(wèn)。這是因?yàn)槌绦蛟谠L問(wèn)內(nèi)存時(shí)，通常會(huì)按照一定的順序進(jìn)行。比如，在訪問(wèn)一個(gè)數(shù)組時(shí)，程序會(huì)依次訪問(wèn)數(shù)組中的各個(gè)元素，這些元素在內(nèi)存中是連續(xù)存儲(chǔ)的，訪問(wèn)了一個(gè)元素后，下一個(gè)被訪問(wèn)的元素大概率是與之相鄰的元素，這體現(xiàn)了空間局部性。例如，有一個(gè)包含 100 個(gè)整數(shù)的數(shù)組，當(dāng)程序訪問(wèn)數(shù)組的第 5 個(gè)元素時(shí)，接下來(lái)很可能會(huì)訪問(wèn)第 6 個(gè)、第 7 個(gè)等相鄰的元素。

基于局部性原理，頁(yè)交換算法在選擇置換頁(yè)面時(shí)，會(huì)重點(diǎn)關(guān)注頁(yè)面的訪問(wèn)頻率和訪問(wèn)時(shí)間。對(duì)于那些長(zhǎng)時(shí)間沒(méi)有被訪問(wèn)，或者訪問(wèn)頻率極低的頁(yè)面，算法會(huì)認(rèn)為它們?cè)谖磥?lái)一段時(shí)間內(nèi)被訪問(wèn)的可能性也較小，從而將這些頁(yè)面作為優(yōu)先置換的對(duì)象。這樣，就可以確保物理內(nèi)存中始終保留著那些最有可能被頻繁訪問(wèn)的頁(yè)面，提高內(nèi)存的使用效率，減少頁(yè)面置換的次數(shù)，進(jìn)而提升系統(tǒng)的整體性能。如果一個(gè)程序在運(yùn)行過(guò)程中，某個(gè)頁(yè)面已經(jīng)很長(zhǎng)時(shí)間沒(méi)有被訪問(wèn)了，根據(jù)局部性原理，這個(gè)頁(yè)面在未來(lái)短時(shí)間內(nèi)被訪問(wèn)的概率相對(duì)較低，頁(yè)交換算法就會(huì)考慮將這個(gè)頁(yè)面置換到磁盤(pán)交換分區(qū)，為更需要內(nèi)存的頁(yè)面騰出空間 。

三、最佳置換算法（OPT）

最佳置換算法，其所選擇的被淘汰的頁(yè)面將是以后永不使用的，或是在最長(zhǎng)（未來(lái)）時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面。采用最佳置換算法通?？杀ＷC最低的缺頁(yè)率。但是人們目前還無(wú)法與之，一個(gè)進(jìn)程在內(nèi)存的若干個(gè)頁(yè)面中，哪一個(gè)頁(yè)面是未來(lái)最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的，因而該算法是無(wú)法實(shí)現(xiàn)的，但是可以利用該算法取評(píng)價(jià)其他的算法。

(1)算法思想

舉例如下：

我們將頁(yè)面隊(duì)列存在一個(gè)Vector動(dòng)態(tài)數(shù)組中。我們可以從圖中得知：當(dāng)發(fā)生頁(yè)面置換時(shí)，就要尋找在未來(lái)最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面，將其置換出去，比如當(dāng)內(nèi)存中存在的頁(yè)面為 7、0、1,且要訪問(wèn)頁(yè)面2時(shí)，此時(shí)我們要尋找頁(yè)面隊(duì)列中將要訪問(wèn)到的頁(yè)面2以后的頁(yè)面隊(duì)列（0、3、0、4、2、3、0、3、2、1、2、0、1、7、0、1）中，頁(yè)面7、0、1哪個(gè)最久未被訪問(wèn)到，即尋找頁(yè)面7、0、1在以后的隊(duì)列中第一次出現(xiàn)的這三個(gè)頁(yè)面的下標(biāo)值最大的那一個(gè)。因?yàn)轫?yè)面7在后面的頁(yè)面隊(duì)列中再次被訪問(wèn)到是數(shù)組中下標(biāo)為17的地方,頁(yè)面0再次被訪問(wèn)到是數(shù)組下標(biāo)為4的地方，頁(yè)面1再次被訪問(wèn)的是數(shù)組中下標(biāo)為13,所以頁(yè)面7是未來(lái)最久才被訪問(wèn)的頁(yè)面，所以將頁(yè)面7置換出去，將頁(yè)面2調(diào)入內(nèi)存中。

具體算法：每個(gè)頁(yè)面都有兩個(gè)屬性，一個(gè)是頁(yè)面號(hào)id，一個(gè)是時(shí)間參數(shù)count（此屬性在LRU中才會(huì)用到）

//pageId 要調(diào)入內(nèi)存的頁(yè)面號(hào)
//currentPoint 記錄當(dāng)前將要調(diào)入內(nèi)存中頁(yè)面所在頁(yè)面隊(duì)列中的下標(biāo)號(hào)
void OPT::replace(int pageId, int currentPoint)
{
    //cur為內(nèi)存塊下標(biāo),searchCounter紀(jì)錄是否內(nèi)存塊搜索完畢
    //循環(huán)爆出最長(zhǎng)為使用的頁(yè)面
    int max = 0, perCount, outPageId = -1, cur = 0;
    int search_count[PRO_MEMORY];

    for (int i = 0; i < PRO_MEMORY; i++)
    {
    //比如，從頁(yè)面2后面的頁(yè)面開(kāi)始掃描記錄頁(yè)面7、0、1再次被訪問(wèn)的數(shù)組的下標(biāo)號(hào)
        for (int j = currentPoint + 1; j < length; j++)
        {
            if (pages_OPT[i].getId() == usePageNumList_OPT[j])
            {
                search_count[i] = j;
                break;
            }
        }
        if (search_count[i] == 0)
        {
            search_count[i] = length;
        }
    }
    //以上面內(nèi)存中存在的是頁(yè)面7、0、1為例。尋找頁(yè)面7、0、1再次被訪問(wèn)的下標(biāo)號(hào)最大的    //哪個(gè)頁(yè)面
    for (int k = 0; k < PRO_MEMORY; ++k)
    {
        perCount = search_count[k];
        if (max < perCount)
        {
            max = perCount;
            cur = k;
        }
    }

    outPageId = pages_OPT[cur].getId();

    pages_OPT[cur].setId(pageId);
    cout << "頁(yè)號(hào)ID：" << pageId << "正在放入內(nèi)存，頁(yè)號(hào)ID：" << outPageId << "被替換出去" << endl;
    ofs_OPT << "頁(yè)號(hào)ID：" << pageId << "正在放入內(nèi)存，頁(yè)號(hào)ID：" << outPageId << "被替換出去\n";
}

運(yùn)行結(jié)果截圖：

四、先進(jìn)先出法(FINO)

頁(yè)面替換算法是操作系統(tǒng)中用于解決內(nèi)存不足的問(wèn)題的一種算法。在實(shí)現(xiàn)時(shí)，可將內(nèi)存在等大塊，稱(chēng)作頁(yè)面，將進(jìn)程所需的內(nèi)存也分成等大的塊，即頁(yè)，當(dāng)進(jìn)程訪問(wèn)一個(gè)新頁(yè)時(shí)，若內(nèi)存已滿，則需要選擇一個(gè)已駐留的頁(yè)，將其后備存儲(chǔ)設(shè)備中的內(nèi)容讀入內(nèi)存中，以使新頁(yè)能夠進(jìn)入內(nèi)存。頁(yè)面替換算法中的「組 2」指的是先進(jìn)先出算法（FIFO）。

這是最簡(jiǎn)單的頁(yè)面替換算法。在該算法中，操作系統(tǒng)跟蹤隊(duì)列中內(nèi)存中的所有頁(yè)面，最舊的頁(yè)面在隊(duì)列的前面。當(dāng)一個(gè)頁(yè)面需要被替換時(shí)，隊(duì)列前面的頁(yè)面被選中進(jìn)行刪除。

示例-1?？紤]頁(yè)面引用字符串1、3、0、3、5、6 和 3 頁(yè)槽。

最初所有的槽都是空的，所以當(dāng) 1、3、0 到來(lái)時(shí)，它們被分配到空槽——> 3頁(yè)錯(cuò)誤。 當(dāng) 3 出現(xiàn)時(shí)，它已經(jīng)在內(nèi)存中，所以 —> 0 Page Faults。然后是 5，它在內(nèi)存中不可用，因此它替換了最舊的頁(yè)槽，即 1?！?gt;1頁(yè)錯(cuò)誤。 最后是 6，它在內(nèi)存中也不可用，因此它替換了最舊的頁(yè)槽，即 3 —>1頁(yè)錯(cuò)誤。

(1)算法實(shí)現(xiàn)

FIFO 算法簡(jiǎn)單易懂，實(shí)現(xiàn)方便。它基于隊(duì)列數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)，將最先進(jìn)入隊(duì)列的頁(yè)面置換出去，以便騰出空間給新頁(yè)面使用。這里給出 FIFO 頁(yè)面替換算法的示例代碼

#include <iostream>
#include <queue>
using namespace std;

int FIFO(int pages[], int n, int capacity) {
    queue<int> pageQueue; // 用于存儲(chǔ)頁(yè)面的隊(duì)列
    int pageFaults = 0; // 頁(yè)面錯(cuò)誤次數(shù)

    for (int i = 0; i < n; i++) {
        if (pageQueue.size() < capacity) { // 隊(duì)列未滿時(shí)直接插入頁(yè)面
            if (!pageQueue.empty() && pageQueue.front() == pages[i]) {
                continue;
            }
            pageQueue.push(pages[i]);
            pageFaults++;
        } else { // 隊(duì)列已滿，進(jìn)行頁(yè)面替換
            if (pageQueue.front() != pages[i]) {
                pageQueue.pop();
                pageQueue.push(pages[i]);
                pageFaults++;
            }
        }
    }

    return pageFaults;
}

int main() {
    int pages[] = {2, 3, 1, 4, 5, 2, 1}; // 頁(yè)面引用序列
    int n = sizeof(pages) / sizeof(pages[0]); // 頁(yè)面引用序列長(zhǎng)度
    int capacity = 3; // 頁(yè)面幀數(shù)

    int faults = FIFO(pages, n, capacity);
    cout << "Total Page Faults: " << faults << endl;

    return 0;
}

這個(gè)示例使用了一個(gè)隊(duì)列來(lái)模擬內(nèi)存中的頁(yè)面幀，當(dāng)隊(duì)列未滿時(shí)直接插入頁(yè)面，當(dāng)隊(duì)列已滿時(shí)進(jìn)行頁(yè)面替換。每次發(fā)生頁(yè)面錯(cuò)誤（即訪問(wèn)不在內(nèi)存中的頁(yè)面）時(shí)，計(jì)數(shù)器增加。最后輸出總的頁(yè)面錯(cuò)誤次數(shù)。

(2)算法分析

FIFO 頁(yè)面替換算法的優(yōu)點(diǎn)是簡(jiǎn)單易懂，實(shí)現(xiàn)方便。它不需要對(duì)進(jìn)程訪問(wèn)的頁(yè)面做特定的訪問(wèn)規(guī)劃，因此適用于任何進(jìn)程。另外，由于 FIFO 算法嚴(yán)格按照頁(yè)面進(jìn)入內(nèi)存的順序進(jìn)行替換，所以可以保證每個(gè)頁(yè)面的等待時(shí)間相同，避免了某些頁(yè)面總是被替換的問(wèn)題。

然而，F(xiàn)IFO 頁(yè)面替換算法也存在明顯的缺陷。由于該算法只關(guān)注頁(yè)面進(jìn)入內(nèi)存的時(shí)間，而未考慮各頁(yè)面的重要性和使用頻率，因此會(huì)導(dǎo)致某些頻繁使用的頁(yè)面被不必要地替換出去，從而降低系統(tǒng)的性能。此外，F(xiàn)IFO 算法還容易受到局部性原理的影響，即剛剛被訪問(wèn)的頁(yè)面很可能很快再次被訪問(wèn)，但由于 FIFO 算法只考慮頁(yè)面進(jìn)入內(nèi)存的時(shí)間，因此可能導(dǎo)致這些重要頁(yè)面被替換出去。

五、經(jīng)典LRU鏈表算法

LRU是Least Recently Used的縮寫(xiě)，意為最近最少使用。根據(jù)局部性原理，LRU假定最近不使用的頁(yè)面在較短的時(shí)間內(nèi)也不會(huì)頻繁使用。在內(nèi)存不足時(shí)，這些頁(yè)面將成為被換出的候選者。內(nèi)核使用雙向鏈表來(lái)定義LRU鏈表，并且根據(jù)頁(yè)面的類(lèi)型將LRU鏈表分為L(zhǎng)RU_ANON和LRU_FILE。每種類(lèi)型根據(jù)頁(yè)面的活躍性分為活躍LRU鏈表和不活躍LRU鏈表，所以內(nèi)核中一共有如下5個(gè)LRU鏈表：

// 定義了各種 LRU 鏈表的類(lèi)型
enum lru_list {
	// 不活躍匿名頁(yè)面鏈表
    LRU_INACTIVE_ANON = LRU_BASE,
    // 活躍匿名頁(yè)面鏈表
	LRU_ACTIVE_ANON = LRU_BASE + LRU_ACTIVE,
    // 不活躍文件映射頁(yè)面鏈表
	LRU_INACTIVE_FILE = LRU_BASE + LRU_FILE,
    // 活躍文件映射頁(yè)面鏈表
	LRU_ACTIVE_FILE = LRU_BASE + LRU_FILE + LRU_ACTIVE,
    // 不可回收頁(yè)面鏈表
	LRU_UNEVICTABLE,
	NR_LRU_LISTS
};

LRU鏈表之所以要分成這樣，是因?yàn)楫?dāng)內(nèi)存緊缺時(shí)總是優(yōu)先換出文件映射的文件緩存頁(yè)面 （LRU_FILE鏈表中的頁(yè)面），而不是匿名頁(yè)面。因?yàn)榇蠖鄶?shù)情況下，文件緩存頁(yè)面不需要被回寫(xiě)到磁盤(pán)，除非頁(yè)面內(nèi)容修改了（稱(chēng)為臟頁(yè)），而匿名頁(yè)面總是要在寫(xiě)入交換分區(qū)之后，才能被換出。LRU鏈表按照內(nèi)存節(jié)點(diǎn)配置，也就是說(shuō)，每個(gè)內(nèi)存節(jié)點(diǎn)中都有一整套LRU鏈表，因此內(nèi)存節(jié)點(diǎn)的描述符數(shù)據(jù)結(jié)構(gòu)（pglist_data）中有一個(gè)成員lruvec指向這些鏈表。枚舉類(lèi)型變量lru_list 列舉出上述各種LRU鏈表的類(lèi)型，lruvec數(shù)據(jù)結(jié)構(gòu)中定義了上述各種LRU類(lèi)型的鏈表：

// 定義了各種 LRU 鏈表
struct lruvec {
	struct list_head		lists[NR_LRU_LISTS];
	...
};

// 內(nèi)存節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)
typedef struct pglist_data {
	// 每個(gè)內(nèi)存節(jié)點(diǎn)中都有一整套 LRU 鏈表，由 lruvec 指向
	struct lruvec		lruvec;
} pg_data_t;

萬(wàn)事從圖說(shuō)起，經(jīng)典LRU鏈表算法如下圖所示：

為了使讀者有更真切的理解，下文將根據(jù)流程圖圍繞源代碼進(jìn)行講解這個(gè)過(guò)程：

將頁(yè)面加入 LRU 鏈表：

static void __lru_cache_add(struct page *page)
{
	// 這里使用了頁(yè)向量數(shù)據(jù)結(jié)構(gòu)，借助一個(gè)數(shù)組來(lái)保存特定數(shù)目的頁(yè)，可以對(duì)這些頁(yè)面執(zhí)行同樣的操作
	// 頁(yè)向量會(huì)以“批處理的方式”執(zhí)行，比單獨(dú)處理一個(gè)頁(yè)面的方式效率要高
	struct pagevec *pvec = &get_cpu_var(lru_add_pvec);

	get_page(page);
	// pagevec_add() 函數(shù)首先往 pvec->pages[] 數(shù)組里添加頁(yè)面，
	// 如果沒(méi)有空間了，則調(diào)用 __pagevec_lru_add() 函數(shù)把原有的頁(yè)面添加到 LRU 鏈表中
	if (!pagevec_add(pvec, page) || PageCompound(page))
		__pagevec_lru_add(pvec);
	put_cpu_var(lru_add_pvec);
}

void lru_cache_add(struct page *page)
{
	...
	__lru_cache_add(page);
}

lru_to_page(&lru_list)和list_del(&page->lru)函數(shù)的組合用于從LRU鏈表中獲取頁(yè)面。其中，lru_to_page()的實(shí)現(xiàn)如下：

#define lru_to_page(head) (list_entry((head)->prev, struct page, lru))

lru_to_page()使用了(head)->prev，表示從鏈表的末尾獲取頁(yè)面。因此，LRU鏈表實(shí)現(xiàn)了 FIFO算法。最先進(jìn)入LRU鏈表的頁(yè)面在LRU中的時(shí)間會(huì)越長(zhǎng)，老化時(shí)間也越長(zhǎng)。

在系統(tǒng)執(zhí)行過(guò)程中，頁(yè)面總是在活躍LRU鏈表和不活躍LRU鏈表之間轉(zhuǎn)移，不是每次訪問(wèn)內(nèi)存頁(yè)面都會(huì)發(fā)生這種轉(zhuǎn)移，而是發(fā)生的時(shí)間間隔比較長(zhǎng)。隨著時(shí)間的推移，這會(huì)導(dǎo)致—種熱平衡，最不常用的頁(yè)面將慢慢移動(dòng)到不活躍LRU鏈表的末尾，這些頁(yè)面正是頁(yè)面回收中最合適的候選者。

六、時(shí)鐘置換算法

時(shí)鐘置換算法可以認(rèn)為是一種最近未使用算法，即逐出的頁(yè)面都是最近沒(méi)有使用的那個(gè)。我們給每一個(gè)頁(yè)面設(shè)置一個(gè)標(biāo)記位u，u=1表示最近有使用u=0則表示該頁(yè)面最近沒(méi)有被使用，應(yīng)該被逐出。

按照1-2-3-4的順序訪問(wèn)頁(yè)面，則緩沖池會(huì)以這樣的一種順序被填滿：

注意中間的指針，就像是時(shí)鐘的指針一樣在移動(dòng)，這樣的訪問(wèn)結(jié)束后，緩沖池里現(xiàn)在已經(jīng)被填滿了，此時(shí)如果要按照1-5的順序訪問(wèn)，那么在訪問(wèn)1的時(shí)候是可以直接命中緩存返回的，但是訪問(wèn)5的時(shí)候，因?yàn)榫彌_池已經(jīng)滿了，所以要進(jìn)行一次逐出操作，其操作示意圖如下：

最初要經(jīng)過(guò)一輪遍歷，每次遍歷到一個(gè)節(jié)點(diǎn)發(fā)現(xiàn)u=1的，將該標(biāo)記位置為0，然后遍歷下一個(gè)頁(yè)面，一輪遍歷完后，發(fā)現(xiàn)沒(méi)有可以被逐出的頁(yè)面，則進(jìn)行下一輪遍歷，這次遍歷之后發(fā)現(xiàn)原先1號(hào)頁(yè)面的標(biāo)記位u=0，則將該頁(yè)面逐出，置換為頁(yè)面5，并將指針指向下一個(gè)頁(yè)面。假設(shè)我們接下來(lái)會(huì)訪問(wèn)2號(hào)頁(yè)面，那么可以直接命中指針指向的頁(yè)面，并將這個(gè)頁(yè)面的標(biāo)記為u置為1。<br />但是考慮一個(gè)問(wèn)題，數(shù)據(jù)庫(kù)里逐出的頁(yè)面是要寫(xiě)回磁盤(pán)的，這是一個(gè)很昂貴的操作，因此我們應(yīng)該優(yōu)先考慮逐出那些沒(méi)有被修改的頁(yè)面，這樣可以降低IO。因此在時(shí)鐘置換算法的基礎(chǔ)上可以做一個(gè)改進(jìn)，就是增加一個(gè)標(biāo)記為m，修改過(guò)標(biāo)記為1，沒(méi)有修改過(guò)則標(biāo)記為0。那么u和m組成了一個(gè)元組，有四種可能，其被逐出的優(yōu)先順序也不一樣：

• (u=0, m=0) 沒(méi)有使用也沒(méi)有修改，被逐出的優(yōu)先級(jí)最高；
• (u=1, m=0) 使用過(guò)，但是沒(méi)有修改過(guò)，優(yōu)先級(jí)第二；
• (u=0, m=1) 沒(méi)有使用過(guò)，但是修改過(guò)，優(yōu)先級(jí)第三；
• (u=1, m=1) 使用過(guò)也修改過(guò)，優(yōu)先級(jí)第四。