动态无锁内存分配器
Dynamic Lock-free memory allocators
编写满足无锁进度保证的算法或数据结构的困难之一是动态内存分配：不能保证调用 malloc 或 new 之类的东西是无锁的以便携的方式。然而，malloc或new的许多无锁实现是存在的，也有多种无锁内存分配器可以用来实现无锁algorithms/data-structures.
但是，我仍然不明白这实际上如何能够完全满足无锁进度保证，除非您专门将数据结构或算法限制在某个预分配的静态内存池中。但是如果你需要 动态 内存分配，我不明白任何所谓的无锁内存分配器如何在 long-运行 中实现真正的无锁。问题是，无论你的无锁 malloc 或 new 多么惊人，最终你可能 运行 内存不足，此时你必须求助于操作系统以获得更多内存。这意味着最终您必须调用 brk() 或 mmap() 或类似的低级等价物才能实际访问更多内存。并且根本无法保证这些低级调用中的任何一个都是以无锁方式实现的。
根本没有办法解决这个问题，（除非你使用像 MS-DOS 这样不提供内存保护的古老 OS，或者你自己编写完全锁定-免费操作系统 - 两种不实际或不太可能的场景。）那么，任何动态内存分配器如何才能真正做到无锁？
正如您自己发现的那样，基本的 OS 分配器很可能不是无锁的，因为它必须处理多个进程和各种有趣的东西，这使得很难不引入一些有点锁。
然而，在某些情况下，“无锁内存分配”并不意味着“从不锁定”，而是“统计上很少锁定，所以它并不重要”。除了最严格的实时系统，这对任何东西都很好。如果你的锁上没有高争用，那么锁或不锁并不重要——无锁的目的并不是锁本身的开销，而是锁成为瓶颈的难易程度系统中的每个线程或进程都必须经过这个地方才能做任何有用的事情，并且在这样做时，它必须在队列中等待[它可能也不是真正的队列，它可能是“谁先醒来”或者其他一些机制来决定谁在当前调用者之后出现。
有几个不同的选项可以解决这个问题：
如果您的内存池大小有限，您可以在软件启动时立即向 OS 请求所有内存。在内存从 OS 中分块后，它可以用作无锁池。明显的缺点是它对可以分配的内存量有限制。然后您要么必须停止分配（使应用程序全部失败，要么使该特定操作失败）。
当然，在Linux或Windows这样的系统中，仍然不能保证内存分配，在无锁场景下，意味着“即时访问分配的内存”，因为系统可以并且将会在没有实际物理内存支持的情况下分配内存，并且只有在实际使用内存时，才会将物理内存页面分配给它。这可能都涉及锁，例如 disk-I/O 将其他页面分页到交换区。
对于实时性如此严格的系统，单次系统调用可能争锁的时间“太多”了，解决方案当然是使用专用的OS, 一个在 OS 内部有一个无锁分配器的分配器（或者至少一个具有可接受的已知实时行为的分配器 - 它最多锁定 X 微秒 [X 可以小于 1.0]） .实时系统通常有一个内存池和固定大小的桶来回收旧的分配，这可以以无锁的方式完成——桶是一个链表，所以你可以 insert/remove 从那个列表中使用 atomic比较和交换操作[可能有重试，所以虽然它在技术上是无锁的，但在竞争情况下它不是零等待时间]。
另一个可行的解决方案是拥有“每个线程池”。如果您在线程之间传递数据，这可能会变得有点复杂，但是如果您接受“为重用而释放的内存可能会在不同的线程中结束”（这当然会导致“所有内存现在位于一个线程从许多其他线程收集和释放信息，而所有其他线程 运行 内存不足")
编写满足无锁进度保证的算法或数据结构的困难之一是动态内存分配：不能保证调用 malloc 或 new 之类的东西是无锁的以便携的方式。然而，malloc或new的许多无锁实现是存在的，也有多种无锁内存分配器可以用来实现无锁algorithms/data-structures.
但是，我仍然不明白这实际上如何能够完全满足无锁进度保证，除非您专门将数据结构或算法限制在某个预分配的静态内存池中。但是如果你需要 动态 内存分配，我不明白任何所谓的无锁内存分配器如何在 long-运行 中实现真正的无锁。问题是，无论你的无锁 malloc 或 new 多么惊人，最终你可能 运行 内存不足，此时你必须求助于操作系统以获得更多内存。这意味着最终您必须调用 brk() 或 mmap() 或类似的低级等价物才能实际访问更多内存。并且根本无法保证这些低级调用中的任何一个都是以无锁方式实现的。
根本没有办法解决这个问题，（除非你使用像 MS-DOS 这样不提供内存保护的古老 OS，或者你自己编写完全锁定-免费操作系统 - 两种不实际或不太可能的场景。）那么，任何动态内存分配器如何才能真正做到无锁？
正如您自己发现的那样，基本的 OS 分配器很可能不是无锁的，因为它必须处理多个进程和各种有趣的东西，这使得很难不引入一些有点锁。
然而，在某些情况下，“无锁内存分配”并不意味着“从不锁定”，而是“统计上很少锁定，所以它并不重要”。除了最严格的实时系统，这对任何东西都很好。如果你的锁上没有高争用，那么锁或不锁并不重要——无锁的目的并不是锁本身的开销，而是锁成为瓶颈的难易程度系统中的每个线程或进程都必须经过这个地方才能做任何有用的事情，并且在这样做时，它必须在队列中等待[它可能也不是真正的队列，它可能是“谁先醒来”或者其他一些机制来决定谁在当前调用者之后出现。
有几个不同的选项可以解决这个问题：
如果您的内存池大小有限，您可以在软件启动时立即向 OS 请求所有内存。在内存从 OS 中分块后，它可以用作无锁池。明显的缺点是它对可以分配的内存量有限制。然后您要么必须停止分配（使应用程序全部失败，要么使该特定操作失败）。
当然，在Linux或Windows这样的系统中，仍然不能保证内存分配，在无锁场景下，意味着“即时访问分配的内存”，因为系统可以并且将会在没有实际物理内存支持的情况下分配内存，并且只有在实际使用内存时，才会将物理内存页面分配给它。这可能都涉及锁，例如 disk-I/O 将其他页面分页到交换区。
对于实时性如此严格的系统，单次系统调用可能争锁的时间“太多”了，解决方案当然是使用专用的OS, 一个在 OS 内部有一个无锁分配器的分配器（或者至少一个具有可接受的已知实时行为的分配器 - 它最多锁定 X 微秒 [X 可以小于 1.0]） .实时系统通常有一个内存池和固定大小的桶来回收旧的分配，这可以以无锁的方式完成——桶是一个链表，所以你可以 insert/remove 从那个列表中使用 atomic比较和交换操作[可能有重试，所以虽然它在技术上是无锁的，但在竞争情况下它不是零等待时间]。
另一个可行的解决方案是拥有“每个线程池”。如果您在线程之间传递数据，这可能会变得有点复杂，但是如果您接受“为重用而释放的内存可能会在不同的线程中结束”（这当然会导致“所有内存现在位于一个线程从许多其他线程收集和释放信息，而所有其他线程 运行 内存不足")