1．原理

Linux的伙伴算法把所有的空閑頁面分為10個塊組，每組中塊的大小是2的冪次方個頁面，例如，第0組中塊的大小都為2 ⁰ （1個頁面），第1組中塊的大小為都為2 ¹ （2個頁面），第9組中塊的大小都為2 ⁹ （512個頁面）。也就是說，每一組中塊的大小是相同的，且這同樣大小的塊形成一個鏈表。

我們通過一個簡單的例子來說明該算法的工作原理。

假設要求分配的塊其大小為128個頁面（由多個頁面組成的塊我們就叫做 頁面塊 ）。該算法先在塊大小為128個頁面的鏈表中查找，看是否有這樣一個空閑塊。如果有，就直接分配；如果沒有，該算法會查找下一個更大的塊，具體地說，就是在塊大小為256個頁面的鏈表中查找一個空閑塊。如果存在這樣的空閑塊，內核就把這256個頁面分為兩等份，一份分配出去，另一份插入到塊大小為128個頁面的鏈表中。如果在塊大小為256個頁面的鏈表中也沒有找到空閑頁塊，就繼續找更大的塊，即512個頁面的塊。如果存在這樣的塊，內核就從512個頁面的塊中分出128個頁面滿足請求，然后從384個頁面中取出256個頁面插入到塊大小為256個頁面的鏈表中。然后把剩余的128個頁面插入到塊大小為128個頁面的鏈表中。如果512個頁面的鏈表中還沒有空閑塊，該算法就放棄分配，并發出出錯信號。

以上過程的逆過程就是塊的釋放過程，這也是該算法名字的來由。滿足以下條件的兩個塊稱為伙伴：

·兩個塊的大小相同

·兩個塊的物理地址連續

伙伴算法把滿足以上條件的兩個塊合并為一個塊，該算法是迭代算法，如果合并后的塊還可以跟相鄰的塊進行合并，那么該算法就繼續合并。

2．數據結構

在6.2.5節中所介紹的管理區數據結構struct zone_struct中，涉及到空閑區數據結構：

free_area_t free_area[MAX_ORDER];

我們再次對free_area_t給予較詳細的描述。

#difineMAX_ORDER10

typestruct free_area_struct {

structlist_headfree_list

unsignedint*map

} free_area_t

其中list_head域是一個通用的雙向鏈表結構，鏈表中元素的類型將為mem_map_t(即struct page結構)。Map域指向一個位圖，其大小取決于現有的頁面數。free_area第k項位圖的每一位，描述的就是大小為2 ^k 個頁面的兩個伙伴塊的狀態。如果位圖的某位為0，表示一對兄弟塊中或者兩個都空閑，或者兩個都被分配，如果為1，肯定有一塊已被分配。當兄弟塊都空閑時，內核把它們當作一個大小為2 ^k+1 的單獨快來處理。如圖6.9給出該數據結構的示意圖：

圖6.9伙伴系統使用的數據結構

圖6.9中，free_aea數組的元素0包含了一個空閑頁（頁面編號為0）；而元素2則包含了兩個以4個頁面為大小的空閑頁面塊，第一個頁面塊的起始編號為4，而第二個頁面塊的起始編號為56。

我們曾提到，當需要分配若干個內存頁面時，用于DMA的內存頁面必須是連續的。其實為了便于管理，從伙伴算法可以看出，只要請求分配的塊大小不超過512個頁面（2KB），內核就盡量分配連續的頁面。

內核源碼學習：伙伴算法