[cpp-threads] RE: "Agenda" for august 23-25 concurrency meeting

[Herb Sutter]

I'll expand on the example, but I think there are two important high-level points to add:

1. This is also about lock-based code, not just lock-free code (see lock-based variant below; I only show one, but all of them could be turned into lock-based versions the same way with the same issue).

2. This is why PC (and TSO as I understand it) isn't sufficient.


Peter Dimov wrote:
> Herb Sutter wrote:
> > For example, the canonical "toy" example was:
> >
> >   init: x = y = 0;
> >
> >   P1:   x = 1;               // a
> >
> >   P2:   if( x==1 )           // b
> >           y = 1;             // c
> >
> >   P3:   if( y==1 )           // d
> >           assert( x == 1 );  // e

Incidentally, in the Prism spec, the above is the first example in the "causality examples" section (it's 3.4.1).

> Slight variation:
>
> init: X *p1 = 0, *p2 = 0;
>
> P1: p1 = new X;
>
> P2: if( p1 ) p2 = p1;
>
> P3: if( p2 ) p2->f();
>
> Is it not a killer?

Yes. This is basically identical to the immediately following one, provided by Hans:

// Example 3.4.2

T1: construct X;
    p = reference to X;

T2: r2 = p;
    q = r2;

T3: r3 = q;
    if( r3 != null ) {
      q.foo();
    }

[These example numbers are as of the 0.8 version. Note these example numbers will change slightly in the 0.9 version because I'm reorganizing the subsections slightly. I hope to have the 0.9 ready soon, in time for the mailing next Friday.]

While we're at it, note that the issue happens even for lock-based code:

// 3.4.2 variant using a lock to protect p1 and p2

T1: lock();
    construct X;
    p = reference to X;
    unlock();

T2: lock();
    r2 = p;
    q = r2;
    unlock();

T3: lock();
    r3 = q;
    if( r3 != null ) {
      q.foo();
    }
    unlock();

Still a killer example, no?


Note also Example 3.4.3, mentioned on this (cpp-threads) list by Hans:

// Example 3.4.3

T1: p = new X;
    p_initialized = true;

T2: while( !p_initialized ) { ; }
    q = new Y( p );
    q_initialized = true;

T3: while( !q_initialized ) { ; }
    ... access *p via *q ...


The fourth example in that section was also provided by Hans:

// Example 3.4.3

T1: x = 17;
    lck = 1;

T2: while( lck == 0 ) { ; }
    r1 = x;
    y = r1;
    lck = 2;

T3: while( lck < 2 ) { ; }
    r2 = y;

We must guarantee that r1 == r2 == 17. (Assuming the variables are atomic/volatile/interlocked/whatever.)


General note: In the Prism doc I've tried to capture as many canonical and important examples as possible in one place, so please let me know as you find important examples that are not yet in there. Thanks,

Herb