Peter Dimov wrote:

Alexander Terekhov wrote:

...

Consider also that

"Load Seq_Cst: MOV (from memory) Store Seq Cst: (LOCK) XCHG // alternative: MOV (into memory),MFENCE"

is an overkill for typical use cases...

But that's not a problem because everyone who understands should use explicit constraints, even if they happen to be memory_order_seq_cst. Relying on the SC default is bad practice because it can (and, to be on the safe side, should) be interpreted to mean that the author just hasn't figured out the minimum requirements.

I think that atomic<>'s memory order default should express minimum requirements, not maximum (SC). regards, alexander.

On Mon, Aug 29, 2011 at 5:03 PM, Hans Boehm <Hans.Boehm@hp.com> wrote:

Dave Abrahams <dave <at> boostpro.com> writes:

...

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. Yes.

...

on Fri Aug 26 2011, "Boehm, Hans" <hans.boehm-AT-hp.com> wrote:

...

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? Don't work with just acquire/release semantics.  Sorry about being unclear.

...

...

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?

You can clearly reason explicitly in terms of happens-before ordering, as in 1.10 of the standard.  I think you can also informally reason in a way similar to the sequentially consistent model, but you have to consider that atomic (release) stores are indefinitely buffered, and only become visible to other threads at some later time, but in their original order.  I haven't thought enough about the implications this would have on programming rules and interface specifications.

The canonical example of how this gets tricky, based on Dekker's example, is (thread1_busy, thread2_busy acquire/release atomics, z an ordinary variable, everything initially zero/false):

Thread 1: thread1_busy = true; if (!thread2_busy) {    // thread 2 either not busy, or will see that we are    z = 17; }

Thread 2: thread2_busy = true; if (!thread1_busy) {    // thread 1 either not busy, or will see that we are    z = 42; }

This DOES have a data race in the acquire/release model, i.e. the comments are incorrect.  And that race can't be understood in terms of interleaving.  But you can understand it if you explicitly reason about buffered stores.

Well, I don't know about interleaving, but reordering works, as long as you remember that thread1_busy = true and if (!thread2_busy) (and 1 <-> 2 vice versa) are fenced such that they can actually be reordered. Not sure if that is different than "interleaving". You can also understand it in terms of synchronizes-with. Or at least come to the conclusion that you can't find the right variable to synchronize with. See the discussion in the comments in http://bartoszmilewski.wordpress.com/2008/12/01/c-atomics-and-memory-orderin... and Anthony's explanation at http://www.justsoftwaresolutions.co.uk/threading/petersons_lock_with_C++0x_a...

Unfortunately, I think you also need to view unlock operations as getting buffered, and occuring at a later time, since the first and fourth operation in

x.store(1, memory_order_release); m.unlock(); m2.lock(); r1 = y.load(memory_order_acquire);

can become visible out of order.

The acquire/release model is more-or-less what is used by C# volatiles, for better or worse.  Some of the Microsoft Research folks have thought about it more than I have.

Hans

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Alexander Terekhov <terekhov <at> web.de> writes:

Hans Boehm wrote: [...]

...

...

...

plus a number of real lock-free algorithms (which do matter) don't work.

I'm really interested to know the exact number/names of algorithms.

I asked Doug Lea this question 3 or 4 years ago when this was still being actively discussed. He's more of an expert on practical concurrent algorithms. I got back a bunch of answers. One simple and common example is the algorithm for releasing a queued lock. I need to set the lock state to unlocked and then check the queue for waiters. If those are reordered, I get lost wakeup problems. His assessment was that such cases are surprisingly common, though there are clearly also a bunch of scenarios, like lazy initialization via double-checked locking, for which acquire-release atomics suffice.

[... "based on Dekker's example" ...]

Yes, acquire/release is free from implicit store-load barrier (same as with TSO and even IBM 370).

Note that computer hardware vendors never provided and still do not provide implicit store-load barrier for hardware.

Note that we're not actually requiring a full store-load barrier in the implementation. We only need a barrier that orders atomic stores and atomic loads, which could perhaps be appreciably cheaper, though on current architectures it isn't.

In this respect I really like "Figure 8":

http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf (Figure 8: Simple categorization of relaxed models. ...)

The situation is really quite different when you're talking about 1995 hardware ISAs as opposed to programming languages like C++. At the 1995 hardware level, you can no longer distinguish data and synchronization accesses, so you would also add the overhead to data accesses. And whatever you promise is unlikely to be visible to the programmer anyway, since compiler reordering is likely to invalidate whatever properties you tried to guarantee at the hardware level. Providing full sequential consistency at the hardware level without compiler changes is likely to buy you essentially nothing, and do so at significant expense either in hardware complexity and/or performance. For what it's worth, Sarita Adve is both an author of the report you cite and the original and perhaps strongest advocate for the "sequential consistency for data-race-free programs" programming model.

Why the heck is C++'s default mode for atomics so special in this respect?

At the programming language level, this isn't at all unique. I believe Ada 83 atomic accesses were sequentially consistent. Certainly Java volatiles are.

regards, alexander.

Alexander Terekhov <terekhov <at> web.de> writes:

Hans Boehm wrote: [...]

...

For what it's worth, Sarita Adve is both an author of the report you cite

and

...

the original and perhaps strongest advocate for the "sequential consistency for data-race-free programs" programming model.

I'm not contra "sequential consistency for data-race-free programs" programming model for programs using locks. On PPC, for example, such programs don't even need hwsync. For programs with lock-free atomics OTOH, the races (concurrent accesses to the same locations with loads competing with concurrent stores) is a feature, not a bug, and SC is simply way too expensive (e.g. it needs hwsync on PPC) for use in default mode for lock-free atomics: C/C++ is "you don't pay for what you don't need".

regards, alexander.

The question is when the "sequential consistency for data-race-free programs" should extend to programs using atomic load, store, and RMW operations. The C++ committee, including me, came to the conclusion that the answer needs to be the yes; there are many cases in which the use of atomics is fairly straightforward and useful. And it should be possible to use them without leaving this relatively simple programming model. By doing so, you get a safe programming model by default. Since we do have explicit ordering primitives, you have the option of only paying for what you need. But 90%, or probably 99% of programmers will not know what they need here. And that's fine. This is entirely consistent with many other C++ design decisions. The default operator new allocates memory that lives as long as the process, even though that's more expensive than allocating memory local to the current stack frame or thread, and often one of those latter two options would be sufficient. But it would be nasty to use that as default behavior. The overhead of enforcing sequential consistency is unfortunately currently very platform-specific. On X86, it's increasingly minor, since it's possible to confine the added cost to stores and, as far as I can tell, the added cost is becoming much less than the cost of a coherence miss. And if your performance is limited by the cost of stores to shared variables, you are fairly likely to unavoidably see lots of coherence misses, so there is a hand- wavy argument that this is likely to be a minor perturbation. On other architectures, the costs are unfortunately larger. But my impression is that they are decreasing everywhere, as architects pay more attention to synchronization costs. Hans

Alexander Terekhov <terekhov <at> web.de> writes:

Hans Boehm wrote: [...]

...

...

I'm really interested to know the exact number/names of algorithms. I asked Doug Lea this question 3 or 4 years ago when this was still being actively discussed. He's more of an expert on practical concurrent algorithms. I got back a bunch of answers. One simple and common example

is

...

the algorithm for releasing a queued lock. I need to set the lock state to unlocked and then check the queue for waiters. If those are reordered, I get lost wakeup problems. ...

Dejavu...

http://www.mailarchive.ca/lists/comp.unix.solaris/2003-12/0937.html#start937

The relevant part is:

------

...

...

...

and subsequent store-load barrier + load to check whether you have a blocked waiter to unblock? Store-load barrier is known to be "the most expensive"...

The store-load barrier is avoided by carefully setting up the sleeping and blocking interactions so that the above code + the slow paths can never loose a waiter.

And you can do it without atomic read-{modify-}write on the fast path in mutex_exit()? Hmm. Please elaborate.

Casper already got this, but here:

1. As long as the thread is on-CPU, you spin. Blocking is a four-stage process: 2. atomically set the waiters bit, 3. re-scan all of the other CPUs on the system, checking to make sure the owner is still not running on them. 4. check that the lock hasn't changed while you were looking. 5. Finally, block. If any of the above steps fail, you go back to spinning. 6. if a thread is in the "critical section" (i.e. after the load and before the clear) when we are resuming it (either from an interrupt or in a context switch), we back up the program counter to the beginning of mutex_exit.

There are further complications, but that's the crucial bit.

• jonathan

Although the existence of such an algorithm is interesting, the point is that avoiding the equivalent of the sequentuially consistent store here is incredibly complicated, appears to require scheduler help and, at least for me, would require careful study of the proof before I were willing to implement it. On the other hand, the algorithm using the equivalent of sequentially consistent atomics (which I think is still far more widely used) is orders of magnitude simpler. If you understand the complex algorithm, we assume you can add the ordering constraints corectly. Interestingly, there is a 2011 POPL paper by Attiya et al that proves, IIRC, that store-load ordering or atomic RMW operations are unavoidable in some cases. I haven't looked into this enough to understand how to reconcile that with the above result. The kind of scheduler hack needed in step 6 above is probably outside their model. Hans Hans

Alexander Terekhov <terekhov <at> web.de> writes:

Hans Boehm wrote: [...]

...

Although the existence of such an algorithm is interesting, the point is

that

...

avoiding the equivalent of the sequentuially consistent store here is incredibly complicated, appears to require scheduler help and, at least for me, would require careful study of the proof before I were willing to implement it. On the other hand, the algorithm using the equivalent of sequentially consistent atomics (which I think is still far more widely used) is orders of magnitude simpler. If you understand the complex algorithm, we assume you can add the ordering constraints corectly.

With waiters bit (0x80000000) and atomic RMW, mutex is simply: (pseudo-code below)

WHILE atomic_bit_test_set_hlb(&lock, 1) // efficient acquire MO lock_queue_wait(&lock, 1) // wait if locked bit is set

for lock() and

uintptr_t lock_queue IF atomic_decrement_rel(lock_queue = &lock) // release MO THEN lock_queue_wake(lock_queue, 1) I'm not sure I understand your syntax here.

I don't see the correctness argument. What prevents the sequence: 1. In thread T0, performing unlock, atomic_decr_rel update completes, sees no waiters, puts updated (released) lock word in store buffer. (I'm informally viewing memory_order_release as just putting a value in a store buffer, which I think is reasonable here.) 2. Thread T1 tries to acquire the lock, sees it still held, since store buffer hasn't drained. Enqueues itself. 3. Thread T0s store buffer drains. Thread T1 is now waiting on an unlocked lock. The real point here again is that such arguments are subtle. I don't want to have to deal with them unless performance considerations warrant that I do, especially since we have lots of evidence that even experts get these things wrong. Hans

Alexander Terekhov <terekhov <at> web.de> writes:

Hans Boehm wrote:

...

Alexander Terekhov <terekhov <at> web.de> writes:

...

Hans Boehm wrote: [...]

...

Although the existence of such an algorithm is interesting, the point

is

...

that

...

...

avoiding the equivalent of the sequentuially consistent store here is incredibly complicated, appears to require scheduler help and, at least for me, would require careful study of the proof before I were willing to implement it. On the other hand, the algorithm using the equivalent of sequentially consistent atomics (which I think is still far more widely used) is orders of magnitude simpler. If you understand the complex algorithm, we assume you can add the ordering constraints corectly.

With waiters bit (0x80000000) and atomic RMW, mutex is simply: (pseudo-code below)

WHILE atomic_bit_test_set_hlb(&lock, 1) // efficient acquire MO lock_queue_wait(&lock, 1) // wait if locked bit is set

for lock() and

uintptr_t lock_queue IF atomic_decrement_rel(lock_queue = &lock) // release MO THEN lock_queue_wake(lock_queue, 1) I'm not sure I understand your syntax here.

I don't see the correctness argument. What prevents the sequence:

1. In thread T0, performing unlock, atomic_decr_rel update completes, sees no waiters, puts updated (released) lock word in store buffer. (I'm informally viewing memory_order_release as just putting a value in a store buffer, which I think is reasonable here.) 2. Thread T1 tries to acquire the lock, sees it still held, since store buffer hasn't drained. Enqueues itself. 3. Thread T0s store buffer drains. Thread T1 is now waiting on an unlocked lock.

lock_queue_wait() is meant to block the calling thread and set waiters bit only if locked bit is actually set (an RMW operation).

The races for setting/clearing bits are resolved by RMWs on the same (&lock) memory location.

The situation is no different when (&lock) memory location would be protected by a lock except that with RMWs the program is lock-free on fast paths.

I think I see what you're doing. By embedding the state of the queue into the same atomic object as the lock set bit, you can rely on single-location cache coherence to get the right ordering. That can be made to work for the low- level bit-twiddling implementation, but not for a more generic approach that keeps the queue and the lock-bit itself separate. I would still much rather see a default that works for the full solution space. I prefer to have people like us who are sometimes willing to go through subtle reasoning about memory ordering add the annotations, rather than insisting that the average programmer who has never heard of these issues add them to avoid subtle bugs. Hans

Hans Boehm wrote: [... RMW/store-load barrier free (on fast path) release for lock with a queue ...]

Interestingly, there is a 2011 POPL paper by Attiya et al that proves, IIRC, that store-load ordering or atomic RMW operations are unavoidable in some cases. I haven't looked into this enough to understand how to reconcile that with the above result. The kind of scheduler hack needed in step 6 above is probably outside their model.

http://infoscience.epfl.ch/record/161286/files/popl168gf-attiya.pdf (Laws of Order: Expensive Synchronization in Concurrent Algorithms Cannot be Eliminated) Nice title. ;-) I think they are talking about impossibility of RMW/store-load barrier free lock acquisition. RMW/store-load barrier free (on fast path) release for queued lock is out of scope of their paper, AFAICS. regards, alexander.