在我的多线程应用程序中，我看到其中存在严重的锁争用，从而阻碍了跨多个内核的良好可扩展性。我决定使用无锁编程来解决这个问题。
如何编写无锁结构？
Suma
问问题
10671 次
21 回答
45
简短的回答是：
你不能。
长答案是：
如果您问这个问题，您可能还没有足够的知识来创建无锁结构。创建无锁结构非常困难，只有该领域的专家才能做到。不要自己编写，而是搜索现有的实现。当你找到它时，检查它的使用范围有多广，它的文档记录如何，如果它被充分证明，有什么限制 - 甚至其他人发布的一些无锁结构也被破坏了。
如果您没有找到与您当前使用的结构相对应的无锁结构，请调整算法以便您可以使用一些现有的。
如果您仍然坚持创建自己的无锁结构，请务必：
- 从非常简单的事情开始
- 了解目标平台的内存模型（包括读/写重新排序约束，哪些操作是原子的）
- 研究其他人在实现无锁结构时遇到的问题
- 不要只是猜测它是否会起作用，而是要证明它
- 重度测试结果
更多阅读：
于 2008-09-18T13:36:31.990 回答
16
使用诸如Intel 的 Threading Building Blocks 之类的库，它包含相当多的无锁结构和算法。我真的不建议您尝试自己编写无锁代码，它极易出错并且很难做到正确。
于 2008-09-18T13:25:50.240 回答
12
编写线程安全的无锁代码很难；但是Herb Sutter 的这篇文章会让你开始。
于 2008-09-18T13:23:14.380 回答
12
正如sblundy指出的那样，如果所有对象都是不可变的、只读的，则您无需担心锁定，但这意味着您可能需要大量复制对象。复制通常涉及 malloc 并且 malloc 使用锁定来同步线程之间的内存分配，因此不可变对象可能比您想象的要少（malloc 本身的扩展性很差，而且 malloc 很慢；如果您在性能关键部分执行了很多 malloc，请不要不要指望有好的表现）。
当您只需要更新简单变量（例如 32 或 64 位 int 或指针），对它们执行简单的加法或减法运算或只是交换两个变量的值时，大多数平台为此提供“原子操作”（进一步 GCC 提供这些以及）。Atomic 与 thread-safe 不同。但是，原子确保，例如，如果一个线程将 64 位值写入内存位置，而另一个线程从中读取，则读取的线程要么在写操作之前或在写操作之后获取值，但绝不会出现损坏的值在写入操作之间（例如，前 32 位已经是新值，最后 32 位仍然是旧值！如果您不对此类变量使用原子访问，则可能会发生这种情况）。
但是，如果您有一个想要更新的具有 3 个值的 C 结构，即使您使用原子操作更新所有三个值，这也是三个独立的操作，因此读者可能会看到一个值已被更新而两个未更新的结构更新。如果您必须保证，在这里您将需要一个锁，读者要么看到结构中的所有值要么是旧值要么是新值。
使锁的扩展性更好的一种方法是使用 R/W 锁。在许多情况下，对数据的更新很少（写操作），但访问数据却非常频繁（读取数据），想想集合（哈希表、树）。在这种情况下，R/W 锁将为您带来巨大的性能提升，因为许多线程可以同时持有一个读锁（它们不会相互阻塞），并且只有当一个线程想要写锁时，所有其他线程在执行更新时被阻止。
避免线程问题的最佳方法是不跨线程共享任何数据。如果每个线程大部分时间都处理其他线程无法访问的数据，那么您根本不需要锁定该数据（也不需要原子操作）。所以尽量在线程之间共享尽可能少的数据。然后，如果确实需要，您只需要一种快速的方法在线程之间移动数据（ITC，线程间通信）。根据您的操作系统、平台和编程语言（不幸的是，您都没有告诉我们这些），可能存在各种强大的 ITC 方法。
最后，另一个使用共享数据但没有任何锁定的技巧是确保线程不会访问共享数据的相同部分。例如，如果两个线程共享一个数组，但一个只会访问偶数，另一个只会访问奇数索引，则不需要锁定。或者如果两者共享同一个内存块并且一个只使用它的上半部分，另一个只使用下半部分，则不需要锁定。虽然没有说这会带来良好的性能；尤其是在多核 CPU 上。一个线程对该共享数据的写入操作（运行一个内核）可能会强制为另一个线程（运行在另一个内核上）刷新缓存，并且这些缓存刷新通常是在现代多核 CPU 上运行的多线程应用程序的瓶颈。
于 2008-09-18T13:42:31.570 回答
10
正如我的教授（来自“多处理器编程艺术”的 Nir Shavit）告诉全班同学：请不要。主要原因是可测试性——你不能测试同步代码。您可以运行模拟，甚至可以进行压力测试。但它充其量只是粗略的近似。你真正需要的是数学正确性证明。很少有人能够理解它们，更不用说写它们了。因此，正如其他人所说：使用现有的库。Joe Duffy 的博客调查了一些技术（第 28 节）。您应该尝试的第一个是树拆分 - 分解为较小的任务并合并。
于 2009-04-09T08:47:46.387 回答
7
不变性是避免锁定的一种方法。请参阅Eric Lippert 对不可变堆栈和队列等事物的讨论和实现。
于 2008-09-18T13:24:32.987 回答
6
在重新。Suma 的回答，Maurice Herlithy 在多处理器编程的艺术中表明，实际上任何东西都可以在没有锁的情况下编写（参见第 6 章）。iirc，这本质上涉及将任务拆分为处理节点元素（如函数闭包），并将每个元素加入队列。线程将通过跟踪最新缓存节点中的所有节点来计算状态。显然，在最坏的情况下，这可能会导致顺序性能，但它确实具有重要的无锁属性，可以防止线程在持有锁时可能被长时间调度的情况。Herlithy 还实现了理论上的无等待性能，这意味着一个线程不会永远等待来赢得原子队列（这是很多复杂的代码）。
多线程队列/堆栈非常困难（检查ABA 问题）。其他的事情可能很简单。习惯 while(true) { atomicCAS until I swaped it } 块；他们非常强大。对 CAS 正确性的直觉可以帮助开发，尽管您应该使用良好的测试和更强大的工具（可能是SKETCH、即将推出的 MIT Kendo或spin？）来检查正确性，如果您可以将其简化为一个简单的结构。
请发布更多关于您的问题的信息。没有细节很难给出一个好的答案。
编辑不变性很好，但如果我理解正确的话，它的适用性是有限的。它并没有真正克服读后写的危险。考虑两个线程执行“mem = NewNode(mem)”；他们都可以读取内存，然后都可以写入；不适合经典的增量函数。此外，由于堆分配（必须跨线程同步），它可能很慢。
于 2009-04-09T07:50:45.277 回答
5
不变性会产生这种效果。对对象的更改会产生一个新对象。Lisp 在幕后以这种方式工作。
Effective Java的第 13 项解释了这种技术。
于 2008-09-18T13:21:51.480 回答
4
Cliff Click 利用有限状态机对无锁数据结构进行了一些主要研究，并发布了许多 Java 实现。您可以在他的博客上找到他的论文、幻灯片和实现：http: //blogs.azulsystems.com/cliff/
于 2008-09-18T13:37:33.423 回答
2
使用现有的实现，因为这个工作领域是领域专家和博士的领域（如果你想把它做好！）
例如这里有一个代码库：
于 2008-09-18T15:30:25.057 回答
1
无锁同步的基本原理是这样的：
每当您阅读结构时，您都会在阅读后进行测试，以查看自开始阅读以来结构是否发生了突变，然后重试直到您成功阅读，而在您这样做时没有其他东西出现并发生突变；
每当你改变结构时，你安排你的算法和数据，以便有一个原子步骤，如果采取这个步骤，会导致整个更改对其他线程可见，并安排事情以使任何更改都不可见，除非迈出了这一步。您可以使用平台上存在的任何无锁原子机制来执行该步骤（例如，比较和设置、加载链接+条件存储等）。在该步骤中，您必须检查自突变操作开始以来是否有任何其他线程对对象进行了突变，如果没有则提交，如果有则重新开始。
网络上有很多无锁结构的例子；在不了解您正在实施的内容以及在哪个平台上的情况下，很难更具体。
于 2008-09-18T13:28:31.497 回答
1
如果您正在为多核 cpu 编写自己的无锁数据结构，请不要忘记内存屏障！此外，考虑研究软件事务内存技术。
于 2008-09-18T15:24:40.187 回答
0
好吧，这取决于结构的类型，但是您必须制作结构，以便它可以仔细、静默地检测和处理可能的冲突。
我怀疑你可以制作一个 100% 无锁的，但同样，这取决于你需要构建什么样的结构。
您可能还需要对结构进行分片，以便多个线程处理单个项目，然后再进行同步/重组。
于 2008-09-18T13:22:27.017 回答
0
如前所述，这实际上取决于您正在谈论的结构类型。例如，您可以编写一个有限的无锁队列，但不能编写一个允许随机访问的队列。
于 2008-09-18T13:24:03.613 回答
0
减少或消除共享的可变状态。
于 2008-09-18T13:26:43.200 回答
0
在 Java 中，使用 JDK 5+ 中的 java.util.concurrent 包，而不是自己编写。如上所述，这确实是专家的领域，除非您有一两年的空闲时间，否则无法自己动手。
于 2008-09-18T14:42:38.650 回答
0
你能澄清一下你所说的结构是什么意思吗？
现在，我假设您的意思是整体架构。您可以通过不在进程之间共享内存并为您的进程使用参与者模型来实现它。
于 2008-09-18T16:06:30.180 回答
0
查看我的链接 ConcurrentLinkedHashMap，了解如何编写无锁数据结构的示例。它不是基于任何学术论文，也不需要像其他人暗示的那样需要多年的研究。它只需要仔细的工程。
我的实现确实使用了 ConcurrentHashMap，这是一个每桶锁算法，但它不依赖于该实现细节。它可以很容易地被 Cliff Click 的无锁实现所取代。我从 Cliff 那里借用了一个想法，但使用得更明确，即使用状态机对所有 CAS 操作进行建模。这极大地简化了模型，您会看到我通过 'ing 状态拥有伪锁。另一个技巧是根据需要允许懒惰和解决。通过回溯或让其他线程“帮助”清理，您会经常看到这一点。就我而言，我决定允许列表上的死节点在到达头部时被驱逐，而不是处理从列表中间删除它们的复杂性。我可以改变这一点，但我没有
“多处理器编程的艺术”一书是一本很好的入门书。不过，总的来说，我建议在应用程序代码中避免使用无锁设计。通常，在其他更不容易出错的技术更适合的情况下，这只是矫枉过正。
于 2008-09-20T02:26:12.280 回答
0
如果您看到锁争用，我会首先尝试在您的数据结构上使用更细粒度的锁，而不是完全无锁的算法。
例如，我目前正在研究多线程应用程序，它有一个自定义消息传递系统（每个线程的队列列表，队列包含线程要处理的消息）来在线程之间传递信息。这个结构有一个全局锁。就我而言，我不需要这么多的速度，所以这并不重要。但是，如果这个锁会成为一个问题，例如，它可以被每个队列上的单独锁替换。然后在特定队列中添加/删除元素不会影响其他队列。仍然会有一个用于添加新队列等的全局锁，但不会有太多的竞争。
即使是单个多生产者/消费者队列也可以在每个元素上使用粒度锁定来编写，而不是使用全局锁定。这也可以消除争用。
于 2009-04-09T08:02:17.260 回答
0
如果您阅读有关该主题的几个实现和论文，您会注意到有以下共同主题：
1)共享状态对象是 lisp/clojure 风格的不可变对象：也就是说，所有写操作都是在新对象中复制现有状态，对新对象进行修改，然后尝试更新共享状态（从对齐指针获得可以使用 CAS 原语进行更新）。换句话说，您永远不会修改可能被超过当前线程读取的现有对象。对于大而复杂的对象，可以使用 Copy-on-Write 语义来优化不变性，但那是另一棵坚果树
2）您清楚地指定当前和下一个状态之间允许的转换是有效的：然后验证算法是否有效变得容易几个数量级
3)处理每个线程的危险指针列表中丢弃的引用。引用对象安全后，尽可能重用
请参阅我的另一篇相关文章，其中一些使用信号量和互斥锁实现的代码（部分）以无锁样式重新实现： 互斥和信号量
于 2010-11-11T18:38:30.107 回答