动态无锁内存分配器

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

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

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

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

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

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

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

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

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

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