Re: [9fans] waitfree

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

So you seem to be worried that N processors in a tight loop of LOCK
XADD could have a single processor. This isn't a problem because
locked instructions have total order. Section 8.2.3.8:

"The memory-ordering model ensures that all processors agree on a
single execution order of all locked instructions, including those
that are larger than 8 bytes or are not naturally aligned."



2014-05-19 16:21 GMT-04:00 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 you mean is that the processor might not LOCK#, but it can. LOCK
will signal LOCK# on the bus if it thinks it has to. (And if whatever
is being ainc()'ed is ainc()'ed frequently, or whatever is being
ainc()'ed is just never in cache for whatever reason, that will
happen.)

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

In Section 8.2.3.8 of the manual:

"8.2.3.8 Locked Instructions Have a Total Order

The memory-ordering model ensures that all processors agree on a
single execution order of all locked instructions, including those
that are larger than 8 bytes or are not naturally aligned."

Thus, LOCK-prefixed instructions will never cause processor
starvation, which seems to be your worry. They're wait-free.

--dho

> - erik
>