本文將簡要介紹一下Linux內核中的伙伴分配算法。

    算法作用

     它要解決的問題是頻繁地請求和釋放不同大小的一組連續頁框，必然導致在已分配頁框的塊內分散了許多小塊的空閑頁面，由此帶來的問題是，即使有足夠的空閑頁框可以滿足請求，但要分配一個大塊的連續頁框可能無法滿足請求。

     伙伴算法（Buddy system）把所有的空閑頁框分為11個塊鏈表，每塊鏈表中分布包含特定的連續頁框地址空間，比如第0個塊鏈表包含大小為2^0個連續的頁框，第1個塊鏈表中，每個鏈表元素包含2個頁框大小的連續地址空間，….，第10個塊鏈表中，每個鏈表元素代表4M的連續地址空間。每個鏈表中元素的個數在系統初始化時決定，在執行過程中，動態變化。

     伙伴算法每次只能分配2的冪次頁的空間，比如一次分配1頁，2頁，4頁，8頁，…，1024頁(2^10)等等，每頁大小一般為4K，因此，伙伴算法最多一次能夠分配4M的內存空間。

    核心概念和數據結構

      兩個內存塊，大小相同，地址連續，同屬于一個大塊區域。（第0塊和第1塊是伙伴，第2塊和第3塊是伙伴，但第1塊和第2塊不是伙伴）

      伙伴位圖：用一位描述伙伴塊的狀態位碼，稱之為伙伴位碼。比如，bit0為第0塊和第1塊的伙伴位碼，如果bit0為1，表示這兩塊至少有一塊已經分配出去，如果bit0為0，說明兩塊都空閑，還沒分配。

      Linux2.6為每個管理區使用不同的伙伴系統，內核空間分為三種區，DMA，NORMAL，HIGHMEM，對于每一種區，都有對于的伙伴算法，

      1. free_area數組：

   1:  struct zone{

   2:     ....

   3:     struct free_area    free_area[MAX_ORDER];  

   4:     ....

   5:  }

   struct free_area  free_area[MAX_ORDER]    #MAX_ORDER 默認值為11

      2.  zone_mem_map數組

   free_area數組中，第K個元素，它標識所有大小為2^k的空閑塊，所有空閑快由free_list指向的雙向循環鏈表組織起來。其中的nr_free，它指定了對應空間剩余塊的個數。

   整個分配圖示，大概如下：

    申請和回收過程

      比如，我要分配4(2^2)頁（16k）的內存空間，算法會先從free_area[2]中查看nr_free是否為空，如果有空閑塊，則從中分配，如果沒有空閑塊，就從它的上一級free_area[3]（每塊32K）中分配出16K，并將多余的內存（16K）加入到free_area[2]中去。如果free_area[3]也沒有空閑，則從更上一級申請空間，依次遞推，直到free_area[max_order]，如果頂級都沒有空間，那么就報告分配失敗。

      釋放是申請的逆過程，當釋放一個內存塊時，先在其對于的free_area鏈表中查找是否有伙伴存在，如果沒有伙伴塊，直接將釋放的塊插入鏈表頭。如果有或板塊的存在，則將其從鏈表摘下，合并成一個大塊，然后繼續查找合并后的塊在更大一級鏈表中是否有伙伴的存在，直至不能合并或者已經合并至最大塊2^10為止。

     內核試圖將大小為b的一對空閑塊（一個是現有空閑鏈表上的，一個是待回收的），合并為一個大小為2B的單獨塊，如果它成功合并所釋放的塊，它會試圖合并2b大小的塊，

     內核使用_rmqueue()函數來在管理區中找到一個空閑塊，成功返回第一個被分配頁框的頁描述符，失敗返回NULL。

       內核使用

    __free_pages_bulk()函數按照伙伴系統的策略釋放頁框。它使用3個基本輸入參數：
    page：被釋放塊中所包含的第一個頁框描述符的地址。
    zone：管理區描述符的地址。
    order：塊大小的對數。

伙伴算法的優缺點

    優點：

     較好的解決外部碎片問題

     當需要分配若干個內存頁面時，用于DMA的內存頁面必須連續，伙伴算法很好的滿足了這個要求

     只要請求的塊不超過512個頁面(2K)，內核就盡量分配連續的頁面。

     針對大內存分配設計。

     缺點：

      1. 合并的要求太過嚴格，只能是滿足伙伴關系的塊才能合并，比如第1塊和第2塊就不能合并。

      2. 碎片問題：一個連續的內存中僅僅一個頁面被占用，導致整塊內存區都不具備合并的條件

      3. 浪費問題：伙伴算法只能分配2的冪次方內存區，當需要8K（2頁）時，好說，當需要9K時，那就需要分配16K（4頁）的內存空間，但是實際只用到9K空間，多余的7K空間就被浪費掉。

      4. 算法的效率問題： 伙伴算法涉及了比較多的計算還有鏈表和位圖的操作，開銷還是比較大的，如果每次2^n大小的伙伴塊就會合并到2^(n+1)的鏈表隊列中，那么2^n大小鏈表中的塊就會因為合并操作而減少，但系統隨后立即有可能又有對該大小塊的需求，為此必須再從2^(n+1)大小的鏈表中拆分，這樣的合并又立即拆分的過程是無效率的。

    Linux針對大內存的物理地址分配，采用伙伴算法，如果是針對小于一個page的內存，頻繁的分配和釋放，有更加適宜的解決方案，如slab和kmem_cache等，這不在本文的討論范圍內。

      參考鏈接：伙伴算法剖析(原創)

                   伙伴系統算法

                   Buddy伙伴算法