Take the 2-minute tour ×

I've read that wait-free causes all threads to finish independently and lock-free ensures the program as a whole completes. I couldn't quite get it. Can anyone give an example (java) illustrating this.

EDIT: Does lock-free mean a program without deadlock?

share|improve this question

2 Answers 2

up vote 6 down vote accepted

If a program is lock-free, it basically means that at least one of its threads is guaranteed to make progress over an arbitrary period of time. If a program deadlocks, none of its threads (and therefore the program as a whole) cannot make progress - we can say it's not lock-free. Since lock-free programs are guaranteed to make progress, they are guaranteed to complete (assuming finite execution without exceptions).

Wait-free is a stronger condition which means that every thread is guaranteed to make progress over an arbitrary period of time, regardless of the timing/ordering of thread execution; and so we can say that the threads finish independently. All wait-free programs are lock-free.

I don't know offhand of any Java examples which illustrate this but I can tell you that lock-free/wait-free programs are typically implemented without locks, using low-level primitives such as CAS instructions.

share|improve this answer
does that mean any program without deadlock is lock-free? If one of the threads complete, how can we say that the program as a whole has completed? –  devnull Nov 18 '10 at 3:46
@iJeeves: lock-free means no locks, so deadlocks are out of question. And no you can't. –  Adeel Ansari Nov 18 '10 at 4:14
You're wondering how the lock-free property of a program implies that it's guaranteed to complete? Well, if there's a finite number of threads with finite workloads and at least one live thread is guaranteed to make progress on its workload over some period of time (lock-free property), then we know that all the threads (and therefore the program) will eventually complete. –  Nathan Pitman Nov 18 '10 at 4:48
We should be clear that the terminology; lock free doesn't mean deadlock free, it's a side affect of using lock free algorithms ... I think about the term are more being about not using mutually exclusive locks to achieve syncrhonisation between shared resources (which is what Nathan mentions when talking about CAS instructions). –  Toby Nov 18 '10 at 9:15
Of course, you can roll-your-own lock with the tools of lock-free programming, and I guess that needn't always be particularly evident. (Similarly you can simulate locks with transactions.) –  Tom Hawtin - tackline Jan 8 '13 at 18:54

No. Lock-free means a program without locks. And BTW, a wait-free algorithm is also lock-free, but not vice versa. Hence, both are non-blocking algorithms.

This wiki entry is a great read to understand lock-free and wait-free thingy.

Well, java.util.concurrent.atomic package is an example of lock-free programming on single variables. And in Java 7 ConcurrentLinkedQueue is an example of wait-free implementation.

For further insight, I would like you to read this article, Going atomic by Brian Goetz -- the guy who wrote Java Concurrency in Practice.

share|improve this answer

Your Answer


