内存管理有两篇文章讲的还是满清晰的：
操作系统学习笔记-储存管理
The Linux
Kernel-Chapter 3 Memory Management
下面这本书是有不少中文翻译的，可以自行查找
本文主要是讨论伙伴算法的，讲伙伴算法的文章虽然多，但是没几篇讲的很清楚的。我也是结合了几篇文章看了好久才弄明白，特地记下来。
使用伙伴算法能减少外部碎片，快速分配和回收资源。
伙伴算法的最典型应用就是linux中的页面管理了，然而只要是涉及到资源池的实现，都可以参考这个算法。
把空闲块组织成固定大小块数（2的幂数）组成的链表。
例如1个空闲页面属于链表order0，2个空闲页面属于链表order1，4个空闲页面属于链表order2
如果请求一个2个页面大小的块，就会去寻找链表order1，如果没找到会寻找order2，然后把order2分裂：一部分分配出去；另外一部分加入链表order1。
回收内存相当于分配的逆过程，尽可能的将相近的块归并成一个固定大小的大块
伙伴算法的核心就是那么多，但是实际实现上使用了伙伴位图来进行快速定位和合并，这才是伙伴算法的精髓。
举个实例会清楚的多。
例如现在我们有一块16大小的内存
内存的内容是这样的 1
2
3
4
5
6
7
8
9
10
11
| pages: 0 1 2 3 4 5 6 7 8 9 A B C D E F
content: 1 1 0 1 1 1 1 1 0 1 0 0 0 0 0 0
order0: 0 1 0 0 1 0 0 0
order1: 1 0 1 0
order2: 0 1
order3: 0
|
pages代表地址，content代表内容，orderX代表各个链表对应的伙伴位图
可以看到，初始链表为
1
2
3
4
5
6
7
| order0:2,8
order1:A[A,B]
order2:C[C,D,E,F]
order3:
|
在这个初始情况下分别做内存分配和回收
内存分配
要分配两次2大小的块
1 第一次很简单，把order1中的A[A,B]分配出去即可
1
2
3
4
5
6
7
| order0:2,8
order1:
order2:C[C,D,E,F]
order3:
|
2 第二次分配时order1不存在空闲，在高一级order2去找
3
拿到C，将其分割成两部分C[C,D],E[E,F]，把C[C,D]分配出去，把E[E,F]放入order1
最终
1
2
3
4
5
6
7
| order0:2,8
order1:E[E,F]
order2:
order3:
|
内存回收
回到初始情况下，我们要回收9这一个页面
1
首先在伙伴位图计算出order0中9的位置，注意这里算出来的位置是从0开始而不是1开始的
index >> (order + 1) = 9 >> 1 = 4
2 order0中bit 4位值为1
3 我们设置他的值为0，因为此时8,9都为0
4 然后将8从order0链表中删除
5 此时，我们获得了空闲块8[8,9]，计算得到他在order1中的位置为2
6
该值为1，但由于现在8[8,9]和A[A,B]都为空闲，所以将该值改为0，把A[A,B]从order1链表中删除
7 此时，我们获得了空闲块8[8,9,A,B],计算得到他在order2中的位置为1
8
该值为1，但由于现在8[8,9,A,B]和C[C,D,E,F]都为空闲，所以将该值改为0，把C[C,D,E,F]从order2链表中删除
9
此时我们获得了空闲块8[8,9,A,B,C,D,E,F],计算得到他在order3中的位置为0
10
该值为0，说明伙伴不是全部空闲的，不能再继续合并，我们把这一位设置为1，然后把空闲块插入order3链表
最终成为这样：
1
2
3
4
5
6
7
8
9
10
11
| pages: 0 1 2 3 4 5 6 7 8 9 A B C D E F
content: 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0
order0: 0 1 0 0 0 0 0 0
order1: 1 0 0 0
order2: 0 0
order3: 1
|
链表成为这样：
1
2
3
4
5
6
7
| order0:2
order1:
order2:
order3:8[8,9,A,B,C,D,E,F]
|
算法实现
这部分待续
linux的实际使用
可以通过sysrq查看伙伴算法的实际使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| root@ubuntu:~# echo m > /proc/sysrq-trigger
root@ubuntu:~# dmesg -c
[ 365.583431] SysRq : Show Memory
[ 365.583512] Mem-Info:
[ 365.583514] DMA per-cpu:
[ 365.583516] CPU 0: hi: 0, btch: 1 usd: 0
[ 365.583517] Normal per-cpu:
[ 365.583518] CPU 0: hi: 90, btch: 15 usd: 42
[ 365.583521] active_anon:1709 inactive_anon:69 isolated_anon:0
[ 365.583522] active_file:6613 inactive_file:15375 isolated_file:0
[ 365.583523] unevictable:0 dirty:8 writeback:0 unstable:0
[ 365.583524] free:45461 slab_reclaimable:1311 slab_unreclaimable:1615
[ 365.583524] mapped:1817 shmem:78 pagetables:158 bounce:0
[ 365.583529] DMA free:8180kB min:112kB low:140kB high:168kB active_anon:0kB
inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:0kB isolated(anon):0kB
isolated(file):0kB present:15804kB mlocked:0kB dirty:0kB writeback:0kB mapped:0kB
shmem:0kB slab_reclaimable:24kB slab_unreclaimable:12kB kernel_stack:0kB pagetables:0kB
unstable:0kB bounce:0kB writeback_tmp:0kB pages_scanned:0 all_unreclaimable? no
[ 365.583532] lowmem_reserve[]: 0 281 281 281
[ 365.583537] Normal free:173664kB min:2088kB low:2608kB high:3132kB active_anon:6836kB
inactive_anon:276kB active_file:26452kB inactive_file:61500kB unevictable:0kB isolated(anon):0kB
isolated(file):0kB present:288416kB mlocked:0kB dirty:32kB writeback:0kB mapped:7268kB
shmem:312kB slab_reclaimable:5220kB slab_unreclaimable:6448kB kernel_stack:480kB pagetables:632kB
unstable:0kB bounce:0kB writeback_tmp:0kB pages_scanned:0 all_unreclaimable? no
[ 365.583541] lowmem_reserve[]: 0 0 0 0
[ 365.583546] DMA: 5*4kB 8*8kB 6*16kB 8*32kB 7*64kB 7*128kB 5*256kB 2*512kB 0*1024kB 0*2048kB 1*4096kB = 8180kB
[ 365.583551] Normal: 48*4kB 100*8kB 56*16kB 24*32kB 16*64kB 6*128kB 9*256kB 22*512kB 12*1024kB 12*2048kB 29*4096kB = 173664kB
[ 365.583557] 22065 total pagecache pages
[ 365.583558] 0 pages in swap cache
[ 365.583559] Swap cache stats: add 0, delete 0, find 0/0
[ 365.583560] Free swap = 1479676kB
[ 365.583561] Total swap = 1479676kB
[ 365.584098] 76784 pages RAM
[ 365.584099] 0 pages HighMem
[ 365.584100] 3176 pages reserved
[ 365.584101] 13275 pages shared
[ 365.584101] 18919 pages non-shared
|
其中这两项就是伙伴算法的实际使用 1
2
| [ 365.583546] DMA: 5*4kB 8*8kB 6*16kB 8*32kB 7*64kB 7*128kB 5*256kB 2*512kB 0*1024kB 0*2048kB 1*4096kB = 8180kB
[ 365.583551] Normal: 48*4kB 100*8kB 56*16kB 24*32kB 16*64kB 6*128kB 9*256kB 22*512kB 12*1024kB 12*2048kB 29*4096kB = 173664kB
|
这里大块的内存不多可能会造成内存申请失败，甚至引发OOM（假如配置了OOM机制）
当然在具体场景可能还能看到DMA32和HighMem，都可以忽略，基本申请内存是以Normal为准的
具体为什么我也说不太清楚，对此有兴趣的可以查看这篇文章
《Linux内核设计与实现》读书笔记（十二）-
内存管理
对SysRq诊断工具感兴趣的可以看这里
利用
SysRq 键排除和诊断系统故障
内存问题排查手段及相关文件介绍