[cpp-threads] High-level concurrency issues

[Herb Sutter]

(Sorry for the lag, I'm going to have slow responsiveness until after
C++ Connections is out of the way...)

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

Imagine two invariants, I1 and I2, maintained under locks (for readers
and/or writers).

In the ST case, the problem arises only when we have
  a) a cycle
  b) on one thread.
There has to be a "reentrant" path on the same thread whereby code that
is reading/modifying I1 calls into code that reads/modifies I2 that then
arcs back to read/modify I1.

In the MT case, the problem arises whenever we have
  a) _any_ two threads
  b) one thread arcs from within I1 into I2
  c) the other thread can concurrently arc from within I2 into I1.
(Note that the ST case is a degenerate form of this more general case.)
In this general case, no call cycle is necessary anywhere in the system,
and it is sufficient to have any two threads with conflicting arcs to
have a potential deadlock.

For example, consider a system that allows plugins. In the initial
system, no thread uses both I1 and I2 at the same time. Then the user
downloads a plugin P1 that, while reading/modifying I1, can call into
code that can read/modify I2. This is still fine. Then the end user
downloads a plugin P2 that happens to read/modify I2 and pass it a
callback that can read/modify I1 -- by providing the second arc, we now
have a potential deadlock. So we have:

  - the original system is correct (deadlock-free)
  - P1 is correct on its own
  - P2 is correct on its own
  - the original system composed with P1 is correct
  - the original system composed with P2 is correct

We might even have done testing and analysis to prove each of the above.
But then:

  - the original system composed with P1 and P2 is not correct

And, worse luck, in this particular case the combination was composed
for the first time on the end user's machine (which is often the case in
practice). I could easily imagine situations where even with great
diligence it would not be possible to test and analyze that particular
combination in advance.

Absent the locks, we know how to write the above three pieces (original
system and two plugins) so that we can know they'll compose correctly.
With the locks, we don't.

Just a quick response, after having given it some background thought
over the past week, but I wanted to at least get a quick response out
before I go dark again... Thanks,

Herb