Information Technology Reference
In-Depth Information
1 and the other with the value 2, the final value of the the variable depends on
which of the threads' writes nishes last.
Although this example is simple, the problem is severe because programs
need to work for any possible interleaving. In particular, recall that thread
programmers should not make any assumptions about the relative speed at
which their threads operate.
Worse, as programs grow, there is a combinatorial explosion in the number
of possible interleavings.
How can we reason about all possible interleavings of threads' actions in a
multi-million line program.?
2. Program execution can be nondeterministic.
Different runs of the same program may produce different results. For example,
the scheduler may make different scheduling decisions, the processor may run
at a different frequency, or another concurrently running program may affect
the cache hit rate. Even common debugging techniques|such as running a
program under a debugger, recompiling with the -g option instead of -O, or
adding a
printf()
|can change how a program behaves.
Jim Gray, the 1998 ACM Turing Award winner, coined the term Heisenbugs
for bugs that disappear or change behavior when you try to examine them.
Multi-threaded programming is a common source of Heisenbugs.
In contrast
Bohrbugs are deterministic and generally much easier to diagnose.
How can we debug programs whose behaviors change across runs?
3. Compilers and architectures reorder instructions.
Modern compilers and hardware will reorder instructions to improve perfor-
mance. This reordering is generally invisible to single-threaded programs; com-
pilers and processors take care to ensure that dependencies within a sequence
of instruction are preserved. However, this reordering can become visible when
multiple threads interact and observe intermediate states.
For example, consider the following code to compute
q
as a function of
p
.
Thread 1
Thread 2
while(!pIsInitialized)
;
q=anotherComputation(p);
p=someComputation();
pIsInitialized=true;
