真正的无锁 MPMC 环形缓冲区？线程可以互相协助避免阻塞吗？
Truly Lock-free MPMC Ring Buffer? Threads able to assist each other to avoid blocking?
本题灵感来自。所示代码并非严格无锁。每当写入线程在队列不为空或未满时挂起，reader 线程返回 false，阻止整个数据结构取得进展。
真正无锁环形缓冲区的正确行为应该是什么？
Generally, truly lock-free algorithms involve a phase where a pre-empted thread actually tries to ASSIST the other thread in completing an operation.
有任何关于此技术的参考吗？对于基于数组的 MPMC 队列如何实现？
我看了一些代码，也有类似的问题。
- craflin's version使用两个内部原子来记录读写。
- https://codereview.stackexchange.com/questions/263157/c-lock-free-mpmc-ring-buffer-in-c20 使用忙等待，而不是无锁。
作为 cross-thread 辅助通常如何在现实生活中工作的一个很好的例子，考虑一个 lock-free MPMC 队列可以通过改变 liblfds 算法来获得:
使用 3 个计数器：
alloc_pos：已启动的推送操作总数。当推送开始时，这会自动增加。write_pos: 已知低位的所有写操作已完成。read_pos: 已知写在较低位置的所有项目已被消耗。
在此方案中，推送或弹出操作由受影响槽中的CAS 完成。 write_pos 和 read_pos 变量是 冗余的 。
因此，要推送，线程首先递增 alloc_pos，然后递增 write_pos，使其前面的所有插槽都已完成。这是一个辅助——它正在完成之前在其他线程中启动的写入。然后线程必须扫描 write_pos 和 alloc_pos 之间的插槽，直到它找到一个空闲的插槽并设法用 CAS 保留它。
为了弹出，reader 第一次增量 read_pos 超过了它可以看到的写在较低位置的所有项目。这又是一个帮助——完成以前的阅读。然后它从 read_pos 扫描到 alloc_pos 以查看是否可以找到已完成写入的项目。
正如评论中提到的那样，真正这样做会很烦人，因为实施决策会牺牲性能与您需要的订购和可用性保证，以及跳过箍以防止 ABA 问题。
本题灵感来自
真正无锁环形缓冲区的正确行为应该是什么？
Generally, truly lock-free algorithms involve a phase where a pre-empted thread actually tries to ASSIST the other thread in completing an operation.
有任何关于此技术的参考吗？对于基于数组的 MPMC 队列如何实现？
我看了一些代码，也有类似的问题。
- craflin's version使用两个内部原子来记录读写。
- https://codereview.stackexchange.com/questions/263157/c-lock-free-mpmc-ring-buffer-in-c20 使用忙等待，而不是无锁。
作为 cross-thread 辅助通常如何在现实生活中工作的一个很好的例子，考虑一个 lock-free MPMC 队列可以通过改变 liblfds 算法来获得:
使用 3 个计数器：
alloc_pos：已启动的推送操作总数。当推送开始时，这会自动增加。write_pos: 已知低位的所有写操作已完成。read_pos: 已知写在较低位置的所有项目已被消耗。
在此方案中，推送或弹出操作由受影响槽中的CAS 完成。 write_pos 和 read_pos 变量是 冗余的 。
因此，要推送，线程首先递增 alloc_pos，然后递增 write_pos，使其前面的所有插槽都已完成。这是一个辅助——它正在完成之前在其他线程中启动的写入。然后线程必须扫描 write_pos 和 alloc_pos 之间的插槽，直到它找到一个空闲的插槽并设法用 CAS 保留它。
为了弹出，reader 第一次增量 read_pos 超过了它可以看到的写在较低位置的所有项目。这又是一个帮助——完成以前的阅读。然后它从 read_pos 扫描到 alloc_pos 以查看是否可以找到已完成写入的项目。
正如评论中提到的那样，真正这样做会很烦人，因为实施决策会牺牲性能与您需要的订购和可用性保证，以及跳过箍以防止 ABA 问题。