Art of Multiprocessor Programming
Maurice Herlihy and Nir Shavit
Some Terms
- A safety property states that some "bad thing" never happens. For example, a traffic light never displays green in all
directions, even if the power fails.
- A liveness property states that a particular good thing will happen. For example, a red traffic light will eventually turn green.
- The problem of making sure that only one thread at a time can execute a particular block of code is called the
mutual exclusion problem.
- The property of deadlock-freedom ensures that at least one thread will eventually gain access to some resource.
- The property of starvation-freedom ensures that every thread will eventually gain access to some resource.
- Transient communication requires both parties to participate at the same time.
Shouting, gestures, or cell phone calls are examples of transient commun- ication.
- Persistent communication allows the sender and receiver to participate at dif-
ferent times. Posting letters, sending email, or leaving notes under rocks are all examples of persistent communication.
- An example of persistent communication is that of interrupts. Thread A interrupts thread B by setting a bit at a location periodically checked by B. Sooner or later, B notices the bit has been set and reacts. After reacting, B typically resets the bit (A cannot reset the bit).