Not-so-classical problems

• The search-insert-delete problem
• The unisex bathroom problem
• Baboon crossing problem

The search-insert-delete problem

This one is from Andrews’s Concurrent Programming .

Three kinds of threads share access to a singly-linked list: searchers, inserters and deleters. Searchers merely examine the list; hence they can execute concurrently with each other. Inserters add new items to the end of the list; insertions must be mutually exclusive to preclude two inserters from inserting new items at about the same time. However, one insert can proceed in parallel with any number of searches. Finally, deleters remove items from anywhere in the list. At most one deleter process can access the list at a time, and deletion must also be mutually exclusive with searches and insertions.

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

The unisex bathroom problem

I wrote this problem⁹ when a friend of mine left her position teaching physics at Colby College and took a job at Xerox.

She was working in a cubicle in the basement of a concrete monolith, and the nearest women’s bathroom was two floors up. She proposed to the Uberboss that they convert the men’s bathroom on her floor to a unisex bathroom, sort of like on Ally McBeal.

The Uberboss agreed, provided that the following synchronization constraints can be maintained:

• There cannot be men and women in the bathroom at the same time.

• There should never be more than three employees squandering company time in the bathroom.

Of course the solution should avoid deadlock. For now, though, don’t worry about starvation. You may assume that the bathroom is equipped with all the semaphores you need.

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.

fix the problem.

No-starve unisex bathroom solution

As we have seen before, we can use a turnstile to allow one kind of thread to stop the flow of the other kind of thread. This time we’ll look at the male code:

turnstile.wait()

    maleSwitch.lock(empty)

turnstile.signal()



    maleMultiplex.wait()

        # bathroom code here

    maleMultiplex.signal()



maleSwitch.unlock (empty)

As long as there are men in the room, new arrivals will pass through the turnstile and enter. If there are women in the room when a male arrives, the male will block inside the turnstile, which will bar all later arrivals (male and female) from entering until the current occupants leave. At that point the male in the turnstile enters, possibly allowing additional males to enter.

The female code is similar, so if there are men in the room an arriving female will get stuck in the turnstile, barring additional men.

This solution may not be efficient. If the system is busy, then there will often be several threads, male and female, queued on the turnstile. Each time empty is signaled, one thread will leave the turnstile and another will enter. If the new thread is the opposite gender, it will promptly block, barring additional threads. Thus, there will usually be only 1-2 threads in the bathroom at a time, and the system will not take full advantage of the available concurrency.

Baboon crossing problem

This problem is adapted from Tanenbaum’s Operating Systems: Design and Implementation . There is a deep canyon somewhere in Kruger National Park, South Africa, and a single rope that spans the canyon. Baboons can cross the canyon by swinging hand-over-hand on the rope, but if two baboons going in opposite directions meet in the middle, they will fight and drop to their deaths. Furthermore, the rope is only strong enough to hold 5 baboons. If there are more baboons on the rope at the same time, it will break.

Assuming that we can teach the baboons to use semaphores, we would like to design a synchronization scheme with the following properties:

• Once a baboon has begun to cross, it is guaranteed to get to the other side without running into a baboon going the other way.

• There are never more than 5 baboons on the rope.

• A continuing stream of baboons crossing in one direction should not bar baboons going the other way indefinitely (no starvation).

I will not include a solution to this problem for reasons that should be clear.