1 页框管理

内核把物理页（4kb）作为内存管理的基本单位。每个页放置在页框中，内核记录页框的状态信息保存在page页描述符中，page放置在mem_map数组中。每个page长度为32字节，故mem_map占RAM不到1%（32/4k = 1/128）.

由于有些页位于内存中特定的物理地址上，不能进行一些特定的任务（DMA只能对前16MB寻址，32位计算机只能访问部分内存等）。内核将特定性质的页划分成区（zone）。

• ZONE_DMA :低于16mb的内存页框 ，DMA使用的页
• ZONE_NORMAL:低于896mb的内存页框 ，正常寻址的页
• ZONE_HIGHMEM:高于896mb的内存页框 ，高端内存，动态映射的页

Linux把系统的页划分成为区（zone），形成不同的内存池。当内核调用一个内存分配函数时，必须指明请求页框所在管理区。

进行内存分配请求时有两种方法：首先当有足够的空闲内存时，请求会被立刻满足；否则，必须回收一些内存并将发出请求的内核控制路径阻塞，直到有内存被释放（原子内存请求则直接失败）。
为了减少失败的情况，内核位原子内存请求保留了一个页框池，仅仅在内存不足时才使用。

1.1 分区内框分配器

分区页框分配器处理对连续页框组的内存分配请求，主要组成如下图所示：

管理区分配器接受动态内存分配与释放的请求，它首先从每CPU页框高速缓存 （很小） 中请求页框，若无法满足才从伙伴系统中请求分配。

1.2 伙伴算法（解决外碎片问题）

在实际应用中，经常需要分配一组连续的页框，而频繁地申请和释放不同大小的连续页框，必然导致在已分配页框的内存块中分散了许多小块的空闲页框。这样，即使有足够的页框是空闲的，其他需要分配连续页框的应用也很难得到满足。（外碎片问题）

为了避免出现这种情况，Linux内核中引入了伙伴系统算法(buddy system)。把所有的空闲页框分组为11个块链表 存于数组free_area，每个块链表分别包含大小为1，2，4，8，16，32，64，128，256，512和1024个连续页框的页框块。最大可以申请1024个连续页框，对应4MB大小的连续内存。**每个页框块的第一个页框的物理地址是该块大小的整数倍。**如大小为16框的块，起始地址是16 x 2¹²（16 x 4KB = 16 x 4 x 2¹⁰ 字节）

假设要申请一个256个页框的块，先从256个页框的链表中查找空闲块，如果没有，就去512个页框的链表中找，找到了则将页框块分为2个256个页框的块，一个分配给应用，另外一个移到256个页框的链表中。如果512个页框的链表中仍没有空闲块，继续向1024个页框的链表查找，如果仍然没有，则返回错误。

上面的逆过程就是页框块的释放过程，**页框块在释放时，会主动将两个连续的页框块合并为一个较大的页框块。**这样被合并的块被称为伙伴块，伙伴块满足以下条件：

1. 两个块大小相同；
2. 两个块地址连续；
3. 两个块必须是同一个大块中分离出来的；
   
   free_area[k]的元素的free_list字段是双向循环链表的头，标识了所有页数量为2^k的空闲块，这个双向循环链表集中了大小为2^k页的空闲块的起始页框的页描述符。
   一个大小为2^k页的空闲块的描述符的private字段存放了块的order为k。靠这个字段内核可以确定其伙伴是否空闲。

2.1.1 分配原理：

1. 假如系统需要4(2²)个页面大小的内存块，该算法就到free_area[2]中查找。
2. 如果链表中有空闲块，就直接从中摘下并分配出去。
3. 如果没有，算法将顺着数组向上查找free_area[3],如果free_area[3]中有空闲块，则将其从链表中摘下，分成等大小的两部分，前四个页面作为一个块插入free_area[2]，后4个页面分配出去，
4. free_area[3]中也没有，就再向上查找，如果free_area[4]中有，就将这16(2⁴)个页面等分成两份，前一半挂如free_area[3]的链表头部，后一半的8个页等分成两等分，前一半挂free_area[2]的链表中，后一半分配出去。
5. 假如free_area[4]也没有，则重复上面的过程，知道到达free_area数组的最后，如果还没有则放弃分配。

2.1.2 释放原理：

1. 内存的释放是分配的逆过程，也可以看作是伙伴的合并过程。
2. 当释放一个块时，先在其对应的链表中考查是否有伙伴存在，如果没有伙伴块，就直接把要释放的块挂入链表头；如果有，则从链表中摘下伙伴，合并成一个大块，
3. 然后继续考察合并后的块在更大一级链表中是否有伙伴存在，直到不能合并或者已经合并到了最大的块(2¹⁰个页面)。

1.3 每CPU页框高速缓存

在每个内存管理区都设置有每CPU页框高速缓存，其中包含一些预先分配的页框，其目的是为了解决内核经常请求和释放单个页框，满足本地CPU发出的单一内存请求。
细节略

1.4 管理区分配器

管理区分配器是内核页框分配器的前端，分配满足内存请求的足够多的空闲页框的内存区。
细节略

2内存区管理

伙伴算法采用页框作为基本内存区，提供了以page为单位的内存分配接口，这适用于大块内存。
然而为了存放很少的字节而给它分配一个整页框，这是一种浪费。
引入一种新的数据结构来描述在同一页框中如何分配小内存区，成为内碎片问题，内碎片的产生主要是由于请求内存的大小与分配给他的大小不匹配而造成的。
一种早期的方法是以2的幂建立空闲内存区链表（stl空间配置器）。
然而在伙伴算法之上用这种内存区分配算法并没有显著效率，更好的是slab算法与建立slab层，避免频繁分配和释放页。

2.1 slab算法

slab分配器是基于对象object进行管理的，相同类型的对象归为一类(如进程描述符就是一类)，

每当要申请这样一个对象，slab分配器就从一个slab列表中分配一个这样大小的单元出去，
而当要释放时，将其重新保存在该列表中，而不是直接返回给伙伴系统，从而避免这些内碎片。
slab分配器并不丢弃已分配的对象，而是释放并把它们保存在内存中。当以后又要请求新的对象时，就可以从内存直接获取而不用重复初始化。

2.1.1 工作机制

slab分配器的底层依托于buddy system，上层却对用户提供了更加灵活的内存分配服务。
工作机制主要包括两点：

1. 从buddy system分配pages，放入slab分配器内存池，也可以称为cache。
2. 用户调用slab分配器提供的内存分配接口如kmalloc，从slab分配器内存池中分配内存，内存的size没有按page size对齐的要求。

2.1.2 什么是object

object是slab内存分配器对外提供的申请内存的基本单位。slab内存分配器从buddy system申请了buddy之后，会将其拆分成一个个object，并缓存在kmem cache实例的cpu_cache中，用户申请内存时，其实获取的就是一个个object。

一旦object缓存耗尽，就会重新从buddy system申请slab，并将其拆分成object，放入内存池。

2.1.3 高速缓存

内核把不同的对象划分程所谓高速缓存（kmem_cache）组，然后这些高速缓存又被划分成slab，slab由一个或多个物理上的连续页组成（一般都是一页，也可以是更多），每个slab都包含一些对象成员。每个高速缓存都是同类型对象的储备。

2.1.4 什么是内碎片

因为所有的内存分配必须起始于可被 4、8 或 16 整除（视处理器体系结构而定）的地址或者因为MMU的分页机制的限制，决定内存分配算法仅能把预定大小的内存块分配给客户。假设当某个客户请求一个 43 字节的内存块时，因为没有适合大小的内存，所以它可能会获得 44字节、48字节等稍大一点的字节，因此由所需大小四舍五入而产生的多余空间就叫内部碎片。

2.1.5 分配过程

Linux 的slab 可有三种状态：

1. 满的：slab 中的所有对象被标记为使用。存于kmem_cache的 slabs_full链表
2. 空的：slab 中的所有对象被标记为空闲。存于kmem_cache的 slabs_partial链表
3. 部分：slab 中的对象有的被标记为使用，有的被标记为空闲。存于kmem_cache的 slabs_empty链表