1．原理

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

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

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

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

·兩個(gè)塊的大小相同

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

伙伴算法把滿足以上條件的兩個(gè)塊合并為一個(gè)塊，該算法是迭代算法，如果合并后的塊還可以跟相鄰的塊進(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域是一個(gè)通用的雙向鏈表結(jié)構(gòu)，鏈表中元素的類型將為mem_map_t(即struct page結(jié)構(gòu))。Map域指向一個(gè)位圖，其大小取決于現(xiàn)有的頁面數(shù)。free_area第k項(xiàng)位圖的每一位，描述的就是大小為2 ^k 個(gè)頁面的兩個(gè)伙伴塊的狀態(tài)。如果位圖的某位為0，表示一對兄弟塊中或者兩個(gè)都空閑，或者兩個(gè)都被分配，如果為1，肯定有一塊已被分配。當(dāng)兄弟塊都空閑時(shí)，內(nèi)核把它們當(dāng)作一個(gè)大小為2 ^k+1 的單獨(dú)快來處理。如圖6.9給出該數(shù)據(jù)結(jié)構(gòu)的示意圖：

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

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

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

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