Linux伙伴系統

伙伴系統的概述

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>

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

<mmzone.h>

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

free_area共有MAX_ORDER個元素，其中第order個元素記錄了2^order的空閒塊，這些空閒塊在free_list中以雙向鏈表的形式組織起來，對於同等大小的空閒塊，其類型不同，將組織在不同的free_list中，nr_free記錄了該free_area中總共的空閒內存塊的數量。MAX_ORDER的默認值為11，這意味著最大內存塊的大小為2^10=1024個頁框。對於同等大小的內存塊，每個內存塊的起始頁框用於鏈表的節點進行相連，這些節點對應的著struct page中的lru域

1. struct page {
3. ...
4. ...
5. struct list_head lru; /* Pageout list, eg. active_list
6. * protected by zone->lru_lock !
7. */
8. ...
9. }

連接示意圖如下：

在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>

1. #define MIGRATE_UNMOVABLE 0
2. #define MIGRATE_RECLAIMABLE 1
3. #define MIGRATE_MOVABLE 2
4. #define MIGRATE_PCPTYPES 3 /* the number of types on the pcp lists */
5. #define MIGRATE_RESERVE 3
6. #define MIGRATE_ISOLATE 4 /* can't allocate from here */
7. #define MIGRATE_TYPES 5

前三種類型已經介紹過

MIGRATE_PCPTYPES是per_cpu_pageset，即用來表示每CPU頁框高速緩存的數據結構中的鏈表的遷移類型數目

MIGRATE_RESERVE是在前三種的列表中都沒用可滿足分配的內存塊時，就可以從MIGRATE_RESERVE分配

MIGRATE_ISOLATE用於跨越NUMA節點移動物理內存頁，在大型系統上，它有益於將物理內存頁移動到接近於是用該頁最頻繁地CPU

MIGRATE_TYPES表示遷移類型的數目

當一個指定的遷移類型所對應的鏈表中沒有空閒塊時，將會按以下定義的順序到其他遷移類型的鏈表中尋找

1. static int fallbacks[MIGRATE_TYPES][MIGRATE_TYPES-1] = {
2. [MIGRATE_UNMOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE },
3. [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE },
4. [MIGRATE_MOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
5. [MIGRATE_RESERVE] = { MIGRATE_RESERVE, MIGRATE_RESERVE, MIGRATE_RESERVE }, /* Never used */
6. };