シリウスの砂

空闲空间管理

✏️ 🔧 📄 9 min read

这一部分, 我们聚焦于内存管理系统的一个基本方面: 空闲空间管理.

这里是对程序的虚拟内存进行分配, 例如 malloc 库管理进程中堆的页;
又或者操作系统用分段管理地址空间.

在这两种情况下, 管理的空闲空间由不同大小的单元构成, 管理起来比较复杂.
空闲空间会被分割成不同大小的小块, 可能会出现外部碎片, 导致后续请求失败.

底层机制

注意, 内存一旦分配给客户, 是不可以重定位到其他位置的, 因此无法用紧凑的方式减少碎片.

堆上管理空闲空间的数据结构通常被称为空闲列表, 包含了管理内存区域中所有空闲块的引用.

Address Space

形如以上的地址空间, 可以用如下的空闲列表记录状态:

Free List

分割与合并

在以上的状态, 任何大于 10 字节的申请都会失败.

如果我们申请少于一个字节的空间, 例如一字节, 分配程序会进行分割:
找到一块可以满足请求的空闲程序, 将其分割后, 第一块返还给用户, 第二块留在空闲列表.

Splitting

相反, 如果我们通过 free(10) 返还中间占用的空间.

Before Coalescing

分配程序会在释放内存的时候, 触发合并:
也即查看归还的内存块的临近空闲空间块, 如果归还的空间和原有空闲块相邻, 就将其合并为一个较大的空闲块.

Coalescing

追踪已分配空间大小

注意到, free() 没有接受块大小的参数, 这是因为大多数分配程序会在头块保存诸如分配空间大小的信息(以及幻数检查完整性等).
因此释放的时候, 分配程序可以自行读取分配空间大小并释放, 无须人工维护.

Header

假设头块如下:

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

那么, 则有: header_t *hptr = (void *)ptr - sizeof(header_t);
随后释放头块大小加上分配给用户的空间大小的内存.

所需空间大小

正如刚刚所述, 分配空间时要分配头块, 所以每次消耗的空闲空间实际要略多于我们申请的.
也因此, 申请 N 字节的空间时, 分配程序要寻找的是 N + sizeof(header_t) 大小的空闲块.

嵌入空闲列表

如何在空闲空间内部建立一个空闲列表呢?
要知道, 没有空闲列表, 我们就不能使用 malloc() 分配空间;
而不用 malloc(), 我们似乎无法分配内存?

但实际上我们是可以的, 利用系统调用, 例如 mmap().

假设我们要管理 4096 字节的内存块.

首先我们定义空闲列表节点:

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

随后, 我们初始化堆, 把空闲列表的第一个元素放在该空间:

node_t *head = mmap(NULL, 4096, PROT_READ|PROT_WRITE,
                    MAP_ANON|MAP_PREVATE, -1, 0);
head->size = 4096 - sizeof(node_t);
head->next = NULL;

是的, 我们只需要申请到空间之后, 直接把链表放在开头就好, 然后链表之外的空间(4096-8)就是我们的空闲块.
此时, 我们的内存布局如下:

A Heap With One Free Chunk

假设我们有一个 100 字节的请求, 我们分割 4088 字节大小的块, 分配 100+8 字节, 并且空闲列表的节点 size.

Heap After One Allocation

假如大量分配后,

After Three Allocation

而后, 我们 free(16500), 也就是第二块内存. 库会用头块计算要出释放的空间大小, 并且进行释放.
释放后, 原来的头块变成一个新的空闲列表节点, 记录 size, 插入到空闲列表(next 指向下一块空闲块的节点地址)

Free a Chunk

全部释放后…

All Free

而后, 我们还需要遍历, 合并.

让堆增长

一般传统分配程序会从很小的堆开始, 如果堆的空间耗尽, 再向操作系统申请更大的空间.
这一般是通过某些系统调用, 例如 UNIX 的 sbrk.

基本策略

一个理想的分配程序策略, 应该尽量保证快速和碎片最小化.
但是由于申请内存的随机性, 任何的策略都有表现不佳的时候, 因此我们下面分析不同策略的优缺点.

  • 最优匹配

    • 策略: 遍历整个空闲列表, 找到与请求大小一样或更大的空闲块, 然后返回其中最小的一块.
    • 利弊: 这可以选择与请求大小接近的块, 尽量避免空间浪费, 但是要遍历全部空闲块, 付出较高性能代价.

  • 最差匹配

    • 策略: 与最优匹配相反, 查实找到最大的空闲块, 分割并满足请求.
    • 利弊: 同样要遍历空闲列表, 付出较高性能代价, 并且表现一般很差, 会造成大量碎片.

  • 首次匹配:

    • 策略: 找到第一个足够大的块, 将请求的空间返回.
    • 利弊: 有速度优势, 但有时会让空闲列表开头有很多小块.
      因此管理空闲列表顺序很重要, 例如基于地址排序, 保持空袭那块按内存地址有序, 便于合并.

  • 下次匹配:

    • 策略: 不同于首次匹配每次从列表开头开始查找, 而是从上次查找结束的位置开始找.
    • 利弊: 将对空闲空间的查找操作扩散到整个列表中, 避免对列表开头频繁分割, 性能与首次匹配接近.

其他方式

  • 分离空闲列表: 如果某个应用程序经常申请一种或几种大小的内存空间, 那么用一个独立列表, 只管理这样的对象.
    其他大小的请求交给更通用的内存分配程序.
    更进一步地, 厚块分配程序, 预分配并预初始化了一些可能频繁请求的对象缓存,
    并且在快耗尽的时候额外申请内存创造缓存.
    避免了频繁初始化与销毁, 提升性能.

  • 伙伴系统: 把空闲空间看作 的空间, 当有请求时, 递归地将其一份为二, 直到可以刚好满足请求.
    这一策略会有内碎片, 但是在块被释放的时候, 可以很快的检查伙伴是否空闲, 并进行合并.
    (这是因为相邻的伙伴块, 地址只有一位不同, 可以轻松根据这一位确定自己在伙伴树的位置)

Buddy Allocation

  • 更多方法: 更先进的分配程序会采用更复杂的数据结构优化开销, 例如平衡二叉树, 伸展树, 偏序树等. 牺牲简单性换取性能.

关系图谱

反向链接