講了這么多了，很多人肯定會一頭霧水，前邊提到的都是些數據結構或者是些概念性的東西，真正對動態(tài)頁面的管理機制在哪里？換句話說，如何將每個節(jié)點，每個區(qū)中的頁框分配給進程？要理清這個思路，我們首先必須學習一種算法 —— 伙伴系統(tǒng)算法。

內核要分配一組連續(xù)的頁框，必須建立一種健壯、高效的分配策略。為此，必須解決著名的外部碎片（external fragmentation）問題。頻繁地請求和釋放不同大小的一組連續(xù)頁框，必然導致在已分配頁框的塊內分散了許多小塊的空閑頁框。由此帶來的問題是，即使有足夠的空閑頁框可以滿足請求，但要分配一個大塊的連續(xù)頁框就可能無法滿足。

Linux 采用伙伴系統(tǒng)（buddy system）算法來解決外碎片問題。把所有的空閑頁框分組為11個塊鏈表，每個塊鏈表分別包含大小為1, 2, 4, 8, 16, 32, 64, 128, 256，512和1024 個連續(xù)的頁框。對1024 個頁框的最大請求對應著4MB 大小的連續(xù)RAM塊。每個塊的第一個頁框的物理地址是該塊大小的整數倍。例如，大小為16 個頁框的塊，其起始地址是16 × 212（212 ＝ 4096，這是一個常規(guī)頁的大?。┑谋稊?。

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

假設要請求一個256 個頁框的塊（即1MB）。算法先在256 個頁框的鏈表中檢查是否有一個空閑塊。如果沒有這樣的塊，算法會查找下一個更大的頁塊，也就是，在512 個頁框的鏈表中找一個空閑塊。如果存在這樣的塊，內核就把256 的頁框分成兩等份，一半用作滿足請求，另一半插入到256 個頁框的鏈表中。如果在512 個頁框的塊鏈表中也沒找到空閑塊，就繼續(xù)找更大的塊 —— 1024個頁框的塊。如果這樣的塊存在，內核把1024個頁框塊的256 個頁框用作請求，然后從剩余的768 個頁框中拿512個插入到512個頁框的鏈表中，再把最后的256個插入到256個頁框的鏈表中。如果1024個頁框的鏈表還是空的，算法就放棄并發(fā)出錯信號。

以上過程的逆過程就是頁框塊的釋放過程，也是該算法名字的由來。內核試圖把大小為b的一對空閑伙伴塊合并為一個大小為2b的單獨塊。滿足以下條件的兩個塊稱為伙伴： ? 兩個塊具有相同的大小，記作b。 ? 它們的物理地址是連續(xù)的。 ? 第一塊的第一個頁框的物理地址是2×b×212的倍數。

該算法是迭代的，如果它成功合并所釋放的塊，它會試圖合并2b 的塊，以再次試圖形成更大的塊。

看暈了吧？如果實在理解不了就自己拿筆畫一畫，這個算法的原理還是比較簡單的，下面我們來看看Linux具體是怎么實現的：

1 數據結構

Linux 2.6 為每個管理區(qū)使用不同的伙伴系統(tǒng)。因此，在80x86 結構中，有三種伙伴系統(tǒng)：第一種處理適合ISA DMA 的頁框，第二種處理“常規(guī)”頁框，第三種處理高端內存頁框。每個伙伴系統(tǒng)使用的主要數據結構如下： （1）前面介紹過的mem_map數組。實際上，每個管理區(qū)都關系到mem_map元素的子集。子集中的第一個元素和元素的個數分別由管理區(qū)描述符的zone_mem_map和size字段指定。 （2）包含有11個元素、元素類型為free_area的一個數組，每個元素對應一種塊大小。該數組存放在管理區(qū)描述符zone_t的free_area字段中。

如圖，我們考慮管理區(qū)描述符中free_area數組的第k個元素，它標識所有大小為2k的空閑塊。這個元素的free_list字段是雙向循環(huán)鏈表的頭，這個雙向循環(huán)鏈表集中了大小為2k頁的空閑塊對應的頁描述符。更精確地說，該鏈表包含每個空閑頁框塊（大小為2k）的起始頁框的頁描述符；指向鏈表中相鄰元素的指針存放在頁描述符page的lru字段中。

除了鏈表頭外，free_area數組的第k個元素同樣包含字段nr_free，它指定了大小為2k頁的空閑塊的個數。當然，如果沒有大小為2k 的空閑頁框塊，則nr_free等于0且free_list為空（free_list的兩個指針next和prev都指向它自己的free_list字段）。

最后，一個2k的空閑頁塊的第一個頁的描述符的private字段存放了塊的order，也就是數字k。正是由于這個字段，當頁塊被釋放時，內核可以確定這個塊的伙伴是否也空閑。如果是的話，它可以把兩個塊結合成大小為2k＋1頁的單一塊。

【文章福利】小編推薦自己的Linux內核技術交流群:【891587639】整理了一些個人覺得比較好的學習書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦！?。。ê曨l教程、電子書、實戰(zhàn)項目及代碼)? ??

2 塊分配

內核使用__rmqueue()函數來在管理區(qū)中找到一個空閑塊。該函數需要兩個參數：管理區(qū)描述符的地址zone和order，order表示請求的空閑頁塊大小的對數值（0 表示一個單頁塊，1 表示一個兩頁塊，2表示四個頁塊）。如果頁框被成功分配，__rmqueue()函數就返回第一個被分配頁框的頁描述符。否則，函數返回NULL。

在__rmqueue()函數中，從所請求order的鏈表開始，它掃描每個可用塊鏈表進行循環(huán)搜索，如果需要搜索更大的order，就繼續(xù)搜索：

如果直到循環(huán)結束還沒有找到合適的空閑塊，那么__rmqueue()就返回NULL。否則，找到了一個合適的空閑塊，在這種情況下，從鏈表中刪除它的第一個頁框描述符，并減少管理區(qū)描述符中的free_pages的值：

如果從curr_order鏈表中找到的塊大于請求的order，就執(zhí)行一個while循環(huán)。這幾行代碼蘊含的原理如下：當為了滿足2h 個頁框的請求而有必要使用2k個頁框的塊時（h < k），程序就分配前面的2h 個頁框，而把后面2k - 2h 個頁框循環(huán)再分配給free_area鏈表中下標在h到k之間的元素：

因為__rmqueue()函數已經找到了合適的空閑塊，所以它返回所分配的第一個頁框對應的頁描述符的地址page。

3 塊釋放

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

__free_pages_bulk()首先聲明和初始化一些局部變量： struct page * base = zone->zone_mem_map; unsigned long buddy_idx, page_idx = page - base; struct page * buddy, * coalesced; int order_size = 1 << order;

page_idx局部變量包含塊中第一個頁框的下標，這是相對于管理區(qū)中的第一個頁框而言的。order_size 局部變量用于增加管理區(qū)中空閑頁框的計數器： zone->free_pages += order_size;

現在函數開始執(zhí)行循環(huán)，最多循環(huán) (10-order) 次，每次都盡量把一個塊和它的伙伴進行合并。函數以最小的塊開始，然后向上移動到頂部：

這個循環(huán)我看了半天沒有看懂，后來舉個例子，再畫個圖才漸漸明白。比如，我們這里order是4，那么order_size的值為24，也就是16，表明要釋放16個連續(xù)的page。page_idx為這個連續(xù)16個page的老大的mem_map數組的下標。進入循環(huán)后，函數首先尋找該塊的伙伴，即mem_map數組中page_idx-16或page_idx+16的下標buddy_idx，進一步說明一下，就是為了在下標為16的free_area中找到一個空閑的塊，并且這個塊與page所帶的那個擁有16個page的塊相鄰。

尤其要注意：buddy_idx = page_idx ^ (1 << order)這行代碼。這行代碼很巧妙，短小精干。因為order一來就等于4，所以循環(huán)從4開始的，即第一個循環(huán)為buddy_idx = page_idx ^ (1<<4)，即buddy_idx = page_idx ^ 10000。如果page_idx第5位為1，比如是20號頁框（10100），那么在異或以后，buddy_idx為4號頁框（00100）。如果page_idx第5位為0，比如是第40號頁框（101000），那么在異或以后，buddy_idx為56號頁框（111000）。

為什么要做這么一個運算呢？想想我們的目的是什么。__free_pages_bulk是將以其參數page為首的2^order個頁面找到一個伙伴，并與其合并。在mem_map數組中，這個伙伴的老大要么是在這個page的前2^order，要么就是后2^order。如果單單是加或者減，那么就會忽略前面的或者后面的伙伴。大家不妨對照上圖好好的琢磨一下。至于為啥不既加又減呢，我估計Linux的開發(fā)者們沒這么做是因為性能的問題吧，各個資料上也說了這里主要是盡量合并而已，我們就不去管他了。

找到伙伴以后，把該伙伴的老大page的地址賦給buddy： buddy = base + buddy_idx;

現在函數調用page_is_buddy()來檢查buddy是否是真正的值得信賴的伙伴，也就是大小為order_size的空閑頁框塊的第一個頁。

正如所見，要想成為伙伴，必須滿足以下四個條件：

（1）buddy的第一個頁必須為空閑（_count字段等于－1）；

（2）它必須屬于動態(tài)內存（PG_reserved 位清零）；

（3）它的private 字段必須有意義（PG_private 位置位）；

（4）它的private字段必須存放將要被釋放的塊的order。

如果所有這些條件都符合，就說明有新的伙伴存在啦，那么伙伴塊就要跟我page結合，先必須得脫離原來的free_list，執(zhí)行page_idx &= buddy_idx合并（注意，這行代碼與前邊的buddy_idx = page_idx ^ (1 << order)是緊密結合的），并再執(zhí)行一次循環(huán)以尋找兩倍大小的伙伴塊。

如果page_is_buddy()中至少有一個條件沒有被滿足，則該函數跳出循環(huán)，因為獲得的空閑塊不能再和其他空閑塊合并。函數將它插入適當的鏈表并以塊大小的order 更新第一個頁框的private 字段。 coalesced = base + page_idx; coalesced->private = order; SetPagePrivate(coalesced); list_add(&coalesced->lru, &zone->free_area[order].free_list); zone->free_area[order].nr_free++;