Subj : Re: [.NET] Volatile Fields [correction]
To   : comp.programming.threads
From : David Hopwood
Date : Tue Sep 20 2005 02:29 am

Sean Kelly wrote:
> David Hopwood wrote:
> 
>>Oops, wrong example. This is the example I meant
> 
> For what it's worth, your previous example showed the same problem

Actually, it doesn't.

  Start with X == Y == Z == 0.

  Processor 1:  X = 1; Y = 1;
  Processor 2:  if (Y == 1) { Z = 1; }
  Processor 3:  if (Z == 1) { assert(X == 1); }

If it were possible, the space-time diagram for the execution that
causes an assertion failure would be:


P1  --(X = 1)--(Y = 1)------------------------------------------------
         \\________\ _________________________________
          \         \                                 \
P2  -------*---------*-(Y == 1)--(Z = 1)-------------- \ ------------
                    (a)             \                   \
                                     \                   \
P3  ----------------------------------*-(Z == 1)-(X == 0)-*-(X == 1)-
                                                         (b)

But this execution can't occur in a processor consistent model:

<http://research.compaq.com/wrl/people/kourosh/papers/1993-tr-68.pdf>

# Definition 1: Performing a Memory Request
#
# A load by Pi is considered performed with respect to Pk at a point in
# time when the issuing of a store to the same address by Pk cannot affect
# the value returned by the load. A store by Pi is considered performed
# with respect to Pk at a point in time when an issued load to the same
# address by Pk returns the value defined by this store (or a subsequent
# store to the same location). An access is performed when it is performed
# with respect to all processors.
[...]
# Condition 1: Conditions for Processor Consistency
#
# (A) before a load is allowed to perform with respect to any other
#     processor, all previous load accesses must be performed, and
# (B) before a store is allowed to perform with respect to any other
#     processor, all previous accesses (loads and stores) must be performed.

In particular, (B) implies that before Y = 1 is allowed to perform with
respect to P2, X = 1 must have performed with respect to P3.

(I.e. there would have to be a way to draw the space-time diagram so that
(b) is to the left of (a) without changing the causal relationships, which
can't be done.)


If we go back to the second example and try to use similar reasoning:

P1  --(Y = 1)-----------------------------------------------
         \\__________________________________
          \                                  \
P2  -------*--(Y == 1)--(Z = 1)-------------- \ ------------
          (a')             \                   \
                            \                   \
P3  -------------------------*-(Z == 1)-(Y == 0)-*-(Y == 1)-
                                                (b')

in this case there is no rule that requires (b') to be before (a').

-- 
David Hopwood <david.nospam.hopwood@blueyonder.co.uk>

.