Part 3 of 7 · 2 min read
Requirements
Think of it this way. A traffic light at a one-lane bridge must satisfy several conditions. It must never let two cars in from opposite sides (safety). It must let a car in when the bridge is empty and nobody else is entering (no needless stopping). It must not make a car wait for ever while others pass again and again (fairness). The analogy stops in one place: traffic lights use a clock, and the solutions here cannot assume any timing.
A solution to the critical-section problem must satisfy three requirements:
- Mutual exclusion. If one thread is executing in its critical section, no other thread is executing in its critical section.
- Progress. If no thread is in its critical section and some threads want to enter, only the threads that want to enter take part in choosing who goes next, and the choice cannot be postponed for ever. A thread in its remainder section must not block the others.
- Bounded waiting. After a thread has asked to enter, there is a limit on the number of times other threads enter before it does. This means that nobody starves (page 2 of Level 3).
In plain words: The solution may not assume anything about the speed of the threads or about the number of processors, except that every thread makes progress at some speed above zero. It also may not assume that the scheduler is fair.
The three requirements are different in kind. Mutual exclusion is a safety property: nothing bad ever happens. Progress and bounded waiting are liveness properties: something good eventually happens. A solution that never lets anyone in satisfies mutual exclusion and is useless. It fails progress.
Mutual exclusion
Mutual exclusion is the property that at most one thread is inside its critical section at any moment; together with progress and bounded waiting, it defines a correct solution of the critical-section problem.
Example: if thread A is between the load and the store of balance, thread B must be held back at its entry section until A has left.
Check yourself: 1. Which requirement fails if a solution lets nobody in? 2. Which of the three is a safety property? 3. Why must a solution not assume a fair scheduler?