on Fri Aug 26 2011, "Boehm, Hans" <hans.boehm-AT-hp.com> wrote:
I agree with Alexander and most of the recent postings. If I write
mx.lock(); x = 1; mx.unlock(); my.lock(); y = 1; my.unlock();
There is nothing to prevent the stores to x and y from becoming visible out of order at the hardware level. Enforcing ordering here would add needless and substantial cost. But a data-race-free program cannot observe such reordering. (One reference for that is Sarita Adve's and my PLDI 08 paper. Unofficial TR version at http://www.hpl.hp.com/techreports/2008/HPL-2008- 56.html. I believe Mark Batty et al have a much more complete and formal proof.)
And that actually supports what I've been saying. It doesn't really matter if a program with data races can observe such a reordering, because programs with data races invoke undefined behavior, so they can observe the moon being carved open to reveal green cheese.
If we change x and y to be atomic variables, and the stores to be memory_order_relaxed, then an observer can tell the difference.
Meaning a data-race-free observer.
I.e. if x and y are initially zero, and another thread does
r1 = y; r2 = x;
(or the acquire versions), it can see r1 = 1 and r2 = 0, since there are no synchronizes-with relationships between threads, and thus nothing to enforce ordering. If you use memory_order_relaxed, or even the acquire/release forms, things do get MUCH more complicated.
Right, but―just for the record―we were explicitly discussing the default behaviors.
In my mind, the main way in which sequential consistency differs from the cheaper acquire/release semantics that Alexander wants is that
a) Dekker's algorithm (which by itself isn't that practically interesting), plus a number of real lock-free algorithms (which do matter) don't work.
Don't work with with SC or with acquire/release semantics?
b) In my mind, acquire/release is a far more difficult model to explain to non- experts than the model for C++ with only sequentially consistent atomics. You can no longer reason about interleaving thread actions, either for purposes of determining the existence of a data-race, nor when defining what data-race- free programs mean.
How *do* you reason about data races in that model? -- Dave Abrahams BoostPro Computing http://www.boostpro.com