在計算機系統的復雜架構中，內存就如同人體的血液，源源不斷地為各個程序和進程輸送著數據與指令，支撐著整個系統的高效運轉。當我們在電腦上同時打開多個應用程序，或是運行大型游戲、進行復雜的數據處理時，內存的高效管理便成為了決定系統性能優劣的關鍵因素。

在 Linux 操作系統的龐大體系中，內核內存管理如同堅實的基石，支撐著整個系統的穩定運行。而在眾多內存管理技術中，伙伴算法以其獨特的魅力和強大的功能，成為了高效內存管理的一把利器。當我們深入探索 Linux 內核的奧秘時，伙伴算法就像是一位默默無聞卻又無比可靠的守護者，精心地調配著內存資源，確保每一個程序都能在恰當的時機獲得所需的內存空間，同時又能最大限度地減少內存碎片，提高內存的利用率。

那么，究竟什么是伙伴算法？它是如何在復雜的內核環境中發揮關鍵作用的呢？接下來，就讓我們一同開啟這場關于 Linux 內核內存伙伴算法的精彩之旅。

一、伙伴算法簡介

伙伴算法，簡單來說，是一種在操作系統內存管理中廣泛應用的動態存儲管理算法 。它如同一位精打細算的管家，對內存資源進行著巧妙的分配與回收。在 Linux 系統中，內存被劃分成一個個大小固定的頁框，而伙伴算法就圍繞著這些頁框展開工作。它將所有的空閑頁框分組為 11 個塊鏈表，每塊鏈表分別包含大小為 1、2、4、8、16、32、64、128、256、512 和 1024 個連續頁框的頁框塊。這些不同大小的塊鏈表，就像是一個個不同規格的 “資源倉庫”，等待著被合理調配。

在Linux系統中，內存的分配與回收速率直接影響系統的存取效率。當內核頻繁請求和釋放不同大小的一組連續頁框時，會導致許多外部空閑碎片，造成空間的浪費。使用伙伴算法可以有效地緩解該問題。伙伴關系機制是操作系統中的一種動態存儲管理算法。在進行內存分配時，該算法通過不斷平分較大的空閑內存塊來獲得較小的空閑內存塊，直到獲得所需要的內存塊；在進行內存回收時，該算法盡可能地合并空閑塊。

內存管理是應用程序通過硬件和軟件協作訪問內存的一種方法，當進程請求內存使用時，它給進程分配可用的內存；當進程釋放內存時，回收相應的內存，同時負責跟蹤系統中內存的使用狀態。

在Linux系統中，首先將內存分為若干個節點，然后每個節點又可以分為1-3個區，每個區下又有若干個頁。頁是內存管理的基本單元。

當前存在的問題

當系統工作時，CPU最先訪問的地址不是物理內存中的實地址，而是虛擬地址空間的虛地址。當請求分頁時，首先在虛擬地址空間中分配一個虛擬空間，然后根據需要為此區間分配相應的物理頁面并建立映射。

在分配空間時，我們首先想到的便是malloc函數。由于在實際情況中，操作系統必須能夠在任意時刻申請和釋放任意大小的內存，該函數的實現并不容易，導致的主要問題有延時問題和碎片問題。

延時問題指的是系統查找到可分配單元的時間變長，例如程序請求分配一個64KB的內存空間，系統查看64KB空間發現不全是空余的，于是查看65KB的空間，發現仍不能滿足需求，直到查看80KB空間時，才滿足了需求，這種方式請求次數多達17次，頻繁操作時，非常耗時。

若系統以較大的定長空間來分配內存，在一定程度上可以節省時間，但帶來的是碎片過多問題，由于每次用較大的空間進行分配，系統中出現大量碎片，導致內存浪費。嚴重者會導致內存無法完成分配，雖然仍有許多碎片空間。

基于此，系統需要一種能夠高效分配內存，同時又能減少產生碎片的算法，伙伴算法能有效地解決該問題，如今已成為操作系統中的一種基礎算法。

二、伙伴算法核心原理

2.1伙伴關系的奧秘

在伙伴算法的世界里，伙伴關系是其核心概念，如同連接各個內存塊的紐帶，貫穿于整個內存管理的過程。所謂伙伴關系，是指在內存分配過程中，當一個較大的內存塊被分割時，由同一個大塊內存分裂出來的兩個大小相等的小塊內存，它們之間就構成了伙伴關系 。這就好比一對雙胞胎，它們在內存的 “家族” 中有著緊密的聯系。

伙伴關系需要滿足三個關鍵條件：一是兩個內存塊必須具有相同的大小，這是伙伴關系的基礎，就像天平的兩端，只有重量相等才能保持平衡；二是它們的物理地址是連續的，如同相鄰的兩座房子，緊密相連；三是這兩個塊必須是從同一個大塊中分離出來的，這體現了它們的 “血緣關系”。例如，假設系統中有一個大小為 8 個頁框的內存塊，當它被分割成兩個大小為 4 個頁框的內存塊時，這兩個 4 頁框的內存塊就互為伙伴。它們大小相同，物理地址連續，且都來自于最初的 8 頁框內存塊，完全符合伙伴關系的定義。

伙伴關系在內存分配和回收過程中起著舉足輕重的作用。在分配內存時，當系統找不到與請求大小完全匹配的空閑內存塊時，就會從更大的內存塊中進行分割，產生的伙伴內存塊，一部分用于滿足當前的分配需求，另一部分則作為空閑內存塊保留下來，以備后續分配。

而在內存回收時，伙伴關系則成為了合并空閑內存塊的關鍵依據。當一個內存塊被釋放時，系統會首先檢查其伙伴內存塊是否也處于空閑狀態。如果伙伴內存塊空閑，那么這兩個伙伴就會合并成一個更大的內存塊，重新回到空閑內存塊的鏈表中。這樣一來，通過伙伴關系的巧妙運用，系統能夠有效地減少內存碎片的產生，提高內存的利用率，就像一位心靈手巧的裁縫，將零碎的布料巧妙地拼接起來，使其發揮更大的作用。

2.2分配過程的深度剖析

當系統中的進程發出內存分配請求時，伙伴算法便開始了它的高效運作。其分配過程可以分為以下幾個關鍵步驟：

首先，伙伴算法會根據請求的內存大小，確定所需內存塊的階數。在伙伴算法中，內存塊的大小是以 2 的冪次方來表示的，例如 1 頁、2 頁、4 頁、8 頁等，每一個不同的大小對應著不同的階數。假設請求分配的內存大小為 n 頁，那么系統會通過計算找到滿足 2^k >= n 的最小 k 值，這個 k 值對應的階數就是所需內存塊的階數。

接下來，系統會在相應階數的空閑內存塊鏈表中進行查找。如果該鏈表中有空閑的內存塊，那么直接從鏈表中取出一個內存塊分配給請求者，分配過程就此完成。例如，當請求分配 4 頁內存時，系統會先確定其階數為 2（因為 2^2 = 4），然后在階數為 2 的空閑內存塊鏈表中查找。若鏈表中有空閑塊，就可以直接將其分配給進程。

然而，當相應階數的空閑內存塊鏈表為空時，分配過程就會變得復雜一些。此時，系統會向上查找更大階數的空閑內存塊鏈表。找到一個更大的空閑內存塊后，將其分割成兩個大小相等的子塊，這兩個子塊就成為了伙伴關系。其中一個子塊的大小與請求的內存大小相同，將其分配給請求者；另一個子塊則插入到對應的空閑內存塊鏈表中，以備后續分配使用。例如，當請求分配 4 頁內存，但階數為 2 的鏈表為空時，系統會查找階數為 3（2^3 = 8）的鏈表。若找到一個 8 頁的空閑內存塊，就將其分割成兩個 4 頁的子塊，一個分配給請求進程，另一個插入到階數為 2 的空閑內存塊鏈表中。

如果一直向上查找，直到最大階數的空閑內存塊鏈表都沒有找到合適的內存塊，那么分配過程就會失敗，系統會返回錯誤信息，告知請求者內存分配失敗。

為了更直觀地理解，我們來看一個具體的例子。假設系統的內存被劃分為多個頁框，當前有一個進程請求分配 8 頁內存。系統首先確定所需內存塊的階數為 3（2^3 = 8），然后在階數為 3 的空閑內存塊鏈表中查找。發現該鏈表為空，于是向上查找階數為 4（2^4 = 16）的鏈表。在階數為 4 的鏈表中找到一個 16 頁的空閑內存塊，將其分割成兩個 8 頁的子塊，一個子塊分配給請求進程，另一個子塊插入到階數為 3 的空閑內存塊鏈表中，至此，分配過程完成。通過這個例子，我們可以清晰地看到伙伴算法在內存分配過程中的具體操作步驟和邏輯。

下面通過一個簡單的例子來說明該算法分配過程：

假設要請求一個256（129~256）個頁框的塊。算法先在256個頁框的鏈表中檢查是否有一個空閑塊。如果沒有這樣的塊，算法會查找下一個更大的頁塊，也就是，在512個頁框的鏈表中找一個空閑塊。如果存在這樣的塊，內核就把512的頁框分成兩等分，一般用作滿足需求，另一半則插入到256個頁框的鏈表中。如果在512個頁框的塊鏈表中也沒找到空閑塊，就繼續找更大的塊——1024個頁框的塊。如果這樣的塊存在，內核就把1024個頁框塊的256個頁框用作請求，然后剩余的768個頁框中拿512個插入到512個頁框的鏈表中，再把最后的256個插入到256個頁框的鏈表中。如果1024個頁框的鏈表還是空的，算法就放棄并發出錯誤信號。相關數據結構：

#define MAX_ORDER 11
 
struct zone {
  ……
 struct free_area free_area[MAX_ORDER];
 ……
} 
struct free_area {
 struct list_head free_list;
 unsigned long nr_free;//該組類別塊空閑的個數
};

Zone結構體中的free_area數組的第k個元素，它保存了所有連續大小為2^k的空閑塊，具體是通過將連續頁的第一個頁插入到free_list中實現的，連續頁的第一個頁的頁描述符的private字段表明改部分連續頁屬于哪一個order鏈表。

(1)伙伴算法系統初始化

Linux內核啟動時，伙伴算法還不可用，linux是通過bootmem來管理內存，在mem_init中會把bootmem位圖中空閑的內存塊插入到伙伴算法系統的free_list中。

調用流程如下：

mem_init----->__free_all_bootmem()—>free_all_bootmem()>free_all_bootmem_core(NODE_DATA(0))–>free_all_bootmem_core(pgdat)

//利用free_page 將頁面分給伙伴管理器
free_all_bootmem
    return(free_all_bootmem_core(NODE_DATA(0)));  //#define NODE_DATA(nid) (&contig_page_data)
        bootmem_data_t *bdata = pgdat->bdata;
        page = virt_to_page(phys_to_virt(bdata->node_boot_start));
 idx = bdata->node_low_pfn - (bdata->node_boot_start >> PAGE_SHIFT);
 map = bdata->node_bootmem_map;

 for (i = 0; i < idx; ) 
 unsigned long v = ~map[i / BITS_PER_LONG];
 //如果32個頁都是空閑的
 if (gofast && v == ~0UL)
 count += BITS_PER_LONG;
 __ClearPageReserved(page);
 order = ffs(BITS_PER_LONG) - 1;
 //設置32個頁的引用計數為1
 set_page_refs(page, order)

 //一次性釋放32個頁到空閑鏈表
 __free_pages(page, order);
 __free_pages_ok(page, order);
 list_add(&page->lru, &list);
 //page_zone定義如下return zone_table[page->flags >> NODEZONE_SHIFT];
 //接收一個頁描述符的地址作為它的參數，它讀取頁描述符的flags字段的高位，并通過zone_table數組來確定相應管理區描述符的地址，最終將頁框回收到對應的管理區中
 free_pages_bulk(page_zone(page), 1, &list, order);
 i += BITS_PER_LONG;
 page += BITS_PER_LONG;

 //這32個頁中，只有部分是空閑的
 else if (v)
 for (m = 1; m && i < idx; m<<=1, page++, i++)
 if (v & m)
 count++;
 __ClearPageReserved(page);
 set_page_refs(page, 0);
 //釋放單個頁
 __free_page(page);
 else
 i+=BITS_PER_LONG;
 page += BITS_PER_LONG;

 //釋放內存分配位圖本身
 page = virt_to_page(bdata->node_bootmem_map);
 for (i = 0; i < ((bdata->node_low_pfn-(bdata->node_boot_start >> PAGE_SHIFT))/8 + PAGE_SIZE-1)/PAGE_SIZE; i++,page++)
 __ClearPageReserved(page);
 set_page_count(page, 1);
 __free_page(page);

(2)伙伴算法系統分配空間

page = __rmqueue(zone, order);
 //從所請求的order開始，掃描每個可用塊鏈表進行循環搜索。
    for (current_order = order; current_order < MAX_ORDER; ++current_order)
        area = zone->free_area + current_order;
        if (list_empty(&area->free_list))
            continue; 
        page = list_entry(area->free_list.next, struct page, lru);  
 //首先在空閑塊鏈表中刪除第一個頁框描述符。
        list_del(&page->lru);
 //清楚第一個頁框描述符的private字段，該字段表示連續頁框屬于哪一個大小的鏈表
        rmv_page_order(page);
        area->nr_free--;
        zone->free_pages -= 1UL << order;
 //如果是從更大的order鏈表中申請的，則剩下的要重新插入到鏈表中
        return expand(zone, page, order, current_order, area);
            unsigned long size = 1 << high;
            while (high > low)
                area--;
                high--;
                size >>= 1; 
 //該部分連續頁面插入到對應的free_list中
                list_add(&page[size].lru, &area->free_list); 
                area->nr_free++;
 //設置該部分連續頁面的order
                set_page_order(&page[size], high);
                    page->private = order;
                    __SetPagePrivate(page);
                         __set_bit(PG_private, &(page)->flags)
            return page;

(3)伙伴算法系統回收空間

free_pages_bulk
 //linux內核將空間分為三個區，分別是ZONE_DMA、ZONE_NORMAL、ZONR_HIGH，zone_mem_map字段就是指向該區域第一個頁描述符
    struct page *base = zone->zone_mem_map;
    while (!list_empty(list) && count--)  
        page = list_entry(list->prev, struct page, lru);
        list_del(&page->lru);
        __free_pages_bulk
            int order_size = 1 << order;
 //該段空間的第一個頁的下標
            page_idx = page - base; 
            zone->free_pages += order_size;
 //最多循環10 - order次。每次都將一個塊和它的伙伴進行合并。
            while (order < MAX_ORDER-1)
 //尋找伙伴，如果page_idx=128，order=4，則buddy_idx=144
                buddy_idx = (page_idx ^ (1 << order)); 
                buddy = base + buddy_idx;
                /**
                 * 判斷伙伴塊是否是大小為order的空閑頁框的第一個頁。
                 * 首先，伙伴的第一個頁必須是空閑的(_count == -1)
                 * 同時，必須屬于動態內存(PG_reserved被清0,PG_reserved為1表示留給內核或者沒有使用)
                 * 最后，其private字段必須是order
                 */
                if (!page_is_buddy(buddy, order))
                    break;
                list_del(&buddy->lru);
                area = zone->free_area + order;
 //原先所在的區域空閑頁減少
                area->nr_free--;   
                rmv_page_order(buddy);
                    __ClearPagePrivate(page);
                    page->private = 0;
                page_idx &= buddy_idx;
                order++;

 /**
 * 伙伴不能與當前塊合并。
 * 將塊插入適當的鏈表，并以塊大小的order更新第一個頁框的private字段。
 */
            coalesced = base + page_idx;
            set_page_order(coalesced, order);
            list_add(&coalesced->lru, &zone->free_area[order].free_list);
            zone->free_area[order].nr_free++;

2.3回收過程的全面解讀

當進程使用完內存并將其釋放時，伙伴算法的回收機制便開始發揮作用。內存回收過程是分配過程的逆過程，同樣遵循著一定的規則和步驟：

1. 首先，當一個內存塊被釋放時，系統會根據該內存塊的大小確定其所屬的階數，然后將其插入到對應階數的空閑內存塊鏈表中。例如，釋放一個大小為 4 頁的內存塊，系統會確定其階數為 2，然后將該內存塊插入到階數為 2 的空閑內存塊鏈表中。
2. 接著，系統會檢查剛插入的內存塊的伙伴是否也在空閑鏈表中。如果伙伴內存塊也處于空閑狀態，那么就將這兩個伙伴內存塊合并成一個更大的內存塊。合并后的內存塊的階數會增加 1，然后將其插入到新階數對應的空閑內存塊鏈表中。例如，釋放的 4 頁內存塊在階數為 2 的鏈表中找到了伙伴，它們合并成一個 8 頁的內存塊，階數變為 3，然后將這個 8 頁的內存塊插入到階數為 3 的空閑內存塊鏈表中。

這個合并過程會持續進行，系統會不斷檢查合并后的內存塊在更大階數的鏈表中是否還有伙伴，直到不能合并或者已經合并至最大塊為止。例如，合并后的 8 頁內存塊在階數為 3 的鏈表中又找到了伙伴，它們再次合并成一個 16 頁的內存塊，階數變為 4，然后將這個 16 頁的內存塊插入到階數為 4 的空閑內存塊鏈表中。如果在某個階數的鏈表中沒有找到伙伴，那么合并過程就會停止。

為了更好地理解回收過程，我們來看一個具體的實例：

假設系統中有一個進程釋放了一個大小為 16 頁的內存塊，其階數為 4。系統將這個 16 頁的內存塊插入到階數為 4 的空閑內存塊鏈表中。此時，檢查發現其伙伴也在空閑鏈表中，于是將這兩個 16 頁的內存塊合并成一個 32 頁的內存塊，階數變為 5，然后將這個 32 頁的內存塊插入到階數為 5 的空閑內存塊鏈表中。接著，在階數為 5 的鏈表中檢查，發現沒有伙伴，合并過程停止。通過這個實例，我們可以清楚地看到伙伴算法在內存回收過程中的詳細操作流程，以及如何通過伙伴合并來減少內存碎片，提高內存的利用率。

三、伙伴算法的實現與數據結構

3.1關鍵數據結構解析

在伙伴算法的實現中，涉及到幾個關鍵的數據結構，它們相互協作，共同完成內存的分配與回收任務。

struct zone 結構體是內存管理區的重要描述結構 ，它包含了系統中不同類型內存區域的相關信息。在 Linux 系統中，內存被劃分為多個不同的區域，如 DMA 區域、Normal 區域和 HighMem 區域等，每個區域都有其獨特的用途和特點。struct zone 結構體中的 free_area 數組是伙伴算法的核心數據結構之一，它保存了所有連續大小為 2^k 的空閑塊，其中 k 表示分配階數 。通過這個數組，系統可以快速地找到不同大小的空閑內存塊，為內存分配和回收提供了便利。

struct free_area 結構體則是對空閑內存塊的具體描述。它包含一個 free_list 鏈表，用于將相同大小的空閑內存塊組織在一起，方便管理和查找。每個空閑內存塊都通過其起始頁框的 lru 域連接到 free_list 鏈表中，形成一個雙向鏈表結構 。這樣，在進行內存分配和回收時，系統可以通過遍歷鏈表快速地找到合適的空閑內存塊。nr_free 字段記錄了該 free_area 中總共的空閑內存塊的數量，通過這個字段，系統可以快速了解當前空閑內存的總量，以便進行合理的內存分配決策。

struct page 結構體是頁描述符，用于描述系統中的每一個物理頁。在伙伴算法中，每個內存塊都是由多個連續的物理頁組成，而 struct page 結構體則為這些物理頁提供了詳細的描述信息。lru 域作為鏈表節點，用于將物理頁連接到 free_list 鏈表中，實現內存塊的組織和管理。private 字段在伙伴算法中也有著重要的作用，它用于保存物理頁所在內存塊的分配階數等相關信息，為內存分配和回收過程中的各種操作提供了必要的依據。

這些關鍵數據結構之間存在著緊密的聯系。struct zone 結構體通過 free_area 數組與 struct free_area 結構體相連，從而管理不同大小的空閑內存塊。而 struct free_area 結構體又通過 free_list 鏈表將相同大小的空閑內存塊組織在一起，每個內存塊的起始頁框通過 lru 域連接到鏈表中，實現了內存塊的有效管理。struct page 結構體則作為內存塊的基本組成單位，通過其各個字段與其他數據結構相互關聯，共同完成內存的分配與回收任務。這種緊密的聯系和協作，使得伙伴算法能夠高效地管理內存資源，確保系統的穩定運行。

3.2系統初始化流程

在 Linux 內核啟動時，伙伴算法的初始化是一個至關重要的過程，它為后續的內存管理工作奠定了堅實的基礎。初始化過程主要包括內存塊的初始化和鏈表的構建等步驟。

在系統啟動的早期階段，內存是通過 bootmem 分配器進行管理的。當系統進入到 mem_init 階段時，伙伴算法開始接管內存管理工作 。此時，系統會將 bootmem 位圖中空閑的內存塊插入到伙伴算法系統的 free_list 鏈表中，實現內存管理的交接。

具體的調用流程如下：從 start_kernel 函數開始，經過一系列的調用，最終到達 mem_init 函數。在 mem_init 函數中，會調用 __free_all_bootmem 函數，該函數進一步調用 free_all_bootmem 函數，然后通過 free_all_bootmem_core 函數，利用 free_page 函數將頁面分給伙伴管理器 。在這個過程中，系統會遍歷 bootmem_data_t 結構體，獲取每次返回的頁數，并將這些空閑內存塊按照伙伴算法的規則插入到相應的 free_list 鏈表中。

除了插入空閑內存塊，系統還會對 free_area 數組中的各個元素進行初始化。在 free_area_init_core 函數中，會對每個 free_area 結構體的 free_list 鏈表進行初始化，將其設置為空鏈表，并將 nr_free 字段初始化為 0 。這樣，在初始化完成后，free_area 數組中的每個元素都處于初始狀態，等待著后續的內存分配和回收操作。

在初始化過程中，系統還會對每個 pageblock 的起始頁框對應的 struct zone 中的 pageblock_flags 代表的位圖相關區域進行標記，將其標記為可移動的，表示該 pageblock 為可移動的 。這一操作在內核初始化伙伴系統時非常重要，它為后續的內存管理提供了重要的信息，確保系統能夠正確地處理不同類型的內存塊。通過這些初始化步驟，伙伴算法在 Linux 內核啟動時完成了自身的準備工作，為系統的內存管理提供了可靠的支持。

3.3分配與回收的代碼實現

以 Linux 內核代碼為例，我們來深入分析伙伴算法內存分配和回收的具體代碼實現，從而更直觀地了解算法的實際運行機制。

在內存分配方面，內核中使用 alloc_pages 系列函數來實現基于伙伴算法的頁框分配 。這些函數最終都會調用伙伴算法的入口函數 buffered_rmqueue 。在 buffered_rmqueue 函數中，首先會判斷分配階是否為 0 。如果分配階為 0，說明請求的是單個頁框，此時會啟用 per-CPU 機制來分配物理內存，以提高分配效率。因為對于單個頁框的分配，per-CPU 機制可以直接從每個 CPU 的本地緩存中獲取空閑頁框，避免了全局搜索的開銷。如果分配階不為 0，則調用 __rmqueue 函數進行內存分配。

__rmqueue 函數是內存分配的核心函數之一，它首先會調用 __rmqueue_smallest 函數，嘗試從當前指定的分配階到最高分配階依次進行遍歷 。在每次遍歷的分配階鏈表中，根據參數 migratetype 選擇正確的遷移隊列。如果在指定的遷移類型上分配失敗后，再選用其他備用的遷移列表進行內存分配，該過程通過 __rmqueue_fallback 函數完成。通過這種方式，內核總是在竭盡全力保證滿足分配內存的請求，確保系統的正常運行。

當在 __rmqueue_smallest 函數中選定一個頁框塊鏈表后，只要該鏈表不為空，就說明可以分配該分配階對應的頁框塊 。此時，會通過 list_entry 函數將該頁框塊從鏈表上移除，然后將頁框塊首頁框的 PG_buddy 標志刪除，這標志著當前頁框塊已經不屬于伙伴鏈表。并且將該首頁框描述符中的 private 置 0，該字段中本來保存的是其所處頁框塊的分配階。以上這個過程通過 rmv_page_order 函數完成。此外，還要更新頁框塊鏈表 nr_free 的值，以反映當前空閑內存塊的數量變化。

在內存回收方面，當一個內存塊被釋放時，會調用 __free_pages 函數 。該函數首先會根據釋放內存塊的大小確定其所屬的階數，然后將其插入到對應階數的空閑內存塊鏈表中。接著，系統會檢查剛插入的內存塊的伙伴是否也在空閑鏈表中。如果伙伴內存塊也處于空閑狀態，那么就將這兩個伙伴內存塊合并成一個更大的內存塊。合并后的內存塊的階數會增加 1，然后將其插入到新階數對應的空閑內存塊鏈表中。這個合并過程會持續進行，直到不能合并或者已經合并至最大塊為止。在合并過程中，會調用 merge_free_area 等函數來完成內存塊的合并和鏈表的調整操作，確保空閑內存塊的有效管理和利用。

四、伙伴算法場景及優缺點

4.1伙伴算法的用途

管理物理內存，解決外碎片問題。

4.2滿足以下條件的兩個塊稱為伙伴

• 兩個塊具有相同的大小，記作b
• 它們的物理地址是連續的
• 第一塊的第一個頁框的物理地址是2*b*2^12的倍數

4.3伙伴算法管理結構

伙伴算法把物理內存分為11個組，第0、1、...10組分別包含2^0、2^1、...2^10個連續物理頁面的內存。在zone結構中，有一個free_area數組，數組的每一個成員代表一個組，相關定義如下：

#define MAX_ORDER 11

struct zone {

    ...

struct free_area free_area[MAX_ORDER];

    ...

}

struct free_area {

struct list_head free_list;

/*該組類別塊空閑的個數*/

unsigned long nr_free;

};

4.4伙伴算法的初始化和釋放

(1)伙伴算法初始化過程

在start_kernel->mem_init-> free_all_bootmem_node->free_all_bootmem_core-> __free_pages_bootmem-> __free_pages->__free_pages_ok->free_one_page-> __free_one_page函數中，通過對每一個頁面進行釋放，從而完成對伙伴算法的初始化工作。

(2)伴算法的具體釋放過程

伙伴算法釋放的思想：當釋放2^order頁大小內存時，查看它的伙伴是否空閑，如果空閑就將伙伴從該組鏈表中刪除，并且將這兩個空閑的伙伴內存區域合并成一個更高階的空閑內存區域，依次這樣操作下去。

_free_one_page函數分析如下：

static inline void __free_one_page(struct page *page,

struct zone *zone, unsigned int order)

{

    unsigned long page_idx;
    int order_size = 1 << order;
    int migratetype = get_pageblock_migratetype(page);
    /*用PFN作為mem_map數組下標就可以索引到對應的page結構*/
    page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);
    __mod_zone_page_state(zone, NR_FREE_PAGES, order_size);

    /*這個循環主要查看當前釋放塊伙伴是否空閑，如果空閑則合并它們*/

    while (order < MAX_ORDER-1) { 

    unsigned long combined_idx;

    struct page *buddy;


    /*找到釋放塊的伙伴*/

    buddy = __page_find_buddy(page, page_idx, order);

    /*判斷釋放塊的伙伴是否空閑*/

    if (!page_is_buddy(page, buddy, order))

        break;


    list_del(&buddy->lru);

    zone->free_area[order].nr_free--;

    rmv_page_order(buddy);

    combined_idx = __find_combined_index(page_idx, order);

    page = page + (combined_idx - page_idx);

    page_idx = combined_idx;

    order++;

    }

    set_page_order(page, order);

    list_add(&page->lru,

    &zone->free_area[order].free_list[migratetype]);

    zone->free_area[order].nr_free++;

}

4.5伙伴算法優缺點

(1)顯著優勢

伙伴算法在 Linux 內存管理中展現出了諸多顯著優勢，這些優勢使其成為內存管理的核心算法之一，為系統的高效穩定運行提供了有力保障。

首先，伙伴算法在減少內存碎片方面表現出色 。在傳統的內存分配方式中，頻繁的內存分配和釋放操作容易導致內存碎片化，使得內存空間被分割成許多小塊，這些小塊可能因為太小而無法滿足后續的內存分配需求，從而造成內存資源的浪費。而伙伴算法通過將內存塊按照 2 的冪次方大小進行組織和管理，有效地減少了外部碎片的產生。在內存分配時，它總是從最接近請求大小的內存塊中進行分配，如果沒有完全匹配的內存塊，就會從更大的內存塊中進行分割，產生的伙伴內存塊會被合理地管理和利用，避免了內存空間的碎片化。在內存回收時，通過伙伴合并機制，能夠將相鄰的空閑內存塊合并成更大的內存塊，進一步減少了內存碎片的數量，提高了內存的連續性。

其次，伙伴算法大大提高了內存利用率 。由于其合理的內存分配和回收策略，使得內存資源能夠得到充分的利用。它能夠根據進程的實際需求，精確地分配合適大小的內存塊，避免了內存的過度分配和浪費。在分配內存時，它會盡量選擇最接近請求大小的內存塊進行分配，減少了內部碎片的產生。當進程釋放內存時，通過伙伴合并機制，能夠將空閑內存塊合并成更大的內存塊，使得這些內存塊能夠更好地滿足后續的內存分配需求，從而提高了內存的整體利用率。

此外，伙伴算法還具有高效的分配和回收效率 。在內存分配過程中，通過對空閑內存塊鏈表的快速查找和分割操作，能夠迅速地找到合適的內存塊并進行分配，大大縮短了內存分配的時間。在內存回收過程中，通過伙伴合并機制，能夠快速地將空閑內存塊合并成更大的內存塊，并將其插入到相應的空閑內存塊鏈表中，提高了內存回收的效率。這種高效的分配和回收機制，使得系統能夠快速地響應進程的內存請求，提高了系統的整體性能。

(2)固有缺陷

盡管伙伴算法在內存管理中具有諸多優勢，但它也并非完美無缺，存在一些固有的局限性。

首先，伙伴算法存在內部碎片問題 。由于伙伴算法按照 2 的冪次方大小來分配內存塊，當請求的內存大小不是 2 的冪次方時，分配的內存塊往往會比實際需求大，從而產生內部碎片。如果一個進程需要 10 字節的內存，而伙伴算法只能分配 16 字節的內存塊，那么就會產生 6 字節的內部碎片。這些內部碎片雖然不會像外部碎片那樣導致內存無法分配，但也會造成內存空間的浪費，降低了內存的實際利用率。

其次，伙伴算法的分配粒度受到限制 。它只能分配大小為 2 的冪次方的內存塊，這在一定程度上限制了其靈活性。對于一些對內存大小要求非常精確的應用場景，伙伴算法可能無法提供最合適的內存塊，從而影響應用的性能。在一些嵌入式系統中，由于內存資源非常有限，對內存的分配粒度要求非常高，伙伴算法的這種限制就可能會帶來一些問題。

此外，伙伴算法在內存塊合并時也存在一定的限制 。在回收內存時，只有當兩個伙伴內存塊都處于空閑狀態時才能進行合并，如果其中一個伙伴內存塊被占用，那么就無法進行合并，這可能會導致內存碎片的產生。一個大小為 8 頁的內存塊被釋放，但其伙伴內存塊被占用，那么這個 8 頁的內存塊就無法與伙伴合并成 16 頁的內存塊，只能以 8 頁的空閑內存塊的形式存在，這就可能會影響后續的內存分配效率。

五、伙伴算法的應用場景及優化策略

5.1應用場景

伙伴算法在 Linux 內核中有著廣泛的應用場景，它為系統的高效運行提供了有力支持。在進程內存分配方面，伙伴算法發揮著關鍵作用。當一個新的進程被創建時，它需要申請一定的內存空間來存儲其代碼、數據和堆棧等信息。伙伴算法能夠根據進程的需求，快速地分配合適大小的內存塊，確保進程能夠順利啟動和運行。在多進程并發運行的環境中，各個進程可能會隨時申請或釋放內存，伙伴算法能夠高效地處理這些請求，保證內存資源的合理分配和利用，避免出現內存分配失敗或內存碎片過多的情況，從而維持系統的穩定運行。

在設備驅動程序中，伙伴算法也有著不可或缺的應用。設備驅動程序需要與硬件設備進行交互，而這些交互往往需要大量的內存來存儲設備數據、控制信息等。例如，在網絡設備驅動中，需要分配內存來緩存網絡數據包；在磁盤設備驅動中，需要分配內存來存儲磁盤讀寫的數據。伙伴算法能夠為設備驅動程序提供高效的內存分配服務，確保設備能夠正常工作。當網絡設備接收到大量的數據包時，伙伴算法能夠迅速分配足夠的內存來緩存這些數據包，保證網絡通信的順暢；當磁盤設備進行讀寫操作時，伙伴算法能夠及時分配內存來存儲數據，提高磁盤的讀寫效率。

在內存映射文件系統中，伙伴算法同樣發揮著重要作用。內存映射文件系統允許將文件直接映射到內存中，使得對文件的訪問就像對內存的訪問一樣高效。在這種情況下，伙伴算法負責分配內存來存儲映射的文件數據。當用戶打開一個大文件并進行頻繁的讀寫操作時，內存映射文件系統通過伙伴算法分配內存，將文件數據映射到內存中，用戶可以直接在內存中對文件進行操作，大大提高了文件訪問的速度。同時，當文件操作完成后，伙伴算法又能及時回收內存，避免內存資源的浪費。

5.2優化策略

盡管伙伴算法在內存管理中表現出色，但為了進一步提升其性能，針對其局限性，研究者們提出了一系列優化策略。在改進分配策略方面，一種常見的優化方法是引入自適應分配策略 。傳統的伙伴算法按照固定的 2 的冪次方大小來分配內存塊，容易產生內部碎片。而自適應分配策略則可以根據實際請求的內存大小，更加靈活地選擇分配的內存塊。當請求的內存大小接近某個 2 的冪次方時，可以嘗試分配稍大的內存塊，但通過一定的機制來減少內部碎片的產生。可以對分配的內存塊進行標記，記錄其實際使用的內存大小，當該內存塊被釋放時，根據標記信息進行更加合理的合并操作，提高內存的利用率。

引入新的數據結構也是優化伙伴算法的重要方向之一 。例如，一些研究提出使用哈希表來輔助伙伴算法的內存分配和回收。哈希表可以快速地查找空閑內存塊，提高分配和回收的效率。通過將空閑內存塊的地址和大小等信息存儲在哈希表中，當需要分配內存時，可以直接在哈希表中查找合適的內存塊，避免了對鏈表的遍歷，從而大大縮短了分配時間。在內存回收時，也可以通過哈希表快速地找到伙伴內存塊，實現高效的合并操作。

此外，還可以結合其他內存管理技術來優化伙伴算法 。將伙伴算法與 slab 分配器相結合，對于一些頻繁分配和釋放的小對象，可以使用 slab 分配器來進行管理，而對于大內存塊的分配和回收，則繼續使用伙伴算法。這樣可以充分發揮兩種算法的優勢，既減少了伙伴算法在處理小對象時的內部碎片問題，又利用了伙伴算法在管理大內存塊時的高效性，從而提高整個內存管理系統的性能。通過這些優化策略的實施，伙伴算法能夠在不同的應用場景中更好地發揮作用，為 Linux 內核的內存管理提供更加高效、可靠的支持。

六、伙伴算法在不同Linux版本中的演進

6.1版本變化概述

隨著 Linux 內核的不斷發展和演進，伙伴算法也在持續改進和優化，以適應日益復雜的系統需求和硬件環境。在早期的 Linux 版本中，伙伴算法的實現相對簡單，主要側重于基本的內存分配和回收功能。隨著系統對內存管理性能要求的不斷提高，伙伴算法在后續版本中經歷了一系列的改進和擴展。

在 Linux 2.6 版本中，對伙伴算法進行了多項重要改進。引入了內存熱插拔功能，使得系統能夠在運行時動態地添加或移除內存模塊。為了支持這一功能，伙伴算法在內存塊的管理和鏈表操作上進行了相應的調整，確保在內存熱插拔過程中內存分配和回收的穩定性和正確性。該版本還對伙伴算法的分配策略進行了優化，通過更合理地選擇空閑內存塊，提高了內存分配的效率，減少了內存碎片的產生。

到了 Linux 3.0 版本，伙伴算法進一步引入了一些新的特性和優化。引入了基于遷移類型的內存分配機制，將內存塊分為不同的遷移類型，如不可移動、可回收和可移動等。在內存分配時，根據不同的遷移類型選擇合適的內存塊，提高了內存分配的靈活性和效率。該版本還對內存回收機制進行了改進，通過更智能地合并空閑內存塊，減少了內存碎片的積累，提高了內存的利用率。

在 Linux 4.0 及之后的版本中，伙伴算法繼續在性能優化和功能擴展方面進行演進。在一些高并發場景下，對伙伴算法的鎖機制進行了優化，減少了鎖競爭，提高了內存分配和回收的并發性能。還引入了一些新的數據結構和算法，如哈希表輔助的內存查找機制，進一步提高了內存分配和回收的速度。

6.2改進意義分析

這些在不同 Linux 版本中對伙伴算法的改進，對提升內存管理性能和效率具有重要意義。內存熱插拔功能的引入，使得系統在運行時能夠靈活地調整內存配置，滿足不同的應用場景需求。在服務器環境中，當業務量增加時，可以動態添加內存模塊，而伙伴算法能夠正確地管理這些新增的內存，確保系統的穩定運行；當業務量減少時，又可以移除不必要的內存模塊，節省能源消耗。

基于遷移類型的內存分配機制，有效地提高了內存分配的靈活性和效率。在現代操作系統中，不同類型的內存需求越來越多樣化，通過將內存塊分為不同的遷移類型，系統可以根據具體的需求選擇最合適的內存塊進行分配。對于一些不可移動的內核數據結構，分配不可移動類型的內存塊，確保其在內存中的穩定性；對于一些可移動的用戶數據，分配可移動類型的內存塊，便于在內存管理過程中進行優化和調整。

對內存回收機制的改進，大大減少了內存碎片的積累，提高了內存的利用率。內存碎片的存在會導致內存空間的浪費，降低系統的性能。通過更智能地合并空閑內存塊，伙伴算法能夠及時地將相鄰的空閑內存塊合并成更大的內存塊，使得內存空間更加連續，提高了內存的可分配性。在一些長時間運行的系統中，這種改進能夠有效地避免內存碎片化問題的惡化，確保系統在長時間運行過程中始終保持良好的性能。

在高并發場景下對鎖機制的優化以及引入新的數據結構和算法，顯著提高了內存分配和回收的速度和并發性能。在多線程、多進程的高并發環境中，內存分配和回收操作頻繁，如果鎖競爭嚴重，會導致系統性能大幅下降。通過優化鎖機制，減少了鎖競爭，使得多個線程或進程能夠更高效地同時進行內存操作。新的數據結構和算法的引入，如哈希表輔助的內存查找機制，能夠快速地定位空閑內存塊，大大縮短了內存分配和回收的時間，提高了系統的整體性能。這些改進使得 Linux 內核的內存管理更加高效、靈活和穩定，為系統的運行提供了有力的支持。