[cpp-threads] Ok, here is a modified model

[Nick Maclaren]

Here is what I suggest as a basic model for the nasty issues that
I raised.  As far as I can see, it is entirely compatible with
Hans's, but ties down some of the aspects that I was wittering on
about.  It obviously needs work :-)

I have taken arbitrary decisions on (a) the topology and (b) what
non-pthreads operations that imply synchronisation and serialisation.
The latter are selected because I know that they are used in a good
many real programs.  The former is chosen as a compromise between
efficiency and comprehensibility.


Local Synchronisation
---------------------

In this context, a full synchronisation operation is one that has an
synchronisation effect on ordinary memory access.  Atomic operations and
others that are defined to not do that are not included.

At a full synchronisation operation, whether with release or acquire
semantics or both, all actions performed in the current thread that do
not involve an external interaction are synchronised.  In particular,
none of the following may be moved over such an operation by a compiler:

    Data accesses, their results and other effects, whether ordinary,
volatile or atomic

    Entirely local state changes, such as the setting of the locale, the
setting of floating-point modes and flags, changes to signal handling
and calls to library functions that maintain internal state (such as
srand)

    Exceptions (in the Computer Science sense) caused by local data
accesses or state changes, including C++ exceptions, the setting of
errno, floating-point exception flags, signals and other forms of
interrupt

[ The above lists are exemplary and not restricted to current C++.
They clearly would need editing. ]


Synchronisation Between Threads
-------------------------------

When a thread A performs a synchronisation operation with release
semantics, then serialises itself with thread B ("B happens after A")
and then thread B performs a synchronisation operation with acquire
semantics, all memory updates that A performed before its
synchronisation operation are visible to B after its synchronisation
operation, and no memory updates that B performs after its
synchronisation operation are visible to A before its synchronisation
operation.

Serialisation is transitive, and any intermediate threads need not
perform synchronisation operations.  Thus the following sequence of
operations will cause thread B to see the update of X by thread A:

Thread A:
    X = 123;
    Synchronise with release semantics
    Send a message to thread C
Thread C:
    Wait for the message from thread A
    Send a message to thread B
Thread B:
    Wait for the message from thread C
    Synchronise with acquire semantics
    Z = X;

Note that, if thread C had accessed X, it would not necessarily have
seen the update of X, as it has not synchronisation operation.

[ The above uses the transitive topology.  I believe that using the
pairwise one will cause too many existing programs to fail, and too many
programmers to get confused, and using the global one is just too
constraining on implementations. ]


Intrinsic Synchronisation and Serialisation
-------------------------------------------

The following operations cause synchronisation or thread A to be
serialised with thread B ("B happens after A").  An implementation may
define other such operations.  Note that serialisation does not imply
synchronisation.

    A sets an atomic datum, B reads the value of that datum, and B sees
the changed value, then B happens after A

    Opening or closing a file, or attempting to do so, causes a
synchronisation operation with both release and acquire semantics,
between the call of the function and its return

    If A opens or closes a file, B attempts to open or close the file,
and B sees the changed state, then B happens after A

[ Note that this does NOT mean that opening and closing a single file
can be used as a serialised synchronisation - there is still a race
condition - but a lot of programs use file existence as a serialisation
primitive ]

    Calling fflush causes synchronisation with release semantics,
between the call of the function and its return

    When thread A writes some data to a file or FIFO and thread B reads
part or all of that data, the sequence of operations is as follows:
        A writes the data
        A performs a synchronisation operation with release semantics
        B happens after A
        B performs a synchronisation operation with acquire semantics
        B reads the data
[ Note that that is ALL that is specified - the exact location of the
synchronisation is unspecified ]

    When thread A sends a signal, semaphore or other message to thread
B, which is then received by B, the sequence of operations is as
follows:
        A sends the message
        A performs a synchronisation operation with release semantics
        B happens after A
        B performs a synchronisation operation with acquire semantics
        B receives the message
[ Note that that is ALL that is specified - the exact location of the
synchronisation is unspecified ]

Note that the mere passage of time, including the reading and checking
of clocks, is not a serialisation operation, let alone a synchronisation
one.

An implementation is recommended to support as many transitively causal
serialisations as is compatible with reasonable efficiency.  While it is
outside the scope of this standard, this should include thread A writing
some data to a FIFO to an alien process P, which reads the data and
writes some data to a FIFO to thread B, which then reads that data.  The
same should apply to sending Internet messages rather than using FIFOs.


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