Clojure使用无锁算法实现了无锁特性吗？

Question

我正在进行Clojure的学习之旅（已经在4clojure.com上解决了大约80个问题），一直在阅读、编码和尝试“理解它”。

现在，我有点困惑于Clojure被设计为“无锁并发”。我对死锁非常了解（例如：“我曾编写过不良Java代码导致死锁”，而不是“我是并发方面的专家”）。我也读过这篇文章：

为什么“无锁并发”在Clojure中如此重要？

我意识到Clojure程序不会出现死锁的好处。

但我有点困惑：这种成就是通过实现底层的无锁算法实现的，还是可能使用了“可以发生死锁”的算法，但是使用正确的实现保证永远不会死锁（这种方式对Clojure程序员来说似乎是“隐藏的”）？

最近在 hacker news 上讨论了无锁算法：

http://news.ycombinator.com/item?id=4103921

引用了 "Lock-free algorithms" 页面上的 1024cores.net：

http://www.1024cores.net/home/lock-free-algorithms

我不理解这篇文章与Clojure下并发工作的关系。

这让我非常困惑：当我在Clojure中开发并发程序时，这是否意味着“锁和无锁算法”对我来说是不重要的？

- Cedric Martin

---

同时，“lock-free”和“lockless”标签都没有维基页面。它们是同义词吗？这两个标签应该合并还是它们代表着不同的东西？ - Cedric Martin

Clojure有深刻的概念，这些概念非常不寻常，以至于仅仅通过学习语法和解决难题是几乎不可能“理解”它们的。如果你的目标是“真正理解Clojure”，那么我建议你阅读一本好的Clojure书籍。亚马逊上大约有5本这样的书。然后我保证你能够回答自己的问题。 - Dimagog

@Dmitry Kakurin：我看得出你是新来的。你的评论表明你不了解SO的工作方式。SO是一个提问的地方，就像这个问题获得了8个赞和3个收藏一样。SO不是一个你可以高高在上、对正在通过解决难题学习新语言的人们进行指责的地方，告诉他们他们不会“懂”，并且应该阅读书籍来回答自己的问题，而不是在SO上提问。现在，如果你“真的想了解StackOverflow”，我建议你阅读SO FAQ ;) - Cedric Martin

@Dmitry Kakurin：关于SO的工作方式，我给你一个提示：它是通过人们的参与来运作的。看看我的问题和两个很棒的答案：谁为SO带来了更多的价值？是我提出这个问题和那两个伟大的回答者，还是你用轻蔑的评论贬低我和我的解谜活动呢？ - Cedric Martin

你的激烈反应是毫无预兆和无端的。但最重要的是，你没有理解我的观点：如果你的目标是熟悉这门语言，那么你现在所做的是可以的（我绝不会贬低你的努力）。然而，如果你想真正理解Clojure与其他许多语言在概念上的区别，那么阅读一本好书是正确的方法，而解决谜题很难帮助你达到这个目标。再次强调，请把我的评论看作是基于经验的建议，而不是攻击。然后请随意忽略它。 - Dimagog

Answer 1

一般来说，Clojure通过正确处理时间避免了锁问题。在许多系统中，对象的时间是一个非常宽松的概念，因为在时间-1（更新之前），对象被编辑以成为时间-2（更新后）的对象，在此过程中，它既不是第一也不是第二，因此我们使用锁来确保它只在此转换之前或之后可见。协调锁从此而来，死锁从那里而来...

这是算法、数据结构和时间的组合。

Clojure通过组合不可变数据结构、函数式编程和协调时间模型（refs、atoms、agents等）来实现这一点。在这个模型中，一个函数接受某物并生成它的下一个版本，同时保存过去，只要有人在看它（直到垃圾收集器到达它）。

• 不可变数据结构：Clojure的集合在FP意义上是持久的。新版本制作后，旧副本“持久”存在。这样观察者无需锁定对象，因为它们永远不会在其下更改。可能会存在基于他们正在查看的版本的新版本，但没有任何东西会更改他们的副本。

• 函数式编程：纯函数（或尽可能接近）在不共享其内部状态的情况下，将一组集合在一个时间点上并生成下一个版本，因此不需要锁定。这也有许多其他好处。

• 协调时间：当多个对象需要协调时（如任何有趣的系统），则Clojure的时间模型就会发挥作用。不同的机制用于不同的目的。它具有一个锁，用于计算时间增量，以便恰好有一个时间零、一个时间一和一个时间N。因此它不是严格无锁的。STM包含您几乎永远不需要交互的锁

---

*嗯...几乎从不需要;-)

- Arthur Ulfeldt

Answer 2

如果你在Clojure源代码中查找，特别是.java文件中，你会发现有很多对java.util.concurrent包的引用。java.util.concurrent包是Doug Lea在SUNY Oswego数十年关于并发性方面研究的结晶。具体而言，有关原子变量类（例如AtomicReference）的引用允许访问“比较和交换”（也称为“比较和设置”或CAS）指令instruction。CAS指令有点难以解释（我在下面提供了一个参考），但正确使用CAS是算法实现“无锁”（至少在Java世界中）所必需的核心。无锁算法最终导致高并发应用程序的更高吞吐量和更少争用；这正是Clojure所针对的领域。

要深入了解这个主题，请阅读Brian Goetz的Java Concurrency in Practice。此外，还可以查看该作者的article。

作为一个旁注，我一直觉得直接使用java.util.concurrent包很困难，即使它在发展中。对我来说，它感觉太底层了。Clojure的美妙之处在于它通过非常易于使用的软件事务内存（STM）抽象提供对这个专家并发库的访问。这真的是非常了不起的成就。

- Julien Chastang