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

Question

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?

Knudsen

Answer 1

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.

Slob

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? – Knudsen

@iJeeves: lock-free means no locks, so deadlocks are out of question. And no you can't. – Walsingham

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. – Slob

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). – Thorfinn

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.) – Resigned

You are confusing "lock-free" with "deadlock-free". – Swanger

Answer 2

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.

Walsingham

Curiously, while ConcurrentLinkedQueue is indeed described as a "wait-free" implementation in Java 7, in Java 8 that description changed to the less-strict "non-blocking" (the description persists to Java 13, the current version as of this comment): docs.oracle.com/javase/8/docs/api/java/util/concurrent/… I wonder what changed? – Psittacine

@Peter, I think, they changed the word to "non-blocking", in order to match the title of the original paper, by Maged M. Michael and Michael L. Scott, given as a link there -- the link seems broken, in Java 7/8 docs. – Walsingham

@AdeelAnsari Lock-free does not mean "without locks". That is typically called lockless. – Darsie

It looks to me like they improved the docs because the actual paper doesn't describe a wait-free algorithm and I think that implementation is actually only lock-free or non-blocking and not in-fact wait-free. – Kittle

Answer 3

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.

Tenaille