[concurrency-interest] question the about the JMM

Ben Horowitz horowitz2 at llnl.gov
Thu Dec 6 21:25:09 EST 2007


>> [...] "cache coherence" doesn't address reorderings
>> that the runtime compiler is allowed to do.
>>     
>
> Is there a canonical or ubiquitous example of this?  I
> am interested in the difficulties with using a model
> which includes, for example, a simple object cache
> coherence protocol based on a distributed directory.
>   
I believe the following comes close to a canonical example.  This 
example is borrowed from Jeremy Manson.  I like it; please don't make me 
return it. :)

Initially, o.x == o.y == 0.
Thread 1:
    o.x = 1; // 1a
    j = o.y; // 1b
Thread 2:
    o.y = 1; // 2a
    i = o.x; // 2b

In the absence of happens-before constraints, it is possible that i == 0 
and j == 0 after both threads execute.

This would seem to be impossible: i == 0 seems to imply that 2b precedes 
1a; j == 0 seems to imply 1b precedes 2a; and in program order 1a 
precedes 1b and 2a precedes 2b - put these together and it follows that 
1a precedes 1a - clearly impossible...

...but: In the absence of happens-before constraints, a compiler or 
run-time environment is free to reorder the operations of thread 2 as 
follows:

Thread 2:
    i = o.x; // 2b
    o.y = 1; // 2a

Executing the operations in the order 2b, 1a, 1b, 2a then yields i == 0 
and j == 0 after both threads execute.

The compiler or run-time reordering could occur even on a system with 
one core and no cache.

Ben


More information about the Concurrency-interest mailing list