os 3- 内存管理算法

ddatsh

dev #os 2020/04/04

假设这是一段连续的页框，阴影部分表示已经被使用的页框，现在需要申请一个连续的5个页框

这段内存上不能找到连续的5个空闲的页框，就会去另一段内存上去寻找5个连续的页框，久而久之形成了页框的浪费

所有空闲页框分组为11个块链表，每个块链表分别包含大小为1，2，4，8，16，32，64，128，256，512和1024个连续页框的页框块

最大可以申请1024个连续页框，对应4MB大小的连续内存

假设申请一个256个页框的块，先从256个页框的链表中查找空闲块，如果没有，就去512个页框的链表中找，找到了则将页框块分为2个256个页框的块，一个分配给应用，另外一个移到256个页框的链表中

如果512个页框的链表中仍没有空闲块，继续向1024个页框的链表查找，如果仍然没有，则返回错误

页框块在释放时，会主动将两个连续的页框块合并为一个较大的页框块

Buddy算法一直在对页框做拆开合并拆开合并的动作。正整数都可以由2^n的和组成，这是Buddy算法管理空闲页表的本质

Buddy算法对内存拆拆合合的过程中会造成碎片化的现象，以至于内存后来没有了大块的连续内存，全是小块内存

这对应用程序是不影响的(用页表可以把不连续的物理地址在虚拟地址上连续起来)，但是内核态就没有办法获取大块连续的内存（比如DMA, Camera, GPU都需要大块物理地址连续的内存）

嵌入式设备中一般用CMA来解决上述的问题

预留一段的内存给驱动使用，但当驱动不用的时候，CMA区域可以分配给用户进程用作匿名内存或者页缓存

当驱动需要使用时，就将进程占用的内存通过回收或者迁移的方式将之前占用的预留内存腾出来，供驱动使用

Linux中伙伴系统（buddy system）以页为单位管理和分配内存

但是现实的需求却以字节为单位，申请20Bytes，分配一页严重浪费内存

slab分配器应运而生，专为小内存分配而生。slab分配器分配内存以Byte为单位

slab分配器并没有脱离伙伴系统，基于伙伴系统分配的大内存进一步细分成小内存分配

从内存分为不同的ZONE，到CPU访问的Page通过页表来映射ZONE，再到通过Buddy算法和Slab算法对这些Page进行管理