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

[Boehm, Hans]

I certainly think that this sort of example must work for atomic/Java
volatile operations.  Thus I think there has to be a cheap way to make
it work, in general not necessarily with standard load and store
instructions.

For X86, there's the added problem that I'm sure there's code out there
that assumes that it works with ordinary loads and stores, since it
generally does.  I would be amazed if there is no such code in the Linux
kernel.  However I have no idea how to find it.

The other fundamental problem is that I haven't a clue as to what a
programming language level memory model would look like that doesn't
require this, or what semi-understandable rules one could give the
programmer.

Hans

> -----Original Message-----
> From: cpp-threads-bounces at decadentplace.org.uk 
> [mailto:cpp-threads-bounces at decadentplace.org.uk] On Behalf 
> Of Peter Dimov
> Sent: Friday, September 01, 2006 4:35 PM
> To: C++ threads standardisation
> Cc: Meredith, Alisdair; c++std-ext at accu.org; David Miller; 
> Lawrence Crowl; omp-lang at openmp.org; Terrence.Miller at sun.com; 
> David Miller; Howard Hinnant; Bill Seymour; P.J. Plauger 
> (Dinkumware Ltd); Bjarne Stroustrup; Bronis R. deSupinski; 
> Eric Niebler; Becker
> Subject: Re: [cpp-threads] RE: "Agenda" for august 23-25 
> concurrency meeting
> 
> Herb Sutter wrote:
> > Doug Lea wrote:
> >> Robison, Arch wrote:
> >>> 
> >>>> 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.
> >>> 
> >>> If you have a non-toy example algorithm that shows a need for 
> >>> causality or total store order, I would very much like to 
> see it and 
> >>> show it to our hardware architects.
> >> 
> >> Despite lack of a killer example,
> > 
> > Hmm. I keep seeing this assertion, and it surprises me. :-)
> > 
> > I am under the impression that not having transitivity would break 
> > essentially every algorithm falling into the following general case:
> > a lock-free multi-variable invariant maintained by more than one 
> > thread, where the two threads update disjoint parts of the 
> invariant.
> > 
> > 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
> 
> 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?
> 
> 
> --
> cpp-threads mailing list
> cpp-threads at decadentplace.org.uk
> http://www.decadentplace.org.uk/cgi-bin/mailman/listinfo/cpp-threads
>