RFC: Multithreading design constraints

From: scleary_at_[hidden]
Date: 2000-06-05 08:38:34

Here's by 2 bits :)

> WHAT IS "THREAD SAFE"?
> ~~~~~~~~~~~~~~~~~~~
> 
> Level 0:
> (Unsafe)
>
> Level 1:
> (Apartment)
> Unrelated instances of the object can be safely used in separate threads
> (by unrelated I mean "not a copy of").  Objects that meet this guarantee
> have no unprotected non-constant shared global data, but may be mutable.
> 
> Level 2:
> (weak guarantee)
> Unrelated instances of an object can be used in separate threads.
> An object may be shared between thread without external locking if all the
> threads that operate on the object treat it as constant (access no mutable
> data, call no non-constant member functions).
> An shared object treated as non-constant by any one thread, must be
> protected by an external lock for all accesses to that object 
> (const and non-constant) by all threads.
> 

Levels 1.5 & 2.5 (?):
Unrelated or related instances of an object can be used in separate threads.
. .

The "related/unrelated" brings in another dimension to the thread safety
levels.

> Level 3:
> (strong guarantee)
> Objects in this category may be shared between threads without any
external
> locking being required.
> 
> ****
> 
> In addition we can define sub-levels for startup/exit code guarantees:
> 

I like these startup/exit codes, but this brings in another issue.  We can
have a class (specifically, I'm thinking of my pool allocators) that are
Level 1.5b under systems with static locks, but under Win32 are demoted to
Level 1.5a.  We need to be aware of the levels on different platforms for
the same code, so that our users don't have to re-design when they port.

> WHAT IS A LOCK?
> ~~~~~~~~~~~~
>
> ...
> 
> However there are a number of possible defects with this idiom:
> 
> Issue 1:
> The variable g is never used.
> I'm not actually sure whether this is a problem or not, but in principle
> the compiler could decide that variable g has no observable effect and
> remove it altogether...

No.  The compiler may not remove expressions with side effects, and both the
constructor and destructor have side effects.  [3.7.2/3]

> Issue 2:
> Compiler instruction reordering:
> As far as the compiler is concerned operations on the lock object are
> independent of those on the protected data, the compiler is therefore free
> to reorder the assembler it produces so that the guard objects destructor
> is over before the protected code has finished executing.  

No.  The compiler may not re-order instructions unless it *really knows*
what it is doing!  As mentioned above "guard"s constructor and destructor
have side effects.  Furthermore, there is a sequence point at the end of
each full-expression [1.9/16], and at each sequence point, all side effects
from previous code are complete, and no future side effects are complete
[1.9/7].

> Issue 3:
> Hardware out of order execution:
> Most modern hardware can now execute instructions in parallel or "out of
> order", That means that when the guard objects destructor executes there
> may still be instructions that have been scheduled, but not executed. 

No.  We are guaranteed an abstract machine by the Standard, which follows an
"execution sequence" [1.9/3], which implies a strictly sequential execution.
The compiler *is* free to parallel its instructions, but only under similar
rules as seen above -- guaranteeing no extra side effects, removing no
expected side effects, honoring sequence points, etc.

> Issue 4:
> Dangling braces:
> The main problem with the scoped guard object is that the extent of the
> lock may not coincide with the extent of the scope
>    ...
> Solution: add an "acquire" method to the guard object that lets us control
> the locks duration (an analogous example would be "reset" on the smart
> pointers):

Agreed.  But I would recommend two methods, "acquire" and "release", rather
than just "acquire" with a boolean parameter.

> Issue 5:
> Unnamed variable bug:
> One problem with the scoped variable method is that it is too easy to
> forget to name the guard variable. . .

Yes.  This is a serious problem, since a small coding error may cause a very
subtle bug.  The "if" idiom may help as a reminder, but if we forget that,
too. . .

> Issue 6:
> Generic thread coding:
> One common idiom may be to add a "threaded" bool template parameter to
> template classes, when true the object is thread safe, when false its
> thread unsafe (or offers a lower guarantee - see smart pointers for
> example).

Then have the default value be BOOST_MT?  Just a thought :)

> Issue 7:
> Emulation slowdown:
> There are many different kinds of locks, only some of which will be
> natively available on a given platform.

Right.  I think we can assume that Mutexes and Binary Semaphores will be
available on all platforms.  All other synchronization primitives can be
constructed from these, but we should, if possible, use native types.

Although I do not think that we will have situations where we will want to
choose at compile-time whether to use a RWLock or just a Mutex, based on
what's available.  I think our code should choose the sync primitive that
satisfies our need, and if there's native code for it, use that, otherwise
use the emulated code.  (So I don't think we need a synchronization_traits
class).

> WHAT KIND OF LOCKS?
> ~~~~~~~~~~~~~~~~
> 
> Although there are a lot of possible lock types there would seem to be
> three that are key and should be available on all platforms:
> 
> static lock: need not be re-entrant, but must be an aggregate type to
allow
> for static initialisation.
> thread lock: should be re-entrant and default constructable.
> process lock: should be re-entrant and sharable between processes, the
> constructor should take a string to act as a name for the lock.

There's another dimension of considerations.  Can the lock be used as a
"signal"?  For example, if thread A owns a mutex, can it wait on that mutex
until thread B "releases" it?  It's been a few years since I've worked on
UNIX, but I don't think that was an issue.  But under Win32, if you do that
a few times, you BSOD.  That's why I made a distinction above between a
"Mutex", which I define as only releasable if you own it, and a "Binary
Semaphore", which can be used as a "signal".

> ATOMIC OPERATIONS
> ~~~~~~~~~~~~~~~~

I don't know enough about these to contribute.  I follow a simple guideline
which says "assume nothing is atomic".

> let me know what you think (and what I've missed!).

Thank you for taking this up, John!  Hopefully, we will hash something out.
:)

        -Steve