Not-so-classical problems

Prev: Less classical synchronization problems Next: Not remotely classical problems

The search-insert-delete problem

Three kinds of threads share access to a singly-linked list:

1. Searchers merely examine the list, so they can execute concurrently with each other.
2. Inserters add new items to the end of the list, and insertions must be mutually exclusive with other insertions.
3. One insert can proceed in parallel with any number of searches.
4. Deleters remove items from anywhere in the list.
5. At most one deleter can access the list at a time, and deletion must also be mutually exclusive with searches and insertions.

Exercise

Write code for searchers, inserters, and deleters that enforces this three-way categorical mutual exclusion.

The unisex bathroom problem

The synchronization constraints are:

1. There cannot be men and women in the bathroom at the same time.
2. There should never be more than three employees in the bathroom at the same time.

Exercise

Write a solution that enforces these constraints and avoids deadlock. For this version, do not worry about starvation.

No-starve unisex bathroom problem

The problem with the previous solution is that it allows starvation. A long line of women can arrive and enter while there is a man waiting, and vice versa.

Exercise

Fix the problem.

Baboon crossing problem

The rope can hold at most 5 baboons, and baboons traveling in opposite directions must never meet on the rope.

The desired properties are:

1. Once a baboon has begun to cross, it is guaranteed to get to the other side without meeting a baboon going the other way.
2. There are never more than 5 baboons on the rope.
3. A continuing stream of baboons crossing in one direction should not bar baboons going the other way indefinitely.

Exercise

Design a synchronization scheme that satisfies these constraints.

The Modus Hall Problem

This is a categorical exclusion problem with majority rule.

While one faction controls the critical section, members of the other faction accumulate in queue until they achieve a majority. Then they can bar new opponents from entering while they wait for the critical section to clear.

Exercise

Write code that implements categorical exclusion with majority rule.