Less classical synchronization problems

Prev: Classical synchronization problems Next: Not-so-classical problems

The dining savages problem

Any number of savage threads run:

while True:
    getServingFromPot()
    eat()

One cook thread runs:

while True:
    putServingsInPot(M)

The synchronization constraints are:

1. Savages cannot invoke getServingFromPot() if the pot is empty.
2. The cook can invoke putServingsInPot(M) only if the pot is empty.

Exercise

Add code for the savages and the cook that satisfies the synchronization constraints.

The barbershop problem

The barbershop has a waiting room with n chairs and one barber chair.

Additional constraints:

1. Customer threads should invoke getHairCut().
2. If a customer arrives when the shop is full, it can invoke balk(), which does not return.
3. The barber thread should invoke cutHair().
4. When the barber invokes cutHair(), there should be exactly one thread invoking getHairCut() concurrently.

Exercise

Write a solution that guarantees these constraints.

The FIFO barbershop

In the previous solution there is no guarantee that customers are served in arrival order.

Exercise

Modify the barbershop solution so that customers are served in the order they pass the turnstile.

Hint in the prompt: You can refer to the current thread as self, so if you write self.sem = Semaphore(0), each thread gets its own semaphore.

Hilzer’s Barbershop problem

The synchronization constraints are:

1. Customers invoke, in order, enterShop(), sitOnSofa(), getHairCut(), and pay().
2. Barbers invoke cutHair() and acceptPayment().
3. Customers cannot invoke enterShop() if the shop is at capacity.
4. If the sofa is full, an arriving customer cannot invoke sitOnSofa().
5. When a customer invokes getHairCut(), there should be a corresponding barber executing cutHair() concurrently, and vice versa.
6. It should be possible for up to three customers to execute getHairCut() concurrently, and up to three barbers to execute cutHair() concurrently.
7. The customer has to pay() before the barber can acceptPayment().
8. The barber must acceptPayment() before the customer can exit.

Exercise

Write code that enforces the synchronization constraints for Hilzer’s barbershop.

The Santa Claus problem

Additional specifications:

1. After the ninth reindeer arrives, Santa must invoke prepareSleigh(), and then all nine reindeer must invoke getHitched().
2. After the third elf arrives, Santa must invoke helpElves(). Concurrently, all three elves should invoke getHelp().
3. All three elves must invoke getHelp() before any additional elves enter and increment the elf counter.

Santa should run in a loop so he can help many sets of elves. You can assume that there are exactly 9 reindeer, but there may be any number of elves.

Exercise

Write synchronization code for Santa, the reindeer, and the elves that satisfies these requirements.

Building $H_{2}O$

As each thread passes the barrier, it should invoke bond(). You must guarantee that all the threads from one molecule invoke bond() before any of the threads from the next molecule do.

In particular:

1. If an oxygen thread arrives at the barrier when no hydrogen threads are present, it has to wait for two hydrogen threads.
2. If a hydrogen thread arrives at the barrier when no other threads are present, it has to wait for an oxygen thread and another hydrogen thread.

Exercise

Write synchronization code for oxygen and hydrogen threads that enforces these constraints.

River crossing problem

The ferry can hold exactly four people. It is not permissible to put one hacker in the boat with three serfs, or one serf with three hackers. Any other combination is safe.

As each thread boards the boat it should invoke board(). You must guarantee that all four threads from each boatload invoke board() before any of the threads from the next boatload do.

After all four threads have invoked board(), exactly one of them should call rowBoat(). It does not matter which thread calls it, as long as exactly one does.

Exercise

Write synchronization code for hackers and serfs that enforces these constraints.

The roller coaster problem

Suppose there are n passenger threads and a car thread. The car holds C passengers, where C < n.

Additional details:

1. Passengers should invoke board() and unboard().
2. The car should invoke load(), run(), and unload().
3. Passengers cannot board until the car has invoked load().
4. The car cannot depart until C passengers have boarded.
5. Passengers cannot unboard until the car has invoked unload().

Exercise

Write code for the passengers and car that enforces these constraints.

Multi-car Roller Coaster problem

Additional constraints:

1. Only one car can be boarding at a time.
2. Multiple cars can be on the track concurrently.
3. Since cars cannot pass each other, they have to unload in the same order they boarded.
4. All the threads from one carload must disembark before any of the threads from subsequent carloads.

Exercise

Modify the previous solution to handle these additional constraints. You can assume that there are m cars, and that each car has a local variable named i containing an identifier between 0 and m - 1.