在當今數字化時代，隨著軟件應用的不斷發展和功能的日益強大，它們對內存的需求也在持續攀升。無論是運行大型數據庫管理系統、進行復雜的數據分析和人工智能模型訓練，還是暢玩精美的 3A 游戲，內存的重要性愈發凸顯。就拿一款熱門的 3A 游戲來說，在高畫質和高分辨率的設置下，其運行時所占用的內存輕松就能達到十幾 GB。而對于那些進行大數據分析的專業軟件，在處理海量數據時，對內存的渴望更是強烈，幾十 GB 的內存占用也并不罕見。

在 Linux 操作系統中，內存管理是一項至關重要的任務，而其中的頁交換算法則是內存管理的核心關鍵。它就像是一位精明的管家，在物理內存資源有限的情況下，巧妙地協調內存的使用，確保系統能夠高效穩定地運行。當系統內存緊張時，頁交換算法能夠精準地決定哪些內存頁面需要被暫時轉移到磁盤的交換空間中，以便為更急需內存的程序騰出空間。而當這些被轉移的頁面再次被需要時，它又能迅速將其從交換空間中取回，重新加載到物理內存里。

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

一、頁交換算法概述

在Linux操作系統中，當內存充足時，內核會盡量多地使用內存作為文件緩存（page cache）， 從而提高系統的性能。文件緩存頁面會添加到文件類型的LRU鏈表中；當內存緊張時，文件緩存頁面會被丟棄，或者把修改的文件緩存頁面回寫到存儲設備中，與塊設備同步之后便可釋放出物理內存。現在的應用程序轉向內存密集型，無論系統中有多少物理內存都是不夠用的，因此Linux操作系統會使用存儲設備作為交換分區，內核將很少使用的內存換出到交換分區，以便釋放出物理內存，這個機制稱為頁交換（swapping），這些處理機制統稱為頁面回收（page reclaim）。

在最近幾十年操作系統的發展過程中，出現了很多頁面交換算法，其中每個算法都有各自的優點和缺點。Linux內核中采用的頁交換算法主要是經典LRU鏈表算法和第二次機會（second chance）法。

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

• 第1步：找出所需頁面在磁盤上的位置。
• 第2步：找出一個空閑內存塊。如果有空閑塊，就用它；如果沒有空閑塊，就用頁面置換算法選擇一個可置換的內存塊，把該頁寫到磁盤上，并相應地修改頁表和存儲塊表。
• 第3步：把所需頁面讀入剛剛得到的內存空閑塊，修改頁表和存儲塊表。
• 第4步：重新啟動該用戶進程。

(2)頁面走向

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

好的頁面置換算法能夠適當降低頁面更換頻率（減少缺頁率），盡量避免系統“抖動”。

為評價一個算法的優劣，可將該算法應用于一個特定的存儲訪問序列（也叫頁面走向）上，并且計算缺頁數量。

二、Linux 內存管理基礎

2.1內存管理的重要性

內存管理，作為操作系統的關鍵核心功能，對于系統的穩定高效運行而言，有著舉足輕重的意義，其主要任務涵蓋內存分配、回收、保護等多個重要方面。

在內存分配方面，當一個新的程序啟動時，操作系統需要為其精準地分配足夠的內存空間，以確保程序能夠順利加載并運行。這就好比在一座大型寫字樓里，為每一家新入駐的公司合理分配辦公場地，讓它們能夠正常開展業務。如果內存分配不合理，比如分配的內存過小，程序可能無法完整加載，導致運行出錯；而分配過大，則會造成內存資源的浪費，就像給一家小型創業公司分配了一個超大的辦公區域，卻有大量空間閑置。

內存回收同樣不可或缺。當程序運行結束或者不再需要某些內存空間時，操作系統必須及時將這些內存回收，以便重新分配給其他有需求的程序。這類似于寫字樓里的公司退租后，物業要及時清理場地，重新出租給新的租戶。若內存回收不及時，就會出現內存泄漏的問題，隨著時間的推移，系統可用內存會越來越少，最終導致系統性能嚴重下降，甚至崩潰。

內存保護則是保障系統安全穩定運行的重要防線。它能防止不同程序之間的內存相互干擾和非法訪問，確保每個程序只能在自己被分配的內存空間內進行操作。這就如同寫字樓里的每家公司都有自己獨立的辦公區域，彼此之間不能隨意闖入和破壞，保證了各個公司的正常運作和數據安全。如果沒有內存保護機制，一個惡意程序可能會隨意修改其他程序的內存數據，導致其他程序運行出錯，甚至整個系統癱瘓。

2.2Linux 內存管理的特點

與其他操作系統相比，Linux 內存管理在靈活性、高效性和對硬件的適應性等方面展現出了顯著的特點 。

Linux 內存管理的靈活性體現在多個方面。它支持多種內存分配策略，能夠根據不同的應用場景和需求，選擇最合適的分配方式。在一些對內存使用效率要求極高的科學計算應用中，Linux 可以采用特定的內存分配策略，減少內存碎片的產生，提高內存的利用率。同時，Linux 還允許用戶根據自己的需求對內存管理進行定制和優化，用戶可以通過修改內核參數等方式，調整內存管理的行為，以滿足特定的業務需求。

高效性也是 Linux 內存管理的一大亮點。它采用了先進的內存管理算法，能夠快速地進行內存分配和回收操作，減少系統的開銷。在處理大量并發進程時，Linux 的內存管理系統能夠迅速為每個進程分配所需的內存，并且在進程結束后及時回收內存，使得系統能夠高效地處理多任務。Linux 還通過內存緩存等技術，提高了數據的訪問速度，進一步提升了系統的整體性能。例如，它會將經常訪問的數據緩存到內存中，當再次訪問這些數據時，就可以直接從內存中讀取，而無需從速度較慢的磁盤中讀取，大大提高了數據的讀取效率。

Linux 內存管理對硬件的適應性也非常出色，它能夠很好地支持各種不同類型的硬件平臺，無論是常見的 x86 架構，還是 ARM、PowerPC 等架構，Linux 都能充分發揮硬件的性能優勢，實現高效的內存管理。在嵌入式設備中，由于硬件資源有限，Linux 可以根據設備的具體硬件配置，靈活地調整內存管理策略，確保系統在有限的內存條件下穩定運行。對于具有不同內存大小和特性的硬件，Linux 能夠自動識別并進行優化，以達到最佳的內存使用效果。

2.3頁交換算法原理

頁交換算法的設計和實現，緊密依賴于局部性原理。局部性原理包含時間局部性和空間局部性兩個重要方面 。

時間局部性指的是，在程序運行過程中，如果一個數據項在某個時刻被訪問，那么在不久的將來，它很可能會再次被訪問。例如，在一個循環結構的程序中，循環變量會在每次循環時被頻繁訪問，這就體現了時間局部性。假設一個程序中有一個循環，用于計算數組中所有元素的總和，循環變量 i 在每次循環中都會被訪問，而且在整個循環執行期間，i 會被多次重復訪問，這就是時間局部性的典型表現。

空間局部性則是說，如果一個數據項的地址被訪問，那么與它在空間位置上臨近的數據項的地址，很可能也會在不久之后被訪問。這是因為程序在訪問內存時，通常會按照一定的順序進行。比如，在訪問一個數組時，程序會依次訪問數組中的各個元素，這些元素在內存中是連續存儲的，訪問了一個元素后，下一個被訪問的元素大概率是與之相鄰的元素，這體現了空間局部性。例如，有一個包含 100 個整數的數組，當程序訪問數組的第 5 個元素時，接下來很可能會訪問第 6 個、第 7 個等相鄰的元素。

基于局部性原理，頁交換算法在選擇置換頁面時，會重點關注頁面的訪問頻率和訪問時間。對于那些長時間沒有被訪問，或者訪問頻率極低的頁面，算法會認為它們在未來一段時間內被訪問的可能性也較小，從而將這些頁面作為優先置換的對象。這樣，就可以確保物理內存中始終保留著那些最有可能被頻繁訪問的頁面，提高內存的使用效率，減少頁面置換的次數，進而提升系統的整體性能。如果一個程序在運行過程中，某個頁面已經很長時間沒有被訪問了，根據局部性原理，這個頁面在未來短時間內被訪問的概率相對較低，頁交換算法就會考慮將這個頁面置換到磁盤交換分區，為更需要內存的頁面騰出空間 。

三、最佳置換算法（OPT）

最佳置換算法，其所選擇的被淘汰的頁面將是以后永不使用的，或是在最長（未來）時間內不再被訪問的頁面。采用最佳置換算法通常可保證最低的缺頁率。但是人們目前還無法與之，一個進程在內存的若干個頁面中，哪一個頁面是未來最長時間內不再被訪問的，因而該算法是無法實現的，但是可以利用該算法取評價其他的算法。

(1)算法思想

舉例如下：

我們將頁面隊列存在一個Vector動態數組中。我們可以從圖中得知：當發生頁面置換時，就要尋找在未來最長時間內不再被訪問的頁面，將其置換出去，比如當內存中存在的頁面為 7、0、1,且要訪問頁面2時，此時我們要尋找頁面隊列中將要訪問到的頁面2以后的頁面隊列（0、3、0、4、2、3、0、3、2、1、2、0、1、7、0、1）中，頁面7、0、1哪個最久未被訪問到，即尋找頁面7、0、1在以后的隊列中第一次出現的這三個頁面的下標值最大的那一個。因為頁面7在后面的頁面隊列中再次被訪問到是數組中下標為17的地方,頁面0再次被訪問到是數組下標為4的地方，頁面1再次被訪問的是數組中下標為13,所以頁面7是未來最久才被訪問的頁面，所以將頁面7置換出去，將頁面2調入內存中。

具體算法：每個頁面都有兩個屬性，一個是頁面號id，一個是時間參數count（此屬性在LRU中才會用到）

//pageId 要調入內存的頁面號
//currentPoint 記錄當前將要調入內存中頁面所在頁面隊列中的下標號
void OPT::replace(int pageId, int currentPoint)
{
    //cur為內存塊下標,searchCounter紀錄是否內存塊搜索完畢
    //循環爆出最長為使用的頁面
    int max = 0, perCount, outPageId = -1, cur = 0;
    int search_count[PRO_MEMORY];

    for (int i = 0; i < PRO_MEMORY; i++)
    {
    //比如，從頁面2后面的頁面開始掃描記錄頁面7、0、1再次被訪問的數組的下標號
        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;
        }
    }
    //以上面內存中存在的是頁面7、0、1為例。尋找頁面7、0、1再次被訪問的下標號最大的    //哪個頁面
    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 << "頁號ID：" << pageId << "正在放入內存，頁號ID：" << outPageId << "被替換出去" << endl;
    ofs_OPT << "頁號ID：" << pageId << "正在放入內存，頁號ID：" << outPageId << "被替換出去\n";
}

運行結果截圖：

四、先進先出法(FINO)

頁面替換算法是操作系統中用于解決內存不足的問題的一種算法。在實現時，可將內存在等大塊，稱作頁面，將進程所需的內存也分成等大的塊，即頁，當進程訪問一個新頁時，若內存已滿，則需要選擇一個已駐留的頁，將其后備存儲設備中的內容讀入內存中，以使新頁能夠進入內存。頁面替換算法中的「組 2」指的是先進先出算法（FIFO）。

這是最簡單的頁面替換算法。在該算法中，操作系統跟蹤隊列中內存中的所有頁面，最舊的頁面在隊列的前面。當一個頁面需要被替換時，隊列前面的頁面被選中進行刪除。

示例-1。考慮頁面引用字符串1、3、0、3、5、6 和 3 頁槽。

最初所有的槽都是空的，所以當 1、3、0 到來時，它們被分配到空槽——> 3頁錯誤。 當 3 出現時，它已經在內存中，所以 —> 0 Page Faults。然后是 5，它在內存中不可用，因此它替換了最舊的頁槽，即 1。—>1頁錯誤。 最后是 6，它在內存中也不可用，因此它替換了最舊的頁槽，即 3 —>1頁錯誤。

(1)算法實現

FIFO 算法簡單易懂，實現方便。它基于隊列數據結構來實現，將最先進入隊列的頁面置換出去，以便騰出空間給新頁面使用。這里給出 FIFO 頁面替換算法的示例代碼

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

int FIFO(int pages[], int n, int capacity) {
    queue<int> pageQueue; // 用于存儲頁面的隊列
    int pageFaults = 0; // 頁面錯誤次數

    for (int i = 0; i < n; i++) {
        if (pageQueue.size() < capacity) { // 隊列未滿時直接插入頁面
            if (!pageQueue.empty() && pageQueue.front() == pages[i]) {
                continue;
            }
            pageQueue.push(pages[i]);
            pageFaults++;
        } else { // 隊列已滿，進行頁面替換
            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}; // 頁面引用序列
    int n = sizeof(pages) / sizeof(pages[0]); // 頁面引用序列長度
    int capacity = 3; // 頁面幀數

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

    return 0;
}

這個示例使用了一個隊列來模擬內存中的頁面幀，當隊列未滿時直接插入頁面，當隊列已滿時進行頁面替換。每次發生頁面錯誤（即訪問不在內存中的頁面）時，計數器增加。最后輸出總的頁面錯誤次數。

(2)算法分析

FIFO 頁面替換算法的優點是簡單易懂，實現方便。它不需要對進程訪問的頁面做特定的訪問規劃，因此適用于任何進程。另外，由于 FIFO 算法嚴格按照頁面進入內存的順序進行替換，所以可以保證每個頁面的等待時間相同，避免了某些頁面總是被替換的問題。

然而，FIFO 頁面替換算法也存在明顯的缺陷。由于該算法只關注頁面進入內存的時間，而未考慮各頁面的重要性和使用頻率，因此會導致某些頻繁使用的頁面被不必要地替換出去，從而降低系統的性能。此外，FIFO 算法還容易受到局部性原理的影響，即剛剛被訪問的頁面很可能很快再次被訪問，但由于 FIFO 算法只考慮頁面進入內存的時間，因此可能導致這些重要頁面被替換出去。

五、經典LRU鏈表算法

LRU是Least Recently Used的縮寫，意為最近最少使用。根據局部性原理，LRU假定最近不使用的頁面在較短的時間內也不會頻繁使用。在內存不足時，這些頁面將成為被換出的候選者。內核使用雙向鏈表來定義LRU鏈表，并且根據頁面的類型將LRU鏈表分為LRU_ANON和LRU_FILE。每種類型根據頁面的活躍性分為活躍LRU鏈表和不活躍LRU鏈表，所以內核中一共有如下5個LRU鏈表：

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

LRU鏈表之所以要分成這樣，是因為當內存緊缺時總是優先換出文件映射的文件緩存頁面 （LRU_FILE鏈表中的頁面），而不是匿名頁面。因為大多數情況下，文件緩存頁面不需要被回寫到磁盤，除非頁面內容修改了（稱為臟頁），而匿名頁面總是要在寫入交換分區之后，才能被換出。LRU鏈表按照內存節點配置，也就是說，每個內存節點中都有一整套LRU鏈表，因此內存節點的描述符數據結構（pglist_data）中有一個成員lruvec指向這些鏈表。枚舉類型變量lru_list 列舉出上述各種LRU鏈表的類型，lruvec數據結構中定義了上述各種LRU類型的鏈表：

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

// 內存節點的數據結構
typedef struct pglist_data {
	// 每個內存節點中都有一整套 LRU 鏈表，由 lruvec 指向
	struct lruvec		lruvec;
} pg_data_t;

萬事從圖說起，經典LRU鏈表算法如下圖所示：

為了使讀者有更真切的理解，下文將根據流程圖圍繞源代碼進行講解這個過程：

將頁面加入 LRU 鏈表：

static void __lru_cache_add(struct page *page)
{
	// 這里使用了頁向量數據結構，借助一個數組來保存特定數目的頁，可以對這些頁面執行同樣的操作
	// 頁向量會以“批處理的方式”執行，比單獨處理一個頁面的方式效率要高
	struct pagevec *pvec = &get_cpu_var(lru_add_pvec);

	get_page(page);
	// pagevec_add() 函數首先往 pvec->pages[] 數組里添加頁面，
	// 如果沒有空間了，則調用 __pagevec_lru_add() 函數把原有的頁面添加到 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)函數的組合用于從LRU鏈表中獲取頁面。其中，lru_to_page()的實現如下：

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

lru_to_page()使用了(head)->prev，表示從鏈表的末尾獲取頁面。因此，LRU鏈表實現了 FIFO算法。最先進入LRU鏈表的頁面在LRU中的時間會越長，老化時間也越長。

在系統執行過程中，頁面總是在活躍LRU鏈表和不活躍LRU鏈表之間轉移，不是每次訪問內存頁面都會發生這種轉移，而是發生的時間間隔比較長。隨著時間的推移，這會導致—種熱平衡，最不常用的頁面將慢慢移動到不活躍LRU鏈表的末尾，這些頁面正是頁面回收中最合適的候選者。

六、時鐘置換算法

時鐘置換算法可以認為是一種最近未使用算法，即逐出的頁面都是最近沒有使用的那個。我們給每一個頁面設置一個標記位u，u=1表示最近有使用u=0則表示該頁面最近沒有被使用，應該被逐出。

按照1-2-3-4的順序訪問頁面，則緩沖池會以這樣的一種順序被填滿：

注意中間的指針，就像是時鐘的指針一樣在移動，這樣的訪問結束后，緩沖池里現在已經被填滿了，此時如果要按照1-5的順序訪問，那么在訪問1的時候是可以直接命中緩存返回的，但是訪問5的時候，因為緩沖池已經滿了，所以要進行一次逐出操作，其操作示意圖如下：

最初要經過一輪遍歷，每次遍歷到一個節點發現u=1的，將該標記位置為0，然后遍歷下一個頁面，一輪遍歷完后，發現沒有可以被逐出的頁面，則進行下一輪遍歷，這次遍歷之后發現原先1號頁面的標記位u=0，則將該頁面逐出，置換為頁面5，并將指針指向下一個頁面。假設我們接下來會訪問2號頁面，那么可以直接命中指針指向的頁面，并將這個頁面的標記為u置為1。<br />但是考慮一個問題，數據庫里逐出的頁面是要寫回磁盤的，這是一個很昂貴的操作，因此我們應該優先考慮逐出那些沒有被修改的頁面，這樣可以降低IO。因此在時鐘置換算法的基礎上可以做一個改進，就是增加一個標記為m，修改過標記為1，沒有修改過則標記為0。那么u和m組成了一個元組，有四種可能，其被逐出的優先順序也不一樣：

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