[cpp-threads] Causality on more than two processors, write atomicity

[Herb Sutter]

> Herb Sutter wrote:
> > Does that mean I can't always reliably maintain invariants, if I'm
using
> > unsynchronized updates (no locks) and the variables involved in the
> > invariant can be updated by more than one thread over the life of
the
> > program?

Doug replied:
> And historically, almost no algorithms/programs have ever been
> found to require such strong guarantees. We once challenged
> people to come up with non-toy examples, and never got any.

Really? Off the top of my head (imagine these represent a bounded queue,
or a series of state changes in a FSM, or a series of barrier/gate
flags, or...):

  int x, y;

  start: x == y == 0;
  invariant: x <= y <= x+1

  P0: if( x == 0 ) x = 1;
  P1: if( x == 1 ) y = 2;
  P2: assert( invariant );

Each of P0 and P1 preserve the invariant, but P2 might fail -- is that
right, or did I misunderstand the issue?

Assuming the above example breaks: I don't think that's a toy example,
because it's only a degenerate case of this producer/consumer code with
a bounded queue of size 1 (for just one example). Here P0 can only
dequeue an item when y is ahead of x, and P1 and only enqueue an item
when y equals x:

  P0 (consumer, moves x forward):
    int N = 0;
    while(true)
      if( y == N+1 ) {
        // process item in position N
        N++;
        x = N;
      }

  P1 (producer, moves y forward):
    int N = 0;
    while(true)
      if( x == N ) {
        // add item to queue in position N+1
        N++;
        y = N;
      }

And this is fine until someone else tries to look at it:

  P2 (the observer):
    assert( invariant );

That breaks, right? Sorry if the code's not quite right, I'm literally
just tossing it out off the top of my head as the first thing that comes
to mind.

The general form of what breaks seems to be just:

  1. Pn can observe an effect E

  2. Pn cannot observe the value C that caused E

  3. C and E are related in some program invariant => inconsistency

Assuming I haven't made some other stupid oversight above (which is
entirely likely, and please do enlighten me): I'm not sure how even a
genius could program reliably without locks in such an environment.

Hopefully I'm missing something, because I'm not following the thread in
depth and you guys all have way more experience with this than I do, but
this part got me interested and I always like to learn what I don't know
so I can make progress. So, enlightenment would be appreciated! Thanks,

Herb