[cpp-threads] High-level concurrency issues

[Herb Sutter]

As quoted in this thread, Hans wrote:
> > >> But in most cases, it seems to work tolerably well, and layers of
> > >> calls seem to compose reasonably.  And I'm not 100% convinced
that
> > >> the cases in which it breaks don't have single-threaded lock-free
> > >> analogs in which I break object invariants with an unintentional
> > >> recursive call.

But immediately before that he wrote the key two lines:
> > >> This can get me into trouble if atomicity or other considerations
> > >> require me to hold a lock during a client call-back, for example.

Aye, there's the rub. I wrote, and Peter responded:

> > > I'd be interested to see analogs.
> >
> > The general case is a class making an external call while one of its
> > invariants temporarily doesn't hold. Note that this is independent
of
> > threads or locks. The lock case is a specific instance where
> > the invariant is "no internal locks are held".

I agree that reentrancy is independent of threads and locks, but it's
still a much lower bar than locks. Hans added:

> In single threaded code, you avoid the deadlock issues, etc., but you
> still see the object with the broken state.  Which is arguably worse,
> since the failure may be harder to detect.  

> So why do we usually associate these problems with threads?  Perhaps
> it's just a quantitative issue?  

Consider when invariants must hold:

In a sequential app, invariants must hold on method entry/exit and
inside a method at the point of any call that could transitively call
external code. Programmers easily grok the entry/exit part. The last
part requires care and not everyone remembers to do that, but the point
is that it's usually easy to write correctly so that the invariant is
restored and the result is composable. (I think it turns out that most
and often all the work needed to make this correct is also needed just
for exception safety.)

But in a concurrent app, invariants (on mutable shared state) must
additionally hold _anytime_ the protecting lock is not held. This is a
higher bar. It is not always easy to maintain a lock correctly so that
the result is composable. First you try not to hold a lock; the very
first example in Doug's book is about how to reduce locks to avoid
holding them during calls to external code.

But it's not always possible to eliminate the lock before calling
external code (e.g., there are times the lock is required to prevent
races with other threads, regardless of sequential reentrancy on this
thread). In those cases where the lock must be held, the whole result is
rendered noncomposable.

> > One simple example is
> >
> >     v.insert( v.begin(), x );
> >
> > where the vector can make an external call to the copy constructor
or
> > assignment operator of X while being in an inconsistent state.

Yes. And in a sequential program we can write vector to be correct and
composable for such code, even in the presence of recursion, right? (I
think you have to do most or all of it just to get exception safety.) If
you must call external code, you arrange to reestablish your invariants,
and you're composable.

But in a concurrent program, if a lock must be held across the call(s),
then it is impossible to write the locking code to be composable,
because locks are inherently noncomposable.

Herb