Linux 内存管理
Linux 内存管理
Ref
概念
碎片
内部碎片（Internal Fragmentation）
对于已分配的块（即归属于某一进程），如果有效负载（程序请求的大小）比块大小小，就会产生内部碎片。
外部碎片（External Fragmentation）
频繁分配回收导致某些块（太小）不满足进程要求而无法分配出去的块（即不属于任何进程），这些无法被利用起来的块就是外部碎片。
管理和分配
基本策略
下面几种分配策略都是内存分配的肤浅策略，真实场景下的内存分配要复杂得多。
最优匹配（best fit）
遍历整个空闲列表，将空间大小比所请求大小大的块作为候选，取其中最小的作为结果返回。这样需要遍历整个空闲列表，但是可以避免内存空间浪费。
最差匹配（worst fit）
遍历整个空闲列表，将空间大小比所请求大小大的块作为候选，取其中最大的最作为结果返回。目的是为了保留较大的块，但是遍历花费的开销大，还容易导致过量的碎片。
最先匹配（first fit）
在遍历过程中找到符合条件的块就直接返回，性能较好。有时会造成头部很多小碎片，所以这种策略需要考虑如何管理空闲列表的顺序。
常用算法
伙伴算法和 Slab 算法都是通过 Segregated free list 来管理空闲列表，前者主要解决外部碎片问题，后者则是处理内部碎片。
分离空闲列表（Segregated free list）
分离空闲列表的基本想法很简单，应用程序通常会申请几种固定大小的空间，所以可以划分出几种固定大小的空闲块，相同大小的空闲块作为同一类进行管理。这样一来，每个空闲块的分配和回收都只在该类别进行操作，提高了管理效率。但是，该方法引入了新的复杂性，应该如何划分空闲块大小和确定每种大小的空闲块初始数量。
伙伴系统（Buddy system）
- 空闲列表：空闲列表由 m 个组组成，每个组的空闲块大小为 2(m-1) 个页，空闲块通过链表连接。
- 分配：假设申请内存大小为 x 页，有 x <= 2(y-1)，则在第 y 组找到空闲块分配，如果该组没有空闲块可分配，则一直向上，找到可分配的空闲块，利用二分法切分出对应块分配给用户，其余部分并入对应组。如果知道最后一个组都没有找到，分配失败。
- 合并：分配块被释放时，检查“伙伴”块是否空闲，如果是，就合并这两块，然后递归合并过程继续上溯，直到合并整个内存区域或者某一个块的‘伙伴“还没被释放，最后把块并入对应组。
Slab 算法
空闲列表： 分配： 合并：