![](https://csdnimg.cn/release/download_crawler_static/3202460/bg8.jpg)
10
° G. R. Andrews and F. B. Schneider
tiple instances of each declared process to
be created. By contrast, in other languages
(e.g., PLITS[Feldman, !979] and Ada
[U. S. Department of Defense, 1981]) pro-
cesses can be created at any time during
execution, which makes possible computa-
tions having a variable number of pro-
cesses.
3. SYNCHRONIZATION PRIMITIVES BASED
ON SHARED VARIABLES
When shared variables are used for inter-
process communication, two types of syn-
chronization are useful: mutual exclusion
and condition synchronization.
Mutual ex-
clusion
ensures that a sequence of state-
ments is treated as an indivisible operation.
Consider, for example, a complex data
structure manipulated by means of opera-
tions implemented as sequences of state-
ments. If processes concurrently perform
operations on the same shared data object,
then unintended results might occur. (This
was illustrated earlier where the statement
x :ffi x + 1 had to be executed indivisibly
for a meaningful computation to result.) A
sequence of statements that must appear
to be executed as an indivisible operation is
called a
critical section.
The term "mutual
exclusion" refers to mutually exclusive ex-
ecution of critical sections. Notice that the
effects of execution interleavings are visible
only if two computations access shared var-
ibles. If such is the case, one computation
can see intermediate results produced by
incomplete execution of the other. If two
routines have no variables in common, then
their execution need not be mutually exclu-
sive.
Another situation in which it is necessary
to coordinate execution of concurrent proc-
esses occurs when a shared data object is in
a state inappropriate for executing a partic-
ular operation. Any process attempting
such an operation should be delayed until
the state of the data object (i.e., the values
of the variables that comprise the object)
changes as a result of other processes exe-
cuting operations. We shall call this type
of synchronization
condition synchroniza-
tion. 9
Examples of condition synchroniza-
tion appear in the simple batch operating
system discussed above. A process attempt-
9 Unfortunately, there is no 'commonly agreed upon
term for this.
ing to execute a "deposit" operation on a
buffer (the buffer being a shared data ob-
ject) should be delayed if the buffer has no
space. Similarly, a process attempting to
"fetch" from a buffer should be delayed if
there is nothing in the buffer to remove.
Below, we survey various mechanisms for
implementing these two types of synchro-
nization.
3.1 Busy-Waiting
One way to implement synchronization is
to have processes set and test shared vari-
ables. This approach works reasonably well
for implementing condition synchroniza-
tion, but not for implementing mutual ex-
clusion, as will be seen. To signal a condi-
tion, a process sets the value of a shared
variable; to wait for that condition, a proc-
ess repeatedly tests the variable until it is
found to have a desired value. Because a
process waiting for a condition must re-
peatedly test the shared variable, this tech-
nique to delay a process is called
busy-wait-
ing
and the process is said to be
spinning.
Variables that are used in this way are
sometimes called
spin locks.
To implement mutual exclusion using
busy-waiting, statements that signal and
wait for conditions are combined into care-
fully constructed protocols. Below, we pres-
ent Peterson's solution to the two-pro-
cess mutual exclusion problem [Peterson,
1981]. (This solution is simpler than the so-
lution proposed by Dekker [Shaw, 1974].)
The solution involves an
entry protocol,
which a process executes before entering its
critical section, and an
exit protocol,
which
a process executes after finishing its critical
section:
process P1;
loop
Entry Protocol;
Critical Section;
Exit Protocol;
Noncritical Section
end
end
process P2;
loop
Entry Protocol;
Critical Section;
Exit Protocol;
Noncritical Section
end
end
Computing Surveys, Vol. 15, No. 1, March 1983