``Classical'' Synchronization Problems

Tom Kelliher, CS42

Oct. 11, 1996

``Classical'' Synchronization Problems

First Readers-Writers Problem

We looked at the second Readers-Writers problem --- writer priority.

First r-w problem --- readers have priority.

• Implement using semaphores.

• Implement using locks and condition variables.

Dining Philosophers

Five philosophers, five chopsticks, five chairs, a table, a bowl of noodles.

Some ``solutions:''

while (1)
{
   think;
   pick up left chopstick;
   pick up right chopstick;
   eat;
   put down left chopstick;
   put down right chopstick;
}

while (1)
{
   think;
   while (haven't obtained both chopsticks)
   {
      pick up left chopstick;
      if (right chopstick is available)
         pick up right chopstick;
      else
         put down left chopstick;
   }
   eat;
   put down left chopstick;
   put down right chopstick;
}

while (1)
{
   think;
   while (haven't obtained both chopsticks)
   {
      if (both chopsticks available)
      {
         pick up left chopstick;
         pick up right chopstick;
      }
   }
   eat;
   put down left chopstick;
   put down right chopstick;
}

The real solution: put a total order on the chopsticks.

while (1)
{
   think;
   pick up lower-numbered chopstick;
   pick up higher-numbered chopstick;
   eat;
   put down lower-numbered chopstick;
   put down higher-numbered chopstick;
}

The Sleeping Barber Problem

A barbershop consists of a waiting room with N chairs, and the barber room containing the barber chair. If there are no customers to be served the barber goes to sleep. If a customer enters the barbershop and all chairs are busy, then the customer leaves the shop. If the barber is busy, then the customer sits in one of the available free chairs. If the barber is asleep, the customer wakes the barber up. Write a program to coordinate the barber and the customers.

Global variables:

Semaphore door(0);      // Mutex to shared variables.
Semaphore chair(0);     // Haircut synch., barber sleep.
Semaphore q(0);         // Waiting customers.

bool sleeping = FALSE;  // Barber sleeping.
int waiting = 0;        // # of waiting customers.

Barber:

door.signal();
while (1)
{
   door.wait();

   if (waiting == 0)
   {
      sleeping = TRUE;
      door.signal();
      chair.wait();
   }
   else
   {
      q.signal();
      --waiting;
      door.signal();

   cut hair;         // Rendezvous.
   chair.wait();     // Synch.
}

Customer:

door.wait();
if (waiting == N)
{
   door.signal();
   leave;
}
else if (sleeping)
{
   sleeping = FALSE;
   chair.signal();
   door.signal();
   get hair cut;     // Rendezvous.
   chair.signal();   // Synch.
}
else
{
   ++waiting;
   door.signal();    // Fairness problem???
   q.wait();
   get hair cut;     // Rendezvous.
   chair.signal();   // Synch.
}

Implement using locks and condition variables.