动态无锁内存分配器

Question

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

但是，我仍然不明白这如何才能完全满足无锁的进度保证，除非您具体地将数据结构或算法限制在某些预先分配的静态内存池上。但是，如果您需要动态内存分配，我不明白从长远来看，任何所谓的无锁内存分配程序都是真正没有锁的。问题是，无论您的无锁malloc或new有多么神奇，最终您可能会耗尽内存，此时您必须退回到要求操作系统提供更多内存。这意味着最终您必须调用brk()或mmap()或一些类似的低级级别，才能真正访问更多内存。而且无法保证这些低级别调用都是以无锁的方式实现的。

这是无法避免的(除非你使用的是像MS这样不提供内存保护的老操作系统，或者是你自己编写的完全没有锁的操作系统--这两个方案既不实用，也不可能。)那么，任何动态内存分配程序如何才能真正实现无锁呢？

Answer 1

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

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

要解决这个问题，有几种不同的选择：

• 如果您有一个有限大小的内存池，您可以在软件启动时立即向操作系统询问所有这些内存。当内存从操作系统中分块出来后，它可以作为一个无锁池使用。明显的缺点是，它有一个限制，多少内存可以分配。然后，您必须停止分配(一起失败应用程序，或者失败特定的操作)。 当然，在Linux或Windows这样的系统中，仍然不能保证内存分配在无锁的情况下意味着“立即访问分配的内存”，因为系统可以并且将在没有实际物理内存备份的情况下分配内存，而且只有当内存实际被使用时，物理内存页才会被分配给它。这两种方法都可能涉及锁，例如磁盘I/O将其他页面分页到交换区。
• 对于这样严格的实时系统来说，单个系统调用可能争锁的时间“太长”，解决方案当然是使用专用操作系统，在操作系统中有一个无锁的分配器(或者至少有一个已知的实时行为是可以接受的--它最多只能锁定X microsecons X可能小于1.0)。实时系统通常有一个内存池和固定大小的桶，用于回收旧分配，这可以以无锁的方式完成--存储桶是一个链接列表，因此您可以使用原子比较和交换操作(可能是重试)从该列表中插入/删除，所以尽管在技术上是没有锁的，但在竞争的情况下，它并不是零等待时间。
• 另一个可行的解决方案是“每个线程池”。如果您在线程之间传递数据，这可能会变得有点复杂，但如果您接受“释放用于重用的内存可能会在另一个线程中结束”(这当然会导致类似于“所有内存都位于一个线程中，它收集并释放来自许多其他线程的信息，而所有其他线程都已耗尽内存”)。