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.