Linux內存管理伙伴算法

在系統初始化進行到伙伴系統分配器能夠承擔內存管理的責任後，必須停用bootmem分配器，畢竟不能同時用兩個分配器管理內存。在UMA和NUMA系統上，停用分別由free_all_bootmem和free_all_bootmem_node完成（前面的博客已經詳細討論過）。伙伴系統基於一種相對簡單而令人吃驚的強大算法，它結合了優秀內存分配器的兩個關鍵特性：速度和效率。Linux內核中采用了一種同時適用於32位和64位系統的內存分頁模型，對於32位系統來說，兩級頁表足夠用了，而在x86_64系統中，用到了四級頁表，四級頁表分別為：

頁全局目錄(Page Global Directory)

頁上級目錄(Page Upper Directory)

頁中間目錄(Page Middle Directory)

頁表(Page Table)

頁全局目錄包含若干頁上級目錄的地址，頁上級目錄又依次包含若干頁中間目錄的地址，而頁中間目錄又包含若干頁表的地址，每一個頁表項指向一個頁框。Linux中采用4KB

大小的頁框作為標准的內存分配單元。

在實際應用中，經常需要分配一組連續的頁框，而頻繁地申請和釋放不同大小的連續頁框，必然導致在已分配頁框的內存塊中分散了許多小塊的空閒頁框。這樣，即使這些頁框

是空閒的，其他需要分配連續頁框的應用也很難得到滿足。為了避免出現這種情況，Linux內核中引入了伙伴系統算法(buddy system)。把所有的空閒頁框分組為11個塊鏈表，每個塊鏈表分別包含大小為1，2，4，8，16，32，64，128，256，512和1024個連續頁框的頁框塊。最大可以申請1024個連續頁框，對應4MB大小的連續內存。每個頁框塊的第一個頁框的物理地址是該塊大小的整數倍。假設要申請一個256個頁框的塊，先從256個頁框的鏈表中查找空閒塊，如果沒有，就去512個頁框的鏈表中找，找到了則將頁框塊分為2個256個頁框的塊，一個分配給應用，另外一個移到256個頁框的鏈表中。如果512個頁框的鏈表中仍沒有空閒塊，繼續向1024個頁框的鏈表查找，如果仍然沒有，則返回錯誤。

頁框塊在釋放時，會主動將兩個連續的頁框塊合並為一個較大的頁框塊。

為清楚了解其分配制度，先給個伙伴系統數據的存儲框圖如下：

也就是每個order對應一個free_area結構，free_area以不同的類型以鏈表的方式存儲這些內存塊。

主要的數據域結構分析：

1. struct zone  
2. {  
3.       ...  
4.       ...  
5.       struct free_area free_area[MAX_ORDER];  
6.       ...  
7. };  

1. struct free_area {  
2.     struct list_head    free_list[MIGRATE_TYPES];  
3.     unsigned long       nr_free;  
4. };  

nr_free指定了當前內存區中空閒頁塊的數目（對0階內存區逐頁計算，對1階內存區計算頁對的數目，對2階內存區計算4頁集合的數目，依此類推）。free_list是用於連接空閒頁的鏈表。order（階）是伙伴系統中一個非常重要的概念，它描述了內存分配的數量單位，內存塊的長度是2的order次方，其中order的范圍從0到MAX_ORDER，而MAX_ORDER的值通常設置為11，這意味著一次分配可以請求的頁數最大是2048（2的11次方）。但如果特定於體系結構的代碼設置了FORCE_MAX_ZONEORDER配置選項，該值也可以手工改變。MIGRATE_TYPES指定了遷移類型的種類數。

1. #define MIGRATE_UNMOVABLE     0   //不可移動頁：在內存中有固定位置，不能移動到其他地方   
2. #define MIGRATE_RECLAIMABLE   1   //可回收頁：不能直接移動，但可以刪除，其內容可以從某些源重新生成   
3. #define MIGRATE_MOVABLE       2   //可移動頁：可以隨意的移動   
4. #define MIGRATE_RESERVE       3   //如果向具有特定可移動性地列表請求分配內存失敗，這種緊急情況下可以從MIGRATE_RESERVE分配內存   
5. #define MIGRATE_ISOLATE       4  //是一個特殊的虛擬區域，用於跨域NUMA結點移動物理內存頁，在大型系統上，它有益於將物理內存頁移動到接近於是用該頁最頻繁的CPU   
6. #define MIGRATE_TYPES         5  //只是表示遷移類型的數目，不代表具體的區域  

在伙伴系統中，每種遷移類型都對應於一個空閒列表。

注：我只是一個內核的初學者，如果有哪些地方說的不對或是不准確，請指正；如果你有什麼問題希望能提出來，一起分析討論一下，以求共同進步。謝謝