我怎样才能写一个无锁结构？
在我的multithreading应用程序中，我看到了严重的锁争用，阻止了多核心之间的良好可伸缩性。 我决定使用无锁编程来解决这个问题。
我怎样才能写一个无锁结构？
简短的回答是：
你不能。
长的答案是：
如果你问这个问题，你可能不知道能够创build一个无锁结构。 创build无锁结构非常困难，只有这个领域的专家才能做到这一点。 search现有的实现，而不是编写自己的。 当你find它的时候，检查它的使用范围，使用的程度，logging的程度，是否被certificate有效，有什么限制 – 甚至一些其他人发布的无锁结构也被破坏了。
如果您没有find与当前使用的结构相对应的无锁结构，请调整algorithm，以便可以使用现有结构。
如果您仍然坚持创build自己的无锁结构，请务必：
- 从非常简单的事情开始
- 理解你的目标平台的内存模型（包括读/写重排约束，什么操作是primefaces的）
- 研究其他人在实现无锁结构时遇到的问题
- 不要只是猜测它是否会起作用，certificate它
- 严重testing结果
更多阅读：
在维基百科locking免费并等待免费algorithm
香草萨特：无锁密码：安全的错误意识
使用像英特尔线程构build模块这样的库，它包含了不less无锁结构和algorithm。 我真的不会推荐你自己编写无锁代码，这是非常容易出错，很难得到正确的。
编写线程安全的无锁代码很难; 但是这个来自Herb Sutter的文章会让你开始。
正如sblundy所指出的，如果所有的对象都是不可变的，只读的，你不需要担心locking，但是，这意味着你可能不得不复制对象。 复制通常涉及malloc和malloc使用locking跨线程同步内存分配，所以不可变的对象可能会比你想象的less买你（malloc本身扩展比较差，malloc是慢的 ;如果你在性能关键部分做了很多malloc，不要期待好的performance）。
当你只需要更新简单的variables（例如32或者64位的int或者指针）时，只需要对它们进行加或减运算，或者只是交换两个variables的值，大多数平台都提供了“primefaces操作”以及）。 primefaces不是一样的线程安全 。 但是，primefaces可以确保，如果一个线程向内存位置写入一个64位值，而另一个线程从中读取，则读取操作在写入操作之前或写入操作之后获取值，但不会有损坏的值在写入操作之间（例如，前32位已经是新的，最后的32位仍然是旧的值！如果你不使用primefaces访问这个variables）。
然而，如果你有一个C结构，它有三个值，即使你用三个独立的操作来更新所有这三个值，那么读者可能会看到一个值已经更新的结构，两个不是更新。 在这里，如果您必须保证，您将需要一个锁，读者可以看到结构中的所有值都是旧值或新值。
一种使locking更好的方法是使用R / W锁。 在很多情况下，更新数据是很less见的（写入操作），但访问数据非常频繁（读取数据），考虑集合（哈希表，树）。 在这种情况下，R / W锁会给你带来巨大的性能提升，因为许multithreading可以同时持有一个读锁（它们不会相互阻塞），只有当一个线程想要写锁时，所有其他线程在执行更新时被阻塞。
避免线程问题的最好方法是不跨线程共享任何数据。 如果每个线程大多数时间处理其他线程无法访问的数据，则根本不需要locking该数据（也不需要primefaces操作）。 所以尽量在线程之间分享尽可能less的数据。 那么，如果您真的需要（ITC，线程间通信），则只需要一种在线程间快速移动数据的方法。 根据您的操作系统，平台和编程语言（不幸的是，您不告诉我们这些），可能存在各种强大的ITC方法。
最后，处理共享数据但是没有任何locking的另一个技巧是确保线程不访问共享数据的相同部分。 例如，如果两个线程共享一个数组，但是只能访问偶数，另一个只有奇数索引，则不需要locking。 或者，如果两个共享同一个内存块，一个只使用其上半部分，另一个只有下一个，则不需要locking。 虽然没有说，这会导致良好的performance; 特别是在多核CPU上。 将一个线程写入此共享数据（运行一个内核）可能会强制高速caching刷新另一个线程（在另一个内核上运行），这些高速caching刷新通常是在现代多核CPU上运行的multithreading应用程序的瓶颈。
正如我的教授（来自“多处理器编程艺术”的Nir Shavit）告诉全class：请不要。 主要原因是可testing性 – 您不能testing同步代码。 你可以运行模拟，你甚至可以压力testing。 但最好是粗略的近似。 你真正需要的是math正确性certificate。 很less有人能够理解它们，更不用说写它们了。 所以，正如其他人所说：使用现有的库。 Joe Duffy的博客调查了一些技巧（第28节）。 你应该尝试的第一个是树分裂 – 分解成更小的任务和结合。
不变性是避免locking的一种方法。 请参阅Eric Lippert关于不可变堆栈和队列的讨论和实现。
在重新。 Suma的回答，Maurice Herlithy在“多处理器编程艺术”中表示，实际上任何东西都可以在没有锁的情况下编写（见第6章）。 iirc，这基本上涉及将任务分解成处理节点元素（如函数闭包），并将每个元素排入队列。 线程将通过关注最新caching的所有节点来计算状态。 显然，这可能在最坏的情况下导致顺序性能，但是它确实具有重要的无锁特性，从而避免了线程在持有锁的情况下长时间排队的情况。 Herlithy也实现了理论上的免等待performance，意味着一个线程不会永远等待赢得primefaces入队（这是很多复杂的代码）。
一个multithreading队列/堆栈是非常困难的（检查ABA问题 ）。 其他的事情可能很简单。 习惯了while（true）{atomicCAS直到我换了它}块; 他们是非常强大的。 CAS的正确直觉可以帮助开发，尽pipe你应该使用好的testing和更强大的工具（也许SKETCH ，即将到来的MIT Kendo ，或者旋转 ？）来检查正确性，如果你能把它简化成一个简单的结构。
请发布更多关于您的问题。 没有细节就很难给出好的答案。
编辑 immutibility是好的，但它的适用性是有限的，如果我正确的理解。 它并没有真正克服“读后危害”。 考虑执行“mem = NewNode（mem）”的两个线程; 他们都可以读取mem，然后都写入; 不是一个经典增量函数的正确。 另外，由于堆分配（它必须跨线程同步），可能会很慢。
置身性将会产生这种效果。 对该对象的更改会生成一个新对象。 Lisp以这种方式工作。
Effective Java的第13项解释了这种技术。
Cliff Click利用有限状态机展开了关于无锁数据结构的一些主要研究，并为Java提出了许多实现。 你可以在他的博客上find他的论文，幻灯片和实现： http : //blogs.azulsystems.com/cliff/
使用现有的实现，因为这个领域的工作是领域专家和博士的领域（如果你想要它做对了！）
例如，这里有一个代码库：
大多数无锁algorithm或结构都是以一些primefaces操作开始的，也就是说，一旦某个线程开始执行某个内存位置的更改，将会在任何其他线程执行相同的操作之前完成。 你的环境中有这样的操作吗？
关于这个问题的规范文件见这里 。
也请尝试这个维基百科文章文章进一步的想法和链接。
无锁同步的基本原理是这样的：
-
每当你阅读结构时，你都要按照阅读的顺序进行testing，看看结构在开始阅读之后是否发生了变化，然后重试，直到阅读成功，而没有别的事情发生，并且在你这样做的时候变异。
-
无论何时你改变结构，你都要安排你的algorithm和数据，以便有一个单独的primefaces步骤，如果这个primefaces步骤使整个变化变得对其他线程可见，并且排列这些变化，除非可见该步骤被采取。 你可以在你的平台上使用任何lockfreeprimefaces机制（例如比较和设置，加载链接+存储条件等）。 在这个步骤中，你必须检查是否有其他线程在变异操作开始后已经突变了对象，如果没有则提交，如果有，则重新开始。
networking上有很多无锁结构的例子。 不知道你正在执行什么，在什么平台上更难以更具体。
如果你正在编写自己的多核cpu的无锁数据结构，不要忘记内存障碍！ 另外，考虑到软件事务内存技术。
如果看到锁争用，我会首先尝试在数据结构上使用更多的粒度锁，而不是完全无锁的algorithm。
例如，我目前正在使用multithreading应用程序，该应用程序具有自定义消息传递系统（每个线程的队列列表，该队列包含要处理线程的消息）以在线程之间传递信息。 这个结构有一个全局locking。 就我而言，我不需要太多的速度，所以这并不重要。 但是，如果这个锁会成为一个问题，例如，它可能会被每个队列中的单个锁取代。 然后，将元素添加到/从特定队列中移除将不会影响其他队列。 仍然会有一个全局的锁，用于添加新的队列等，但不会有太多争议。
即使是单个多产品/消费者队列，也可以使用每个元素的粒度locking来写入，而不是使用全局locking。 这也可以消除争用。
那么，这取决于结构的types，但是你必须使结构，以便它仔细，默默地检测和处理可能的冲突。
我怀疑你可以做一个100％无锁的，但是这又取决于你需要build立什么样的结构。
您可能还需要对结构进行分片，以便多个线程在各个项目上工作，然后再进行同步/重组。
如上所述，这实际上取决于你在谈论什么types的结构。 例如，你可以写一个有限的无锁队列，但不能允许随机访问。
减less或消除共享的可变状态。
在Java中，使用JDK 5+中的java.util.concurrent包而不是编写自己的包。 正如上面提到的，这对于专家来说确实是一个领域，除非你有一两年的闲暇时间，否则你自己的做法是不可行的。
你能澄清一下你的意思吗？
现在，我假设你的意思是整体架构。 您可以通过不在进程之间共享内存并通过使用进程的参与者模型来实现它。
看看我的链接ConcurrentLinkedHashMap ，了解如何编写一个无锁数据结构的例子。 它不是基于任何学术论文，也不需要像其他人那样进行多年的研究。 它只需要仔细的工程。
我的实现使用ConcurrentHashMap，它是一个每桶lockingalgorithm，但不依赖于实现细节。 它可以很容易地被replace成Cliff Click的无锁实现。 我借用了Cliff的一个想法，但是更明确地使用了一个状态机来模拟所有的CAS操作。 这大大简化了模型，你会看到我通过'ing状态来伪装锁。 另一个诀窍是允许懒惰和需要解决。 你会经常看到这回溯或让其他线程“帮助”清理。 就我而言，我决定让列表中的死亡节点在到达首位时被驱逐，而不是处理从列表中间移除它们的复杂性。 我可能会改变这种情况，但是我并不完全相信我的回溯algorithm，并且想要推迟采用3节点locking方法等重大改变。
这本书“多处理器编程的艺术”是一个很好的入门书。 总的来说，尽pipe如此，我build议避免应用程序代码中的无锁devise。 通常情况下，其他更不容易出错的技术更适合。
如果你阅读了几个有关这个主题的实现和论文，你会注意到有一个共同的主题：
1） 共享状态对象是lisp / clojure样式不可变的 ：也就是说，所有的写操作都是在新对象中拷贝现有状态，修改新对象，然后尝试更新共享状态（从一个alignment的指针可以用CAS原语更新）。 换句话说，永远不要修改比当前线程更多的现有对象。 对于大的，复杂的对象，可以使用写时复制语义来优化可置换性，但这又是另一个坚果树
2） 你明确指定允许的当前状态和下一个状态之间的转换是有效的 ：然后validationalgorithm是有效的，
3） 在每个线程的危险指针列表中处理丢弃的引用 。 引用对象安全后，如果可能的话重用
请参阅我的另一个相关post，其中一些使用信号量和互斥体实现的代码（部分）以无锁方式重新实现： 相互排斥和信号量
