摘要訊息 : 使用我們自己設計的記憶池來接管 C/C++ 內建的記憶體配置行為.

0. 前言

電腦光有硬體是無法使用的, 必須配合軟體, 一定會有軟體來管理電腦硬體, 使得硬體發揮最大的作用. 這個軟體就是作業系統. 如果大家學習過作業系統是如何對記憶體進行管理的, 那麼一定對記憶體碎片化的問題有一定的認識. 即使沒有學習過, 在學習程式設計以及平時在使用電腦的時候, 也肯定對記憶體碎片化有所了解. 簡單地說, 記憶體碎片化是一種資源空置但是無法利用, 從而導致這些資源被浪費的現象.

更新紀錄 :

• 2022 年 4 月 19 日進行第一次更新和修正.

1. 記憶體碎片化

現代的記憶體都是比較大的, 所以作業系統通常採取分區的方式進行管理, 而這種分區的管理方式最大的問題就是會使記憶體碎片化. 現在想像有一片記憶體分區, 每一塊分區尾部都有一點點空閒, 但是如果使用者需要的記憶體永遠都比那些空閒的部分多, 那麼必須在新的記憶體分區中為使用者配置. 每一塊分區尾部那一些空置下來的小片記憶體隨著分區的增多會越來越多. 這些小片的空閒記憶體單獨做不了什麼, 但是一旦把它們合併起來, 就又是一塊大的記憶體空間, 所以這一片大的記憶體空間就被浪費了.

2. 配置時繳稅

我們在使用 C 的函式 malloc 和 C++ 的 operator new 系列函式配置記憶體的時候, 都需要放入物件的具體大小. 但是我們使用函式 free 或者 operator delete 系列函式來回收記憶體的時候, 卻不需要放入物件的大小. 原因就在於作業系統在處理記憶體配置的時候, 使用了額外的空間記錄了我們需要的記憶體大小. 當作業系統接收到一個需要回收的指標的時候, 它會首先去尋找這個指標指向的記憶體大小, 然後再回收對應大小的記憶體.

#include <cstdlib>
#include <cstdio>

int main(int argc, char *argv[]) {
    auto p1 {std::malloc(sizeof(int))};
    auto p2 {std::malloc(sizeof(int))};
    std::printf("%p\n", p1);        // 輸出 : 0x600000db8030
    std::printf("%p\n", p2);        // 輸出 : 0x600000db8040
    std::free(p1);
    std::free(p2);
}

在 Code 1 中, macOS 12 和 Apple Clang 下, int 型別大小為四位元組. 而記憶體指標的輸出通常使用十六進制來表示. 因此, 我們期望 Code 1 中的輸出是 0x600000db8030 和 0x600000db8034. 但是實際上, 指標 p1 和 p2 的距離達到了十六位元組. 這是因為作業系統需要額外的空間記錄記憶體的配置大小. 雖然 Code 1 中我們只向作業系統要求了八位元組的記憶體, 但是實際上作業系統卻使用了超過八位元組大小的記憶體用於記錄記憶體配置的大小, 用於記錄的那一部分甚至比我們需要的還要多. 這部分多出來的空間就好像是我們每一次的向作業系統申請記憶體配置的時候, 都會向作業系統繳出額外的 “稅”.

試想我們如果要實作前向連結串列, 連結串列, 樹結構和圖結構, 那麼每個結點或節點的大小都是固定的. 如果我們不介入記憶體的配置, 那麼每個結點或節點都會需要額外的一些空間來記錄節點的大小. 當資料結構中結點或節點的數量不斷增多, 那麼這些額外記錄的那一部分空間加起來也不可小覷.

3. 記憶池

為了避免記憶體碎片化和作業系統額外記錄大小的問題, 我們通常向作業系統申請配置一塊很大的記憶體, 然後將這一塊記憶體進行劃分, 由我們自己接管. 這便是記憶池 (memory pool).

有很多程式甚至程式設計語言中都會自制記憶池來接管原生的記憶體管理操作. 例如, 程式設計語言 Java 的 JVM 是由 C++ 編寫的, 而 JVM 當中就有一個記憶池; Nginx 是由 C 語言編寫的, 它裡面也包含了一個記憶池.

3.1 記憶體配置

當我們要配置記憶體的時候, 就從記憶池從撥出一些. 相應地, 記憶池肯定也有屬於它的幾個標記, 用於標記哪一部分的記憶體是外界已經使用的.

一般來說, 會有兩個指標用於管理記憶池中空閒的大小. 一個指標指向記憶池的頭部, 另一個指標指向記憶池的尾部. 當需要從記憶池中配置一小塊記憶體的時候, 我們就把頭部的指標向後移動對應大小的位置, 表明這段記憶體已經交給外部支配了. 那麼, 頭部指標和尾部指標的距離代表著記憶池中還剩下多少可用的記憶體.

如果請求配置的記憶體大小比記憶池還要大的話, 我們可以放心地將這個配置請求交給 malloc 或者 operator new 系列函式來完成. 因為大塊的記憶體配置通常不會產生碎片問題.

現在, 我們知道了記憶體配置的大致行為. 實際上, 還有一些細節我們還沒有處理. 這些細節, 我們將在第 3.2.4 節中講述.

3.2 記憶體回收

從記憶池中配置記憶體非常簡單, 然而要回收卻沒有那麼簡單. 因為記憶體的配置我們可以順序地從頭部撥出記憶體區塊, 但是回收的話並不一定按順序了.

像 Figure 3 中, 一旦要歸還的記憶體不是按順序的, 頭部指標應該如何指向? 一種可能的方法是再配置兩個指標, 指向非連續可用區塊的頭部和尾部. 但是現在只歸還了一小個區塊, 一旦歸還的區塊逐漸增多且相互之間不連續呢? 所以使用多個指標這個方案是不可行的. 為此, 我們需要借助其它資料結構的幫助, 這個資料結構就是前向連結串列 (《【資料結構】前向連結串列》).

3.2.1 自由串列

在回收由記憶池配置的記憶體的時候, 我們並不是將這塊記憶體放回記憶池中, 而是把它放到自由串列 (free list) 中. 自由串列實際上是一個前向連結串列的陣列. 一個自由串列中有若干個前向連結串列, 每一個前向連結串列都負責管理不同大小的記憶體區塊. 例如, 某一個前向連結串列用於管理大小為十六位元組的記憶體區塊, 那麼每一次有大小為十六位元組的記憶體區塊需要被回收的時候, 我們就將這塊記憶體放入這個前項連結串列中.

3.2.2 記憶體對位

C++ 中的記憶體對位問題比較複雜, 有興趣的話可以參考這篇文章《【C++】記憶體對位》. 一般來說, 所有的記憶體大小都會對位至 2^{k}. 其中, k 是非負整數. 因此, 我們的記憶池也需要滿足這個對位. 不過, 我們設計的記憶池的對位是從 8 起的. 也就是說, 一旦外部要求的記憶體區塊大小達不到 8 位元組, 那麼我們就將記憶體區塊大小對位至 8. 類似地, 如果一個記憶體區塊大小是 12, 那麼我們對位至 8 \times 2 = 16. 也就是說, 記憶體區塊的對位大小都是 8 的倍數.

#include <cstddef>

constexpr std::size_t round_up(std::size_t bytes) noexcept {
    constexpr std::size_t align {8};
    return (bytes + align - 1) & ~(align - 1);
}

函式 round_up 可以讓記憶體區塊的大小進行對位. 對於那些不是八的倍數的大小, 可以讓其對位至八的倍數.

一般來說, 自由串列中前向連結串列的數量為十六個, 它們分別管理著 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96, 104, 112, 120 和 128 個大小的記憶體區塊.

#include <cstddef>

constexpr std::size_t free_list_index(std::size_t bytes) noexcept {
    constexpr std::size_t align {8};
    return (bytes + align - 1) / align - 1;
}

如果我們要在自由串列中尋找可用記憶體區塊, 必須要給定一個大小, 這個大小不一定以八為倍數, 所以我們需要定義一個額外的調整函式. 函式 free_list_index 就可以根據給定的大小, 回傳該大小是屬於自由串列中哪一個前項連結串列所管理的.

由於自由串列中能夠管理的最大記憶體區塊大小是 128, 所以我們一般設定記憶池的初始大小也是 128 \times n 位元組 (n 一般也不會太大, 通常有 n \in \left \{ 1, 2, 3 \right \}). 如果要配置比 128 位元組大小的記憶體, 就要交給 malloc 或者 operator new 系列函式了.

3.2.3 自由串列結點

在《【資料結構】前向連結串列》中我們提到過, 每一個前項連結串列的結點都需要額外的空間來儲存指向型標記. 但是我們還需要盡力做到以最小的額外空間來管理記憶池. 一般來說, 自由串列中的結點應該是這樣的 :

struct free_list_node {
    free_list_node *next;
    char *data;
};

其中, data 指向了這一小塊記憶體的頭部. 至於 data 指向的這一小塊記憶體有多大, 從自由串列中哪一個前項連結串列中拿出來, 它就有對應的大小. 例如某個結點從 Figure 4 中的 #5 中拿出來, 那麼 data 指向的這塊記憶體大小就有 48 位元組. 但是我們知道, 放入自由串列中的記憶體區塊都是未使用的, 因此我們完全可以借助這塊未使用的記憶體來儲存前向連結串列的指向型標記, 也就是把 free_list_node 中的 next 放入這塊未使用的記憶體中, 而不是額外為 next 配置另外一塊空間. 這樣, 就不需要額外的空間來儲存指向型標記了. 於是, 我們將 free_list_node 從結構體更改為等位 :

union free_list_node {
    free_list_node *next;
    char *data;
};

我們曾在《C++ 學習筆記》中提到, 等位同樣是一個類別, 只不過類別內的所有成員變數共享同一片記憶體空間. 因此在 64 位元作業系統中, sizeof(free_list_node) 的值為 8. 這也就是為什麼我們在第 3.2.2 節中將最小的記憶體對位設定為 8 的原因.

在這篇文章修改之前, free_list_node 是寫成這樣的 :

union free_list_node {
    free_list_node *next;
    char data[0];       // or char data[1];
};

其實這個和 char *data; 這樣宣告的效果是一樣的. 但是大小為 0 的陣列是 Clang 和 GCC 這兩個編碼器的擴展, 這並不是 C++ 標準中規定的可行行為. 因此, 在 MSVC 中, char data[0]; 這樣的宣告就會產生編碼錯誤. 因為 sizeof(char [0]) 的值也是 0, 所以如果使用 char data[0]; 這樣的宣告, 我們就可以把等位改成類別. 一旦陣列的大小不為 0, 那麼就必須使用等位以避免產生額外的空間消耗. 當然, 使用了等位之後, 只要陣列的大小不大於 8, 最終 sizeof(free_list_node) 的大小都是 8. 使用 char data[1]; 只是比較通用的做法. 這個在 C 中被稱為變長陣列.

變長陣列在 C 中使用得比較多. 例如

#include <stdlib.h>

struct flexible_array {
    int x;
    char data[1];
};
typedef struct flexible_array flexible_array;

int main(int argc, char *argv[]) {
    flexible_array *array = (flexible_array *)malloc(32);
}

我們為 array 配置了 32 位元組大小的記憶體, 而 flexible_array 中的成員變數 x 只需要 4 位元組 (在 64 位元的作業系統下), 因此剩下來的 28 位元組就交給成員變數 data 來支配. 也就是說, flexible_array 中 data 的實際可支配大小是由記憶體配置的大小決定的, 所以稱其為變長陣列.

有些人可能有疑問, 讓 Code 3-2 中的 next 和 data 共享一片空間, 即使 data 後面是變長的, 還有剩餘, 但是這樣不會造成記憶體內部資料的混亂嗎? 其實這個問題需要大家了解 C/C++ 中的等位原理, 然後自行想明白. 如果某一片記憶體正在被使用, 它自然不會被放入自由串列中, 此時 next 這個成員根本就不會被用到. 如果某一個區塊的記憶體需要被回收, 那麼說明這塊記憶體中所有的資料都已經失去作用了. 在記憶體回收的過程中, 我們讓這塊記憶體中儲存 next 指標, 指向下一塊可用的空閒記憶體. 換句話說, 如果記憶體是空閒的, 那麼 next 啟用; 如果記憶體是外部正在使用的, next 失效. 至於 data, 它只是一個和 next 共享空間的變長陣列頭部指標罷了.

更進一步地, 甚至我們可以只在 free_list_node 中留一個 next 指標. 但是為了方便理解, 也為了程式碼的可讀性, 我們仍然留下了 data 這個成員變數, 用於在理論上表示這個成員啟用的時候, 這片記憶體正在被外界使用.

3.2.4 重新審視記憶體配置

我們在第 3.1 節中就說過, 直接從記憶池中撥出記憶體是存在細節不足的. 現在引入了自由串列, 大家基本也就明白了. 如果需要配置記憶體的話, 我們首先應該去自由串列中搜尋有沒有對應大小的記憶體區塊可用. 如果自由串列中就有一個甚至多個的可用區塊, 那麼我們就不再需要向記憶池中申請撥出記憶體了, 直接就可以從管理對應大小的前項連結串列頭部拿出一個. 如果自由串列中管理對應區塊大小的前項連結串列中沒有任何可用的記憶體區塊了, 這個時候我們才像第 3.1 節中那樣向記憶池中去請求記憶體.

3.2.5 回收至自由串列

當記憶池收到需要回收記憶體區塊的要求的時候, 我們首先檢查這塊記憶體區塊是否比記憶池還要大. 根據第 3.1 節中的說法, 如果這塊記憶體的大小比記憶池還要大, 我們需要交給 free 或者 operator delete 系列函式來回收. 如果這塊記憶體比記憶池要小, 那麼應該交給自由串列來管理. 這塊記憶體多大, 就應該放到自由串列中管理對應大小的前向連結串列頭部.

3.3 提前配置自由串列

我們在前面章節中說過, 如果自由串列中管理響應大小的前項連結串列為空的時候, 我們會去記憶池中請求記憶體. 但是為了方便, 一旦自由串列中對應的前項連結串列為空的時候, 我們會去記憶池中請求一片記憶體, 然後將這片記憶體分成小塊, 將這些小塊連成前項連結串列之後放入自由串列中並取出其中一塊回傳給記憶池使用者.

這也是為了效能考慮. 因為如果我們經常發現自由串列管理對應大小的前項連結串列中都沒有記憶體區塊, 就會導致我們經常需要去記憶池中去請求, 這必定會造成程式效能的降低. 所以提前為自由串列配置好對應大小的記憶體區塊, 可以減少向記憶池請求這個操作.

3.4 特殊情況

我們前面的分析都建立在記憶池中的記憶體足夠或者自由串列中有足夠記憶體區塊這兩個假設之上. 還有一些很特殊的情況, 也值得我們進行分析.

3.4.1 提前配置要求無法滿足

我們在第 3.3 節中介紹了提前為自由串列配置, 提前為自由串列配置的行為發生在記憶池使用者向記憶池要求配置記憶體的時候. 例如現在我向記憶池要求 16 位元組的記憶體, 而自由串列中負責管理 16 位元組的那個前向連結串列中已經沒有可用的記憶體區塊了, 所以需要向記憶池請求, 同時提前配置出一些 16 位元組的記憶體區塊. 因為 16 位元組的記憶體區塊比較小, 用到的可能性比較多, 所以我們提前配置十六個區塊. 我們首先向記憶池要求 256 位元組的記憶體大區塊, 然後自行分割. 但是現在記憶池中可提供的空閒記憶體大小不足 256 位元組了, 只能提供 128 位元組的空閒記憶體. 沒有關係, 即使記憶池中只能提供 16 位元組的記憶體, 我們也照單全收. 那麼本來我們計畫提前配置十六個區塊, 現在只能減少到提前配置八個區塊. 我們把八個區塊中的其中一塊回傳出去, 交給記憶池使用者, 剩下七個區塊連結起來交給自由串列中負責管理 16 位元組的那個前向連結串列來管理.

如果很不幸, 記憶池只能夠提供給我們 16 位元組的記憶體的話, 那麼這塊記憶體可以直接回傳出去交給記憶池使用者, 而提前配置的要求就無法滿足了.

3.4.2 記憶池擴容

假設我現在向記憶池要求 32 位元組的記憶體, 但是記憶池已經沒有這麼多了, 此時我們就需要將記憶池擴容.

3.4.2.1 剩餘部分處理

現在我們的配置要求是 32 位元組的記憶體, 雖然記憶池無法提供, 但是記憶池可能還剩下了一些 (例如還剩下 16 位元組). 那麼根據記憶池中還剩下的記憶體大小, 我們直接將其放入自由串列中負責管理對應大小記憶體區塊的前項連結串列中就可以了. 例如現在還剩下 16 位元組, 那麼我們將剩下的記憶體放到自由串列中負責管理 16 位元組記憶體區塊的那個前向連結串列中即可.

3.4.2.2 向作業系統申請擴容

當把剩餘部分處理掉之後或者記憶池中本來就沒有剩餘部分, 此時指向記憶池頭部的指標和指向記憶池尾部的指標就會相遇. 這個時候, 我們重新使用 malloc 或者 operator new 系列函式向作業系統申請一塊新的大記憶體區塊, 然後調整那兩個管理記憶池的指標即可.

還需要考慮的是每次擴容的大小. 如果每次擴容的大小都是一樣的, 可能導致記憶池一直在擴容. 這可能不但沒有解決記憶體碎片問題, 反而會導致記憶池的效能低下.

記憶池的擴容必定發生在自由串列中管理對應大小記憶體區塊的前項連結串列中沒有空閒記憶體區塊, 同時記憶池也沒有剩餘的時候. 一般來說, 擴容的時候, 我們向作業系統要求的大小是 \displaystyle {\text {之前向作業系統要求配置的大小} \times 2 + \text {本次要求配置的大小}.} 其中, 本次要求配置的大小又可以表示為 \displaystyle {\text {用戶向記憶池請求的大小} \times \text {提前配置給自由串列的記憶體區塊數量},} 用戶向記憶池請求的大小必須已經調整為 8 的倍數.

3.4.3 記憶體不足

我們在第 3.4.2.2 節中講述了記憶池擴容的情況, 最後一種需要考慮的情況就是如果作業系統也不能向我們提供更多的記憶體, 也就是電腦的記憶體空間已經用盡. 我們首先應該考慮的是, 是否可以榨乾自由串列中可用的記憶體區塊, 而不是急著擲出例外情況 (C++ 的做法) 或者回傳一個空指標 (C 的做法).

如果當前記憶池使用者向記憶池申請配置 24 位元組大小的記憶體, 而在向作業系統申請擴容的時候, 作業系統告訴我們已經沒有更多可用的記憶體了. 這個時候, 我們可以去尋訪自由串列, 看看還有沒有空閒區塊可以拆出來使用. 那些在自由串列裏面管理記憶體區塊的前向連結串列中, 管理著比 24 位元組還小那部分前項連結串列可以直接跳過. 假設現在管理著 k 位元組 (k > 24) 記憶體區塊的前向連結串列中還有空閒的記憶體區塊, 那麼就拿出一塊來使用. 我們需要的是 24 位元組, 於是這一小塊記憶體區塊又被分為兩個部分 : 一部分的大小為 24 位元組, 另一部分的大小為 k - 24 位元組. 大小為 24 位元組的那部分記憶體可以直接回傳給記憶池使用者, 大小為 k - 24 位元組的記憶體區塊需要放入自由串列中專門管理大小為 k - 24 位元組記憶體區塊的前項連結串列中.

不過, 需要注意的是, 在 C++ 中使用可能擲出例外情況的 ::operator new 來向作業系統申請記憶體配置的話, 此時會因為記憶體不足而擲出 std::bad_alloc 例外情況. 所以, 我們應該將這裡的 ::operator new (或者說因為記憶體不足第一次向作業系統請求記憶體的那個 ::operator new) 放入一個 try-catch 區塊中. 然而, 如果我們追求極致的程式效能, 我們就會發現 try-catch 區塊會產生額外的消耗. 所以這裡, 我們應該使用不擲出例外情況的 ::operator new.

如果在自由串列中也找不到任何比配置要求更大的記憶體區塊了, 這個時候我們才告訴記憶池使用者 : 記憶池和作業系統都不能提供更多記憶體了. 按照 C++ 的做法, 應該是擲出例外情況, 通常是 std::bad_alloc 例外情況; 按照 C 的做法, 應該是回傳一個空指標.

3.5 記憶池回收

我們都知道, 配置的記憶體如果不再使用了, 就應該使用函式 free 或者 operator delete 系列函式來回收配置的記憶體. 那麼當程式結束之前, 我們是否應該將記憶池配置的所有記憶體回收呢? 答案是不需要. 並且不論是在程式運作的過程中還是程式運作完成之後都不需要.

在程式運作的過程中, 記憶池接管了程式的記憶體配置, 所以隨意回收記憶池中的記憶體可能導致程式出現錯誤或者效能低下. 另外, 程式運作的時候, 隨時有可能向記憶池申請配置記憶體, 所以即使記憶池中的記憶體都是空閒狀態, 也不應該隨意回收.

另一個方面, 在程式結束的時候, 作業系統會自動回收和這個程式有關的所有資源, 包括記憶體. 這裡面也就包含了由記憶池向作業系統申請配置的那一部分 “丟失” 的記憶體. 這一部分記憶體對於記憶池作者來說確實丟失了, 但是對於作業系統來說並沒有. 一個程式在運作的時候申請配置的所有資源, 作業系統都會有也都應該有記錄.

閣下如果細心的話, 可能會在閱讀第 3.4.2.2 節的時候就提出疑問, 甚至在第 3.1 節中就提出疑問, 我們改變了指向記憶池頭部的那個指標, 我們可能就沒有辦法找回它了, 那麼應該如何回收由記憶池向作業系統申請配置的記憶體呢? 現在既然知道了記憶池向作業系統申請配置的記憶體根本不需要回收, 自然也就沒有這個問題了.

當然, 如果一定想要回收也是沒有問題的. 我們需要在記憶池中增加一個動態指標陣列, 還有一個變數用於記錄這個動態指標陣列的大小. 每一次向作業系統配置一大塊記憶體的時候, 就把這塊記憶體的頭部指標放進陣列即可. 不過這必定會導致記憶池的運作效能降低.

4. 實作

在了解記憶池的基礎之後, 大家可以自行實作一個記憶池. 我自己寫了一個簡單的記憶池給大家參考 : https://github.com/Jonny0201/data_structure/blob/master/data_structure/memory.hpp.