Re: [9fans] waitfree

["Devon H. O'Dell" <devon.odell@gmail.com>]

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 <quanstro@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
>