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
CategoryConcurrencyPatterns