目录

假设

底层机制

分割与合并

  追踪已分配空间的大小

嵌入空闲列表

让堆增长

基本策略

最优匹配

首次匹配

下次匹配

其他方式

  分离空闲列表

伙伴系统

小结

---

分页是将内存成大小相等的内存块，这样的机制下面，很容易去管理这些内存，但是又出现了一点问题，就是无法保证一直分配的时候是大小相等的，比如malloc函数，或者操作系统分段，这些都会将内存分为大小不一的，所以也就是出现了内存碎片，导致后续的请求可能失败。那么就是要学会空闲空间的管理才是最好的。

假设

这些库的空间被称为堆，这个堆上管理空闲空间的数据结构被称为空闲列表，用来管理内存区域中所有空闲块的引用。

在讨论问题之前，先做出一些假设：

1. 基本接口就是malloc和free那样，需要void * malloc(size),需要一个size，然后的到一个指针，free也就通过这个指针来释放空间。

2. 在这种分配的情况下，也可能会产生内部碎片，这个时候不做考虑，只需要关注的是外部碎片

3. 内存一旦被分配，那么就不能再重定向，就属于这个程序了，但是操作系统可以使用分段通过紧凑来减少碎片。

4. 用户级的空间快要使用完的时候，可以向内核进行申请，请求增加堆的空间，但是这里是在整个生命周期内大小固定。

底层机制

这里首先来介绍分割和合并的基础知识，然后可硬跟踪已经分配的空间，最后讨论如何维护一个列表，来观察这些空间。

分割与合并

假设这里有30字节的堆：

暂时无法在飞书文档外展示此内容

这个就是基本的，通过图的描述可以理解。

如果申请大于10字节的内存会失败，刚好等于10的话，其中每一个都可以满足，但是小于10，就需要使用分割了：

如果要申请一字节，那可以选择第二块空闲地方，将其中开始的第一个字节地址返回给用户，其他的给空闲列表中。

那么也还有一个机制，是叫合并：

  在释放空间的时候，会仔细检查空闲列表，方便在归还后，让空间中有一个较大的空闲块，

  追踪已分配空间的大小

  在释放空间的时候，只需要传入一个指针 ，但是怎么知道大小呢？所以基本有的分配程序都是有一个头，

1. 这个头中有这个指针的大小，其中可能还会包含一些其他的东西，

2. 比如额外的指针来加速空间的释放，

3. 还有幻数来检查完整性

  所以这里需要注意的是,释放空间的时候需要释放头和整个指针的空间，那么在申请的时候也就是要去找这两个和的空闲块去申请。

嵌入空闲列表

书中讲的很多，这里简单的总结一下：目前认识的空闲列表就是一个简单列表，用来描述堆中的空闲内存块。首先需要考虑的是这个空闲列表在哪里？那肯定是在空闲空间中的，所以，如果是4KB的堆的话，要用来分配空间，肯定无法分配到4KB，可以通过mmap()去看到后面剩多少，那么要分小一点的空间的话，就需要用分割，申请内存，也需要注意到头的请求，在归还的时候需要注意合并，不能随意释放，那么整个内存看起来就是一团糟。

让堆增长

在很多内存分配库中都有堆增长的机制，当堆的空间快分完的时候，可以使用某种系统调用，让堆增长，操作系统找到空闲的物理内存页，然后通过映射到请求的进程中的地址空间去，返回新的堆的末尾地址。

基本策略

通过上面的知识可以了解到管理空闲空间的底层机制，接下来就了解以下基本策略。

最优匹配

这个很简单，就是遍历一次，然后找到符合条件最小的那块空间返回用来分配。这个导致了大量的碎片还有就是开销

首次匹配

找到第一个足够大的空间返回，具有速度优势，但是可能会导致开头有很多的小块，那么可以通过基址排序，保持空闲块有序合并操作比较容易，较少内存碎片。

下次匹配

和首次匹配比较像，多维护一个指针，不需要每次都从头开始遍历。

其他方式

  分离空闲列表

拿出来一些空间作为列表，专门给一个应用程序来分配一种或几种内存，其他的用通用的内存分配程序，这些内存可以很快的被释放，使用起来速度等方面也是比较快的。

厚块分配程序（Slab Allocator）是一种用于管理内存分配的技术，常见于操作系统的内核中以及许多网络服务的实现中。它的基本思想是将内存分配成一系列大小固定的块，称为slab，每个slab中包含若干个相同大小的内存块。当需要分配内存时，分配器直接从slab中分配一个内存块，而不是像传统的内存分配器那样分配任意大小的内存块。

这种方式有几个优势：

1. 减少碎片化：传统的内存分配器在频繁地分配和释放内存时容易产生内存碎片。而slab allocator通过将内存分配成固定大小的块，可以减少内存碎片的产生，提高内存的利用率。

2. 提高性能：由于slab allocator预先分配了一系列大小固定的块，因此可以减少内存分配时的开销。相比传统的内存分配器，slab allocator通常有更好的性能表现。

3. 缓存效果：slab allocator通常会为不同大小的slab维护一个slab链表，这样可以更好地利用缓存。例如，可以为常用大小的数据结构（如文件描述符、网络连接等）维护一个slab链表，从而提高缓存的命中率。

4. 简化管理：由于slab allocator将内存分配成固定大小的块，因此可以更容易地管理内存。例如，可以通过简单的链表操作来管理slab，而不需要复杂的数据结构和算法。

尽管slab allocator有诸多优点，但也有一些限制和缺点。例如，它可能会浪费一些内存空间，因为每个slab都会预先分配一定数量的内存块，而这些内存块可能并不会全部被使用。此外，slab allocator也可能会导致内存分配不均匀，特别是在面对大小不一的内存请求时。

总的来说，slab allocator是一种高效的内存分配技术，特别适用于需要频繁分配和释放相同大小内存块的场景，如操作系统内核和网络服务。

数据结构的初始化和销毁的开销很大[B94]。通过将空闲对象保持在初始化状态，厚块分配程序避免了频繁的初始化和销毁，从而显著降低了开销。

伙伴系统

合并操作是比较重要的，所以为了方便，想出来了一个比较好的方法，当有内存分配请求的时候，将空间一分为2，知道刚好满足需求，然后在释放的时候，可以找到这个最后的，然后一点点回溯，将其合并，这样就比较好。

小结

讨论了最基本的内存分配程序形式。这样的分配程序存在于所有地方，与你编写的每个 C 程序链接，也和管理其自身数据结构的内存的底层操作系统链接。与许多系统一样，在构建这样一个系统时需要这许多折中。对分配程序提供的确切工作负载了解得越多，就越能调整它以更好地处理这种工作负载。在现代计算机系统中，构建一个适用于各种工作负载、快速、空间高效、可扩展的分配程序仍然是一个持续的挑战。