[concurrency-interest] concurrency puzzle

David Holmes dcholmes at optusnet.com.au
Tue Sep 12 20:30:56 EDT 2006


Peter,

> Aha.. so you are saying that before 'invalidating' cache, all values
> are written to main memory? I though they were not written to main
> memory, but they were 'dropped'. So if they are already in main
> memory, you are lucky, if they only were in cache, you have lost your
> writes.
>
> This is exactly what I don't understand.

You really need to stop thinking about caches. The conceptual model of
"invalidating a cache" is just that - conceptual. Real caches don't work
this way. Actual cache coherency protocols are both simpler and more
complicated than this conceptual model. And this conceptual model is an
incomplete simplification. It was once a useful tool to help describe memory
model effects "imagine that the value is kept in a cache ...". The problem
is that people then go "Aha! In my MOESI-based cache system xxxx can't
happen therefore I don't have to worry about the memory model". That is very
bad because they do have to worry because in practice it isn't the hardware
cache they needed to be concerned about but the JIT compiler.

The memory model allows for things that may be impossible on a given piece
of hardware. The memory model defines the allowed behaviours. You can't
expect to map the memory models allowed behaviours onto the physical
behaviour of an actual machine. Nor should you try to
explain/rationalize/justify what the memory model allows by correlating that
with an actual machine's behaviour.

In your example a partial ordering is established (where -> means
happens-before):

  x=10 -> release_lock_by_T1 -> acquire_lock_by_T2 -> print(x)

  x=20 -> acquire_lock_by_T2 -> print(x)

So all that we can establish is that x=20 and x=10 happen before print(x).
But there is no constraint that either x=10->x=20 or that x=20->x=10. As the
two writes are unordered with respect to each other, either ordering is
possible and so the print(x) is allowed to print either 10 or 20. Whether it
will ever actually do so on your machine is a different question and
irrelevant as we always strive to write portable code.

Cheers,
David Holmes



More information about the Concurrency-interest mailing list