The LOCK prefix is effectively a tiny, tiny mutex, but for all intents and purposes, this is wait-free. The LOCK prefix forces N processors to synchronize on bus and cache operations and this is how there is a guarantee of an atomic read or an atomic write. For instructions like cmpxchg and xadd where reads and writes are implied, the bus is locked for the duration of the instruction.
Wait-freedom provides a guarantee on an upper-bound for completion. The pipeline will not be reordered around a LOCK instruction, so your instruction will cause a pipeline stall. But you are guaranteed to be bounded on the time to complete the instruction, and the instruction decomposed into μops will not be preempted as the μops are executed. Wait-freedom is defined by every operation having a bound on the number of steps required before the operation completes. In this case, you are bound by the number of μops of XADDL + latency to memory. This is a finite number, so this is wait-freedom. Lock-freedom guarantees per-thread progress, but does allow threads to starve. LOCK XADDL will always complete in bounded time, but a while (cmpxchg(&ptr, oldptr, newptr)) loop does not. However, you are guaranteed that at least one thread will always make progress through this loop: preemption of a thread does not cause other threads to starve. (This is how lock-freedom differs from mutex-based critical sections although they sound like they make the same guarantee.) Interestingly, there is also a recent academic paper[1] that shows how most lock-free algorithms are practically wait-free. That's a bit of a tangent, because LOCK XADDL is defined to be wait-free anyway, but it is good to know. --dho [1]: http://arxiv.org/abs/1311.3200 2014-05-19 13:34 GMT-04:00 erik quanstrom <quans...@quanstro.net>: > i've been thinking about ainc() and for the amd64 implementation, > > TEXT ainc(SB), 1, $-4 /* int ainc(int*) */ > MOVL $1, AX > LOCK; XADDL AX, (RARG) > ADDL $1, AX > RET > > does anyone know if the architecture says this is wait-free? > this boils down to exactly how LOCK works, and i can't find > a good-enough definition. i tend to think that it might not be. > > - erik >
