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

java multithreading algorithm nonblocking
softwarematter picture softwarematter · Nov 18, 2010 · Viewed 11.4k times · Source

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?

Answer

Nathan Pitman picture Nathan Pitman · Nov 18, 2010

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.

Related questions

Multi-threaded algorithm for solving sudoku?

I have a homework assignment to write a multi-threaded sudoku solver, which finds all solutions to a given puzzle. I have previously written a very fast single-threaded backtracking sudoku solver, so I don't need any help with the sudoku solving …

Read More
Difference between wait() and sleep()

What is the difference between a wait() and sleep() in Threads? Is my understanding that a wait()-ing Thread is still in running mode and uses CPU cycles but a sleep()-ing does not consume any CPU cycles correct? Why …

Read More
"implements Runnable" vs "extends Thread" in Java

From what time I've spent with threads in Java, I've found these two ways to write threads: With implements Runnable: public class MyRunnable implements Runnable { public void run() { //Code } } //Started with a "new Thread(new MyRunnable()).start()" call Or, with …

Read More