编写内存分配器

这是“垃圾回收算法”类的第六个讲座，专门讨论自动内存管理。

在讨论收集垃圾的算法之前，我们需要了解如何将这些对象（最终成为垃圾）分配到堆上。在今天的讲座中，我们将讨论内存分配机制。

如果您喜欢这项工作并觉得有用，请考虑捐赠以支持无广告的高质量教育。

注意：另请参阅有关编写池分配器和编写标记清除垃圾收集器的相关讲座。

这是一个实验会话，我们将在其中实现一个内存分配器，类似于malloc函数中使用的分配器。另外，我们讨论了分配器背后的理论，讨论了顺序分配器（又称“凹凸分配器”）和自由列表分配器。

在进行实验之前，您可以在“内存分配器”上进行相应的视频讲座，网址为：

从前面的讲座中我们知道，垃圾收集程序是由三个主要模块（称为Mutator，Allocator和Collector）操纵的。

Mutator是我们的用户程序，我们在其中创建用于自己目的的对象。所有其他模块都应遵循对象图上Mutator的视图。例如，在任何情况下，收集器都不能回收活动对象。

但是Mutator不会自行分配对象。相反，它将这个通用任务委托给了分配器模块-这正是我们今天讨论的主题。

通常，在高级编程语言中，我们处理具有结构，字段，方法等的对象：

但是，从较低级别的内存分配器角度来看，一个对象仅表示为一个内存块。众所周知，此块具有一定大小，其内容（不透明）被视为原始字节序列。在运行时，可以将该内存块强制转换为所需的类型，并且其逻辑布局可能会根据此强制转换而有所不同。

回想一下有关对象标头的讲座，内存分配总是伴随着内存对齐和对象标头。标头存储与每个对象有关的元信息，以及分配器和收集器用途的服务器。

我们的内存块将对象标头和实际的有效负载指针结合在一起，该指针指向用户数据的第一个字。该指针在分配请求时返回给用户：

如您所见，标头跟踪对象的大小以及当前是否分配了该块（已使用标志）。分配时将其设置为true，免费操作将其重置为false，因此可以在以后的请求中重复使用。此外，下一个字段指向所有可用块的链接列表中的下一个块。

数据字段指向返回用户值的第一个字。

对象A和C正在使用中，而块B当前未使用。

由于这是一个链表，因此我们将跟踪堆的开始和结束（顶部）：

并不是的！我们在此特定实现中使用C ++只是因为它可以方便地处理原始内存和指针。但是，在课堂上，我们研究抽象的GC算法，这意味着您可以用任何语言实现它们。例如，您可以使用ArrayBuffer在JavaScript中分配虚拟堆，或者在Python，Rust等中类似地分配字节数组。

如前所述，分配内存时，我们对对象的逻辑布局不做任何承诺，而是使用块的大小。

模仿malloc函数，我们具有以下接口（除了我们使用键入的word_t *而不是void *作为返回类型）：

为什么它“至少”是大小字节？由于填充或对齐方式，我们接下来将讨论。

为了更快地访问，应对齐存储块，并且通常按机器字的大小对齐。 让我们定义对齐函数，该函数看起来有些神秘，但可以很好地完成工作： 这意味着，如果用户请求分配6个字节，我们实际上分配了8个字节。 在32位体系结构上分配4个字节可能导致4个字节，而在x64计算机上分配8个字节。 因此，这是我们要分配请求的第一步： 好的，到目前为止很好。 现在，我们需要回顾虚拟内存和内存映射的主题，并从操作系统的角度了解分配的实际含义。 从关于进程的虚拟内存的第4讲中，我们记得OS中的“分配内存”意味着该进程的“映射更多内存”。 让我们再次调用内存布局，并查看堆区域所在的位置。

如我们所见，堆朝着更高的地址向上增长。堆栈和堆之间的区域是未映射的区域。映射由程序中断（brk）指针的位置控制。

有几个用于内存映射的系统调用：brk，sbrk和mmap。生产分配器通常使用这些分配器的组合，但是在这里为简单起见，我们将仅使用sbrk调用。

sbrk函数具有当前堆的顶部，在传递的字节数上增加了（中断）程序中断的值。

通过在（1）中调用sbrk（0），我们获得了指向当前堆中断的指针-这是新分配的块的开始位置。

接下来在（2）中，我们再次调用sbrk，但是这次已经传递了应该增加中断位置的字节数。如果此调用的结果为（void *）-1，我们将发出有关OOM（内存不足）的信号，并返回nullptr。否则，我们返回获得的已分配块的（1）地址。

要重申对allocSize函数的注释：除了实际请求的大小外，我们还应该添加存储对象头的Block结构的大小。但是，由于用户数据的第一个字已被自动保留在块的数据字段中，因此我们将其减少。

仅当链接的阻止列表中没有可用的阻止时，我们才会调用requestFromOS。否则，我们将重用免费版块。

注意：在Mac OS上，不建议使用sbrk，目前已通过mmap在后台使用了预先分配的内存空间来模拟sbrk。

作为以下任务之一，建议您实施自定义版本的sbrk，并建议您在mmap调用的顶部执行。

让我们添加一个辅助函数，以从用户指针获取标头：

在（1）中，分配大小与单词的大小对齐，即x64上的8。在（2）中，它已经对齐，所以我们也得到8。

好，看起来不错但是，这种天真的分配器中存在一个“轻微”（读取：大）问题-它只是不断地碰撞中断指针，向操作系统请求更多和更多的内存。在某些时候，我们会耗尽内存，无法满足分配请求。我们这里需要的是能够重用以前释放的块的功能。

注意：上面的分配器称为顺序分配器（也称为“凹凸”分配器）。是的，这很简单，只是不断地碰撞分配指针，直到到达“堆的尽头”为止，这时将调用GC，该GC回收分配区域，在其周围重新放置对象。下面我们实现了一个自由列表分配器，该分配器可以立即重用这些块。

我们将首先研究对象的释放，然后通过添加重用算法来改进分配器。

free函数接收一个实际的用户指针，从中获取相应的Block，并更新used标志。

简单明了。好的，现在我们终于实现重用功能，这样我们就不会很快耗尽所有可用的操作系统内存。

我们的免费功能实际上并没有将内存返回（取消映射）回操作系统，它只是将used标志设置为false。这意味着我们可以（阅读：应该！）在以后的分配中重用空闲块。

实际的重用功能由（1）中的findBlock函数管理。让我们从“最适合算法”开始看一下它的实现。

findBlock过程应尝试查找适当大小的块。这可以通过几种方式来完成。我们考虑的第一个是最适合的搜索。

首次拟合算法遍历从堆的开头（我们在第一次分配时初始化的heapStart）开始的所有块。如果适合大小，它将返回找到的第一个块，否则返回nullptr。

返回第一个找到的块，即使它的大小比要求的大得多。我们将在下一个和最合适的分配中解决此问题。

确保所有断言仍然通过。现在，让我们看一下如何改善图块的搜索。现在，我们考虑下一个拟合算法，这是您的第一个任务。

以下是您需要完成以完成和改进此分配器的分配。

下一次拟合是第一次拟合的一种变体，但是它从先前的成功位置继续进行下一个搜索。这样可以在堆开始时跳过较小尺寸的块，因此您不必遍历它们就可以不断地频繁请求较大的块。当它到达列表的末尾时，它会从头开始，因此有时也称为循环优先拟合。

同样，它与基本的首次拟合的区别是：假设您在堆的开头有100个大小为8的块，然后是大小为16的块。每个alloc（16）请求将导致遍历所有这100个块首先是堆的开始，而在下一个堆中，它将从上一个16大小块的成功位置开始。

在随后的较大块请求时，我们立即找到了它，跳过了开头的所有较小块。

让我们定义搜索模式以及重置堆的辅助方法：

好的，下一个拟合可能会更好，但是即使还有其他更合适的块，它仍然会返回一个过大的块。让我们看一下最合适的算法，它可以解决这个问题。

最适合搜索的主要思想是尝试找到最适合的块。

例如，对于具有[4、32、8]个大小的块，以及对alloc（8）的请求，第一次和下一次拟合搜索将返回大小为32的第二个块，这不必要地浪费了空间。显然，返回大小为8的第三块将是此处的最佳选择。

注意：下面我们将实现块拆分，而从上方开始的大小为32的块将导致将其拆分为两个块，第一个仅占用8个请求的字节。

此处跳过了第一个空闲块，该块太大了，因此搜索将在第二个块中进行。

好，看起来更好！但是，即使使用最合适的方法，我们也可能最终返回比请求的块大的块。现在，我们应该看看另一个优化，称为块拆分。

当前，如果我们找到了合适大小的块，就可以使用它。如果找到的块比请求的块大得多，这可能是低效的。

现在，我们将执行一个拆分较大的空闲块的过程，仅从其中获取较小的块，这是请求的。另一部分保持空闲状态，并可用于进一步的分配请求。

我们之前的先拟合算法仅占用了整个大块，而列表中的可用块就不多了。尽管块已拆分，但仍有一个空闲块可供重用。

只要在搜索算法中找到一个块，就会调用listAllocate函数。它需要在较小的块上分割较大的块：

通过拆分，我们现在可以很好地重用可用空间。但是，如果我们在大小为8的堆上有两个相邻的收费块，并且用户请求大小为16的块，我们将无法满足分配请求。让我们看一下对此的另一种优化-块合并。

在释放对象时，我们可以执行与拆分操作相反的操作，并将两个（或更多）相邻块合并为一个更大的块。

注意，我们仅与下一个块合并，因为我们只能访问下一个指针。尝试向对象标头添加prev指针，并考虑与前一个块合并。

块合并使我们能够满足较大块的分配需求，但是，我们仍然必须使用O（n）方法遍历列表才能找到空闲块。让我们看看如何使用明确的自由列表算法解决此问题。

目前，我们进行线性搜索，一个一个地分析每个块。一种更有效的算法是使用仅链接空闲块的显式空闲列表。

当堆变得越来越大，并且需要遍历基本算法中的许多对象时，这可能是一项重大的性能改进。

显式的自由列表可以直接在对象头中实现。为此，下一个和上一个指针将指向空闲块。从下一个开始，分割和合并的程序应进行相应的更新，并且上一个不再指向相邻的块。

分配过程将仅遍历free_list：如果未找到任何内容，则来自OS的请求：

实验并实现双链列表方法，使用next和prev在标题中用于自由列表。

最后，让我们考虑另一种速度优化，它可以更快地搜索预定义大小的块。该方法被称为隔离列表。

以上考虑的搜索算法（首次拟合，次拟合和最佳拟合）对不同大小的块进行线性搜索。这减慢了对适当大小的块的搜索。分离拟合的思想是按大小对块进行分组。

也就是说，我们有许多块列表，而不是一个块列表，但是每个列表仅包含一定大小的块。

在此示例中，第一组仅包含大小为8的块，第二组为大小为16，第三组为32，依此类推。然后，如果我们收到分配16个字节的请求，则直接跳转到所需的存储桶（组），并从那里分配。

堆隔离有几种实现。可以预分配一个大型竞技场，然后将其拆分为多个存储桶，这些存储桶具有连续的存储桶阵列，可以快速跳转到所需的组和一个组中的一个块。

另一种方法是只包含一系列列表。下面的示例初始化这些隔离的列表。分配了适当大小的第一个块后，它将替换存储桶中的nullptr值。相同大小的下一个分配将进一步链接它。

也就是说，我们有许多“ heapStarts”和“ tops”，而不是一个heapStart和top。

而且，在存储桶中进行实际搜索可以重用上述任何算法。在下面的示例中，我们重用firstFit搜索。

好的，我们已经优化了搜索速度。现在，让我们看看如何优化存储空间。

当前，对象标头非常繁重：它包含大小，已使用和下一个字段。可以更有效地对某些信息进行编码。

例如，除了显式的下一个指针，我们还可以通过简单的块大小计算来访问下一个块。

另外，由于我们的块是按字长对齐的，因此可以出于我们的目的重用size字段的LSB（最低有效位）。例如：1000-大小8，并且不使用。然后使用1001（尺寸8）。

基本上，这是以存储为代价的。如果您的存储空间较小，则可以考虑进行这种编码/解码。反之亦然，当您拥有大量存储并且速度很重要时，在结构中使用显式字段可能比对对象标头数据进行恒定编码和解码要快。

如上所述，在Mac OS上，sbrk目前已被弃用，并通过mmap进行仿真。

不建议使用特定功能和特定OS。然而，就其本身而言，sbrk不仅仅是一种“功能”，而是一种机制，一种抽象。如前所述，它也直接对应于凹凸分配器。

当请求更大的内存块时，生产malloc实现也使用mmap而不是brk。通常，mmap可用于将外部文件映射到内存，也可用于创建匿名映射（不受任何文件支持）。后者恰好用于内存分配。

至此，我们结束了有关内存分配器的讨论，在接下来的讲座中，将已经开始使用垃圾回收算法。正如我们将看到的，不同的收集器使用不同的分配器，而设计内存管理器需要在收集器和分配器之间选择正确的对应关系。

尝试自己先解决所有任务。如果您遇到困难，可以在此处使用解决方案解决完整的源代码。

顺序（Bump）分配器是最快的，并且类似于堆栈分配：只是不断地增加分配指针。不幸的是，并非每种编程语言都允许使用Bump-allocator。特别是，公开指针语义的C / C ++无法在GC周期上重定位对象，因此必须使用较慢的Free-list分配器

凹凸分配器在带有Mark-Compact，Copy和Generational收集器的系统中使用。自由列表分配器较慢，并且遍历块的链接列表，直到找到所需大小的块。这种遍历是通常认为堆分配比堆栈分配慢的主要原因（对于Bump-allocator而言并非如此）

自由列表分配器（例如malloc）在带有Mark-Sweep，Reference计数收集器的系统中以及在具有手动内存管理的系统中使用

如果您有任何疑问或建议，我将一如既往地在评论中进行讨论。在班上见！

如果您喜欢这项工作并觉得有用，请考虑捐赠以支持无广告的高质量教育。

下次我评论时，请在此浏览器中保存我的姓名，电子邮件和网站。

感谢您的工作，很好的解释。我想知道对象标头是否总是与数据块一起放置吗？

我有几个问题：1.其余的讲座什么时候开始？任何估计的时间？ 2.您用什么制作幻灯片？他们看起来很漂亮！

最适合搜索的测试不正确。它会验证算法的功能，但不能验证其正确性。为此，您需要至少有2个内存块，而第一个（可能还有其他）内存块不是“最适合”的。一个简单的例子是：

谢谢你的材料，太好了。不过，我有一个问题：如何利用共享内存？我记得，您不能在其中使用指针-是否有其他适用的算法？最后，我想将共享内存用作小对象（如map）的STL自定义内存分配器。

非常感谢：我怀疑抵消会发挥作用，但希望得到专家的保证。我想使用一些分配算法来减少碎片-将释放的对象返回到池中，因为那样的话，我可以开发小型内存数据库，该数据库将保存带有需要（例如）开始并进行健康检查。

谢谢！买了关于Udemy的课程–我所有的梦境都变成了现实🙂

块。当分配器超出范围时，不会释放它们。我认为这是在课程中需要澄清和解决的蓄意的内存泄漏？对于不参加课程的读者来说，也许值得一提……

我假设您可能无法通过`std :: vector blocks {0};`解决它。 你会用什么？ 简单的类似于C的某些“结构块{}”的链表？ 您好Dimitry，感谢您的文章！ 在搜索wchar_t *的简单分配器时来到这里。 我想这是“ C风格”的方法 ......