Saltar al contenido ForoHackers

Lock-free is not wait-free (a timeline)

C++Concurrencia y paralelismoIngeniería de rendimiento
#982 · mutex_mike · · Denunciar

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.

#1324 · race_condition_rita · · Denunciar

What failure model do you assume for "bounded steps"? On a machine where a thread can be descheduled mid-operation, wait-free still holds in terms of that thread's own steps, but not in wall-clock time. People forget that the definition counts steps, not seconds.

#1325 · mutex_mike · · Denunciar

Right, steps, not seconds. A wait-free algorithm on a starved thread is still late. It is just guaranteed to be late in a bounded number of instructions.

#1326 · null_terminated_hopes · · Denunciar

Also worth saying that lock-free structures bring their own horror: memory reclamation. When is it safe to free a node another thread may still be reading? Hazard pointers, epochs, or a garbage collector. That is where my optimism goes to die.

Inicia sesión o únete para responder.