动态无锁内存分配器

Question

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

然而，除非你特别限制数据结构或算法为预分配的静态内存池，否则我仍然不理解如何实际上完全满足无锁进度保证。但如果您需要动态内存分配，我不明白任何所谓的无锁内存分配器如何在长期内真正做到无锁。问题在于，无论你的无锁malloc或new有多么神奇，最终您可能会用完内存，在这种情况下，您必须回退并向操作系统请求更多内存。这意味着，最终您必须调用brk()或mmap()或某种低级等效函数才能实际访问更多内存。而且，没有任何保证这些低级调用中的任何一个都以无锁方式实现。

除非您使用像MS-DOS这样不提供内存保护的古老操作系统，或者编写自己完全无锁的操作系统-这两种情况都不实际或不可能，否则没有任何绕过这个问题的方法。那么，任何动态内存分配器真正能做到无锁吗？

- Siler

---

你说得没错，但是......由于分配器只从操作系统请求大块内存，并且不需要及时释放它们，因此对sbrk()或其他函数的调用总数可以严格限制到无关紧要的程度。当然，这并不能满足硬实时要求，但我认为即使完全无锁的动态分配也无法满足这样的要求。 - Matt Timmermans

所有在真实系统上运行的分配器都必须在某个时刻耗尽内存；当静态池被分配完时，无锁分配器耗尽内存并没有与正常分配器在操作系统决定你已经使用足够内存时有本质区别。 - James Picone

@MatsPetersson：是的，显然它并不是无等待(wait-free)，但从技术上讲，您可以将其视为非阻塞式(obstruction-free)和无锁(lock-free)。后者只需要确保至少有一个线程在任何给定时间都能够向前进展。实际上，这些计算机科学术语并不是你关心的问题，当存在争用时，你实际关心的是可扩展性。因此，使用原子操作的无锁算法通常是一种胜利，即使它们不是无锁(例如无锁队列，在这里对差异进行了良好的分析: https://dev59.com/5lcO5IYBdhLWcg3wXwh3#45910129)。 - Peter Cordes

无论如何，如果您在用户空间中拥有一个良好的无锁分配器，并且只偶尔向操作系统请求更多内存（并以大块方式执行此操作），则内核的锁定可能会较少成为问题。（特别是在用户空间中使用每个线程池，因此当共享池运行低时，您不会得到一大堆线程同时调用内核。）这有点虚构，因为我实际上没有编写或调整过这样的代码。但这就是为什么我问OP是否担心延迟（显然会影响调用内核）还是技术上的非阻塞。 - Peter Cordes

是的，这基本上就是我的答案：锁只有在每次应用于所有调用者时才会成为问题，偶尔调用操作系统来扩展池很少会是真正的问题。 - Mats Petersson

Answer 1

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

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

有几种不同的解决方法：

1. 如果您有一个具有有限大小的内存池，则可以在软件启动时一次性向操作系统请求所有内存。在从操作系统分配了内存并将其分块后，它可以用作无锁池。明显的缺点是它分配的内存量有限。您可以停止分配（完全失败应用程序或失败特定操作）。

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

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

3. 另一个可行的解决方案是使用“每个线程池”。如果您在线程之间传递数据，这可能会变得有点复杂，但是如果您接受“为重用而释放的内存可能会出现在不同的线程中”（这当然会导致类似于“所有内存都现在位于那个收集和释放来自许多其他线程的信息的线程中，而所有其他线程已经用尽了内存”的问题）。

- Mats Petersson