Is Clojure lockfree by using lockfree algorithms?

Question

I'm progressing in my Clojure quest (about 80 problems solved on 4clojure.com) and I keep on reading and coding and trying to "get it".

Now I'm a bit confused by Clojure being designed for "lockless concurrency". I know all too well about deadlocks (as in: "I've written poor Java code that ended up in deadlocks", not as in "I'm in expert in concurrency"). I've also read this:

Why is lockless concurrency such a big deal (in Clojure)?

I realize how great it is that Clojure programs cannot deadlock.

But I'm a bit confused: is such a feat achieved by implementing under the hood lockfree algorithms or are there potentially "deadlockable" algorithms used, but using a correct implementation guaranteed never to deadlock (that would somehow be "hidden" to Clojure programmers)?

There's been a recent discussion on hacker news about lockfree algorithms:

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

referencing the following "Lock-free algorithms" page on 1024cores.net:

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

I don't understand the relation between this article and how concurrency works under Clojure.

And it got me totally confused: when I'm developing concurrent programs in Clojure, does it mean "locks and lock-free algorithms" are a non-issue for me?

Attainment

Also neither the lock-free nor the lockless tags do have a wiki. Are they synonyms? Shouldn't these two tags be merged or are they different things? – Attainment

Clojure has deep concepts unusual enough that it is [next to] impossible to "get" them by simply learning syntax and solving puzzles. If your goal is to "really get Clojure" then I would suggest reading a good Clojure book. There are about 5 of them on Amazon. Then I guarantee you'll be able to answer your own question. – Candiot

@Dmitry Kakurin: I can see you're new here. Your comment shows that you don't get how SO works. SO is a place to ask questions, like this one which did get 8 upvotes and 3 favorites. SO is not a place where you come on your high-horse and piss on people who are learning a new language by solving puzzles by telling them that they're not going to "get it" and that they should read books to answer their own questions instead of asking them on SO. Now if you "really want to get StackOverflow" I suggest you read the SO FAQ ; ) – Attainment

@Dmitry Kakurin: as an hint as to how SO works: it works by having people participating there. Look at my question and the two great answers: who did bring more value to SO? Me by asking this question and the two people who greatly answered or you, with your snarky comment downplaying me and my puzzle-solving activiy? – Attainment

Your violent reaction is unprovoked and uncalled for. But most importantly you've missed my point: if your goal is to familiarize yourself with the language then what you are doing is fine (and by no means I was trying to downplay your efforts). However if you want to "get" what makes Clojure conceptually different from many other languages then reading a good book is the way to go, and it's highly unlikely that solving puzzles will get you there. Again try to read my comment not as an assault, but as an advice based on experience. And then feel free to ignore it. – Candiot

Answer 1

In general Clojure avoids the problem of locks by properly handling time In many systems time for an object is a very loose concept because an object at time-1 (before update) is edited in place to become that object at time-2 (after update), during that process it is netither first nor second, so we use locks to ensure it's only visible before or after this transition. Coordinating locks follows from this and deadlocks from that ...

It's a combination of algorithms, data structure, and time.

Clojure does this by combining immutable data structures, functional-programming, and a coordinated time model (refs, atoms, agents, etc). In this model a function takes something and produces the next version of it while preserving the past so long as anyone is looking at it (until the GC gets to it)

• Immutable Data Structures: Clojure's collections are persistent in the FP sense of the word. Old copies "persist" after new versions are made. this way observers don't need to lock objects because they will never change out from under them. Newer versions may exist that are based on the version they are looking at though nothing will change their copy.

• Functional Programming: Pure (or as close as makes no diference) Function take a collection at one point in time and produce the next version with out sharing their internal state so no locking will be required. This has many other benefits as well.

• Coordinated time: When multiple objects do need to be coordinated, as is the case with any interesting system, then Clojure's time model comes into play. There are different mechanisms for different purposes. this has one lock internally used to count the increments of time so that there is exactly one time zero, one time one, and one time N. So it is not strictly lock free. the STM contains locks that you never* need to interact with

---

*well... almost never ;-)

Veronicaveronika

Answer 2

If you grep around the Clojure source, and in particular, the .java files you will find quite a few references to the java.util.concurrent package. The java.util.concurrent package is the culmination of literally decades of research on concurrency by Doug Lea at SUNY Oswego. Specifically, there are references to the atomic variable classes (e.g AtomicReference) that allow access to the "compare and swap" (also called "compare and set", or CAS) instruction. The CAS instruction is a bit difficult to explain (I provide a reference below) but proper use of CAS is at the heart of what it means for an algorithm to be "lock free" (at least in the Java world). Lock free algorithms ultimately lead to higher throughput and less contention for highly concurrent applications; exactly the domain that Clojure is targeting.

For an in-depth look on this subject, read Java Concurrency in Practice by Brian Goetz. Also see this article by the same author.

As a side note, I always found it difficult to use the java.util.concurrent package directly even as it evolved. It just felt too low-level to me. The wonderful thing about Clojure is it provides access to that expert concurrency library but through terrific easy to use software transactional memory (STM) abstractions. That is really quite an accomplishment.

Emilyemina