c# - 无锁多线程适合真正的线程专家

Question

我正在阅读 answer Jon Skeet 给出的一个问题，他在其中提到了这一点:

As far as I'm concerned, lock-free multi-threading is for real threading experts, of which I'm not one.

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

所以我的问题是除了学习所有关于线程等的知识之外，你还从哪里开始尝试学习专门编写无锁多线程代码以及有哪些好的资源。

干杯

Answer 1

当前的“无锁”实现大部分时间都遵循相同的模式:

读取一些状态并复制它*

修改副本*

进行联锁操作

失败重试

(*可选:取决于数据结构/算法)
最后一点与自旋锁非常相似。事实上，它是一个基本的 spinlock 。 :)
我同意@nobugz 的观点:无锁多线程中使用的互锁操作的成本是 dominated by the cache and memory-coherency tasks it must carry out 。
然而，使用“无锁”数据结构所获得的是“锁”的粒度非常细。这减少了两个并发线程访问同一个“锁”(内存位置)的机会。
大多数时候的诀窍是你没有专用的锁——而是你对待例如数组中的所有元素或链表中的所有节点作为“自旋锁”。如果自上次阅读以来没有更新，您可以阅读、修改并尝试更新。如果有，请重试。
这使您的“锁定”(哦，抱歉，非锁定 :) 非常细粒度，而不会引入额外的内存或资源要求。
使其更细粒度会降低等待的可能性。在不引入额外资源需求的情况下使其尽可能细粒度听起来很棒，不是吗？
然而，大部分乐趣都来自 ensuring correct load/store ordering 。
与直觉相反，CPU 可以自由地对内存读/写重新排序——顺便说一下，它们非常聪明:您将很难从单个线程中观察到这一点。但是，当您开始在多个内核上进行多线程处理时，您会遇到问题。你的直觉会崩溃:仅仅因为指令在你的代码中较早，并不意味着它实际上会更早发生。 CPU 可以无序处理指令:他们特别喜欢对具有内存访问的指令执行此操作，以隐藏主内存延迟并更好地利用其缓存。
现在，可以肯定的是，代码序列不会“自上而下”流动，而是像根本没有序列一样运行 - 并且可以称为“魔鬼的操场”。我认为对于将发生什么加载/存储重新排序给出确切的答案是不可行的。相反，人们总是用可能、可能和 jar 头来说话，并为最坏的情况做好准备。 “哦，CPU 可能会将该读取重新排序在该写入之前，所以最好在此处放置一个内存屏障，在这个位置。”
事情变得复杂，因为即使这些可能和可能因 CPU 架构而异。例如，可能会发生这样的情况:在一种架构中保证不会发生的事情可能会在另一种架构中发生。

要正确使用“无锁”多线程，您必须了解内存模型。
然而，获取内存模型并保证正确并非易事，如 this story, whereby Intel and AMD made some corrections to the documentation of MFENCE causing some stir-up among JVM developers 所示。事实证明，开发人员从一开始就依赖的文档并不那么精确。
.NET 中的锁会导致隐式内存屏障，因此您可以安全地使用它们(大多数情况下，即...参见有关延迟初始化、锁、 volatile 和内存屏障的 Joe Duffy - Brad Abrams - Vance Morrison greatness 示例。:)(一定要按照该页面上的链接进行操作。)
作为额外的奖励，您将获得 get introduced to the .NET memory model on a side quest 。 :)
还有一个来自 Vance Morrison 的“oldie but goldie”: What Every Dev Must Know About Multithreaded Apps。
...当然，正如 @Eric 所提到的， Joe Duffy 是关于该主题的权威读物。
一个好的 STM 可以尽可能接近细粒度锁定，并且可能会提供接近或与手工实现相当的性能。
其中之一是来自 MS 的 STM.NET 的 DevLabs projects。
如果您不是仅支持 .NET 的狂热者，则 Doug Lea did some great work in JSR-166 。
Cliff Click 对不​​依赖锁条的哈希表有一个有趣的看法——就像 Java 和 .NET 并发哈希表那样——并且似乎可以很好地扩展到 750 个 CPU。
如果您不害怕冒险进入 Linux 领域，以下文章提供了对当前内存架构内部结构以及缓存行共享如何破坏性能的更多见解: What every programmer should know about memory 。
@Ben 对 MPI 发表了很多评论:我真诚地同意 MPI 可能会在某些领域大放异彩。与试图变得智能的半生不熟的锁定实现相比，基于 MPI 的解决方案可以更容易推理、更容易实现且不易出错。 (然而 - 主观上 - 对于基于 STM 的解决方案也是如此。)我还敢打赌，在例如Erlang，正如许多成功的例子所表明的那样。
然而，当 MPI 在单核、多核系统上运行时，它有其自身的成本和问题。例如。在 Erlang 中，围绕 synchronization of process scheduling and message queues 有一些问题需要解决。
此外，在其核心，MPI 系统通常为“轻量级进程”实现一种协作 N:M scheduling。例如，这意味着轻量级进程之间不可避免地存在上下文切换。确实，它不是“经典的上下文切换”，而主要是用户空间操作，并且可以快速进行 - 但是我真诚地怀疑它是否可以置于 20-200 cycles an interlocked operation takes 之下。即使在 Intel McRT 库中，用户模式上下文切换也是 certainly slower。
使用轻量级进程进行 N:M 调度并不新鲜。 LWP 在 Solaris 中存在很长时间了。他们被遗弃了。 NT中有纤维。他们现在大多是遗物。 NetBSD 中有“激活”。他们被遗弃了。 Linux 对 N:M 线程有自己的看法。它现在似乎有些死了。
不时会有新的竞争者出现:例如 McRT from Intel ，或者最近的 User-Mode Scheduling 和来自微软的 ConCRT 。
在最低级别，它们执行 N:M MPI 调度程序所做的工作。 Erlang - 或任何 MPI 系统 - 可能会通过利用新的 UMS 在 SMP 系统上受益匪浅。
我想 OP 的问题不是关于任何解决方案的优点和主观论据，但如果我必须回答这个问题，我想这取决于任务:用于构建运行在具有多个内核的单个系统，无论是低锁定/“无锁定”技术还是 STM 都会在性能方面产生最佳结果，并且在任何时候都可能在性能方面击败 MPI 解决方案，即使上述问题得到解决例如在二郎。
为了构建在单个系统上运行的任何稍微复杂的东西，我可能会选择经典的粗粒度锁定，或者如果性能非常重要，则选择 STM。
对于构建分布式系统，MPI 系统可能是一个自然的选择。
请注意， MPI implementations 有 .NET as well(尽管它们似乎不那么活跃)。