动态无锁内存分配器

Question

编写满足无锁进度保证的算法或数据结构的困难之一是动态内存分配：以可移植的方式调用类似malloc或new不保证无锁的东西。然而，存在许多malloc或的无锁实现，new也有多种无锁内存分配器可用于实现无锁算法/数据结构。

但是，我仍然不明白这实际上如何完全满足无锁进度保证，除非您将数据结构或算法明确限制为某些预先分配的静态内存池。但是，如果您需要动态内存分配，我不明白从长远来看，任何所谓的无锁内存分配器如何才能真正实现无锁。问题是，无论您的无锁malloc或new可能多么出色，最终您可能会耗尽内存，此时您必须退回到向操作系统请求更多内存。这意味着最终你必须打电话brk()或mmap()或者一些这样的低级等价物来实际访问更多内存。并且根本无法保证任何这些低级调用都是以无锁方式实现的。

根本没有办法解决这个问题（除非您使用的是像 MS-DOS 这样不提供内存保护的古老操作系统，或者您编写自己的完全无锁的操作系统——这两种情况都不实用或不太可能。）那么，动态内存分配器如何才能真正做到无锁呢？

Answer 1

正如您所发现的，基本的操作系统分配器很可能不是无锁的，因为它必须处理多个进程和各种有趣的东西，这使得不引入某种锁真的很难。

然而，在某些情况下，“无锁内存分配”并不意味着“从不锁定”，而是“统计上很少锁定以至于它并不重要”。除了最严格的实时系统之外，这对任何事物都适用。如果你的锁没有高争用，那么加锁或不加锁其实并不重要——无锁的目的并不是锁本身的开销，而是它很容易成为瓶颈系统中的每个线程或进程都必须通过这个地方来做任何有用的事情，并且这样做时，它必须在队列中等待[它也可能不是真正的队列，它可能是“谁先醒来”或其他决定谁在当前调用者之后出现的机制]。

有几个不同的选项可以解决这个问题：

• 如果您有一个有限大小的内存池，您可以在软件启动时立即向操作系统请求所有内存。在内存从操作系统中分块后，它可以用作无锁池。明显的缺点是它对可以分配的内存量有限制。然后，您必须停止分配（使应用程序完全失败，或者使该特定操作失败）。

  当然，在像 Linux 或 Windows 这样的系统中，仍然不能保证内存分配，在无锁场景中，意味着“即时访问分配的内存”，因为系统可以并且将会在没有实际物理内存支持的情况下分配内存并且只有在实际使用内存时，才会将物理内存页分配给它。这可能既涉及锁，也可能涉及磁盘 I/O 以将其他页面调出到交换区。

• 对于如此严格的实时系统，单个系统调用可能争用锁的时间“太多”，解决方案当然是使用专用操作系统，在操作系统内部具有无锁分配器（或至少一个具有可接受的已知实时行为 - 它最多锁定 X 微秒 [X 可以小于 1.0]）。实时系统通常有一个内存池和固定大小的桶用于回收旧分配，这可以以无锁方式完成 - 桶是一个链表，因此您可以使用原子比较和交换操作从该列表中插入/删除[可能有重试，所以虽然它在技术上是无锁的，但在竞争情况下它不是零等待时间]。

• 另一个可行的解决方案是拥有“每个线程池”。如果您在线程之间传递数据，这可能会变得有点复杂，但是如果您接受“为重用而释放的内存可能最终在不同的线程中”（这当然会导致“所有内存现在都位于那个从许多其他线程收集和释放信息的线程，而所有其他线程都已耗尽内存")