问题标签 [lock-free]

这需要无锁，因为它必须在 SMP 系统的中断处理程序中运行。我不能拿锁。

我有一个包含一些值的连续数组。此数组中的某些条目是“空闲的”，它们未被占用。我想列出这些条目，以便我可以快速分配一个。但是，我有时不得不分配一个任意条目。

因此，我认为以下是一种不错的处理方式：连续数组不仅保存值，还保存左右指针，从而形成双端队列。只有自由值具有有效的左/右指针。我可以快速访问任意节点，因为它只是对双端队列的索引访问。

现在，问题的关键是：是否有一个不错的无锁双端队列算法，它相对有效并且可以支持删除任意节点？

当涉及到 MESI 等缓存一致性协议时，CPU 寄存器和 CPU 缓存之间有什么关系？如果某个值存储在 CPU 的缓存中，并且还存储在寄存器中，那么如果缓存行被标记为“脏”会发生什么？据我了解，即使缓存已更新（由于 MESI），也无法保证寄存器会更新其值。

验证此代码：

（假设编译器没有优化循环外“完成”的负载）据
我所知，第二个线程看不到“完成”的更新，因为它的值保存在寄存器中（CPU 2 的缓存是但是更新）。

放置内存屏障会强制“刷新”所有寄存器吗？寄存器与缓存的关系是什么？那么寄存器和内存屏障呢？

我有一个 TI DSP（TMS320F28235，如果有人关心的话），我需要实现一个 FIFO，以便在主循环代码和中断之间排队信息。这个队列的高速执行非常关键，但正确的操作也是如此，我不确定我是否可以在没有任何显式同步的情况下实现 FIFO，或者如果不能，我必须禁用中断。

我找到了这个页面，想知道这里是否有人可以评论它的适用性。

我需要设计一个线程安全的记录器。我的记录器必须有一个 Log() 方法，该方法只是将要记录的文本排队。此外，记录器必须是无锁的 - 以便其他线程可以在不锁定记录器的情况下记录消息。我需要设计一个工作线程，它必须等待一些同步事件，然后使用标准.NET 日志记录队列中的所有消息（这不是线程安全的）。所以我感兴趣的是工作线程的同步 - 和日志功能。下面是我设计的课程的草图。我想我必须在这里使用 Monitor.Wait/Pulse 或任何其他方式来暂停和恢复工作线程。当记录器没有工作时，我不想花费 CPU 周期。

让我换一种说法——我想设计一个不会阻塞使用它的调用者线程的记录器。我有一个高性能系统——这是一个要求。

从理论上讲，至少应该可以蛮力验证无锁算法（只有这么多的函数调用组合相交）。是否有任何工具或正式的推理过程可用于实际证明无锁算法是正确的（理想情况下，它也应该能够检查竞争条件和 ABA 问题）？

注意：如果你知道一种方法来证明一个点（例如只证明它对 ABA 问题是安全的）或者我没有提到的问题，那么无论如何都要发布解决方案。在最坏的情况下，每种方法都可以轮流进行，以充分验证它。

我有一堆线程彼此进行大量通信。我希望这是无锁的。

对于每个线程，我想要一个邮箱，其他线程可以向它发送消息，（但只有所有者可以删除消息）。这是一个多生产者单消费者的情况。我可以在无锁/高性能问题上做到这一点吗？（这是在一个巨大模拟的内部循环中。）

想象一个有两个线程的程序。他们正在运行以下代码（CAS 指的是比较和交换）：

线程 B 是否有可能永久导致线程 A 的 CAS 失败，从而永远不会将 0xdeadbeef 写入“测试”？或者自然调度抖动是否意味着在实践中这永远不会发生？如果在线程 A 的 while 循环中完成了一些工作怎么办？

我正在寻找符合这些要求的无锁设计：

• 单个写入器写入结构，单个读取器从该结构读取（该结构已经存在并且对于同时读/写是安全的）
• 但有时，结构需要由 writer 更改，然后初始化、切换并写入新结构（相同类型但具有新内容）
• 并且在下次阅读器读取时，它切换到这个新结构（如果写入器多次切换到一个新的无锁结构，阅读器丢弃这些结构，忽略它们的数据）。
• 必须重用这些结构，即在写/读/切换操作期间不允许堆内存分配/释放，用于RT 目的。

我目前已经实现了一个包含这些结构的多个实例的环形缓冲区；但是这个实现的问题是，当编写者使用了环形缓冲区中存在的所有结构时，就没有更多的地方可以改变结构了......但是环形缓冲区的其余部分包含一些不必读取的数据由读者使用，但作者不能重复使用。因此，环形缓冲区不适合此目的。

任何关于无锁设计的想法（名称或伪实现） ？感谢您考虑过这个问题。

在我尝试开发线程安全的 C++ 弱指针模板类时，我需要检查一个指示对象仍然存在的标志，如果是，则增加对象的引用计数，我需要原子地执行这两个步骤。

我知道编译器提供的内在函数的存在，例如 _InterlockedCompareExchange() 和 _InterlockedIncrement()。但是我想要的是一个 interlockedCompareIncrement() 函数，是否有一种有效的方法可以使用其他原语来模拟这个内在函数，至少在 Windows x86 平台上是这样？

我正在阅读Jon Skeet对一个问题的回答，他在其中提到了这一点：

就我而言，无锁多线程适用于真正的线程专家，我不是其中之一。

这不是我第一次听说，但是如果你有兴趣学习如何编写无锁多线程代码，我发现很少有人谈论你实际上是如何做到的。

所以我的问题是除了尽可能多地学习线程等，你从哪里开始尝试学习专门编写无锁多线程代码以及什么是好的资源。

干杯