[cpp-threads] RE: "Agenda" for august 23-25 concurrency meeting

[Nick Maclaren]

Herb Sutter <hsutter at microsoft.com> wrote:
>
> I am under the impression that not having transitivity would break
> essentially every algorithm falling into the following general case: a
> lock-free multi-variable invariant maintained by more than one thread,
> where the two threads update disjoint parts of the invariant.

PLEASE don't say this is not having transitivity!  I know that I am
sounding very academic and purist, but this is actually a very important
point.  The issue being discussed is NOT whether to honour transitivity,
which is agreed, but whether the serial ordering of a thread should be
involved.  The true transitivity failure occurs in code like this:

    X == 0 in all threads
    Thread B:  waiting on P, held by A
    Thread C:  waiting on Q, held by B

    Thread A:   X = 1;
                release P, with full release semantics

    Thread B:   wake up as P is released, with full acquire semantics
                /* No reference made to X in this section */
                release Q, with full release semantics

    Thread C:   wake up as Q is released, with full acquire semantics
                what is X?

There have been implementations where X would be 0, because there was
no DIRECT communication between A and C.  I haven't seen any since the
1980s, but there are good architectural performance reasons to allow
this.  However, as experience indicated that no normal user can handle
it, the design has been buried.  This is what I call the 'pairwise'
model, and involves a TRUE failure of transitivity.

The other reason that it is important is that almost everyone is still
thinking in terms of pure memory accesses, and only two types of those
('local' and 'potentially global').  Well, as the design is extended
to real applications, we have something like a dozen types of state
that have memory-like properties.  We are going to have to decide how
many of those use the same transitivity model as memory (and, if so,
whether local or global).  So this problem will recur again then, and
it REALLY will cause confusion if people refer to discrepancies with
(say) IEEE 754 flags, I/O state or signalling as transitivity failure.

Incidentally, the I/O issue is a really big issue on clusters, both with
cluster file systems and NFS, because most imply transitivity but don't
actually honour it.  For example, the NFS specification does honour it,
but nobody (not even Sun) honours the specification because it prevents
ALL caching and is unusably slow.  In practice it rarely catches people,
but most users get awfully confused when they do get caught ....

I don't expect the I/O issue to be major for threading, but I do expect
some of the others to be.  Signalling in particular, though I know that
it is a POSIX/Microsoft matter and not a C++ one.


Regards,
Nick Maclaren,
University of Cambridge Computing Service,
New Museums Site, Pembroke Street, Cambridge CB2 3QH, England.
Email:  nmm1 at cam.ac.uk
Tel.:  +44 1223 334761    Fax:  +44 1223 334679