How can I write a lock free structure?在我的多线程应用程序中，我看到其中有大量锁争用，这妨碍了跨多个内核的良好可伸缩性。我决定使用无锁编程来解决此问题。 如何编写无锁结构？ 最简单的答案是： 你不能。 长答案是： 如果您问这个问题，您可能不了解足以创建无锁结构的知识。创建无锁结构非常困难，只有该领域的专家才能做到。无需编写自己的代码，而是搜索现有的实现。当您找到它时，请检查它的使用范围，是否被很好地证明，是否得到充分证明，有什么限制-甚至其他人发表的一些无锁结构也被破坏了。 如果找不到与当前使用的结构相对应的无锁结构，请改编算法，以便可以使用一些现有的无锁结构。 如果您仍然坚持创建自己的无锁结构，请确保：
更多阅读： 在Wikipedia上免费锁定并等待免费的算法 草药销售商：无锁代码：一种错误的安全感 使用诸如Intel的Threading Building Blocks之类的库，它包含相当多的无锁结构和算法。我真的不建议您自己尝试编写无锁代码，因为它极易出错，而且很难正确设置。 编写线程安全无锁代码非常困难；但是Herb Sutter的这篇文章将帮助您入门。 正如坚定地指出的那样，如果所有对象都是不可变的，只读的，则不必担心锁定，但是，这意味着您可能不得不大量复制对象。复制通常涉及malloc，并且malloc使用锁定来同步线程之间的内存分配，因此，不可变对象可能会给您带来比您想象的要少的价格(malloc本身的伸缩性很差，malloc的速度很慢；如果您在性能关键的部分中做了很多malloc，则不要(期望效果不佳)。 当您只需要更新简单变量(例如32或64位int或指针)，对它们执行简单的加或减运算或仅交换两个变量的值时，大多数平台为此提供"原子操作" (其他GCC也提供这些功能)。原子与线程安全不同。但是，atomic确保，例如，如果一个线程将64位值写入内存位置，而另一个线程从该位置读取，则读取的线程要么在写操作之前或之后获得该值，但绝不会损坏值在写操作之间(例如，前32位已经是新值，后32位仍然是旧值！如果您不对此类变量使用原子访问，则可能发生这种情况)。 但是，如果您要更新的C结构具有3个值，即使您用原子操作更新所有3个值，这些也是3个独立的操作，因此读者可能会看到具有一个值的结构已经被更新，两个没有被更新。如果必须确保，这里将需要一个锁，读者会看到结构中的所有值都是旧值或新值。 使锁扩展更好的一种方法是使用R / W锁。在许多情况下，很少会更新数据(写操作)，但是访问数据非常频繁(读取数据)，请考虑集合(哈希表，树)。在那种情况下，R / W锁将为您带来巨大的性能提升，因为许多线程可以同时持有一个读锁(它们不会互相阻塞)，并且只有一个线程想要写锁时，其他线程才可以。执行更新时，线程被阻塞。 避免线程问题的最佳方法是不跨线程共享任何数据。如果每个线程大部分时间都处理没有其他线程可以访问的数据，则根本不需要锁定该数据(也不需要原子操作)。因此，尝试在线程之间共享尽可能少的数据。然后，如果确实需要，您仅需要一种快速的方法即可在线程之间移动数据(ITC，线程间通信)。根据您的操作系统，平台和编程语言(不幸的是，您没有告诉我们这两者)，可能存在各种强大的ITC方法。 最后，使用共享数据但没有任何锁定的另一个技巧是确保线程不会访问共享数据的相同部分。例如。如果两个线程共享一个数组，但是一个线程只能访问偶数，另一个线程只能访问奇数索引，则无需锁定。或者，如果两个都共享同一个内存块，而一个只使用了它的上半部分，另一个只使用了下一个，则无需锁定。尽管没有说，这将导致良好的性能；特别是在多核CPU上。一个线程对此共享数据的写操作(运行一个内核)可能会强制为另一个线程(在另一个内核上运行)刷新缓存，而这些缓存刷新通常是现代多核CPU上运行的多线程应用程序的瓶颈。 正如我的教授(来自"多处理器编程的艺术"的Nir Shavit)告诉班级：请不要这样做。主要原因是可测试性-您无法测试同步代码。您可以运行模拟，甚至可以进行压力测试。但这充其量只是一个大概的近似值。您真正需要的是数学正确性证明。而且几乎没有能力理解它们，更不用说编写它们了。 不可移植性是避免锁定的一种方法。请参阅Eric Lippert对不可变堆栈和队列之类的讨论和实现。 在重新。苏门答(Suma)的答案，莫里斯·赫利斯蒂(Maurice Herlithy)在《多处理器编程的艺术》中指出，实际上任何东西都可以不用锁来编写(请参阅第6章)。 iirc，这实际上涉及将任务拆分为处理节点元素(如函数闭包)，并将每个元素排队。线程将通过跟踪最新缓存的节点中的所有节点来计算状态。显然，在最坏的情况下，这可能会导致顺序性能，但它确实具有重要的无锁属性，从而防止了线程在持有锁时可能被安排较长时间的情况。 Herlithy还实现了理论上的免等待性能，这意味着一个线程将永远不会永远等待赢得原子队列(这是很多复杂的代码)。 多线程队列/堆栈异常困难(请检查ABA问题)。其他事情可能很简单。习惯了while(true){atomicCAS，直到我交换了它}块；他们非常强大。尽管您应该使用良好的测试以及更强大的工具(例如SKETCH，即将推出的MIT Kendo或spin？)来检查正确性，如果可以将其简化为一个简单的结构，那么对CAS正确的直觉可以帮助开发。 请发布更多有关您的问题的信息。没有细节很难给出一个很好的答案。 编辑不变性很好，但是如果我理解正确的话，它的适用性是有限的。它并不能真正克服读后写的危害。考虑两个执行" mem = NewNode(mem)"的线程；他们都可以读记忆，然后都可以写。对于经典的增量函数而言不正确。另外，由于堆分配(必须在线程之间同步)，它可能很慢。 不变性将具有此效果。对对象的更改将产生一个新对象。 Lisp在后台运行。 有效Java的项目13解释了此技术。 Cliff Click通过利用有限状态机对无锁数据结构进行了一些重大研究，并且还发布了许多Java实现。您可以在他的博客中找到他的论文，幻灯片和实现：http://blogs.azulsystems.com/cliff/ 使用现有的实现，因为这是领域专家和博士学位的领域(如果您想做对的话！) 例如，这里有一个代码库： http://www.cl.cam.ac.uk/research/srg/netos/lock-free/ 大多数无锁算法或结构都以某种原子操作开始，即对某个内存位置的更改，一旦某个线程开始，它将在其他线程无法执行相同操作之前完成。您的环境中有这种操作吗？ 有关此主题的规范论文，请参见此处。 也可以尝试访问此Wikipedia文章，以获取更多想法和链接。 如果您要为多核cpu编写自己的无锁数据结构，请不要忘记内存障碍！另外，请考虑研究软件事务存储技术。 无锁同步的基本原理是：
网络上有许多无锁结构的示例；不了解您正在执行的内容以及在哪个平台上执行操作，就很难更加具体。 看看我的链接ConcurrentLinkedHashMap，以获取有关如何编写无锁数据结构的示例。它不基于任何学术论文，并且不需要其他人暗示的多年研究。它只需要仔细的工程。 我的实现确实使用了ConcurrentHashMap，这是一个"每桶锁"算法，但它不依赖于该实现细节。可以轻松地用Cliff Click的无锁实现方式替换它。我从Cliff借来了一个想法，但更明确地使用了一个想法，即用状态机对所有CAS操作进行建模。这会大大简化模型，因为您会看到我通过\\'ing状态拥有伪锁。另一个技巧是允许懒惰并根据需要解决。通过回溯或让其他线程"帮助"进行清理，您会经常看到这种情况。就我而言，我决定允许列表中的死节点到达头时将其驱逐，而不是处理将它们从列表中间删除的复杂性。我可能会更改它，但是我并不完全相信我的回溯算法，而是希望推迟进行重大更改，例如采用3节点锁定方法。 《多处理器编程的艺术》一书是一本很好的入门书。总体而言，我建议避免在应用程序代码中使用无锁设计。通常，在其他更不易出错的技术更适合的情况下，这只是简单的矫kill过正。 如果您阅读了有关该主题的几种实现和论文，您会发现存在以下共同主题： 1)共享状态对象是lisp / clojure风格的不可变的：也就是说，所有写操作都是通过复制新对象中的现有状态，对新对象进行修改然后尝试更新共享状态来实现的(从可以使用CAS原语更新的对齐的指针)。换句话说，您永远都不能修改一个可能被当前线程读取的现有对象。可以使用写时复制语义为大型，复杂的对象优化不变性，但这就是另一棵坚果树 2)您明确指定当前状态和下一个状态之间允许的哪些过渡有效：然后验证算法有效将变得容易几个数量级 3)处理每个线程的危险指针列表中的废弃引用。参考对象安全后，请尽可能重复使用 请参阅我的另一篇相关文章，其中使用信号量和互斥体实现的一些代码(部分)以无锁样式重新实现： 在Java中，请使用JDK 5中的java.util.concurrent软件包，而不要编写自己的软件包。如上所述，这实际上是专家的一个领域，除非您有一两年的空闲时间，否则自己滚动是不可行的。 减少或消除共享的可变状态。 如果看到锁争用，我将首先尝试在数据结构上使用更多的粒度锁，而不是完全不使用锁的算法。 例如，我目前在多线程应用程序上工作，该应用程序具有自定义消息传递系统(每个线程的队列列表，该队列包含要处理的线程的消息)以在线程之间传递信息。在此结构上有全局锁定。就我而言，我并不需要那么快，所以并不重要。但是，如果此锁成为问题，则可以例如在每个队列中将其替换为单独的锁。然后在特定队列中添加元素或从中删除元素不会影响其他队列。仍然存在用于添加新队列等的全局锁，但是并没有那么大的争议。 即使是单个多产品/消费者队列，也可以在每个元素上进行粒度锁定而不是全局锁定。这也可以消除争用。 如前所述，这实际上取决于您所讨论的结构类型。例如，您可以编写一个有限的无锁队列，但不能编写一个允许随机访问的队列。 您能否阐明结构的含义？ 现在，我假设您是指总体体系结构。您可以通过不共享进程之间的内存，或者对进程使用参与者模型来实现它。 好吧，这取决于结构的类型，但是您必须对结构进行精心设计，以使其能够仔细无声地检测并处理可能的冲突。 我怀疑您可以制造出一种100％无锁的设备，但同样，这取决于您需要构建哪种结构。 您可能还需要分片结构，以便多个线程可以处理单个项目，然后再进行同步/重组。 |
