32

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?

skaffman
  • 398,947
  • 96
  • 818
  • 769
softwarematter
  • 28,015
  • 64
  • 169
  • 263

3 Answers3

37

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.

asdfjklqwer
  • 3,536
  • 21
  • 19
  • 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? – softwarematter Nov 18 '10 at 03:46
  • 1
    @iJeeves: lock-free means no locks, so deadlocks are out of question. And no you can't. – Adeel Ansari Nov 18 '10 at 04:14
  • 1
    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. – asdfjklqwer Nov 18 '10 at 04:48
  • 4
    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 09: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 08 '13 at 18:54
  • 1
    You are confusing "lock-free" with "deadlock-free". – Apprentice Queue Apr 04 '14 at 18:33
22

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.

Adeel Ansari
  • 39,541
  • 12
  • 93
  • 133
  • 2
    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): https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html I wonder what changed? – Peter Dec 15 '19 at 20:31
  • 1
    @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. – Adeel Ansari Dec 16 '19 at 04:19
  • 2
    @AdeelAnsari Lock-free does not mean "without locks". That is typically called lockless. – Acorn May 17 '20 at 14:58
  • 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. – Daniel Aug 30 '21 at 18:06
4

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.

Alboz
  • 1,833
  • 20
  • 29