Information Technology Reference
In-Depth Information
2. Liveness: If milk is needed, eventually somebody buys milk.
Simplifying assumption. Throughout our analysis in this section, we as-
sume that the instructions are executed in exactly the order written|neither
the compiler nor the architecture reorders instructions. Such an assumption is
crucial for reasoning about the order of atomic load and store operations, but
many modern compilers and architectures will violate it, so be careful about
using this approach.
With modern machines and compilers, in addition to the challenges discussed
in this section, one would also have to use memory barriers to constrain such
reordering, further complicating the problem. We discuss memory barriers later.
Solution 1. We first present solution 1 of 3.
1
The basic idea is for a roommate to leave a note on the fridge before leaving
for the store. The simplest way to leave this note|given our programming
model that we have shared memory on which we can perform atomic loads and
stores|is to set a ag when going to buy milk and to check this ag before
going to buy milk. We might have each thread run the following code:
if(milk==0){
//ifnomilk
if(note==0){
//ifnonote
note=1;
//leavenote
milk++;
//buymilk
note=0;
//removenote
}
}
Unfortunately, this implementation can violate safety. For example, the first
thread could execute everything up to and including the check of the
milk
value
and then get context switched. Then the second thread could run through all of
this code and buy milk. Finally, the first thread could be rescheduled, see that
note==0
is true, leave the note, buy more milk, and remove the note, leaving
the system with
milk==2
.
if(milk==0){
if(milk==0){
if(note==0){
note=1;
milk++;
note=0;
}
}
if(note==0){
note=1;
milk++;
note=0;
}
}
Oh no!
1
Two more solutions are coming. The reader should be suspicious.
