Subj : Re: Memory visibility and MS Interlocked instructions
To   : comp.programming.threads
From : Peter Dimov
Date : Thu Sep 01 2005 12:49 pm

Seongbae Park wrote:
> Peter Dimov <pdimov@gmail.com> wrote:

> > X = 0, Y = 0
> >
> > CPU1:
> >
> > st.rel X 1
> > ld.acq Y
> >
> > CPU2:
> >
> > st.rel Y 1
> > ld.acq X
> >
> > It is possible for CPU1 and CPU2 to both load 0. This can't happen in a
> > TSO model (*), because one of the two stores must execute first.
> > --
> > (*) I don't know for sure whether SPARC-TSO is really TSO, though.
>
> You'd better define what TSO is then.

Total store ordering, i.e. stores are observed by all processors in the
same order.

> I'm not aware of any memory model called TSO other than what's defined in
> SPARC.
> There's no such thing as "release" and "acquire" in SPARC's TSO.
>
> Under TSO, the following example (essentially yours
> with rel/acq stripped since they don't exist on TSO):
>
> Initially X=Y=0
> P1: st 1,X; ld Y,reg1
> P2: st 1,Y; ld X,reg2
>
> Under TSO, reg1==0 AND reg2==0 is still possible,
> because those loads can perform before stores.

Right, because a store by itself is not observed by a CPU, but consider
the following slight modification:

P1: st 1, X; ld X, r1; ld Y, r2
P2: st 1, Y; ld Y, r3; ld X, r4

If the stores complete in an order that is the same for all processors,
X,Y for example, then r4 must be 1. That's because r1 and r3 are
obviously 1 (because of single thread constraints) and since the store
of Y has been observed by P2, it follows that the store of X must be
observed as well.

Under x86, r2 == r4 == 0 is still possible, because P1 and P2 are
allowed to observe the stores in a different order. There is no total
order on stores.

.