Chapter 11

Chapter 11 Low level synchronization: Algorithms
Objectives

To give examples of the use of semaphores, then event counts and sequencers, to solve problems that require both mutual exclusion and condition synchronisation, sometimes on more than one condition.

Points to emphasise

When we have implemented semaphore operations atomically we can use them to solve higher level problems.
The difficulty of understanding concurrent programs and writing correct ones.
Eventcounts and sequencers are presented as an alternative to semaphores.

Some of the analysis in the original paper was superseded by Lamport’s paper (1978).

Possible difficulties

Presenting concurrent programs to large classes. Students might not appreciate the difficulties if solutions to the classic problems are only presented in lectures. Some additional private work is needed.

Teaching hints

The semaphore solution to the readers and writers problem illustrates the difficulties of counting how many synchronising signals to send when one doesn’t have a monitor-like structure to simplify matters. The high level language solutions of Chapter 11 are easier to understand and the semaphore solution illustrates is useful to look back on for purposes of comparison.
Consider in advance whether it possible for a compiler to provide more support than we have when using only semaphores.