Linux內核記憶體管理的一項重要工作就是如何在頻繁申請釋放記憶體的情況下，避免碎片的產生。Linux採用伙伴系統解決外部碎片的問題，採用slab解決內部碎片的問題，在這裡我們先討論外部碎片問題。避免外部碎片的方法有兩種：一種是之前介紹過的利用非連續記憶體的分配；另外一種則是用一種有效的方法來監視記憶體，保 ...
Linux內核記憶體管理的一項重要工作就是如何在頻繁申請釋放記憶體的情況下，避免碎片的產生。Linux採用伙伴系統解決外部碎片的問題，採用slab解決內部碎片的問題，在這裡我們先討論外部碎片問題。避免外部碎片的方法有兩種：一種是之前介紹過的利用非連續記憶體的分配；另外一種則是用一種有效的方法來監視記憶體，保證在內核只要申請一小塊記憶體的情況下，不會從大塊的連續空閑記憶體中截取一段過來，從而保證了大塊記憶體的連續性和完整性。顯然，前者不能成為解決問題的普遍方法，一來用來映射非連續記憶體線性地址空間有限，二來每次映射都要改寫內核的頁表，進而就要刷新TLB，這使得分配的速度大打折扣，這對於要頻繁申請記憶體的內核顯然是無法忍受的。因此Linux採用後者來解決外部碎片的問題，也就是著名的伙伴系統。
什麼是伙伴系統？
伙伴系統的宗旨就是用最小的記憶體塊來滿足內核的對於記憶體的請求。在最初，只有一個塊，也就是整個記憶體，假如為1M大小，而允許的最小塊為64K，那麼當我們申請一塊200K大小的記憶體時，就要先將1M的塊分裂成兩等分，各為512K，這兩分之間的關係就稱為伙伴，然後再將第一個512K的記憶體塊分裂成兩等分，各位256K，將第一個256K的記憶體塊分配給記憶體，這樣就是一個分配的過程。下麵我們結合示意圖來瞭解伙伴系統分配和回收記憶體塊的過程。
1 初始化時，系統擁有1M的連續記憶體，允許的最小的記憶體塊為64K，圖中白色的部分為空閑的記憶體塊，著色的代表分配出去了得記憶體塊。
2 程式A申請一塊大小為34K的記憶體，對應的order為0，即2^0=1個最小記憶體塊
2.1 系統中不存在order 0(64K)的記憶體塊，因此order 4(1M)的記憶體塊分裂成兩個order 3的記憶體塊(512K)
2.2 仍然沒有order 0的記憶體塊，因此order 3的記憶體塊分裂成兩個order 2的記憶體塊(256K)
2.3 仍然沒有order 0的記憶體塊，因此order 2的記憶體塊分裂成兩個order 1的記憶體塊(128K)
2.4 仍然沒有order 0的記憶體塊，因此order 1的記憶體塊分裂成兩個order 0的記憶體塊(64K)
2.5 找到了order 0的記憶體塊，將其中的一個分配給程式A，現在伙伴系統的記憶體為一個order 0的記憶體塊，一個order
1的記憶體塊，一個order 2的記憶體塊以及一個order 3的記憶體塊
3 程式B申請一塊大小為66K的記憶體，對應的order為1，即2^1=2個最小記憶體塊，由於系統中正好存在一個order 1的記憶體塊，所以直接用來分配
4 程式C申請一塊大小為35K的記憶體，對應的order為0，同樣由於系統中正好存在一個order 0的記憶體塊，直接用來分配
5 程式D申請一塊大小為67K的記憶體，對應的order為1
5.1 系統中不存在order 1的記憶體塊，於是將order 2的記憶體塊分裂成兩塊order 1的記憶體塊
5.2 找到order 1的記憶體塊，進行分配
6 程式B釋放了它申請的記憶體，即一個order 1的記憶體塊
7 程式D釋放了它申請的記憶體
7.1 一個order 1的記憶體塊回收到記憶體當中
7.2由於該記憶體塊的伙伴也是空閑的，因此兩個order 1的記憶體塊合併成一個order 2的記憶體塊
8 程式A釋放了它申請的記憶體，即一個order 0的記憶體塊
9 程式C釋放了它申請的記憶體
9.1 一個order 0的記憶體塊被釋放
9.2 兩個order 0伙伴塊都是空閑的，進行合併，生成一個order 1的記憶體塊m
9.3 兩個order 1伙伴塊都是空閑的，進行合併，生成一個order 2的記憶體塊
9.4 兩個order 2伙伴塊都是空閑的，進行合併，生成一個order 3的記憶體塊
9.5 兩個order 3伙伴塊都是空閑的，進行合併，生成一個order 4的記憶體塊
相關的數據結構
在前面的文章中已經簡單的介紹過struct zone這個結構，對於每個管理區都有自己的struct zone，而struct zone中的struct free_area則是用來描述該管理區伙伴系統的空閑記憶體塊的
<mmzone.h>
struct zone {
...
...
struct free_area free_area[MAX_ORDER];
...
...
}
<mmzone.h>
struct free_area {
struct list_head free_list[MIGRATE_TYPES];
unsigned long nr_free;
};
free_area共有MAX_ORDER個元素，其中第order個元素記錄了2order的空閑塊，這些空閑塊在free_list中以雙向鏈表的形式組織起來，對於同等大小的空閑塊，其類型不同，將組織在不同的free_list中，nr_free記錄了該free_area中總共的空閑記憶體塊的數量。MAX_ORDER的預設值為11，這意味著最大記憶體塊的大小為210=1024個頁框。對於同等大小的記憶體塊，每個記憶體塊的起始頁框用於鏈表的節點進行相連，這些節點對應的著struct page中的lru域
struct page {
...
...
struct list_head lru; /* Pageout list, eg. active_list
* protected by zone->lru_lock !
*/
...
}
連接示意圖如下：
在2.6.24之前的內核版本中，free_area結構中只有一個free_list數組，而從2.6.24開始，free_area結構中存有MIGRATE_TYPES個free_list,這些數組是根據頁框的移動性來劃分的，為什麼要進行這樣的劃分呢?實際上也是為了減少碎片而提出的，我們考慮下麵的情況：
圖中一共有32個頁，只分配出了4個頁框，但是能夠分配的最大連續記憶體也只有8個頁框(因為伙伴系統分配出去的記憶體必須是2的整數次冪個頁框)，內核解決這種問題的辦法就是將不同類型的頁進行分組。分配出去的頁面可分為三種類型：
- 不可移動頁(Non-movable pages)：這類頁在記憶體當中有固定的位置，不能移動。內核的核心分配的記憶體大多屬於這種類型
- 可回收頁(Reclaimable pages)：這類頁不能直接移動，但可以刪除，其內容頁可以從其他地方重新生成，例如，映射自文件的數據屬於這種類型，針對這種頁，內核有專門的頁面回收處理
- 可移動頁:這類頁可以隨意移動，用戶空間應用程式所用到的頁屬於該類別。它們通過頁表來映射，如果他們複製到新的位置，頁表項也會相應的更新，應用程式不會註意到任何改變。
假如上圖中大部分頁都是可移動頁，而分配出去的四個頁都是不可移動頁，由於不可移動頁插在了其他類型頁的中間，就導致了無法從原本空閑的連續記憶體區中分配較大的記憶體塊。考慮下圖的情況:
將可回收頁和不可移動頁分開，這樣雖然在不可移動頁的區域當中無法分配大塊的連續記憶體，但是可回收頁的區域卻沒有受其影響，可以分配大塊的連續記憶體。
內核對於遷移類型的定義如下:
<mmzone.h>
#define MIGRATE_UNMOVABLE 0
#define MIGRATE_RECLAIMABLE 1
#define MIGRATE_MOVABLE 2
#define MIGRATE_PCPTYPES 3 /* the number of types on the pcp lists */
#define MIGRATE_RESERVE 3
#define MIGRATE_ISOLATE 4 /* can't allocate from here */
#define MIGRATE_TYPES 5
前三種類型已經介紹過
MIGRATE_PCPTYPES是per_cpu_pageset，即用來表示每CPU頁框高速緩存的數據結構中的鏈表的遷移類型數目
MIGRATE_RESERVE是在前三種的列表中都沒用可滿足分配的記憶體塊時，就可以從MIGRATE_RESERVE分配
MIGRATE_ISOLATE用於跨越NUMA節點移動物理記憶體頁，在大型系統上，它有益於將物理記憶體頁移動到接近於是用該頁最頻繁地CPU
MIGRATE_TYPES表示遷移類型的數目
當一個指定的遷移類型所對應的鏈表中沒有空閑塊時，將會按以下定義的順序到其他遷移類型的鏈表中尋找
static int fallbacks[MIGRATE_TYPES][MIGRATE_TYPES-1] = {
[MIGRATE_UNMOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE },
[MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE },
[MIGRATE_MOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
[MIGRATE_RESERVE] = { MIGRATE_RESERVE, MIGRATE_RESERVE, MIGRATE_RESERVE }, /* Never used */
};
