Chapter 17 Free Space Management

第 17 章 空闲空间管理

free-space management

地址分配必须是连续的

如果要管理的空闲空间有大小不同的单元构成...就会变得困难，操作系统用segmentation方式实现虚拟内存。会出现external fragmentation...

1. 假设

1.1. 假定基本的接口像 malloc() 和free()一样

malloc 和 free 的参数和返回值...

• malloc 指定 size 返回 pointer

• free 指定 pointer 无需 size 需要自行记录...

历史上称为空闲列表 free list...

1.2. 进一步假设主要关心外部碎片 external fragmentation

分配程序也有可能是内部碎片...但这会造成空间浪费

1.3. 我们还假设 内存一旦给用户 就不可以重定位

到其他位置

例如：一个程序调用 malloc 获得一个 pointer，这块区域就属于这个程序了，库不能够再移动...知道 free 归还...

因此不可能进行compaction空闲空间的操作...

但是 在 OS 的层面，实现分段可以用紧凑来减少碎片

1.4. 最后我们假设 分配程序管理的是连续的一块字节区域

分配程序可以要求这块区域增长...但是这里我们假设这块区域在整个生命周期内固定...

2. 底层机制

通用机制

2.1. 分割与合并

空闲列表包含一组元素，记录了堆中的那些空间还没有被分配...

假如受到了一个字节内存的申请，分配程序会执行所谓的 splitting

分割空闲内存

合并

coalescing 如何调用了 free 就会触发合并

主要是修改列表里一些能够连续起来的内存块...

列表里主要记录了空闲块的起始地址和长度...

通过合并机制，可以更好确保大块的空闲空间能提供给应用程序...

2.2. 追踪已分配空间的大小

关于 free 为什么不用指定 size 的问题...OS如何解决呢？

大多数分配程序都会在头块 header 中保存一点额外信息...在 malloc() 的时候会保存在一个 header 里

typedef struct {
int size;
int magic;
} header_t;

用户调用 free 时，库进行简单的指针运算得到 header 的位置..

void free(void *ptr) {
header_t *hptr = (header_t *) ptr - 1;
...

所以分配内存的时候，申请 n 大小，系统会查找 n + header 大小的内存，以便...

2.3. 嵌入空闲列表

空闲列表只停留在概念上，我们应该如何创建和维护这样一个列表？

1. 首先要初始化列表

使用的数据结构：

typedef struct __node_t {
int size;
struct __node_t *next;
} node_t;

初始化一个条目...空闲块的堆...相当于在一个连续空间里分配内存...

当你经历多次 malloc 和 free 之后...

As you can see from the figure, we now have a big mess! Why? Simple, we forgot to coalesce the list. Although all of the memory is free, it is chopped up into pieces, thus appearing as a fragmented memory despite not being one. The solution is simple: go through the list and merge neighboring chunks; when finished, the heap will be whole again...

2.4. 让堆增长

如果堆里面的内存耗尽...malloc 失败！返回 NULL！所以任何时候都要记得错误处理！malloc 是有可能失败的！所以这时候OS会释放更大的brk...堆内存

sbrk() 系统调用！这样就有了更大的堆，请求可以得到满足！

3. 基本策略

有了底层策略，可以发展出基本策略

3.1. 最优策略

best fit

1. 遍历空闲列表 找到和请求大小一样或更大的空闲块

2. 返回 candidates 里最小的一块

3. 就是所谓最优匹配

4. 简单的实现背后对应付出较高的性能代价

3.2. 最差匹配

worst fit

1. 相反，尝试找到最大的块

2. 分割并满足用户

3. 剩余的块假如空闲列表

4. 大多数研究它不仅导致过量碎片，性能也堪忧

3.3. 首次匹配

first fit

1. 第一次找到足够大的块就返回

2. 剩余空闲空间里给后续请求

3. 有速度优势...但是也会让开头部分（因为是首次匹配，尾部有可能永远不分配）有很多小块

因此需要进行管理

1. 基于地址排序 address-base ordering保持空闲块按地址有序，合并管理更方便

3.4. 下次匹配

next fit

1. 所维护一个指针

2. 纸箱上依次查找结束的位置

3. 将空闲空间的查找扩散！

4. 就是对比第一次找到的合适和第二次...

5. 1. 一来避免头部碎片

   2. 二来也不用遍历整个链表

4. 其他方式

除了基本策略之外，人们想出了一些技术和算法

4.1. 分离空闲列表

segregated list

1. 如果某个 app 经常申请一种或某几种大小的内存，就用一个独立的列表，之管理这样大小的对象

2. 其他大小留给其他更通用的内存分配

4.2. 伙伴系统

合并是一个重要的策略，所以在这一部分改变也很重要

binary buddy allocators

1. 空闲空间被视为 2^N 大小的空间 允许 2 的幂次方的空闲块

2. 于是会有内部碎片的麻烦

伙伴系统的 amazing point 在于，如果将 8kb 块释放，会检查 另一个 8kb 是否空闲，如果是，就合并，变成16kb 继续递归上溯下去！

良好 operation

因为很容易确定某个块的伙伴，这是固定的，可以写进 address 中！

4.3. 其他想法

上述所有想法都缺乏可扩展性 scaling，我们可以用复杂的 data structure 来换取性能

平衡二叉树 伸展树 偏序树

考虑到现代 OS 是多核的，通常运行 multi threads 的程序...所以会做出更多的工作

优化内村分配程序

5. 作业（模拟作业）

The program, malloc.py, lets you explore the behavior of a simple free-space allocator as described in the chapter. See the README for details of its basic operation.

利用 malloc.py 实现了对内存分配策略学习：

• BEST

• WORST

• FIRST

• 等