TITLE: portability and "test and set"

(Newsgroups: comp.lang.c++.moderated, 13 Feb 97)

[ FYI Steve Clamage is the chair of the ANSI X3J16 Committee
  (C++ Standards Committee). -adc ]


RICHTER: bokr@accessone.com (Bengt Richter) writes:

>	I wonder when/if we are going to get an "atomic"
>keyword analogous to "volatile" 


CLAMAGE: Stephen.Clamage@Eng.Sun.COM (Steve Clamage)

We already have the typedef sig_atomic_t in C standard header <signal.h>,
which defines the largest integral type which can be updated in a single
atomic operation.


[ Terminology:
	SMP = symmetric multiprocessing
	MT  = multi-threaded
  -adc ]


RICHTER:

>so that compilers can potentially
>automatically make use of the most effective CPU instructions for
>finegrained mutex logic in shared-memory SMP environments. Pretty
>soon SMP will probably be the rule rather than the exception.
> ...
>>and it turned out that even though a mutex (or guard) was used
>>to control access to the MT-enabled section of code, sometimes
>>2 threads on 2 cpus would execute the
>
>>	"if (condition)" 
>
>>statement at the same time, then wait for the mutex (guard) to
>			     ^^^^^
>I am not familiar with the paper, but this sounds like a case
>where two threads want to avoid hanging on a mutex by testing
>a "condition" assumed to reflect the state of the mutex. But
>an ordinary variable can't fully do that reliably, 


CLAMAGE:

The problem is not with the variable type, but in using an interruptable
sequence to test and set the variable. That is, a type which can
be atomically updated is a necessary condition, but not a sufficient
condition. It would still be possible for the variable to change
state between a test and a modify instruction.

The usual solution lies in an uninterruptable machine instruction,
often called "test-and-set". This instruction will set a bit in
a variable and return its previous state; no other thread of execution
can change the state of that bit before this instruction finishes.
(Variations on test-and-set include test-and-increment, which is like
a "j++" on an integer variable, but which is an atomic operation.)

You synchronize threads by executing the test-and-set and looking
at the returned value. If the returned value is set, some other
thread has taken the mutex and you have to wait and try again later.
If the returned value is not set, you now own the mutex.

When you are finished, you clear the mutex. The clear operation must
be atomic so that the variable can't be in an indeterminate state when
some other thread executes a test-and-set on it. 

If a language directly supports multiprocessing, e.g. Ada and Java,
the compiler would probably make use of the platform's version of
test-and-set in generating code for its syncronization primitives.

If a language does not directly support multiprocessing, e.g. C and
C++, you cannot write portable code in that language to accomplish it.
(At least I don't think you can. I'm willing to be enlightened.)
Instead, you would use a library customized for the platform that
supported multiprocessing. For example, some versions of Unix
(particularly Solaris) come with such libraries which are callable
from any programming language. (The library interface is portable;
the implementation depends on the platform.)

In principle, C++ could add multiprocessing primitives to the base
language, or could add multiprocessing library routines. The C++
Committee did not want to take on such a project.