These two terms get mixed up constantly. Short version:
- Blocking: if the thread holding a lock is descheduled, everyone waits.
- Lock-free: some thread always makes progress, but an individual thread can retry forever.
- Wait-free: every thread finishes in a bounded number of its own steps.
A classic lock-free counter increment:
std::atomic<int> counter{0};
void inc() {
int old = counter.load();
while (!counter.compare_exchange_weak(old, old + 1)) {
// old was refreshed with the current value, try again
}
}
Timeline with two threads:
T1: load 5 ----------- CAS(5->6) OK
T2: load 5 --- CAS(5->6) FAIL -- load 6 -- CAS(6->7) OK
T1 succeeded, so the system progressed, but T2 retried. With enough contention, T2 could lose again and again. Lock-free, not wait-free.
On x86 the better version is counter.fetch_add(1), which compiles to a single lock xadd. That one is wait-free: it completes in a bounded number of steps, no loop. Moral: when the hardware gives you the operation, do not build it from CAS.