What does "lock-free" mean, and how does it differ from "wait-free"?

Obstruction-free, lock-free and wait-free are three increasingly strong guarantees. Lock-free means at least one thread always makes progress, so the system cannot stall even if a thread is descheduled mid-operation. Individual threads can still starve, retrying forever while others succeed.

Wait-free adds a bound per thread, which is much harder and usually slower in the common case. AtomicInteger.get and getAndIncrement (implemented with getAndAddInt's hardware fetch-and-add on x86) are wait-free; a hand-written CAS loop is only lock-free.

The practical point: absence of locks does not imply absence of starvation, and a lock-free structure under heavy contention can be slower than a plain lock, because every failed CAS is wasted work plus a cache-line invalidation.