[boost] RFC: Multithreading design constraints

From: John Maddock (John_Maddock_at_[hidden])
Date: 2000-06-08 06:49:08

Steve,

>Just note that the burden of proof is on the *compiler*.  If we know that
the program output could be different if it re-ordered the lock/unlock,
then
no such proof could exist, therefore the compiler cannot re-order those
expressions.
<

Yes, the compiler can do anything it wants under the "as if" rule provided
that there is no change in observable behaviour, the standard defines
observable behaviour as:

"5 A conforming implementation executing a well-formed program shall pro-
  duce the same observable behavior as one  of  the  possible  execution
  sequences  of  the corresponding instance of the abstract machine with
  the same program and the same input.  However, if any  such  execution
  sequence  contains an undefined operation, this International Standard
  places no requirement on the  implementation  executing  that  program
  with  that  input  (not  even  with regard to operations preceding the
  first undefined operation).

6 The observable behavior of the abstract machine  is  its  sequence  of
  reads   and   writes  to  volatile  data  and  calls  to  library  I/O
  functions.4)"

The problem is that unless the compiler knows that a lock is in some way
"special", it can not know that the lock has an effect on observable
behaviour - my point was to try and show that we can "trick" a compiler
that knows nothing about threads into behaving the right way by defining
the lock methods as being externals - even now we are relying on the
compiler not performing some kind of global analysis.

>OK.  In this case, when we're not dealing with OS-supplied calls, then
that
>int data member should be volatile.

Why? Its not the reads and writes to the lock that are the problem, it's
how they relate to reads and writes to the data the lock protects.  One
option would be to declare both the lock and the data it protects as
volatile - both now become observable behaviour - and their the relative
sequence of reads/writes becomes well defined, at the expense of turning
off all optimisations for the data we're protecting, when we really just
want to limit the scope of optimisations.

>No processor can or will break the parameterized machine.  If the CPU does
2+ instructions in parallel, it will only do so if the outcome is
*proveably* equivalent.  That is, it may in fact do the last floating-point
operation while releasing the lock, but that's the same as doing the last
floating-point operation and then releasing the lock!<

I admit to being on shaky ground here :-)  However the processor will
basically do anything it wants in parallel unless a data hazard occurs -
remember that the lock and the data it protects are completely separate: no
data hazard occurs.  That means that another thread on another processor
could enter the protected section of code before the first processor has
completed its scheduled code - whether a data hazard happens next I'm not
sure - I guess as the instructions must have been scheduled then the answer
should be "yes", but I suspect that it depends upon the architecture,
whatever this isn't really C++ !

BTW take a look at what the standard guarantees for signals (its scary) -
on most single processor platforms there is no fundamental difference
between being interrupted by a signal and being interrupted by a
pre-emptive thread.

- John.