Information Technology Reference
In-Depth Information
The world's second-simplest cooperating-threads program. Suppose
that initially
y=12
and we run a program with two threads that do the fol-
lowing:
Thread 0 Thread 1
x=y+1;y=y*2;
Q: What are the possible final values of
x
?
A: We can get
x=13
if Thread 0 executes first or
x=25
if Thread 1 executes
first. More precisely, we get
x=13
if Thread 0 reads
y
before Thread 1 updates
y
or we get
x=25
if Thread 1 updates
y
before Thread 0 reads
y
.
The world's third-simplest cooperating-threads program. Suppose that
initially
x=0
and we run a program with two threads that do the following:
Thread 0 Thread 1
x=x+1;x=x+2;
Q: What are the possible final values of
x
?
A: Obviously, we can get
x=3
. For example, Thread 0 can run to completion
and then Thread 1 can start and run to completion. However, we can also get
x=2
or
x=1
. In particular, when we write a single statement like
x=x+
1
, compilers on many processors produce multiple instructions such as (1) load
memory location
x
into a register, (2) add 1 to that register, and (3) store the
result to memory location
x
. If we mentally disassemble the above program into
simple pseudo-assembly-code, we can see some of the possibilities.
One Interleaving
Another Interleaving
Yet Another Interleaving
loadr1,x
loadr1,x
loadr1,x
addr2,r1,1
loadr1,x
loadr1,x
storex,r2
addr2,r1,1
addr2,r1,1
loadr1,x
addr2,r1,2
addr2,r1,2
addr2,r1,2 storex,r2
storex,r2
storex,r2
storex,r2 storex,r2
final:
x==3
final:
x==2
final:
x==1
Already, for this 2-line program, the complexity of reasoning about race
conditions and interleavings is beginning to grow: not only would one have to
reason about all possible interleavings of statements, but one would have to
mentally disassemble the programs and reason about all possible interleavings
of assembly instructions. (And if the compiler and hardware can reorder those
instructions, things are even worse.)
