内存管理与伙伴算法

原创内容,转载请注明出处

Posted by Weakyon Blog on July 2, 2015

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

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

The Linux Kernel-Chapter 3 Memory Management

下面这本书是有不少中文翻译的,可以自行查找

本文主要是讨论伙伴算法的,讲伙伴算法的文章虽然多,但是没几篇讲的很清楚的。我也是结合了几篇文章看了好久才弄明白,特地记下来。


使用伙伴算法能减少外部碎片,快速分配和回收资源。

伙伴算法的最典型应用就是linux中的页面管理了,然而只要是涉及到资源池的实现,都可以参考这个算法。

把空闲块组织成固定大小块数(2的幂数)组成的链表。

例如1个空闲页面属于链表order0,2个空闲页面属于链表order1,4个空闲页面属于链表order2

如果请求一个2个页面大小的块,就会去寻找链表order1,如果没找到会寻找order2,然后把order2分裂:一部分分配出去;另外一部分加入链表order1。

回收内存相当于分配的逆过程,尽可能的将相近的块归并成一个固定大小的大块

伙伴算法的核心就是那么多,但是实际实现上使用了伙伴位图来进行快速定位和合并,这才是伙伴算法的精髓。

举个实例会清楚的多。

例如现在我们有一块16大小的内存

内存的内容是这样的

  
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代表各个链表对应的伙伴位图

可以看到,初始链表为

  
order0:2,8

order1:A[A,B]

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

order3:

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

内存分配

要分配两次2大小的块

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

  
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

最终

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

最终成为这样:

  
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

链表成为这样:

  
order0:2

order1:

order2:

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

算法实现

这部分待续

linux的实际使用

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

  
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

其中这两项就是伙伴算法的实际使用

  
[  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 键排除和诊断系统故障

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

02 Jul 2015