Examples/Illustration of Wait-free And Lock-free Algorithms

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.

A non-blocking algorithm is lock-free if there is guaranteed system-wide progress, and wait-free if there is also guaranteed per-thread progress. Hence, a wait-free algorithm is also lock-free; however, vice versa doesn't hold. But, both are non-blocking algorithms, nonetheless.

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

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.

From the weaker to the stronger condition:

A method is lock-free if it guarantees that infinitely often some method call finishes in a finite number of steps.

A method is wait-free if it guarantees that every call finishes its execution in a finite number of steps.

Clearly, any wait-free method implementation is also lock-free, but not vice versa. Lock-free algorithms admit the possibility that some threads could starve.

However, from a "Practical Perspective" there are many situations in which starvation, while possible, is extremely unlikely, so a fast lock-free algorithm may be more attractive than a slower wait-free algorithm.

NOTE: An even stronger property it is called "bounded wait-free" which means: there is a bound on the number of steps a method call can take.