memory-management - 为什么不将日志结构分配器用于主内存

Question

我刚刚学习了日志结构文件系统。而且我很困惑，为什么不使用日志结构作为主内存分配器。它可以显着减少碎片。

标签： memory-managementfilesystemsdynamic-memory-allocationallocator

Answer 1

日志结构文件系统使用对循环日志的顺序写入来保存文件系统数据，并且通常以相同的方式处理更新。在某些时候，日志结构文件系统必须回收未使用的空间（日志中的过时条目）以使其可用于将来的写入。在一个简单的实现中，可以通过重写日志并在文件系统用完磁盘空间时跳过进程中未使用的条目来回收未使用的条目。

本机代码的内存分配器可以做类似的事情。一个简单的实现将需要一大块内存和一个需要为分配过程递增的下一个指针。释放需要将条目标记为已释放（可以是条目中的标志或专用空闲列表）或需要以其他方式限制释放（按先进先出顺序释放，仅整个分配空间可以解除分配）。事实上，这种分配器被称为“线性分配器”并且在今天使用。一个优点是分配性能，另一个优点是如果它以 FIFO 顺序发生或影响整个分配空间，则释放的简单性和效率。堆栈分配是一个突出的例子。JVM 通常使用线性分配器进行对象分配。

由于空间回收的困难，使用线性分配器作为通用分配器的问题更大。要回收空间，将条目标记为空闲是不够的，因为这可能导致高碎片并破坏线性分配的优势（只需为实际分配任务增加指针）。因此，与文件系统类似，分配空间必须压缩，使其仅包含已分配的条目，并且可用空间可用于线性分配。压缩需要移动分配的条目——这个过程会改变它们先前已知的地址并使其无效。在本机代码中，分配器不知道对已分配条目（存储为指针的地址）的引用位置。malloc.

为什么不可行？更新现有参考将需要以下步骤：

• 暂停所有线程以停止所有分配条目修改器（除非采用所谓的“写屏障”）
• 扫描寄存器、堆栈和堆以查找指向移动对象的指针
  • 指针的确切位置是未知的，与引用匹配的数据可能会被误认为是引用（例如，在像 Boehm 这样不执行复制的保守 GC 的情况下，这不是问题。误报只会延迟收集），因此内存可能会被破坏
  • 指针可能是未对齐的，因此扫描必须使用按字节推进的指针大小的窗口
  • 由于指针标记等策略以及 XOR 链表等数据结构，指针可能会被混淆
  • 代码可能依赖于先前的指针值（与托管代码相比，可以读取引用的值）
• 恢复所有先前挂起的线程

使用 RTTI，可以提供所需的元数据，但将指针传递给您无法控制的库（例如 glibc）仍然是一个问题。所以，在有限的范围内，这是可以实现的。通用分配器必须在所有本机代码场景中都可用 - 对于需要移动分配条目的线性分配器，有太多的约束使得这不可行。最重要的是，用于停止线程和建立写屏障的低级机制可能会干扰分配器用户（例如 JVM）使用的类似机制。

但是，在托管代码的情况下，这是常见的做法。例如，复制垃圾收集器维护两个分配空间 - from-space 和 to-space - 来处理压缩。在垃圾回收期间，仅将引用的分配条目复制到其他分配空间。一旦完成，分配可以再次以线性方式处理。

在特定场景中，使用来自日志结构文件系统的策略的分配器已经被使用。对于本机代码的通用内存分配，移动分配条目不可行的事实意味着线性分配器无法替代更传统的内存分配策略。

一种替代方案是使用池分配器，而不是采用线性分配路线来减少碎片，它为固定大小的分配条目提供分配空间。通过以这种方式限制分配空间，可以减少碎片。许多通用分配器使用池分配器进行小型分配。在某些情况下，这些应用程序空间存在于每个线程的基础上，以消除锁定需求并提高 CPU 缓存利用率。