无等待和无锁算法的示例/说明

Question

我已经读过等待使得所有线程独立完成并且无锁可确保程序整体完成.我不太明白.任何人都可以举一个例子(java)来说明这一点.

编辑:无锁意味着没有死锁的程序？

Answer 1

如果一个程序是无锁的,它基本上意味着它的至少一个线程可以保证在任意时间段内取得进展.如果一个程序死锁,它的所有线程(以及整个程序)都无法取得进展 - 我们可以说它不是无锁的.由于无锁程序可以保证取得进展,因此可以保证它们完成(假设有限执行没有例外).

无等待是一个更强的条件,这意味着无论线程执行的时间/顺序如何,每个线程都可以保证在任意时间段内取得进展; 所以我们可以说线程是独立完成的.所有等待免程的程序都是无锁的.

我不知道任何说明这一点的Java示例,但我可以告诉你,无锁/无等待程序通常在没有锁的情况下使用CAS指令等低级原语实现.

我们应该清楚术语; 锁定免费并不意味着死锁,这是使用无锁算法的一个副作用...我认为这个术语更多的是关于不使用互斥锁来实现共享资源之间的同步化(这是Nathan在谈到的时候提到的CAS说明). (4认同)

Answer 2

号Lock-free是指没有锁的程序; 顺便说一句,wait-free算法也是lock-free,但反之亦然.因此,两者都是非阻塞算法.

这个wiki条目是理解无锁和无等待机制的绝佳读物.

嗯,java.util.concurrent.atomic包是lock-free单个变量编程的一个例子.在Java 7中ConcurrentLinkedQueue是一个wait-free实现的例子.

为了进一步了解,我希望您阅读本文,由Brian Goetz撰写的" Going atomic" - 在实践中编写Java Concurrency的人.

奇怪的是，虽然 ConcurrentLinkedQueue 在 Java 7 中确实被描述为“无等待”实现，但在 Java 8 中，该描述更改为不太严格的“非阻塞”（该描述一直保留到 Java 13，即当前版本）此评论）：https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html 我想知道发生了什么变化？ (2认同)
@AdeelAnsari 无锁并不意味着“没有锁”。这通常称为无锁。 (2认同)