[cpp-threads] Alternatives to SC (SC for race-free)

[Boehm, Hans]

[I'll try to break this up into separate threads]
> From:  Paul E. McKenney
> 
> On Sun, Jan 28, 2007 at 10:48:29PM -0800, Hans Boehm wrote:
> > I finally managed to somewhat catch up with this thread.  
> I'd like to 
> > quickly clarify my position, since it diverges from what's been 
> > discussed here.  I'll put together and/or fix some web pages to 
> > explain some of this:
> > 
> > 1) I would ideally like to see a memory model with the 
> property that 
> > every data-race-free program that does not use low-level atomics 
> > behaves sequentially consistently.  Here "data race free" 
> is ideally 
> > defined as potentially simultaneous conflicting actions, where 
> > conflicting actions are defined more or less as usual.  
> Aside from the 
> > exclusion for low-level atomic operations, this is essentially the 
> > pthread model.  It does have some costs that we need to quantify.
> > But it has the, in my opinion huge and unique, advantage that it is 
> > comprehensible to programmers.
> 
> In other words, programs that use pthread_mutex_lock() and 
> friends in the classic manner (e.g., not accessing 
> lock-protected data from outside the corresponding lock), 
> correct?  If so, makes sense -- sequential consistency is a 
> property of locks and should also be of events.
Right, though the closest facility to events in the standard library are
likely to be condition variables.

But I'm also arguing for extending this guarantee to a flavor of atomic
variables, namely what we have been describing as "high level" atomics.
This is analogous to Java volatiles.  It allows you to do things like
- Implement double checked locking (with hopefully slightly) suboptimal
performance without understanding memory ordering rules in detail.
- Prototype lock-free algorithms while postponing the ordering issues.
- Implement simple lock-free algorithms that are not that performance
critical without understanding memory ordering details.  (This arises
for signal handler code, or for shared memory communication between
processes that may want to avoid locks for fault-tolerance issues.)

Based on the anecdotes I've seen, all of these appear to be important in
practice.  Herb has been arguing that these are the only kind of atomics
that matter.

I'll agree that this is of limited use if those need to be emulated with
locks on most of the major platforms.  Which is why I'm lobbying for
enough hardware support that we need at most a fairly cheap fence for
readers.

Based on the JSR133 cookbook rules, I believe that atomic loads can be
cheap enough.  (You do need an expensive StoreLoad fence between an
atomic store and a load, and you usually don't have enough context to
determine whether that's an issue.  But the fence can be associated with
the store, keeping the load relatively cheap, aside from the "acquire
fence", which tends not to be that expensive.)  This leaves the issue as
to whether we can get hardware to guarantee that the JSR133 rules
actually guarantee SC, or only something weaker, which is being
discussed.

The main point here is that I would like there to be an interesting
language subset that can be correctly reasoned about by assuming SC and
proving data-race-freedom.  I think there is lots of evidence that most
programmers have trouble understanding anything beyond that.

Hans