在計算機系統(tǒng)的復(fù)雜架構(gòu)中，內(nèi)存就如同人體的血液，源源不斷地為各個程序和進程輸送著數(shù)據(jù)與指令，支撐著整個系統(tǒng)的高效運轉(zhuǎn)。當(dāng)我們在電腦上同時打開多個應(yīng)用程序，或是運行大型游戲、進行復(fù)雜的數(shù)據(jù)處理時，內(nèi)存的高效管理便成為了決定系統(tǒng)性能優(yōu)劣的關(guān)鍵因素。

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

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

一、伙伴算法簡介

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

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

內(nèi)存管理是應(yīng)用程序通過硬件和軟件協(xié)作訪問內(nèi)存的一種方法，當(dāng)進程請求內(nèi)存使用時，它給進程分配可用的內(nèi)存；當(dāng)進程釋放內(nèi)存時，回收相應(yīng)的內(nèi)存，同時負責(zé)跟蹤系統(tǒng)中內(nèi)存的使用狀態(tài)。

在Linux系統(tǒng)中，首先將內(nèi)存分為若干個節(jié)點，然后每個節(jié)點又可以分為1-3個區(qū)，每個區(qū)下又有若干個頁。頁是內(nèi)存管理的基本單元。

當(dāng)前存在的問題

當(dāng)系統(tǒng)工作時，CPU最先訪問的地址不是物理內(nèi)存中的實地址，而是虛擬地址空間的虛地址。當(dāng)請求分頁時，首先在虛擬地址空間中分配一個虛擬空間，然后根據(jù)需要為此區(qū)間分配相應(yīng)的物理頁面并建立映射。

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

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

若系統(tǒng)以較大的定長空間來分配內(nèi)存，在一定程度上可以節(jié)省時間，但帶來的是碎片過多問題，由于每次用較大的空間進行分配，系統(tǒng)中出現(xiàn)大量碎片，導(dǎo)致內(nèi)存浪費。嚴(yán)重者會導(dǎo)致內(nèi)存無法完成分配，雖然仍有許多碎片空間。

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

二、伙伴算法核心原理

2.1伙伴關(guān)系的奧秘

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

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

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

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

2.2分配過程的深度剖析

當(dāng)系統(tǒng)中的進程發(fā)出內(nèi)存分配請求時，伙伴算法便開始了它的高效運作。其分配過程可以分為以下幾個關(guān)鍵步驟：

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

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

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

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

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

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

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

#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;//該組類別塊空閑的個數(shù)
};

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

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

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

調(diào)用流程如下：

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;
 //設(shè)置32個頁的引用計數(shù)為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];
 //接收一個頁描述符的地址作為它的參數(shù)，它讀取頁描述符的flags字段的高位，并通過zone_table數(shù)組來確定相應(yīng)管理區(qū)描述符的地址，最終將頁框回收到對應(yīng)的管理區(qū)中
 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;

 //釋放內(nèi)存分配位圖本身
 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)伙伴算法系統(tǒng)分配空間

page = __rmqueue(zone, order);
 //從所請求的order開始，掃描每個可用塊鏈表進行循環(huán)搜索。
    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字段，該字段表示連續(xù)頁框?qū)儆谀囊粋€大小的鏈表
        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; 
 //該部分連續(xù)頁面插入到對應(yīng)的free_list中
                list_add(&page[size].lru, &area->free_list); 
                area->nr_free++;
 //設(shè)置該部分連續(xù)頁面的order
                set_page_order(&page[size], high);
                    page->private = order;
                    __SetPagePrivate(page);
                         __set_bit(PG_private, &(page)->flags)
            return page;

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

free_pages_bulk
 //linux內(nèi)核將空間分為三個區(qū)，分別是ZONE_DMA、ZONE_NORMAL、ZONR_HIGH，zone_mem_map字段就是指向該區(qū)域第一個頁描述符
    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;
 //該段空間的第一個頁的下標(biāo)
            page_idx = page - base; 
            zone->free_pages += order_size;
 //最多循環(huán)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)
                 * 同時，必須屬于動態(tài)內(nèi)存(PG_reserved被清0,PG_reserved為1表示留給內(nèi)核或者沒有使用)
                 * 最后，其private字段必須是order
                 */
                if (!page_is_buddy(buddy, order))
                    break;
                list_del(&buddy->lru);
                area = zone->free_area + order;
 //原先所在的區(qū)域空閑頁減少
                area->nr_free--;   
                rmv_page_order(buddy);
                    __ClearPagePrivate(page);
                    page->private = 0;
                page_idx &= buddy_idx;
                order++;

 /**
 * 伙伴不能與當(dāng)前塊合并。
 * 將塊插入適當(dāng)?shù)逆湵恚⒁詨K大小的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回收過程的全面解讀

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

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

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

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

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

三、伙伴算法的實現(xiàn)與數(shù)據(jù)結(jié)構(gòu)

3.1關(guān)鍵數(shù)據(jù)結(jié)構(gòu)解析

在伙伴算法的實現(xiàn)中，涉及到幾個關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)，它們相互協(xié)作，共同完成內(nèi)存的分配與回收任務(wù)。

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

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

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

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

3.2系統(tǒng)初始化流程

在 Linux 內(nèi)核啟動時，伙伴算法的初始化是一個至關(guān)重要的過程，它為后續(xù)的內(nèi)存管理工作奠定了堅實的基礎(chǔ)。初始化過程主要包括內(nèi)存塊的初始化和鏈表的構(gòu)建等步驟。

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

具體的調(diào)用流程如下：從 start_kernel 函數(shù)開始，經(jīng)過一系列的調(diào)用，最終到達 mem_init 函數(shù)。在 mem_init 函數(shù)中，會調(diào)用 __free_all_bootmem 函數(shù)，該函數(shù)進一步調(diào)用 free_all_bootmem 函數(shù)，然后通過 free_all_bootmem_core 函數(shù)，利用 free_page 函數(shù)將頁面分給伙伴管理器 。在這個過程中，系統(tǒng)會遍歷 bootmem_data_t 結(jié)構(gòu)體，獲取每次返回的頁數(shù)，并將這些空閑內(nèi)存塊按照伙伴算法的規(guī)則插入到相應(yīng)的 free_list 鏈表中。

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

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

3.3分配與回收的代碼實現(xiàn)

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

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

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

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

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

四、伙伴算法場景及優(yōu)缺點

4.1伙伴算法的用途

管理物理內(nèi)存，解決外碎片問題。

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

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

4.3伙伴算法管理結(jié)構(gòu)

伙伴算法把物理內(nèi)存分為11個組，第0、1、...10組分別包含2^0、2^1、...2^10個連續(xù)物理頁面的內(nèi)存。在zone結(jié)構(gòu)中，有一個free_area數(shù)組，數(shù)組的每一個成員代表一個組，相關(guān)定義如下：

#define MAX_ORDER 11

struct zone {

    ...

struct free_area free_area[MAX_ORDER];

    ...

}

struct free_area {

struct list_head free_list;

/*該組類別塊空閑的個數(shù)*/

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函數(shù)中，通過對每一個頁面進行釋放，從而完成對伙伴算法的初始化工作。

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

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

_free_one_page函數(shù)分析如下：

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數(shù)組下標(biāo)就可以索引到對應(yīng)的page結(jié)構(gòu)*/
    page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);
    __mod_zone_page_state(zone, NR_FREE_PAGES, order_size);

    /*這個循環(huán)主要查看當(dāng)前釋放塊伙伴是否空閑，如果空閑則合并它們*/

    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伙伴算法優(yōu)缺點

(1)顯著優(yōu)勢

伙伴算法在 Linux 內(nèi)存管理中展現(xiàn)出了諸多顯著優(yōu)勢，這些優(yōu)勢使其成為內(nèi)存管理的核心算法之一，為系統(tǒng)的高效穩(wěn)定運行提供了有力保障。

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

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

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

(2)固有缺陷

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

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

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

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

五、伙伴算法的應(yīng)用場景及優(yōu)化策略

5.1應(yīng)用場景

伙伴算法在 Linux 內(nèi)核中有著廣泛的應(yīng)用場景，它為系統(tǒng)的高效運行提供了有力支持。在進程內(nèi)存分配方面，伙伴算法發(fā)揮著關(guān)鍵作用。當(dāng)一個新的進程被創(chuàng)建時，它需要申請一定的內(nèi)存空間來存儲其代碼、數(shù)據(jù)和堆棧等信息?；锇樗惴軌蚋鶕?jù)進程的需求，快速地分配合適大小的內(nèi)存塊，確保進程能夠順利啟動和運行。在多進程并發(fā)運行的環(huán)境中，各個進程可能會隨時申請或釋放內(nèi)存，伙伴算法能夠高效地處理這些請求，保證內(nèi)存資源的合理分配和利用，避免出現(xiàn)內(nèi)存分配失敗或內(nèi)存碎片過多的情況，從而維持系統(tǒng)的穩(wěn)定運行。

在設(shè)備驅(qū)動程序中，伙伴算法也有著不可或缺的應(yīng)用。設(shè)備驅(qū)動程序需要與硬件設(shè)備進行交互，而這些交互往往需要大量的內(nèi)存來存儲設(shè)備數(shù)據(jù)、控制信息等。例如，在網(wǎng)絡(luò)設(shè)備驅(qū)動中，需要分配內(nèi)存來緩存網(wǎng)絡(luò)數(shù)據(jù)包；在磁盤設(shè)備驅(qū)動中，需要分配內(nèi)存來存儲磁盤讀寫的數(shù)據(jù)?；锇樗惴軌驗樵O(shè)備驅(qū)動程序提供高效的內(nèi)存分配服務(wù)，確保設(shè)備能夠正常工作。當(dāng)網(wǎng)絡(luò)設(shè)備接收到大量的數(shù)據(jù)包時，伙伴算法能夠迅速分配足夠的內(nèi)存來緩存這些數(shù)據(jù)包，保證網(wǎng)絡(luò)通信的順暢；當(dāng)磁盤設(shè)備進行讀寫操作時，伙伴算法能夠及時分配內(nèi)存來存儲數(shù)據(jù)，提高磁盤的讀寫效率。

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

5.2優(yōu)化策略

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

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

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

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

6.1版本變化概述

隨著 Linux 內(nèi)核的不斷發(fā)展和演進，伙伴算法也在持續(xù)改進和優(yōu)化，以適應(yīng)日益復(fù)雜的系統(tǒng)需求和硬件環(huán)境。在早期的 Linux 版本中，伙伴算法的實現(xiàn)相對簡單，主要側(cè)重于基本的內(nèi)存分配和回收功能。隨著系統(tǒng)對內(nèi)存管理性能要求的不斷提高，伙伴算法在后續(xù)版本中經(jīng)歷了一系列的改進和擴展。

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

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

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

6.2改進意義分析

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

基于遷移類型的內(nèi)存分配機制，有效地提高了內(nèi)存分配的靈活性和效率。在現(xiàn)代操作系統(tǒng)中，不同類型的內(nèi)存需求越來越多樣化，通過將內(nèi)存塊分為不同的遷移類型，系統(tǒng)可以根據(jù)具體的需求選擇最合適的內(nèi)存塊進行分配。對于一些不可移動的內(nèi)核數(shù)據(jù)結(jié)構(gòu)，分配不可移動類型的內(nèi)存塊，確保其在內(nèi)存中的穩(wěn)定性；對于一些可移動的用戶數(shù)據(jù)，分配可移動類型的內(nèi)存塊，便于在內(nèi)存管理過程中進行優(yōu)化和調(diào)整。

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

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