[cpp-threads] High-level concurrency issues

[Hans Boehm]

Summarizing, it appears that the real difference arises for code that
looks like:

(A) Action that invalidates and reestablishes invariant.
(B) Call to unknown external routine.
(C) Action that invalidates and reestablishes invariant.

when I have the additional constraint that the entire sequence, in
particular both A and C, have to be appear atomic with respect to some
other action.  In the single-threaded case, this just works.  In the
multithreaded case, its easy to acquire and release the lock around
(A) and (B), but I cannot release the lock in the middle.

But this still doesn't look quite right.  Even in the single-threaded case,
I may end up invoking the code with respect to which this should appear atomic
as part of (B), hence effectively breaking atomicity.

Thus I'm still not quite sure I really understand the difference.

Hans

On Wed, 19 Oct 2005, Herb Sutter wrote:

> 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
>
>
> --
> cpp-threads mailing list
> cpp-threads at decadentplace.org.uk
> http://www.decadentplace.org.uk/cgi-bin/mailman/listinfo/cpp-threads
>