Re: questions about memory_order_seq_cst fence



Alexander Terekhov <terekhov@xxxxxx> writes:

Anthony Williams wrote:

[... remote write atomicity ...]

However, in particular cases then you can order particular subsets. If
you have an example of code that you would like to work then I can see
if I can think of a way to make it work without using seq_cst everywhere.

See examples in

http://portal.acm.org/citation.cfm?id=1375591
("4.2 Unintended Consequences of Relaxing Write-Atomicity")

"4.2.1 Write-to-Read Causality (WRC) Must be Upheld"

Figure 5:

std::atomic<int> X(0),Y(0);

T1
X.store(1,memory_order_relaxed);

T2
r1=X.load(memory_order_relaxed);
atomic_thread_fence(memory_order_release);
Y.store(memory_order_relaxed);

T3
r2=Y.load(memory_order_relaxed)
atomic_thread_fence(memory_order_acquire);
r3=X.load(memory_order_relaxed);

The required ordering comes from 29.8p2 and 1.10p16, since T2 stores
to
Y and T3 loads from Y: if r1==1 and r2==1 then r3==1.

"4.2.2 Read-to-Write Causality (RWC)"

Figure 6:

std::atomic<int> X(0),Y(0);

T1
X.store(1,T1MO);

T2
r1=X.load(T2MO1);
atomic_thread_fence(T2MO2);
r2=Y.load(T2MO3);

T3
Y.store(1,T3MO1);
atomic_thread_fence(T3MO2);
r3=X.load(T3MO3);

In this case, there are no orderings such that acquire and release can
have any impact. Therefore the choice of ordering for each operation
is
either memory_order_seq_cst or memory_order_relaxed.

I presume we are trying to find a set of ordering constraints such
that
r1==1, r2==0, r3==0 is not possible.

The T1MO is memory_order_relaxed then both T2MO1 and T3MO3 must be
memory_order_seq_cst, and either of T2MO2 and T2MO3 must be
memory_order_seq_cst, and either of T3MO1 and T3MO2 must be
memory_order_seq_cst.

With any of these combinations, if r2==0 then the read of r1 must
occur
before the read of r3 in S, and r1==1, r3==0 is thus impossible by
29.3p3 (otherwise it is not consistent with the modification order of
X).

If T1MO is memory_order_seq_cst, then it is enough to make T2MO1,
T2MO2
and T3MO2 memory_order_seq_cst; the rest can be memory_order_relaxed.

If r1==1 then the load of r1 is after the store to X in S. If r2==0
then
the fence in T2 must be before the fence from T3 in S (by 29.3p5, if
the
fence in T3 is prior to the fence in T2 then r2==1). If T2 precedes T3
in S, and the store to X precedes the load of r1 in S then the store
to
X precedes T3 in S. By 29.3p5 we must have r3==1.

"4.2.3 Subtle Interplay Between Coherence and Causality"

std::atomic<int> X(0),Y(0);

T1
X.store(1,T1MO);

T2
r1=X.load(T2MO1);
atomic_thread_fence(T2MO2);
r2=Y.load(T2MO3);

T3
Y.store(1,T3MO1);
atomic_thread_fence(T3MO2);
X.store(2,T3MO3);

T4
r3=X.load(T4MO1);
atomic_thread_fence(T4MO2);
r4=X.load(T4MO3);

In this example, the "violating result" is given as r1==1, r2==0,
r3==2,
r4==1.

r3==2, r4==1 requires that the store X=2 is prior to the store X=1 in
the modification order of X. There are no stores on thread 4, and no
ordering constraints can change this requirement, so T4MO1, T4MO2 and
T4MO3 can all be memory_order_relaxed.

The requirement that r1==1 requires that the load of r1 is seeing the
result of the store X=1, which is after the store X=2 from T3 in the
MO
of X. If T3MO3 and T2MO1, T3MO1 and T2MO3 are memory_order_seq_cst
then
everything works, even if everything else is memory_order_relaxed,
since
the load of r1 must be later in SC than the store X=2, in order to see
the later stored value, which means the store of Y=1 occurs before the
load of r2, and r2 must be 1.

Likewise, if T3MO3 and T2MO1, T3MO2 and T2MO2 are
memory_order_seq_cst,
then the same rules apply to mean the fence in T3 is before the fence
in
T2 in S, and by 29.3p5 r2==1.

It is possible that there are some alternatives with fewer
memory_order_seq_cst operations, but I don't see them right now.

Anthony
--
Author of C++ Concurrency in Action http://www.stdthread.co.uk/book/
just::thread C++0x thread library http://www.stdthread.co.uk
Just Software Solutions Ltd http://www.justsoftwaresolutions.co.uk
15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No.
5478976
.