RFC: Multithreading design constraints

From: scleary_at_[hidden]
Date: 2000-06-06 09:04:09

> >No.  The compiler may not remove expressions with side effects, and both
the
> >constructor and destructor have side effects.  [3.7.2/3]
> 
> You're assuming that they have side effects, if they are declared as
> externals then I think that I agree with you.

"side effects" is defined in [1.9/7] as "changes in the state of the
execution environment."  Specifically, "accessing an object designated by a
volatile lvalue, modifying an object, calling a library I/O function, or
calling a function that does any of those operations."  In this case, it
either modifies the object or calls a function that modifies the object.

If the constructor takes a lock, then that is a change in the state of the
execution environment.  Note that even expressions with side-effects may be
optimized away *if* the compiler can *prove* that the "observable behavior"
[1.9/6] would be the same -- for example, a program that produced no output
and wrote to no volatile data could be optimized away completely.

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.

> I think you're getting ahead of yourself here - imagine a simple test and
> set lock, the constructor may be out of line (in assembler), but the
> destructor would typically just set the "lock" (usually an int) to zero. 
> The obvious implementation would place the destructor inline, but in this
> case there are no side effects - the compiler just sees an inline function
> that does "lock.data = 0", since the lock appears to the compiler to be
> completely unrelated to the surrounding code (it doesn't know that its
> supposed to be a lock after all), it can reorder the instructions as it
> sees fit.

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

> I'm talking about things beyond the scope of the compiler here - consider
> that we protect some floating point code, depending upon the processor
this
> may be executed in parellel to subsequent integer instructions, behaviour
> on a modern PIII will be very different to behaviour on an old 386 with fp
> emulation.  As modern cpu's become more complex and do more "out of order
> execution", then this becomes more of an issue - but only if you are
> writing your own locks in assembler.

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!

> Yes signals (what win32 calls events and POSIX condition variables) would
> be useful as well, maybe I drew the line too tightly.

One thing we're going to have to settle on is terminology.  Here's the
terminology I have been using when dealing with multithreaded
synchronization (it's a place to start):
  Lock - Either locked or unlocked.  Initialized to unlocked.  Any thread
may lock it, which (if it is already locked) will block until unlocked.  A
thread may unlock it only if it is locked and that thread was the last
thread to lock it.
  Mutex - (Also called "Binary Semaphore").  Either locked or unlocked.
Initialized to unlocked.  Any thread may lock it, which (if it is already
locked) will block until unlocked.  Any thread may unlock it if it is
locked.
  Semaphore - Has a free count, passed to the initialization routine.  Any
thread may lock it; if the free count is 0, that thread will block until it
is unlocked; otherwise, the free count is decremented.  Any thread may
unlock it, which increments the free count.
  Reader-Writer Lock (RWLock) - Has a number of readers (init'ed to 0).  Any
thread may request a read lock, which (if there is a write lock) will block
until the write lock is released; then the number of readers is incremented.
Any thread that has previously acquired a read lock may release that read
lock (as long as it has not already been released), which decrements the
number of readers.  Any thread may request a write lock, which (if there is
a write lock or the number of readers > 0) will block until there are no
unreleased locks; then the write lock is granted.  Any thread that has
previously acquired a write lock may release that write lock (as long as it
has not already been released).
  Condition Variable - Any thread may wait on it, which blocks until the
next broadcast.  Any thread may broadcast it, which releases all waiting
threads.
  Event - Either signalled or unsignalled.  Any thread may set the state to
signalled.  Any thread may set the state to unsignalled.  Any thread may
wait for the state to become signalled, which will block until the state is
signalled.
  Gate - Either open or closed.  Any thread may open the gate.  Any thread
may close the gate.  Any thread may wait for the gate to open, which will
block until the gate is open.  Any thread may atomically open and close the
gate, releasing any waiting threads.

I believe what POSIX calls a "critical section" is the same as my "critical
section".  What Win32 calls an "Event" is what I call a "Gate".  All three
of these are closely related; maybe in the final outcome, we could drop my
"Event".

As Beman pointed out, the use of the term "signal" should be discouraged,
since it already has another definition.  I think I used it in a previous
post -- sorry.

Note that some more "advanced" (what I consider less "pure") operations for
the above objects are not listed: waits with timeouts and try-locks.

More complicated synchronization objects that I use (these are constructed
from the above):
  Monitor - Contains a Lock and a Condition Variable.  Any thread may enter
the monitor, which locks the Lock.  Any thread may exit the monitor, which
unlocks the lock.  Any thread may block on the monitor, which unlocks the
lock, waits on the condition variable, and locks the lock.  Any thread may
signal the monitor, which broadcasts the condition variable.
  Mailbox - Templated on a message type T; has a message queue.  Any thread
may receive a message, which (if the message queue is empty) will block
until a message arrives, then returns the oldest message.  Any thread may
send a message, which will place the message in the message queue and return
immediately.

I have implemented all of these object types on Win32.  I also have some
code for some of these types being based on other sync objects (they can be
based on each other).  I've been multi-thread programming for many years
now, and look forward to seeing this kind of project on Boost!

        -Steve

P.S.  One thing I have not been able to dream up is an efficient portable
interface for is waiting for multiple objects (multiple events, etc).  Maybe
we could just provide an "accessor" member function with a
platform-dependent return type for now, and let any such multiple waits be
in the user code, specific to the platform.

P.P.S.  The list of primitives above is not complete -- spin locks, etc. I
have not yet worked with at all.