Art of Multiprocessor Programming

Maurice Herlihy and Nir Shavit

Introduction

• 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 communication.
• Persistent communication allows the sender and receiver to participate at different 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).
• In a producer-consumer problem, the producer will only produce a resource when it is needed, and only when no one is busy consuming; the consumer will consume only when the resource is present, and only when no one is producing.
• In the readers-writers problem, the reader must be able to read from several locations without interrupting any of the writers from writing.
• Amdahl's law: we have n concurrent processors, and fraction p of the job can be executed in parallel. Then the speedup S of moving from 1 processor to n processors is

<math>S = \frac{1}{1-p+p/n}</math>