夥伴算法
Linux核心記憶體管理的任務包括：
- 遵從CPU的MMU（Memory Management Unit）機制
- 合理、有效、快速地管理記憶體
- 實作記憶體保護機制
- 實作虛拟記憶體
- 共享
- 重定位
Linux核心通過夥伴算法來管理實體記憶體。夥伴系統（Buddy System）在理論上是非常簡單的記憶體配置設定算法。它的用途主要是盡可能減少外部碎片，同時允許快速配置設定與回收實體頁面。為了減少外部碎片，連續的空閑頁面，根據空閑塊（由連續的空閑頁面組成）大小，組織成不同的連結清單（或者orders）。這樣所有的2個頁面大小的空閑塊在一個連結清單中，4個頁面大小的空閑塊在另外一個連結清單中，以此類推。
注意，不同大小的塊在空間上，不會有重疊。當一個需求為4個連續頁面時，檢查是否有4個頁面的空閑塊而快速滿足請求。若該連結清單上（每個結點都是大小為4頁面的塊）有空閑的塊，則配置設定給使用者，否則向下一個級别（order）的連結清單中查找。若存在（8頁面的）空閑塊（現處于另外一個級别的連結清單上），則将該頁面塊分裂為兩個4頁面的塊，一塊配置設定給請求者，另外一塊加入到4頁面的塊連結清單中。這樣可以避免分裂大的空閑塊，而此時有可以滿足需求的小頁面塊，進而減少外面碎片。
夥伴算法舉例
假設我們的系統記憶體隻有16個頁面RAM。因為RAM隻有16個頁面，我們隻需用四個級别（orders）的夥伴位圖（因為最大連續記憶體大小為16個頁面），如下圖所示。
在order（0），第一個bit表示開始的2個頁面，第二個bit表示接下來的2個頁面，以此類推。因為頁面4已配置設定，而頁面5空閑，故第三個bit為1。
同樣在order（1）中，bit3是1的原因是一個夥伴完全空閑（頁面8和9），和它對應的夥伴（頁面10和11）卻并非如此，故以後回收頁面時，可以合并。
配置設定過程
當我們需要order（1）的空閑頁面塊時，則執行以下步驟：
1、初始空閑連結清單為：
order(0): 5, 10
order(1): 8 [8,9]
order(2): 12 [12,13,14,15]
order(3):
2、從上面空閑連結清單中，我們可以看出，order（1）連結清單上，有一個空閑的頁面塊，把它配置設定給使用者，并從該連結清單中删除。
3、當我們再需要一個order（1）的塊時，同樣我們從order（1）空閑連結清單上開始掃描。
4、若在order（1）上沒有空閑頁面塊，那麼我們就到更高的級别（order）上找，order（2）。
5、此時有一個空閑頁面塊，該塊是從頁面12開始。該頁面塊被分割成兩個稍微小一些order（1）的頁面塊，[12，13]和[14，15]。[14，15]頁面塊加到order（1）空閑連結清單中，同時[12，13]頁面塊傳回給使用者。
6、最終空閑連結清單為：
order(1): 14 [14,15]
order(2):
回收過程
當我們回收頁面11（order 0）時，則執行以下步驟：
1、找到在order（0）夥伴位圖中代表頁面11的位，計算使用下面公示：
index = page_idx >> (order + 1)
= 11 >> (0 + 1)
= 5
2、檢查上面一步計算位圖中相應bit的值。若該bit值為1，則和我們臨近的，有一個空閑夥伴。Bit5的值為1（注意是從bit0開始的，Bit5即為第6bit），因為它的夥伴頁面10是空閑的。
3、現在我們重新設定該bit的值為0，因為此時兩個夥伴（頁面10和頁面11）完全空閑。
4、我們将頁面10，從order（0）空閑連結清單中摘除。
5、此時，我們對2個空閑頁面（頁面10和11，order（1））進行進一步操作。
6、新的空閑頁面是從頁面10開始的，于是我們在order（1）的夥伴位圖中找到它的索引，看是否有空閑的夥伴，以進一步進行合并操作。使用第一步中的計算公司，我們得到bit 2（第3位）。
7、Bit 2（order（1）位圖）同樣也是1，因為它的夥伴頁面塊（頁面8和9）是空閑的。
8、重新設定bit2（order（1）位圖）的值，然後在order（1）連結清單中删除該空閑頁面塊。
9、現在我們合并成了4頁面大小（從頁面8開始）的空閑塊，進而進入另外的級别。在order（2）中找到夥伴位圖對應的bit值，是bit1，且值為1，需進一步合并（原因同上）。
10、從oder（2）連結清單中摘除空閑頁面塊（從頁面12開始），進而将該頁面塊和前面合并得到的頁面塊進一步合并。現在我們得到從頁面8開始，大小為8個頁面的空閑頁面塊。
11、我們進入另外一個級别，order（3）。它的位索引為0，它的值同樣為0。這意味着對應的夥伴不是全部空閑的，是以沒有再進一步合并的可能。我們僅設定該bit為1，然後将合并得到的空閑頁面塊放入order（3）空閑連結清單中。
12、最終我們得到大小為8個頁面的空閑塊：
系統運作執行個體
我們可以通過echo m > /proc/sysrq-trigger來檢視目前系統記憶體各個Order空閑情況。
root@chen-ThinkPad-X200:/home/ chen # echo m > /proc/sysrq-trigger
root@ chen -ThinkPad-X200:/home/ chen # dmesg -c
SysRq : Show Memory
Mem-Info:
Node 0 DMA per-cpu:
CPU 0: hi: 0, btch: 1 usd: 0
CPU 1: hi: 0, btch: 1 usd: 0
Node 0 DMA32 per-cpu:
CPU 0: hi: 186, btch: 31 usd: 161
CPU 1: hi: 186, btch: 31 usd: 126
Node 0 Normal per-cpu:
CPU 0: hi: 186, btch: 31 usd: 156
CPU 1: hi: 186, btch: 31 usd: 87
active_anon:99525 inactive_anon:20358 isolated_anon:0
active_file:17376 inactive_file:85309 isolated_file:0
unevictable:4 dirty:119 writeback:0 unstable:0
free:714169 slab_reclaimable:7311 slab_unreclaimable:26660
mapped:33029 shmem:20884 pagetables:6715 bounce:0
Node 0 DMA free:15744kB min:256kB low:320kB high:384kB active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:0kB isolated(anon):0kB isolated(file):0kB present:15352kB mlocked:0kB dirty:0kB writeback:0kB mapped:0kB shmem:0kB slab_reclaimable:0kB slab_unreclaimable:0kB kernel_stack:0kB pagetables:0kB unstable:0kB bounce:0kB writeback_tmp:0kB pages_scanned:0 all_unreclaimable? no
lowmem_reserve[]: 0 2960 3907 3907
Node 0 DMA32 free:2820564kB min:51008kB low:63760kB high:76512kB active_anon:77944kB inactive_anon:11228kB active_file:1792kB inactive_file:35936kB unevictable:0kB isolated(anon):0kB isolated(file):0kB present:3031688kB mlocked:0kB dirty:52kB writeback:0kB mapped:20340kB shmem:11376kB slab_reclaimable:1808kB slab_unreclaimable:960kB kernel_stack:40kB pagetables:1140kB unstable:0kB bounce:0kB writeback_tmp:0kB pages_scanned:0 all_unreclaimable? no
lowmem_reserve[]: 0 0 946 946
Node 0 Normal free:20368kB min:16312kB low:20388kB high:24468kB active_anon:320156kB inactive_anon:70204kB active_file:67712kB inactive_file:305300kB unevictable:16kB isolated(anon):0kB isolated(file):0kB present:969600kB mlocked:16kB dirty:424kB writeback:0kB mapped:111776kB shmem:72160kB slab_reclaimable:27436kB slab_unreclaimable:105680kB kernel_stack:2880kB pagetables:25720kB unstable:0kB bounce:0kB writeback_tmp:0kB pages_scanned:0 all_unreclaimable? no
lowmem_reserve[]: 0 0 0 0
Node 0 DMA: 2*4kB 1*8kB 1*16kB 1*32kB 1*64kB 0*128kB 1*256kB 0*512kB 1*1024kB 1*2048kB 3*4096kB = 15744kB
Node 0 DMA32: 81*4kB 28*8kB 63*16kB 32*32kB 31*64kB 26*128kB 11*256kB 6*512kB 1*1024kB 2*2048kB 684*4096kB = 2820564kB
Node 0 Normal: 176*4kB 80*8kB 29*16kB 10*32kB 3*64kB 5*128kB 22*256kB 9*512kB 3*1024kB 2*2048kB 0*4096kB = 20368kB
123579 total pagecache pages
0 pages in swap cache
Swap cache stats: add 0, delete 0, find 0/0
Free swap = 999416kB
Total swap = 999416kB
1032191 pages RAM
44206 pages reserved
183171 pages shared