我正在阅读Jon Skeet对一个问题的回答，他在其中提到了这一点：
就我而言，无锁多线程适用于真正的线程专家，我不是其中之一。
这不是我第一次听说，但是如果你有兴趣学习如何编写无锁多线程代码，我发现很少有人谈论你实际上是如何做到的。
所以我的问题是除了尽可能多地学习线程等，你从哪里开始尝试学习专门编写无锁多线程代码以及什么是好的资源。
干杯
问问题
25385 次
6 回答
101
当前的“无锁”实现大部分时间都遵循相同的模式：
- 阅读一些状态并复制它*
- 修改副本*
- 做联锁操作
- 如果失败则重试
（*可选：取决于数据结构/算法）
最后一点与自旋锁非常相似。事实上，它是一个基本的自旋锁。:)
我同意@nobugz 的观点：无锁多线程中使用的互锁操作的成本主要由它必须执行的缓存和内存一致性任务决定。
然而，使用“无锁”的数据结构，您获得的是您的“锁”是非常细粒度的。这减少了两个并发线程访问相同“锁”（内存位置）的机会。
大多数时候的诀窍是您没有专用的锁 - 相反，您将数组中的所有元素或链表中的所有节点视为“自旋锁”。如果自上次阅读后没有更新，您阅读、修改并尝试更新。如果有，请重试。
这使您的“锁定”（哦，对不起，非锁定:) 非常细粒度，而不会引入额外的内存或资源要求。
使其更细粒度会降低等待的可能性。在不引入额外资源要求的情况下使其尽可能细化听起来很棒，不是吗？
然而，大部分乐趣来自确保正确的加载/存储顺序。
与直觉相反，CPU 可以自由地重新排序内存读取/写入 - 顺便说一下，它们非常聪明：您将很难从单个线程中观察到这一点。但是，当您开始在多个内核上执行多线程时，您会遇到问题。你的直觉会崩溃：仅仅因为一条指令在你的代码中更早，并不意味着它实际上会更早发生。CPU 可以乱序处理指令：它们特别喜欢对具有内存访问的指令执行此操作，以隐藏主内存延迟并更好地利用其缓存。
现在，与直觉相反，代码序列肯定不会“自上而下”流动，而是像根本没有序列一样运行 - 并且可能被称为“魔鬼游乐场”。我相信要给出一个关于加载/存储重新排序将发生的确切答案是不可行的。相反，人们总是用可能、可能和罐头来说话，并为最坏的情况做准备。“哦，CPU可能会将读取重新排序到写入之前，因此最好在此处，在此位置放置内存屏障。”
事情变得复杂，因为即使这些可能和可能在 CPU 体系结构中也可能不同。例如，在一种架构中保证不会 发生的事情可能会在另一种架构中发生。
要获得正确的“无锁”多线程，您必须了解内存模型。
然而，获得正确的内存模型和保证并非易事，正如这个故事所证明的那样，英特尔和 AMD 对MFENCE在 JVM 开发人员中引起一些骚动的文档进行了一些更正。事实证明，开发人员从一开始就依赖的文档最初并不是那么精确。
.NET 中的锁会导致隐式内存屏障，因此您可以安全地使用它们（大多数情况下，就是......例如参见Joe Duffy - Brad Abrams - Vance Morrison在延迟初始化、锁、易失性和内存方面的伟大之处障碍。:)（请务必点击该页面上的链接。）
作为额外的奖励，您将在支线任务中了解 .NET 内存模型。:)
还有来自 Vance Morrison 的“老歌但金童”：每个开发人员都必须了解的关于多线程应用程序的内容。
...当然，正如@Eric 所提到的，Joe Duffy是该主题的权威读物。
一个好的 STM 可以尽可能接近细粒度的锁定，并且可能会提供接近或与手工实现相当的性能。其中之一是来自 MS 的DevLabs项目的 STM.NET。
如果您不是仅 .NET 的狂热者，Doug Lea 在 JSR-166 中做了一些出色的工作。
Cliff Click对不依赖锁条带化的哈希表有一个有趣的看法——正如 Java 和 .NET 并发哈希表所做的那样——并且似乎可以很好地扩展到 750 个 CPU。
如果您不怕冒险进入 Linux 领域，那么下面的文章将更深入地了解当前内存架构的内部结构以及缓存行共享如何破坏性能：每个程序员都应该了解的内存知识。
@Ben 对 MPI 发表了很多评论：我真诚地同意 MPI 可能会在某些领域大放异彩。基于 MPI 的解决方案比试图变得聪明的半生不熟的锁定实现更容易推理、更容易实现且不易出错。（然而，主观上，对于基于 STM 的解决方案也是如此。）我还敢打赌，正如许多成功的例子所表明的那样，在例如 Erlang 中正确编写一个体面的分布式应用程序要容易很多光年。
然而，当 MPI 在单个多核系统上运行时，它有自己的成本和麻烦。例如在 Erlang 中，围绕进程调度和消息队列的同步有一些问题需要解决。此外，在其核心，MPI 系统通常为“轻量级进程”
实现一种协作式N:M 调度。例如，这意味着轻量级进程之间存在不可避免的上下文切换。确实，它不是“经典上下文切换”，而主要是用户空间操作，并且可以快速完成 - 但是我真诚地怀疑它是否可以在联锁操作所需的 20-200 个周期下进行。用户模式上下文切换肯定更慢即使在英特尔 McRT 库中。使用轻量级进程的 N:M 调度并不新鲜。LWP 在 Solaris 中已经存在很长时间了。他们被遗弃了。NT中有纤维。它们现在大多是遗物。NetBSD 中有“激活”。他们被遗弃了。Linux 对 N:M 线程有自己的看法。它现在似乎已经有些死了。
有时会出现新的竞争者：例如Intel 的 McRT，或者最近的 User-Mode Scheduling和 Microsoft 的ConCRT。
在最低级别，它们执行 N:M MPI 调度程序所做的事情。Erlang - 或任何 MPI 系统 - 通过利用新的UMS可能会极大地受益于 SMP 系统。
我猜 OP 的问题不是关于支持/反对任何解决方案的优点和主观论据，但如果我必须回答这个问题，我想这取决于任务：用于构建运行在具有多个内核的单个系统，无论是低锁定/“无锁定”技术还是 STM，都将在性能方面产生最佳结果，并且可能随时在性能方面击败 MPI 解决方案，即使上述问题已经消除例如在 Erlang 中。
为了构建在单个系统上运行的任何稍微复杂的东西，我可能会选择经典的粗粒度锁定，或者如果性能非常重要，那么可以选择 STM。
对于构建分布式系统，MPI 系统可能是一个自然的选择。
请注意，.NET
也有MPI 实现（尽管它们似乎不那么活跃）。
于 2010-03-27T16:50:22.100 回答
29
乔·达菲的书：
http://www.bluebytesoftware.com/books/winconc/winconc_book_resources.html
他还写了一篇关于这些主题的博客。
正确使用低锁程序的诀窍是在深层次上准确理解内存模型的规则在您的硬件、操作系统和运行时环境的特定组合上是什么。
我个人还不够聪明，无法在 InterlockedIncrement 之外进行正确的低锁编程，但如果你很聪明，那就去吧。只需确保在代码中留下大量文档，以便那些不如您聪明的人不会意外破坏您的内存模型不变量之一并引入无法找到的错误。
于 2010-03-27T15:12:44.813 回答
20
这些天没有“无锁线程”这样的东西。早在上世纪末，当计算机硬件速度缓慢且价格昂贵时，这对学术界等人来说是一个有趣的游乐场。 Dekker 的算法一直是我最喜欢的，现代硬件已经把它淘汰了。它不再起作用了。
两个发展结束了这一点：RAM 和 CPU 的速度之间的差距越来越大。以及芯片制造商在一个芯片上放置多个 CPU 内核的能力。
RAM 速度问题要求芯片设计人员在 CPU 芯片上放置一个缓冲区。缓冲区存储代码和数据，CPU 内核可以快速访问。并且可以以更慢的速度从 RAM 读取和写入 RAM。这个缓冲区称为 CPU 缓存，大多数 CPU 至少有两个。一级缓存小而快，二级缓存大而慢。只要 CPU 可以从一级缓存中读取数据和指令，它就会运行得很快。缓存未命中非常昂贵，如果数据不在第一个缓存中，它会使 CPU 休眠多达 10 个周期，如果它不在第二个缓存中并且需要从第二个缓存中读取，它会使 CPU 休眠多达 200 个周期内存。
每个 CPU 内核都有自己的缓存，它们存储自己的 RAM“视图”。当 CPU 写入数据时，会写入缓存，然后缓存会慢慢刷新到 RAM。不可避免的是，每个内核现在都将拥有不同的 RAM 内容视图。换句话说，一个 CPU 不知道另一个 CPU 写了什么，直到 RAM 写周期完成并且CPU 刷新它自己的视图。
这与线程非常不兼容。当您必须读取另一个线程写入的数据时，您总是非常关心另一个线程的状态。为确保这一点，您需要显式编程所谓的内存屏障。它是一种低级 CPU 原语，可确保所有 CPU 缓存处于一致状态并具有最新的 RAM 视图。所有挂起的写入都必须刷新到 RAM，然后需要刷新缓存。
这在 .NET 中可用，Thread.MemoryBarrier() 方法实现了一个。鉴于这是 lock 语句完成的 90% 的工作（以及 95% 以上的执行时间），因此避免使用 .NET 为您提供的工具并尝试实现自己的工具，您根本无法领先。
于 2010-03-27T15:01:14.790 回答
0
当涉及到多线程时，您必须确切地知道自己在做什么。我的意思是探索在多线程环境中工作时可能发生的所有可能场景/案例。无锁多线程不是我们合并的库或类，它是我们在线程之旅中获得的知识/经验。
于 2010-03-27T10:54:10.857 回答
0
尽管在 .NET 中无锁线程可能很困难，但在使用锁时，您通常可以通过准确研究需要锁定的内容并最小化锁定部分来做出重大改进……这也称为最小化锁粒度。
举个例子，只是说你需要让一个收集线程安全。如果它对每个项目执行一些 CPU 密集型任务，请不要盲目地对迭代集合的方法进行锁定。您可能只需要锁定创建集合的浅表副本。然后迭代副本可以在没有锁定的情况下工作。当然，这在很大程度上取决于您的代码的细节，但我已经能够用这种方法解决锁护卫问题。
于 2012-04-19T07:18:06.690 回答