電腦科學有幾門基礎課程 : 《計算機組織》、《作業系統》和《資料結構與演算法》等等. 如果大家學習過《作業系統》這門課程, 那麼一定對記憶體碎片化的問題有一定的認識. 即使大家沒有系統地學習這些課程, 但是在學習程式設計以及平時在使用電腦的時候, 也對記憶體碎片化有一些了解. 簡單地來說, 記憶體碎片化是一種資源被浪費而無法利用的現象. 電腦光有硬體是無法使用的, 必須配合軟體. 而一定會有軟體來管理電腦硬體, 使硬體的發揮它最大的作用, 這個軟體就是作業系統. 由於現代的記憶體都比較大, 所以作業系統通常採取分區的方式進行管理, 而這種分區的管理方式最大的問題就是會使記憶體碎片化. 碎片化的記憶體雖然是空閒的, 但是一旦碎片化的記憶體不斷增加, 就會使空閒的記憶體不斷增加但是卻無法被利用 (因為碎片化的記憶體比較小, 而程式對記憶體的需求通常都會比這些碎片化的記憶體大), 這並不是我們想要的結果

我們平時所編寫的 C++ 程式碼就會有這樣的問題 :

#include <memory>



int main(int argc, char *argv[]) {

    auto p1 {malloc(8)};

    auto p2 {malloc(12)};

    printf("%p\n", p1);

    printf("%p\n", p2);

    free(p1);

    free(p2);

}

在上述程式碼中, p1 與 p2 是上下連在一起的, 按道理 malloc 函式應該可以分配連續的記憶體. 但是實際上, 不可能碰到 p1 與 p2 記憶體連續的情況. 因此, 假設一個分區只剩下 10 個大小可以被配置, 但是我們只要了 8 個大小, 那麼剩下兩個大小就無法被配置出去, 導致了浪費. 而現代的程式也幾乎不會只申請 2 個大小的記憶體, 這實在是太小了, 只夠裝兩個 char

如果上面的情況不斷地出現, 那麼就會出現我們開頭所提到的情形 : 記憶體總體上有足夠空閒, 但是都是碎片化的, 並無法利用. 此時需要重新整理記憶體, 而任意存儲裝置的整理都需要耗費不少的時間

除此之外, 還有一個原因. 再次審視上面的程式碼, 我們可以發現, 在 malloc 函式的參數中, 我們給定了要配置的記憶體大小的引數. 但是在 free 回收記憶體的時候, 我們並沒有給出這個數字. 如果大家擁有足夠的程式設計實踐經驗, 那麼大家也會發現有些程式庫中的記憶體配置函式在回收記憶體的時候是需要給定的大小的. 顯然地, 我們給出的引數被作業系統給記錄到了記憶體中. 但是這個數字一般來說是可測的, 因此由我們自己來給出也是可以的. 要記錄這個數字, 是肯定需要額外的記憶體. 因此, 我們每一次的向系統申請記憶體進行配置的時候, 都會向系統給出額外的 "稅", 它用來記錄我們申請的記憶體的大小

基於上面兩點原因, 也為了方便我們自己管理記憶體, 這就有了記憶池

記憶池的基本思想就是程式向系統申請一大塊記憶體, 然後這一塊記憶體由程式進行管理. 從外部來看, 程式只使用了這一塊記憶體, 那麼也就不存在記憶體碎片化的問題. 只要系統內足夠提供一塊記憶池量的記憶體, 那麼就可以很好地解決記憶體碎片化以及每一次配置記憶體都需要額外 "繳稅" 的問題. 程式設計語言 Java 的 JVM 是由 C++ 編寫的, 而 JVM 當中就有一個記憶池

對於記憶池的運作, 非常簡單 : 有兩個指標, 一個指向記憶池未使用部分的頭部, 另外一個指向記憶池的最尾部. 每次要使用記憶體的時候, 就從記憶池從撥出一些, 此時讓指向未使用部分的頭部指標向後移動一些即可. 但是這裡有一個問題, 我們向記憶池申請撥出記憶體的時候, 是按照順序進行的. 但是我們使用完記憶體之後, 申請記憶池回收記憶體的時候, 就不再是順序的了. 那應該如何解決這個麻煩呢?

我們曾經在《資料結構》系列中提到了連結串列, 我們只需要將記憶體按照大小分類, 從記憶池撥出之後需要回收時, 將需要回收的記憶體根據它的大小連結到一個對應大小的連結串列即可

例如, 現在記憶池是 128 個大小, 將記憶體按照大小分成 16 種, 這些記憶體的大小分別是 8、16、24、32、40、48、56、64、72、80、88、96、104、112、120 和 128, 那麼我們就應該準備 16 個連結串列來準備接收這些將要被回收的記憶體. 在 C++ 中, 我們盡力做到以最小的空間寫出最快的程式, 因此我們通常想盡一切方法來節省空間. 此處的連結串列代表著它至少有兩個成員, 其中一個成員是指向下一塊記憶體的指標, 另外一個成員是用來存儲資料的記憶體本身. 但是如果這樣去實作, 那麼這和 "繳稅" 沒什麼分別, 因此我們想到使用 union 來節省空間 :

union free_list_node {

    free_list_node *free_list_link;

    char client_data[0];

};

我們曾在《C++ 學習筆記》中提到 : 等位同樣是一個類別, 只不過類別內的所有成員共享同一片記憶體空間. 因此上面這個等位, 每一個連結串列的結點只佔了 8 個大小 (64 位元作業系統中). 如果類別像上面這樣去設計, 那麼使用等位還是普通的類別區別都不太大. 這是因為我們在第二個類別成員 client_data 上應用了一些技巧. 這裡, client_data 使用了維度為 0 的陣列. 這目前僅在 Clang 以及 GCC 中被支援. 如果在 MSVC 在要使用這樣的技巧, 那麼只能使用等位, 而且會有編碼器警告. 這個技巧屬於編碼器拓展, 因此如果要想我們的程式碼具有廣泛的相容性, 此處應該使用 char client_data[1] 以及等位

上面這樣的實作在 C-Style 程式碼中比較常見, 這是一種 C-Style 變長陣列. 由於在 C 以及 C++ 中, 變長陣列可能是非標準的 (或者說是不安全的), 因此當需要變長陣列的時候, 只能用一些技巧去實現. 假如上面使用的是 struct, 如果給 free_list_node 配置的記憶體大於 free_list_node 本身需要的大小, 那麼多出來的部分在記憶體上的分佈就排在 free_list_link 之後, 而 client_datachar [] 型別, 因此之後的每一位元的記憶體都被視為 char 型別, 而且多出來那部分記憶體組成了一個陣列. 使用的過程中可以把 char 型別通過明確型別轉換轉型為其它型別然後使用即可. 而 client_data 這個名稱也表示, 這個陣列是屬於客端使用的, 在我們組織關於記憶體的連結串列的時候, 肯定用不到這個類別成員, 這也是此處可以使用等位來實作的另外一個原因

在 64 位元的作業系統中, 上面這樣的 free_list_node 每個結點佔據 8 個大小. 如果有這樣的陳述式 : ::operator new (sizeof(free_list_node) + 12); 那麼最終它擁有了 20 個大小的記憶體, 而額外附加的 12 個大小是屬於多出來的, 它們形式上就組成了 char client_data[12]

那麼連結串列的結點我們已經寫完了, 接下來只要把獲得的記憶體連結為連結串列即可. 另外, 由於我們的結點實作類似於一個變長陣列, 所以我們不需要擔心不同大小的記憶體造成不同的型別的困擾. 當我們想把 128 個大小的記憶體按照 8、16、24、32、40、48、56、64、72、80、88、96、104、112、120 和 128 個大小這樣劃分, 就需要 128 / 8 = 16 個連結串列的頭部, 每一個連結串列管理著不同大小的記憶體. 連結串列的結點一般使用指標表示, 也就是 free_list_node *, 而我們需要 16 個這樣的連結串列, 因此就有這樣的陣列型別 : free_list_node * [16], 對應的物件我們稱為 free_list (自由串列). 如果大家學過《作業系統》和《計算機組織》, 就會了解暫存器和執行緒這樣的概念. 如果我們直接這樣宣告, 在多執行緒的情況下會造成一些困擾 (例如兩個執行緒一起運作, 可能其中一個執行緒連訪問記憶池的權利都沒有), 這主要是由於編碼器對我們的 free_list 進行了優化. 因此我們需要將其宣告為 volatile 的變數告訴編碼器不要進行優化. 最終, 管理記憶體的連結串列陣列的型別為 : free_list_node *volatile free_list[16];

我們結合圖像來看看管理記憶體結點的連結串列是什麼樣子 :

中間這串陣列就是 free_list, 陣列中的每一個元素都是連結串列的頭部節點. 比如我們現在需要記憶池回收一塊 64 個大小的記憶體, 那麼這塊記憶體就會作為一個連結串列的結點, 然後被掛到 #7 的後面

這裡有個小問題, 我們以 8 的倍數劃分記憶體的大小, 而有些時候我們配置的記憶體大小並不是 8 的倍數. 這裡比較合理的做法是, 如果配置的記憶體大小不是 8 的倍數, 那麼就把它調整到 8 的倍數. 比如 n 為申請的大小, 那麼就把 n 調整到 8 的倍數, 也就是調整之後滿足 n % 8 == 0, 並且調整後的 n 不小於申請的大小

有這樣的結構之後, 記憶池已經算是搭建完畢, 接下來只要寫出配置記憶體、回收記憶體以及填補記憶池的演算法就可以了

回收記憶體的演算法我們已經講過了, 接下來我們需要重新考慮配置記憶體的演算法. 我們目前設定的記憶池最大容量是 128, 但是如果申請的記憶體大小超過 128, 那麼我們的記憶體就算全部貢獻, 也是無法滿足需求的. 而超過記憶池大小的需求一般不至於造成記憶體碎片化, 所以我們可以直接交給記憶池的上層 operator new 或者 malloc 來解決這樣的需求. 對應地, 回收記憶體的演算法也要支援這一部分. 此外, 我們需要注意到, 每一次都到記憶池去撥出一小塊記憶體顯得有點浪費運作效率. 因為當記憶池不足以提供需求大小的區塊的時候, 那麼我們就需要去 free_list 尋找. 如果我們每次都只是去 free_list 尋找, 只有 free_list 中的結點不足的時候才向記憶池申請填充, 那麼事情就會變得簡單得多. 一般來說, 我們每次填充 free_list 管理對應大小結點的個數為 16 個, 這個數字的一般計算方法可以是記憶池初始大小 / 連結串列中的結點個數, 現在是 128 / 8, 當然你也可以給一個固定的數值. 此時, 填補記憶池的演算法會分為兩個部分, 一個是填補連結串列中的結點個數, 另外一個是當記憶池中記憶體用盡的時候填充記憶池

我們簡單地給出填充對應記憶體結點的示例 :

void *refill(size_t size) {

    size_t nodes {16};      //我們給定一個固定的結點個數, 大小為 16

    auto chunk {chunk_alloc(size, nodes)};      //從記憶池中撥出一定大小的區塊, 這個函式會改變 nodes 的值, 最終 nodes 的值是撥出的區塊可以分為多少個 nodes

    /* 如果只能撥出一個結點大小的區塊, 那麼就直接回傳給客端使用 */

    if(nodes == 1) {

        return chunk;

    }

    /* 如果能走到這裡, 就說明撥出的區塊能組成不止 1 個結點 */

    auto current_node {reinterpret_cast<free_list_node *>(chunk + size)};       //通過 current_node->free_list_link = next_node, 以組成一個連結串列

    *(free_list + free_list_index(size)) = current_node;        //將頭部結點指派給 #n, free_list_index 可以根據 size 定位管理對應大小的連結串列. 例如 free_list_index(18) = 2, 此時通過 free_list + free_list_index(18) 定位到 #2. 可以直接指派是因為如果用到這個函式了, 那麼結點必定已經被外面申請完了

    while(--nodes > 1) {

        auto next_node {

                reinterpret_cast<free_list_node *>(reinterpret_cast<char *>(current_node) + size)

        };

        current_node->free_list_link = next_node;

        current_node = next_node;

    }

    current_node->free_list_link = nullptr;

    return chunk;

}

這樣, 配置記憶體和回收記憶體已經完成了. 接下來, 注意到上述程式碼中的 chunk_alloc 函式. 這個函式除了負責回傳填充 free_list 的區塊之外, 還負責填充記憶池. 這裡有很多種實作的方法, 我挑選我比較熟悉的來說 :

當記憶池的大小足以滿足填充區塊的大小 (和傳入的 nodes 有關, 填充區塊的大小為 nodes * size, 一個區塊的大小為 size, 填充區塊可以分為 nodes 個節點)的時候, 直接回傳然後調整記憶池的頭部指標即可; 如果記憶池的大小不足以滿足填充區塊的大小, 但是足以提供一個以上的區塊的時候, 修正傳入的 nodes 然後直接回傳並且調整記憶池的頭部指標即可 (由於這個時候沒有額外的需求, 所以只要供應出一個以上的區塊就可以了, 此時還不需要填充記憶池); 當記憶池的大小連一個區塊都沒有辦法提供的時候, 此時就要考慮是否需要填充記憶池了

填充記憶池是萬不得已的時候才使用的方法, 一般如果能不用這個方法就儘量不要用. 此時, 我們需要定位到 free_list 中, 看看是否有比 size 大的區塊可以供應, 雖然此時供大於求, 而且可能是遠遠大於, 造成了一定的浪費, 但是從運作效率方面考慮, 這是最好的方法. 如果連 free_list 中都沒有任何區塊可以提供了, 那麼就只能填充記憶池了

填充記憶池之前, 記憶池之內可能還有比 size 還要小的記憶體區塊, 我們把這些區塊編成連結串列放入 free_list 中. 因為我們填充之後, 所有關於記憶池的指標都會更新為新的記憶池的指標, 原來的指標被覆蓋之後就會無法找回. 如果此時, 原來的記憶池中還有些區塊沒有被編入 free_list, 就會造成記憶體流失

填充記憶池的時候, 我們還要考慮另外一個問題, 就是新的記憶池的大小問題. 一般來說, 這要根據當時記憶池使用的情況進行調整, 這個大小一般是越來越大. 填充記憶池使用的函式是 operator new 或者 malloc. 填充完畢之後, 我們可以通過遞迴來重新執行這個函式, 填充 free_list. 但是填充記憶池的時候, 可能系統無法配置新記憶池所需求大小的記憶體, 這個時候儘量不要讓例外情況擲出, 嘗試直接使用 operator new 或者 malloc 向系統申請配置 size 大小的記憶體, 修正 nodes 之後直接回傳. 只有當系統連 size 大小的記憶體配置都沒有辦法滿足的時候, 這個時候可以擲出例外情況

整個記憶池這樣就算完成了. 不過這並沒有完, 當時還有一個問題困擾了我很久, 就是程式結束的時候我們申請的記憶體如何釋放. 我們都知道, 由程式設計師配置的記憶體一定要由程式設計師進行釋放, 否則可能會造成記憶體流失, 但是這樣的問題在記憶池中並不存在. 這是因為記憶池承載了整個程式運作時的記憶體配置, 所以記憶池中的記憶體回收一定是在程式終結之後, 並且是在所有程式有關的物件被回收之後才進行釋放. 而作業系統在某一個程式結束之後, 也會承擔起回收這一個程式在運作的時候申請的所有資源, 這其中包括沒有被程式設計師釋放的記憶體. 從程式運作效率的角度來考慮, 與其我們自己來釋放記憶池, 不如直接讓作業系統在回收資源的時候連帶我們的記憶池一起回收, 前後的相差並不大. 而且如果由程式設計師自己釋放記憶池, 那麼會產生更多的程式碼, 並且對於記憶池的運作效率會產生一定的影響. 記憶池是屬於比較低層的物件, 所以我們儘量不要放不必要的操作在記憶池中 (現在想想我們曾經為了節約空間, 將節點做成了等位). 因此, 最終的答案就是不釋放, 由作業系統負責回收

按照上面我的描述, 大家自己寫出一個記憶池的難度已經大大降低了, 此處我放出我自己寫的記憶池給大家參考 :

https://github.com/Jonny0201/data_structure/blob/master/data_structure/memory.hpp