Information Technology Reference
In-Depth Information
5.1.2
Atomic operations
When we mentally disassembled the code in last example, we were able to reason
about atomic operations, indivisible operations that cannot be interleaved or
Definition: atomic
operations
split with or by other operations.
On most modern architectures a load or store of a 32-bit word from or
to memory is an atomic operation. So, our above analysis reasoned about
interleaving of atomic loads and stores to memory.
Conversely, a load or store is not always an atomic operation. Depending on
the implementation of the hardware, if two threads store the value of a a 64-bit
floating point register to a memory address, the final result might be the first
value, the second value, or a mix of the two.
In the next subsection, we will give an example of reasoning about a program
based on its atomic loads and stores to memory. Because of these challenges,
we then move on to a better approach that raises the level of abstraction by
constructing shared objects using synchronization variables.
5.1.3
Too much milk
Although one could, in principle, reason carefully about the possible interleav-
ings of dierent threads' atomic loads and stores, doing so is tricky. To illustrate
this, we will present three solutions to a simple problem called \Too much milk."
The too much milk problem models two roommates who share a refrigerator
and who|as good roommates|make sure the refrigerator is always well stocked
with milk. With such responsible roommates, the following scenario is possible:
Roommate 1's actions
Roommate 2's actions
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
3:35
Oh no!
We can model each roommate as a thread, and we can model the number of
bottles of milk in the fridge with a variable in memory. The question is, if the
only atomic operations on shared state are atomic loads and stores to memory,
can we devise a solution to the too much milk problem that ensures both safety
Denition: safety
(the program never enters a bad state) and liveness (the program eventually
Denition: liveness
enters a good state.) Here, we strive for the following properties:
1. Safety: Never more than one person buys milk.
