Re: [9fans] waitfree

[erik quanstrom <quanstro@quanstro.net>]

On Mon May 19 15:51:27 EDT 2014, devon.odell@gmail.com wrote:
> 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.

there is no bus.

what LOCK really does is invoke part of the MSEI protocol.  the state
diagrams i've seen do not specifiy how this is arbitrated if there are > 1
processor trying to gain exclusive access to the same cacheline.

> 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.

i'm worried about the bound on the number of MSEI rounds.  i don't see
where the memory coherency protocol states that if there are n processors
a cacheline will be acquired in at most f(n) rounds.

- erik