lock-free as a goal
Locks have a hidden fragility: if a thread holding a lock is paused — preempted by the scheduler, or worse, crashes — every other thread waiting for that lock is stuck too. One stalled thread can freeze the whole system. Lock-free is the goal of building shared data structures that need no locks at all, so that no single thread's delay can block the others. It is a property of an algorithm, not just an absence of the word 'lock'.
Precisely, an algorithm is lock-free if, whenever threads run for long enough, at least one thread always makes progress — the system as a whole never gets stuck, even if individual threads are arbitrarily delayed. (A stronger property, wait-free, guarantees every thread makes progress in a bounded number of steps; a weaker one, obstruction-free, only guarantees progress when a thread runs alone.) Lock-free code is built almost entirely from atomic operations, especially compare-and-swap: a thread prepares its change locally, then tries to commit it with a single atomic CAS; if another thread got there first, the CAS fails and it retries with the fresh state. There is no critical section a thread can be 'stuck inside', because there is no lock to hold — the worst that happens is a thread retries its CAS loop.
Lock-free structures (queues, stacks, hash maps) matter most where a stalled or preempted thread holding a lock would be unacceptable: real-time systems, OS kernels, and very high-contention hot paths. But the honest caveats are large, which is why this entry only names the goal and Volume II does the real treatment. Lock-free code is genuinely hard to write correctly — it must contend with the ABA problem, with subtle memory-ordering requirements, and with safe memory reclamation (you cannot free a node another thread might still be reading). It is also not automatically faster: under heavy contention, CAS-retry loops can waste work, and a well-designed lock is often simpler and faster than a hand-rolled lock-free structure. Reach for lock-free only with a measured reason and great care; default to a mutex.
A lock-free counter is just atomic_fetch_add(&count, 1) from every thread — no lock, and a paused thread cannot block the others. A lock-free queue is far harder: it needs CAS loops plus a scheme to safely reclaim removed nodes.
Lock-free means no thread's delay can block the rest; the system always makes some progress.
Lock-free is NOT the same as 'no mutex and therefore faster' — it is a precise progress guarantee, and naive lock-free code is easy to get subtly wrong (ABA, memory ordering, use-after-free during reclamation). For most application code a well-designed mutex is the right default; reserve lock-free for measured, justified hot paths.