在我的多线程应用程序中，我看到其中有大量锁争用，从而阻止了跨多个内核的良好可伸缩性。我决定使用无锁编程来解决此问题。

如何编写无锁结构？

解决方案

不变性将产生这种影响。对对象的更改将产生一个新对象。 Lisp在后台进行这种工作。

有效Java的第13项解释了此技术。

嗯，这取决于结构的类型，但是我们必须对结构进行精心设计，以使其能够仔细无声地检测和处理可能的冲突。

我怀疑我们能否制造出100％无锁的设备，但是同样，这取决于我们需要构建哪种类型的结构。

我们可能还需要分片结构，以便多个线程可以处理单个项目，然后再进行同步/重组。

编写线程安全的无锁代码很难。但是Herb Sutter的这篇文章将入门。

如前所述，它实际上取决于我们所讨论的结构类型。例如，我们可以编写一个有限的无锁队列，但不能编写一个允许随机访问的队列。

不变性是避免锁定的一种方法。请参阅Eric Lippert对不可变堆栈和队列之类的讨论和实现。

使用诸如英特尔线程构建模块之类的库，它包含相当多的无锁结构和算法。我真的不建议我们自己尝试编写无锁代码，因为它极易出错，而且很难正确执行。

减少或者消除共享的可变状态。

无锁同步的基本原理是：

• 每当我们读取结构时，我们都要在读取之后进行测试，以检查自从开始读取以来结构是否发生了变异，然后重试直到成功读取为止，同时不会出现其他变化。
• 每当更改结构时，都要安排算法和数据，以便有一个原子步骤，如果采取这一步骤，则整个更改对其他线程都是可见的，并且安排事物以使所有更改都不可见，除非采取了这一步骤。对于该步骤，我们可以使用平台上存在的任何无锁原子机制(例如，比较设置，加载链接+存储条件等)。然后，在那一步中，我们必须检查自变异操作开始以来是否有其他线程对对象进行了变异，如果没有，则提交，如果已经，则重新开始。

网上有很多无锁结构的例子。在不了解更多信息的情况下，很难具体说明。

大多数无锁算法或者结构都以某种原子操作开始，即，对某个内存位置的更改，一旦某个线程开始，它将在其他线程无法执行相同操作之前完成。环境中是否有这样的操作？

有关此主题的规范论文，请参见此处。

另外，请尝试这篇Wikipedia文章，以获取更多想法和链接。

简短的答案是：

你不能。

长答案是：

如果我们在问这个问题，我们可能不了解足以创建无锁结构的知识。创建无锁结构非常困难，只有该领域的专家才能做到。无需编写自己的代码，而是搜索现有的实现。当我们找到它时，检查它的使用范围，记录的程度，是否得到充分证明，甚至其他人发布的一些无锁结构都受到了哪些限制。

如果找不到与我们当前使用的结构相对应的无锁结构，请改编该算法，以便可以使用一些现有的结构。

如果我们仍然坚持创建自己的无锁结构，请确保：

• 从非常简单的事情开始
• 了解目标平台的内存模型(包括读/写重排序约束，哪些操作是原子操作)
• 研究很多其他人在实现无锁结构时遇到的问题
• 不要只是猜测它是否会工作，就证明它
• 大量测试结果

更多阅读：

在Wikipedia上锁定免费和等待免费的算法

Herb Sutter：无锁代码：一种错误的安全感

Cliff Click通过利用有限状态机对无锁数据结构进行了一些重大研究，并且还发布了许多Java实现。我们可以在他的博客中找到他的论文，幻灯片和实现：http://blogs.azulsystems.com/cliff/

正如斯布隆迪指出的那样，如果所有对象都是不可变的，只读的，则不必担心锁定，但是，这意味着我们可能不得不大量复制对象。复制通常涉及malloc，并且malloc使用锁定来同步线程之间的内存分配，因此，不可变对象可能会给我们带来比我们想象的要少的价格(malloc本身伸缩性很差，malloc速度很慢；如果我们在性能关键的部分中做了很多malloc，则不要不要指望好的性能)。

当我们只需要更新简单变量(例如32或者64位int或者指针)，对它们执行简单的加减运算或者仅交换两个变量的值时，大多数平台为此提供"原子操作"(进一步的GCC提供了以及)。原子与线程安全不同。但是，atomic确保，例如，如果一个线程将64位值写入内存位置，而另一个线程从该位置读取，则读取的线程或者在写操作之前或者之后获得该值，但绝不会损坏值在写操作之间(例如，前32位已经是新值，后32位仍然是旧值！如果我们不对此类变量使用原子访问，则可能会发生这种情况)。

但是，如果我们有一个带有3个值的C结构要更新，即使我们用原子操作更新所有3个，这些都是3个独立的操作，因此读者可能会看到结构中一个值已经被更新而两个值未被更新更新。如果必须确保，这里将需要一个锁，读者会看到结构中的所有值都是旧值或者新值。

使锁扩展更好的一种方法是使用R / W锁。在许多情况下，很少更新数据(写操作)，但是访问数据非常频繁(读取数据)，请考虑集合(哈希表，树)。在这种情况下，R / W锁将为我们带来巨大的性能提升，因为许多线程可以同时持有一个读锁(它们不会互相阻塞)，并且只有一个线程想要写锁时，其他所有线程在执行更新时被阻止。

避免线程问题的最好方法是不跨线程共享任何数据。如果每个线程大部分时间都处理其他线程无法访问的数据，则根本不需要锁定该数据(也不需要原子操作)。因此，尝试在线程之间共享尽可能少的数据。然后，如果确实需要，我们仅需要一种快速的方法即可在线程之间移动数据(ITC，线程间通信)。根据操作系统，平台和编程语言(不幸的是，我们没有告诉我们这两者)，可能存在各种强大的ITC方法。

最后，使用共享数据但没有任何锁定的另一个技巧是确保线程不会访问共享数据的相同部分。例如。如果两个线程共享一个数组，但是一个线程只能访问偶数，另一个线程只能访问奇数索引，则无需锁定。或者，如果两个都共享同一个内存块，而一个只使用了它的上半部分，另一个只使用了下一个，则无需锁定。尽管没有说，这将导致良好的性能。特别是在多核CPU上。一个线程对此共享数据的写操作(运行一个内核)可能会强制为另一个线程(在另一个内核上运行)刷新缓存，而这些缓存刷新通常是现代多核CPU上运行的多线程应用程序的瓶颈。

在Java中，请使用JDK 5+中的java.util.concurrent软件包，而不要编写自己的软件包。如上所述，这确实是专家的领域，除非我们有一两年的空余时间，否则自己滚动是不可行的。

如果我们正在为多核cpu编写自己的无锁数据结构，请不要忘记内存障碍！另外，考虑研究软件事务存储技术。

使用现有的实现，因为这是领域专家和博士学位的领域(如果我们想做得对！)

例如，这里有一个代码库：

http://www.cl.cam.ac.uk/research/srg/netos/lock-free/

我们能说明一下结构的意思吗？

现在，我假设我们是指总体体系结构。我们可以通过不共享进程之间的内存，或者通过为进程使用参与者模型来实现。

看一下我的链接ConcurrentLinkedHashMap，以获取有关如何编写无锁数据结构的示例。它不基于任何学术论文，并且不需要其他人暗示的多年研究。它只需要仔细的工程。

我的实现确实使用了ConcurrentHashMap，这是一个"每桶锁定"算法，但它不依赖于该实现细节。可以用Cliff Click的无锁实现轻松替换它。我从Cliff借来了一个想法，但更明确地使用了一个想法，即用状态机对所有CAS操作进行建模。这将大大简化模型，因为我们会看到我通过'ing状态具有伪锁。另一个技巧是允许懒惰并根据需要解决。通过回溯或者让其他线程"帮助"进行清理，我们会经常看到这种情况。就我而言，我决定允许列表中的死节点到达头时将其驱逐，而不是处理将它们从列表中间删除的复杂性。我可能会更改，但是我并不完全相信我的回溯算法，而是希望推迟进行重大更改，例如采用3节点锁定方法。

《多处理器编程的艺术》一书是一本很好的入门书。但是总的来说，我建议避免在应用程序代码中使用无锁设计。通常，在其他更不易出错的技术更适合的情况下，这简直是矫kill过正。

在重新。苏马(Suma)的答案，莫里斯·赫利西(Maurice Herlithy)在《多处理器编程的艺术》中指出，实际上任何东西都可以不用锁来编写(请参阅第6章)。 iirc，这实际上涉及将任务拆分为处理节点元素(如函数闭包)，并将每个元素排队。线程将通过跟踪最新缓存的节点中的所有节点来计算状态。显然，在最坏的情况下，这可能会导致顺序性能，但是它确实具有重要的无锁属性，从而防止了线程在持有锁时可能被安排较长时间的情况。 Herlithy还实现了理论上的免等待性能，这意味着一个线程将不会永远等待以赢得原子队列(这是很多复杂的代码)。

多线程队列/堆栈异常困难(请检查ABA问题)。其他事情可能很简单。习惯了while(true){atomicCAS，直到我交换了它}块；他们非常强大。尽管我们应该使用良好的测试以及更强大的工具(例如SKETCH，即将推出的MIT Kendo或者spin？)来检查正确性，如果可以将其简化为一个简单的结构，那么对CAS正确的直觉可以帮助开发。

请发布有关问题的更多信息。没有细节很难给出一个很好的答案。

编辑不变性很好，但如果我理解正确的话，它的适用性是有限的。它并不能真正克服读后写的危害。考虑两个执行" mem = NewNode(mem)"的线程；他们都可以读记忆，然后都可以写记忆；对于经典的增量函数而言不正确。另外，由于堆分配(必须在线程之间同步)，它可能很慢。

如果看到锁争用，我将首先尝试在数据结构上使用更精细的锁，而不是完全不使用锁的算法。

例如，我目前在多线程应用程序上工作，该应用程序具有一个自定义消息传递系统(每个线程的队列列表，该队列包含要处理的线程的消息)，以便在线程之间传递信息。在此结构上有全局锁定。就我而言，我并不需要那么快，所以这并不重要。但是，如果此锁成为问题，则可以用每个队列中的单个锁代替。然后向/从特定队列添加/删除元素不会影响其他队列。仍然存在用于添加新队列之类的全局锁，但是并没有那么多争执。

即使是单个多产品/消费者队列，也可以在每个元素上进行粒度锁定，而不用全局锁定。这也可以消除竞争。

正如我的教授("多处理器编程的艺术"中的Nir Shavit)告诉班级：请不要。主要原因是可测试性，我们无法测试同步代码。我们可以运行模拟，甚至可以进行压力测试。但这充其量只是一个大概的近似值。我们真正需要的是数学正确性证明。几乎没有能力理解它们，更不用说编写它们了。
因此，正如其他人所说：使用现有的库。 Joe Duffy的博客调查了一些技术(第28节)。我们应该尝试的第一个方法是将树拆分为较小的任务并合并。

如果我们阅读了有关该主题的几种实现和论文，我们会发现存在以下共同主题：

1)共享状态对象是Lisp / clojure风格的不可变的：也就是说，所有写操作都是通过复制新对象中的现有状态，对新对象进行修改然后尝试更新共享状态(从对齐的指针获得)来实现的。可以使用CAS原语进行更新)。换句话说，我们永远都不能修改一个可能被当前线程读取之外的现有对象。对于大型，复杂的对象，可以使用"写时复制"语义来优化不可变性，但这就是另一棵胡扯

2)我们清楚地指定当前状态和下一个状态之间允许的哪些过渡有效：然后验证算法有效将变得容易几个数量级

3)处理每个线程的危险指针列表中的废弃引用。参考对象安全后，请尽可能重复使用

请参阅我的另一篇相关文章，其中使用信号量和互斥体实现的一些代码(部分)以无锁样式重新实现：
互斥和信号量