Definition
The Too Much Milk problem models two roommates who share a refrigerator and, who make sure the refrigerator is always well stocked with milk.
Example Situation
| Time | Roommate 1 | Roommate 2 |
|---|---|---|
| 3:00 | Look in fridge; out of milk. | |
| 3:05 | Leave for store. | |
| 3:10 | Arrive at store. | Look in fridge; out of milk. |
| 3:15 | Buy milk. | Leave for store. |
| 3:20 | Arrive home; put milk away. | Arrive at store. |
| 3:25 | Buy milk. | |
| 3:30 | Arrive home; put milk away. | |
| Oh no, too much milk! |
One can model each roommate as a thread and the number of bottles of milk in the fridge with a variable in memory. Two properties needs to be met for a solution: safety and liveliness.
Safety
A program never enters a bad state.
- In the too much milk problem, never more than one person buys a milk.
Liveliness
A program must, eventually, enter a good state.
- In the too much milk problem, if milk is needed, someone eventually buys it.
Solutions
Solution 1: Leave a note
The basic idea is to leave a note on the fridge before going to the store. The simplest idea to implement this is to set a flag when going to buy milk and to check this flag before going to buy milk.
if(milk == 0) // If no milk
{
if(!note) // If no note
{
leave note;
buy milk;
remove note;
}
}However, this implementation can violate safety; it makes the problem worse since it fails intermittenly!
| Thread A | Thread B |
|---|---|
if (milk == 0) | |
if (note == 0) | |
| Interleaves | if (milk == 0) |
if (note == 0) | |
note = 1; | Interleaves |
milk++; | |
note = 0; | |
| Interleaves | note = 1; |
milk++; | |
note = 0; |
Solution 2: Using two notes
- Thread A
leave note A;
if(!note B)
{
if(milk == 0)
buy milk;
}
remove note A;- Thread B
leave note B;
if(!note A)
{
if(milk == 0)
buy milk;
}
remove note B;This solution is safe. However, this solution does not ensure liveliness. Although it is unlikely to happen, but it is possible at worst case.
| Thread A | Thread B |
|---|---|
leave note A | |
| Interleaves | leave note B |
if (!note A) | |
(PASS) if (milk == 0) | |
(PASS) buy milk | |
if (!note B) | Interleaves |
(PASS) if (milk == 0) | |
(PASS) buy milk |
Solution 3: Busy waiting
- Thread A
leave note A;
while(note B)
;
if(milk == 0)
buy milk;
remove note A;- Thread B
leave note B;
if(!note A)
{
if(milk == 0)
buy milk;
}
remove note B;This solution is both safe and live. Since thread B does not have a loop, it will eventually finish its execution.
However, this solution is not very satisfying:
- It is complex and requires caregul reasoning to be convinced that it works.
- It is inefficient because thread A is busy waiting, consuming CPU resources.
- It may fail if the compiler or hardware reorders instructions.
Solution 4: Locks
lock.acquire();
if(milk == 0)
buy milk;
lock.release();