Wait Free Synchronization

A wait-free implementation of a concurrent data object is one that guarantees that any process can complete any operation in a finite number of steps of finite time, regardless of the execution speeds of the other processes.

Wait-free algorithms are always lock-free algorithms. Whenever one process locks an object, other objects are forced to wait an unbounded amount of time until the first process releases that object. This causes many well-known problems (indeterministic DeadLock and LiveLock) that are completely avoided by wait-free algorithms.

(stuff that was really merely lock-free, not quite wait-free, moved to LockFreeSynchronization)

Someone changed "DeadLock" to "indeterministic DeadLock". What's the difference ? -- DavidCary

Deterministic deadlock/livelock will happen consistently and predictably (i.e., you could program it to happen if you wanted to, although I'm not quite sure why you would).

Indeterministic deadlock/livelock is unpredictable. Even if you wanted to you could only cause it to occur probabilistically (i.e., run a couple hundred threads together knowing that the odd's of them escaping deadlock are about the same as you winning the lottery).

The reason for the distinction is that you can in theory program your way back into deadlocks; wait-free synchronization demonstrates that it is never necessary.

-- WilliamUnderwood

Are there any ACID database with WaitFree? reads and reasonable updates ? The closest I can get is:

:read - open("cur"); read(); close("cur")

:write - lock("lock"); copy("cur", "tmp"); modify("tmp"); rename("tmp", "cur"); unlock("lock");

Reads are fine and virtually waitfree this way, but writes are not.

See LockFreeSynchronization SynchronizationStrategies http://en.wikipedia.org/wiki/Lock-free_and_wait-free_algorithms


View edit of May 17, 2007 or FindPage with title or text search