内存管理与伙伴算法

发表于 更新于 阅读次数： 本文字数： 4.4k 阅读时长 ≈ 4 分钟

内存管理有两篇文章讲的还是满清晰的：

操作系统学习笔记-储存管理

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
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
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代表各个链表对应的伙伴位图

可以看到，初始链表为

```c  
order0:2,8

order1:A[A,B]

order2:C[C,D,E,F]

order3:
```  

在这个初始情况下分别做内存分配和回收

## 内存分配

要分配两次2大小的块

1 第一次很简单，把order1中的A[A,B]分配出去即可

```c  
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

最终

```c  
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链表

最终成为这样：

```c  
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
```  

链表成为这样：

```c  
order0:2

order1:

order2:

order3:8[8,9,A,B,C,D,E,F]
```  

## 算法实现

这部分待续

## linux的实际使用

可以通过sysrq查看伙伴算法的实际使用

```c  
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
```  

其中这两项就是伙伴算法的实际使用
```c  
[  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 键排除和诊断系统故障

内存问题排查手段及相关文件介绍