It seems to be a common belief that code which uses mutexes/locks/synchronized methods is

Random thoughts on concurrency, databases and distributed systems

submited by

Style Pass

2023-03-22 13:00:09

It seems to be a common belief that code which uses mutexes/locks/synchronized methods is "slow" and, as soon as you replace them with atomics, your code becomes fast and lock-free. Atomic operations don't make your code wait-free, lock-free, or even obstruction-free. This tiny blog post is dedicated to the above definitions.

Wait-freedom means that any thread can make progress in a finite number of steps regardless of external factors, such as other threads blocking. A trivial example of a wait-free data structure is an atomic counter (in x86 it would use a LOCK XADD instruction), e.g. Java's j.u.c.AtomicInteger.

Lock-freedom means that the application as a whole can make progress regardless of anything. So, while individual threads may be blocked, at least one of them would be making progress. A trivial example would be the same atomic counter based on a loop with a CAS operation.

Obstruction-freedom means that a thread can make progress only if there is no contention from other threads. This guarantee is the weakest one on the list. It's hard to illustrate this definition with a simple enough example I'm not aware of a trivial example of this one, but you may refer to this paper.