Not remotely classical problems

Prev: Not-so-classical problems Next: Synchronization in Python

The sushi bar problem

There are 5 seats at the sushi bar. If you arrive while there is an empty seat, you can sit immediately. But if you arrive when all 5 seats are full, you have to wait for the entire party to leave before you sit down.

Exercise

Write code for customers entering and leaving the sushi bar that enforces these requirements.

Non-solution

What is wrong with this solution?

mutex.wait()
if must_wait:
    waiting += 1
    mutex.signal()
    block.wait()
 
    mutex.wait()      # reacquire mutex
    waiting -= 1
 
eating += 1
must_wait = (eating == 5)
mutex.signal()
 
# eat sushi
 
mutex.wait()
eating -= 1
if eating == 0:
    n = min(5, waiting)
    block.signal(n)
    must_wait = False
mutex.signal()

Follow-up

See if you can come up with two different correct solutions.

Hint: Neither solution uses any additional variables.

The child care problem

State regulations require that there is always one adult present for every three children.

Exercise

Write code for child threads and adult threads that enforces this constraint in a critical section.

Non-solution

Hailperin’s near-solution uses:

multiplex = Semaphore(0)

and adult code like:

multiplex.signal(3)
 
# critical section
 
multiplex.wait()
multiplex.wait()
multiplex.wait()

What is the problem?

Minimal change

Solve this problem with a minimal change.

Extended child care problem

One feature of the simple solution is that an adult thread waiting to leave can prevent child threads from entering, even when it would still be legal for a child to enter.

Exercise

Write a solution to this problem that avoids unnecessary waiting.

Hint: Think about the dancers in Section dancers.

The room party problem

The synchronization constraints are:

1. Any number of students can be in a room at the same time.
2. The Dean of Students can only enter a room if there are no students in the room, or if there are more than 50 students in the room.
3. While the Dean is in the room, no additional students may enter, but students may leave.
4. The Dean may not leave the room until all students have left.
5. There is only one Dean of Students.

Exercise

Write synchronization code for students and for the Dean of Students that enforces all of these constraints.

The Senate Bus problem

Riders come to a bus stop and wait for a bus. When the bus arrives, all the waiting riders invoke boardBus(), but anyone who arrives while the bus is boarding has to wait for the next bus. The capacity of the bus is 50 people; if there are more than 50 people waiting, some will have to wait for the next bus.

When all the waiting riders have boarded, the bus can invoke depart(). If the bus arrives when there are no riders, it should depart immediately.

Exercise

Write synchronization code that enforces all of these constraints.

Follow-up

Can you find a solution to this problem using the “I’ll do it for you” pattern?

The Faneuil Hall problem

There are three kinds of threads: immigrants, spectators, and one judge.

Constraints:

1. Immigrants must invoke enter(), checkIn(), sitDown(), swear(), getCertificate(), and leave().
2. The judge invokes enter(), confirm(), and leave().
3. Spectators invoke enter(), spectate(), and leave().
4. While the judge is in the building, no one may enter(), and immigrants may not leave().
5. The judge cannot confirm() until all immigrants who have invoked enter() have also invoked checkIn().
6. Immigrants cannot getCertificate() until the judge has executed confirm().

Exercise

Write synchronization code that enforces these constraints.

Extended Faneuil Hall problem

Modify this solution to handle the additional constraint that after the judge leaves, all immigrants who have been sworn in must leave before the judge can enter again.

Dining Hall problem

Students in the dining hall invoke dine() and then leave(). After invoking dine() and before invoking leave(), a student is considered ready to leave.

The synchronization constraint is that a student may never sit at a table alone. A student is considered to be sitting alone if everyone else who has invoked dine() invokes leave() before that student has finished dine().

Exercise

Write code that enforces this constraint.

Extended Dining Hall problem

Students invoke getFood(), dine(), and then leave(). After invoking getFood() and before invoking dine(), a student is considered ready to eat. After invoking dine(), a student is considered ready to leave.

A student may never sit at a table alone. A student is considered to be sitting alone if either:

1. The student invokes dine() while there is no one else at the table and no one else ready to eat.
2. Everyone else who has invoked dine() invokes leave() before that student has finished dine().

Exercise

Write code that enforces these constraints.