Information Technology Reference
In-Depth Information
Case 3: ( 0,0 ). We know that thread B must not currently be executing
any of the lines marked B1-B5. We also know that either noteA==1 or
milk > 0 will be true from this time forward ( noteAORmilk is also a
stable property.) But, this means that B can not buy milk in the future
(either the test at B1 or B2 must fail), which contradicts our assumpti on
that both A and B buy milk.
Liveness. Unfortunately, solution 2 does not ensure liveness. In particular,
it is possible for both threads to set their respective notes, for each thread to
check the other thread's note, and for both threads to decide not to buy milk.
This brings us to solution 3.
Solution 3. We now present solution 3 of 3. 3
Solution 2 was safe because a thread would avoid buying milk if there was
any chance that the other thread might buy milk. For solution 3, we will make
sure that at least one of the threads determines whether the other thread has
bought milk or not before deciding whether or not to buy. In particular, we do
the following:
Path A
Path B
noteA=1; //leavenoteA
while(noteB==1){ //waitfornonoteB
;
noteB=1; //leavenoteB
if(noteA==0){ //ifnonoteA
if(milk==0){ //ifnomilk
milk++; //buymilk
} //
} //
noteB=0; //removenoteB
//spin
}
if(milk==0){ //ifnomilk**M**
milk++; //buymilk
}
noteA=0; //removenoteA
We can show that solution 3 is safe using a similar argument to the one we
used for solution 2.
To show that solution 3 is live, observe that code path B has no loops, so
eventually thread B must finish executing the listed code and eventually, noteB
==0 becomes true and remains true. Therefore, eventually thread A must reach
line M and decide whether to buy milk. If it finds M==1 , then milk has been
bought, and we are live. If it finds M==0 , then it will buy milk, and we are
live.
5.1.4
Discussion
The above discussion shows that|assuming that instructions are executed in
program order|it is possible to devise a solution to \Too much milk" that is
both safe and live using nothing but atomic load and store operations on shared
memory. However, the solution we developed is not terribly satisfying.
3 This one will work, but even better answers come in the next section.
 
Search WWH ::




Custom Search