1．原理

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

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

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

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

·兩個塊的大小相同

·兩個塊的物理地址連續(xù)

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

2．?dāng)?shù)據(jù)結(jié)構(gòu)

在6.2.5節(jié)中所介紹的管理區(qū)數(shù)據(jù)結(jié)構(gòu)struct zone_struct中，涉及到空閑區(qū)數(shù)據(jù)結(jié)構(gòu)：

free_area_t free_area[MAX_ORDER];

我們再次對free_area_t給予較詳細(xì)的描述。

#difineMAX_ORDER10

typestruct free_area_struct {

structlist_headfree_list

unsignedint*map

} free_area_t

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

圖6.9伙伴系統(tǒng)使用的數(shù)據(jù)結(jié)構(gòu)

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

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

內(nèi)核源碼學(xué)習(xí)：伙伴算法