https://stackoverflow.com/questions/92455
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
在我的多线程应用程序中，我发现其中存在严重的锁争用，从而阻碍了跨多个内核的良好可扩展性。我决定使用无锁编程来解决这个问题。
如何编写无锁结构？
解决方案
简短的回答是：
你不能。
长答案是：
如果您问这个问题，您可能不知道足够的知识来创建无锁结构。创建无锁结构非常困难，只有该领域的专家才能做到。不要自己编写，而是搜索现有的实现。当你找到它时，检查它的使用范围，它的文档记录得如何，是否得到充分证明，有哪些限制 - 甚至其他人发布的一些无锁结构也被破坏了。
如果您没有找到与您当前使用的结构相对应的无锁结构，请调整算法以便您可以使用一些现有的结构。
如果您仍然坚持创建自己的无锁结构，请务必：
- 从非常简单的事情开始
- 了解目标平台的内存模型（包括读/写重新排序约束，哪些操作是原子的）
- 研究很多其他人在实现无锁结构时遇到的问题
- 不要只是猜测它是否有效，要证明它
- 严格测试结果
更多阅读：
其他提示
使用诸如以下的库 英特尔的线程构建模块, ，它包含相当多的无锁结构和算法。我真的不建议尝试自己编写无锁代码，它非常容易出错并且很难正确执行。
编写线程安全的无锁代码很困难；但 这篇文章来自赫伯·萨特 会让你开始。
作为 斯布伦迪 指出，如果所有对象都是不可变的、只读的，则无需担心锁定，但是，这意味着您可能必须大量复制对象。复制通常涉及 malloc，而 malloc 使用锁定来同步线程之间的内存分配，因此不可变对象可能会比您想象的要少（malloc 本身的扩展性相当差，而 malloc 是 慢的;如果您在性能关键部分执行大量 malloc，则不要期望获得良好的性能）。
当您只需要更新简单变量时（例如32 或 64 位 int 或指针），对它们执行简单的加法或减法运算，或者只是交换两个变量的值，大多数平台为此提供“原子操作”（进一步的 GCC 也提供这些）。 原子性与线程安全不同. 。然而，原子确保，例如，如果一个线程将 64 位值写入内存位置，而另一个线程从中读取，则读取线程要么在写入操作之前或在写入操作之后获取该值，但永远不会获取该值。 破碎的 写入操作之间的值（例如其中前 32 位已经是新值，最后 32 位仍然是旧值！如果您不对此类变量使用原子访问，则可能会发生这种情况）。
但是，如果您有一个包含 3 个值的 C 结构体，想要更新，即使您使用原子操作更新所有三个值，这也是三个独立的操作，因此读者可能会看到结构体中的一个值已被更新，而两个值尚未更新。更新。如果您必须确保读者看到结构中的所有值是旧值或新值，那么您将需要一个锁。
使锁更好地扩展的一种方法是使用 R/W 锁。在许多情况下，数据更新相当罕见（写入操作），但访问数据却非常频繁（读取数据），例如集合（哈希表、树）。在这种情况下，读/写锁将为您带来巨大的性能提升，因为许多线程可以同时持有读锁（它们不会互相阻塞），并且只有当一个线程需要写锁时，所有其他线程都需要写锁在执行更新期间被阻止。
避免线程问题的最佳方法是不要跨线程共享任何数据。如果每个线程大部分时间都处理其他线程无法访问的数据，则根本不需要锁定该数据（也不需要原子操作）。因此，尝试在线程之间共享尽可能少的数据。然后，如果确实需要，您只需要一种在线程之间移动数据的快速方法（ITC，线程间通信）。根据您的操作系统、平台和编程语言（不幸的是您没有告诉我们这些），可能存在各种强大的 ITC 方法。
最后，在没有任何锁定的情况下处理共享数据的另一个技巧是确保线程不会访问共享数据的相同部分。例如。如果两个线程共享一个数组，但一个线程只能访问偶数索引，另一个线程只能访问奇数索引，则不需要锁定。或者，如果两者共享相同的内存块，并且一个仅使用其上半部分，另一个仅使用下半部分，则无需锁定。虽然没有说，但这会带来良好的性能；尤其是在多核 CPU 上。一个线程对此共享数据（运行一个内核）的写入操作可能会强制刷新缓存以供另一个线程（在另一个内核上运行）使用，而这些缓存刷新通常是在现代多核 CPU 上运行的多线程应用程序的瓶颈。
正如我的教授（《多处理器编程的艺术》中的 Nir Shavit）告诉全班的那样：请不要。主要原因是可测试性 - 您无法测试同步代码。您可以运行模拟，甚至可以进行压力测试。但这充其量只是粗略的近似。你真正需要的是数学正确性证明。很少有人能够理解它们，更不用说编写它们了。所以，正如其他人所说：使用现有的库。 乔·达菲的博客 调查了一些技术（第 28 节）。您应该尝试的第一个方法是树拆分 - 分解为较小的任务并合并。
不变性是避免锁定的一种方法。看 埃里克·利珀特的讨论 以及诸如不可变堆栈和队列之类的实现。
在 re.Maurice Herlithy 在《多处理器编程的艺术》中展示了 Suma 的答案，实际上 任何事物 可以无锁写入（参见第 6 章）。iirc，这本质上涉及将任务拆分为处理节点元素（如函数闭包），并将每个任务排队。线程将通过跟踪最新缓存节点中的所有节点来计算状态。显然，在最坏的情况下，这可能会导致顺序性能，但它确实具有重要的无锁属性，可以防止线程在持有锁时长时间被调度的情况。Herlithy 还实现了理论上的无等待性能，这意味着一个线程不会永远等待以赢得原子队列（这是很多复杂的代码）。
多线程队列/堆栈非常困难（检查 应用行为分析问题）。其他事情可能非常简单。习惯 while(true) {atomicCAS 直到我交换了它 } 块；他们非常强大。对 CAS 正确性的直觉可以帮助开发，尽管您应该使用良好的测试和可能更强大的工具（也许 草图, ，即将到来的麻省理工学院 剑道, ， 或者 旋转？）来检查正确性是否可以将其简化为简单的结构。
请发布更多有关您的问题的信息。没有细节很难给出好的答案。
编辑 不变性很好，但如果我理解正确的话，它的适用性是有限的。它并没有真正克服读后写的危险；考虑两个线程执行“mem = NewNode(mem)”；他们都可以读内存，然后都可以写；不适合经典增量函数。此外，由于堆分配（必须跨线程同步），它可能会很慢。
不变性会产生这种效果。对对象的更改会产生一个新对象。Lisp 在幕后就是这样工作的。
第 13 项 有效的Java 解释了这项技术。
Cliff Click 利用有限状态机对无锁数据结构进行了一些主要研究，并且还发布了许多 Java 实现。您可以在他的博客中找到他的论文、幻灯片和实现： http://blogs.azulsystems.com/cliff/
使用现有的实现，因为该工作领域是领域专家和博士的领域（如果您希望正确完成！）
例如，这里有一个代码库：
无锁同步的基本原理是这样的：
每当你阅读结构时，你都会在阅读后进行测试，看看自你开始阅读以来结构是否发生了变异，然后重试，直到你成功阅读，而在你这样做时没有其他东西出现和变异；
每当您改变结构时，您都会安排算法和数据，以便有一个原子步骤，如果采取该步骤，则会导致整个更改对其他线程可见，并安排事物以使所有更改都不可见，除非已采取该步骤。您可以使用平台上存在的任何无锁原子机制来执行该步骤（例如比较并设置、加载链接+条件存储等）。在该步骤中，您必须检查自突变操作开始以来是否有任何其他线程对该对象进行了突变，如果没有则提交，如果有则重新开始。
网络上有很多无锁结构的例子；如果不了解您正在实施的内容以及在什么平台上实施的更多信息，则很难更具体。
如果您正在为多核 cpu 编写自己的无锁数据结构，请不要忘记内存屏障！另外，请考虑调查 软件事务内存 技术。
嗯，这取决于结构的类型，但是你必须创建这样的结构，以便它仔细地、默默地检测和处理可能的冲突。
我怀疑你能否制作一个 100% 无锁的结构，但同样，这取决于你需要构建什么样的结构。
您可能还需要对结构进行分片，以便多个线程处理单个项目，然后进行同步/重组。
如前所述，这实际上取决于您所讨论的结构类型。例如，您可以编写一个有限的无锁队列，但不能编写允许随机访问的队列。
减少或消除共享的可变状态。
在 Java 中，使用 JDK 5+ 中的 java.util.concurrent 包，而不是编写自己的包。正如上面提到的，这确实是一个专家领域，除非你有一两年的空闲时间，否则自己动手并不是一个选择。
您能澄清一下结构的含义吗？
现在，我假设您指的是整体架构。您可以通过不在进程之间共享内存并为进程使用参与者模型来实现此目的。
看看我的 链接 ConcurrentLinkedHashMap 有关如何编写无锁数据结构的示例。它不基于任何学术论文，也不需要像其他人暗示的那样需要多年的研究。它只需要仔细的工程设计。
我的实现确实使用了 ConcurrentHashMap，它是一种每桶锁算法，但它不依赖于该实现细节。它可以很容易地被 Cliff Click 的无锁实现所取代。我借用了 Cliff 的一个想法，但使用得更明确，那就是用状态机对所有 CAS 操作进行建模。这极大地简化了模型，因为您将看到我通过 'ing 状态拥有伪锁。另一个技巧是允许懒惰并根据需要解决问题。通过回溯或让其他线程“帮助”清理，您会经常看到这种情况。就我而言，我决定允许列表上的死节点在到达头部时被驱逐，而不是处理从列表中间删除它们的复杂性。我可能会改变这一点，但我并不完全相信我的回溯算法，并且想推迟重大改变，例如采用 3 节点锁定方法。
《多处理器编程的艺术》一书是一本很好的入门读物。但总的来说，我建议避免在应用程序代码中使用无锁设计。很多时候，在其他不易出错的技术更适合的情况下，这简直是矫枉过正。
如果您看到锁争用，我会首先尝试在数据结构上使用更细粒度的锁，而不是完全无锁的算法。
例如，我目前正在开发多线程应用程序，该应用程序具有自定义消息传递系统（每个线程的队列列表，队列包含线程要处理的消息）以在线程之间传递信息。该结构上有一个全局锁。就我而言，我不太需要速度，所以这并不重要。但是，如果此锁成为问题，则可以将其替换为每个队列中的单独锁。然后，向特定队列添加/删除元素不会影响其他队列。仍然会有一个用于添加新队列等的全局锁，但不会有太多竞争。
即使是单个多生产者/消费者队列也可以在每个元素上使用粒度锁定来编写，而不是使用全局锁。这也可以消除争用。
如果您阅读了有关该主题的多个实现和论文，您会注意到有以下共同主题：
1) 共享状态对象是 lisp/clojure 风格的不可变对象: ：也就是说，所有写操作都是通过复制新对象中的现有状态来实现的，对新对象进行修改，然后尝试更新共享状态（从可以使用 CAS 原语更新的对齐指针获取）。换句话说，您永远不会修改可能被当前线程以外的多个线程读取的现有对象。对于大型、复杂的对象，可以使用 Copy-on-Write 语义来优化不可变性，但那是另一棵坚果树
2) 您明确指定当前状态和下一个状态之间允许的转换是有效的: ：然后验证算法的有效性变得更加容易
3) 处理每个线程的危险指针列表中丢弃的引用. 。参考对象安全后，尽可能重用
请参阅我的另一篇相关文章，其中一些使用信号量和互斥体实现的代码以无锁风格（部分）重新实现：互斥和信号量
