Introduction to Algorithms, Third Edition

Figure 27.5
Illustration of the determinacy race in R
ACE
-E
XAMPLE
.
(a)
A computation dag show-
ing the dependencies among individual instructions. The processor registers are
r
1
and
r
2
. Instruc-
tions unrelated to the race, such as the implementation of loop control, are omitted.
(b)
An execution
sequence that elicits the bug, showing the values of
x
in memory and registers
r
1
and
r
2
for each
step in the execution sequence.
printed. Conversely, if the effect were that processor 2 executed all its instructions
before processor 1, the value
2
would still be printed. When the instructions of the
two processors execute at the same time, however, it is possible, as in this example
execution, that one of the updates to
x
is lost.
Of course, many executions do not elicit the bug. For example, if the execution
order were
h
1; 2; 3; 7; 4; 5; 6; 8
i
or
h
1; 4; 5; 6; 2; 3; 7; 8
i
, we would get the cor-
rect result. That’s the problem with determinacy races. Generally, most orderings
produce correct results—such as any in which the instructions on the left execute
before the instructions on the right, or vice versa. But some orderings generate
improper results when the instructions interleave. Consequently, races can be ex-
tremely hard to test for. You can run tests for days and never see the bug, only to
experience a catastrophic system crash in the field when the outcome is critical.
Although we can cope with races in a variety of ways, including using mutual-
exclusion locks and other methods of synchronization, for our purposes, we shall
simply ensure that strands that operate in parallel are
independent
: they have no
determinacy races among them. Thus, in a