Designing a Barbershop Monitor with POSIX Threads

Suppose we want to design a solution to a version of the Barbershop Problem, starting from scratch. This can be approached in the following stages:

1. identify the entities involved,
   their components,
   their attributes
2. distinguish active entities (processes)
   from passive entities (data structures)
3. identify important states of the entities
4. identify the events/actions that drive the system
5. elaborate and refine the actions, using pseudo-code
6. identify points at which the actions require a process to wait
7. specify the logical condition for which the process is waiting
8. identify who is responsible for signaling the corresponding wakeups
9. make sure there is a wakeup signaling action for every wait action
10. protect the critical sections with a mutex
    viewing the entire problem as one monitor
11. expand the wait operations into calls to pthread_cond_wait
12. expand the signal operations into calls to pthread_cond_signal
13. refine the logical wait conditions into specific data structures
14. keep refining until you have a program written in C

Identify the entities involved & their components

customer
barber
shop
 door
 set of waiting_chairs  -- a queue
   for each chair: occupant
 set of barber_chairs
   for each chair: occupant

Identify important states of the entities

customer
  (waiting_at_door
   waiting_in_chair
   being_served
   none_of_these)
barber
  (waiting_for_customer,
   working)
shop
 door
 set of waiting_chairs
   (occupied
    unoccupied)
 set of barber_chairs
   (occupied
    unoccupied)

Distinguish active entities (processes) from passive entities (data structures)

customer (active)
barber (active)
shop (passive)
 door
 set of waiting_chairs
 set of barber_chairs

Identify important states of the entities

Identify the events/actions that drive the system

customer
  -----
  arrive_at_the_door
barber
  -----
  complete_haircut & start_new_haircut

Elaborate and refine the actions, using pseudo-code

customer:
loop
   arrive_at_the_door;
   wait until can enter door;
   get into waiting chair;
   wait until a barber is ready;
   get out of waiting chair;
   get into barber chair;
   wait until barber is done cutting;
   leave the shop;
end loop;

barber:
loop
   wait for a customer;
   start cutting hair;
   complete_haircut;
end loop;

Identify points at which the actions require a process to wait & specify the logical condition for which the process is waiting

customer:
loop
   arrive_at_the_door;
   *wait* until can enter door; (1)
   get into waiting chair;
   *wait* until a barber is ready; (2)
   get out of waiting chair;
   get into barber chair;
   *wait* until barber is done cutting; (3)
   leave the shop;
end loop;

barber:
loop
   *wait* for a customer; (4)
   start cutting hair;
   complete_haircut;
end loop;

Identify who is responsible for signaling the corresponding wakeups & make sure there is a wakeup signaling action for every wait action

customer:
loop
   arrive_at_the_door;
   *wait* until can enter door; (1)
   get into waiting chair;
   *signal* barber that a customer is here; (3)
   *wait* until a barber is ready; (2)
   get out of waiting chair;
   *signal* someone else to come in the door; (1)
   get into barber chair;
   *wait* until barber is done cutting; (3)
   leave the shop;
end loop;

barber:
loop
   *wait* for a customer; (4)
   *signal* a customer to come to the chair; (2)
   start cutting hair;
   complete_haircut;
   *signal* customer to leave shop; (3)
end loop;

Protect the critical sections with a mutex viewing the entire problem as one monitor

customer:
loop
   pthread_mutex_lock (&M);
   arrive_at_the_door;
   *wait* until can enter door; (1)
   get into waiting chair;
   *signal* barber that a customer is here; (3)
   *wait* until a barber is ready; (2)
   get out of waiting chair;
   *signal* someone else to come in the door; (1)
   get into barber chair;
   *wait* until barber is done cutting; (3)
   leave the shop;
   pthread_mutex_unlock (&M);
end loop;

barber:
loop
   pthread_mutex_lock (&M);
   *wait* for a customer; (4)
   *signal* a customer to come to the chair; (2)
   start cutting hair;
   complete_haircut;
   *signal* customer to leave shop; (3)
   pthread_mutex_unlock (&M);
end loop;

Expand the wait operations into calls to pthread_cond_wait

customer:
loop
   pthread_mutex_lock (&M);
   arrive_at_the_door;
   /* *wait* until can enter door; (1) */
   while (no seats are available)
      pthread_cond_wait (&self.C, &M);
   get into waiting chair;
   *signal* barber that a customer is here; (3)
   /* *wait* until a barber is ready; (2) */
   while (no barbers are available)
      pthread_cond_wait (&self.C, &M);
   get out of waiting chair;
   *signal* someone else to come in the door; (1)
   get into barber chair;
   /* *wait* until barber is done cutting; (3) */
   while (barber is cutting)
      pthread_cond_wait (&self.C, &M);
   leave the shop;
   pthread_mutex_unlock (&M);
end loop;

barber:
loop
   pthread_mutex_lock (&M);
   /* *wait* for a customer; (4) */
   while (waiting_chairs_queue.empty)
      pthread_cond_wait (&self.C, &M);
   *signal* a customer to come to the chair; (2)
   start cutting hair;
   complete_haircut;
   *signal* customer to leave shop; (3)
   pthread_mutex_unlock (&M);
end loop;

Expand the signal operations into calls to pthread_cond_signal

customer:
loop
   pthread_mutex_lock (&M);
   arrive_at_the_door;
   /* *wait* until can enter door; (1) */
   while (no seats are available)
      pthread_cond_wait (&self.C, &M);
   get into waiting chair;
   /* *signal* barber that a customer is here; (4) */
   for (every barber)
      pthread_cond_signal (&barber.C);
   /* *wait* until a barber is ready; (2) */
   while (no barbers are available)
      pthread_cond_wait (&self.C, &M);
   get out of waiting chair;
   /* *signal* someone else to come in the door; (1) */
   for (every person at door)
      pthread_cond_signal (&person.C);
   get into barber chair;
   /* *wait* until barber is done cutting; (3) */
   while (barber is cutting)
      pthread_cond_wait (&self.C, &M);
   leave the shop;
   pthread_mutex_unlock (&M);
end loop;

barber:
loop
   pthread_mutex_lock (&M);
   /* *wait* for a customer; (4) */
   while (waiting_chairs_queue.empty)
      pthread_cond_wait (&self.C, &M);
   mycustomer = waiting_chairs_queue.dequeue;
   /* *signal* mycustomer to come to the chair; (2) */
   pthread_cond_signal (&mycustomer.C);
   start cutting hair;
   complete_haircut;
   /* *signal* customer to leave shop; (3) */
   pthread_cond_signal (&mycustomer.C);
   pthread_mutex_unlock (&M);
end loop;

Refine the logical wait conditions into specific data structures

 customer
   
 barber
   is_cutting : boolean
 door -- a queue
 waiting_chairs  -- a queue

customer:
loop
   pthread_mutex_lock (&M);
   arrive_at_the_door;
   door.enqueue(self);
   while (waiting_chairs.is_full)
      pthread_cond_wait (&self.C, &M);
   door.dequeue(self);
   waiting_chairs.enqueue(self);
   for (every barber)
      pthread_cond_signal (&barber.C);
   while (no barbers are available)
      pthread_cond_wait (&self.C, &M);
   waiting_chairs.dequeue(self);
   person = door.dequeue();
   pthread_cond_signal (&person.C);
   get into barber chair;
   while (barber is cutting)
      pthread_cond_wait (&self.C, &M);
   leave the shop;
   pthread_mutex_unlock (&M);
end loop;
----------------------
barber:

loop
   pthread_mutex_lock (&M);
   while (waiting_chairs.is_empty())
      pthread_cond_wait (&self.C, &M);
   mycustomer = waiting_chairs.dequeue();
   pthread_cond_signal (&mycustomer.C);
   start cutting hair;
   complete_haircut;
   pthread_cond_signal (&mycustomer.C);
   pthread_mutex_unlock (&M);
end loop;

Keep refining until you have a program written in C

etc.

Why not Use Numbers?

customer entering shop:

  ...assume mutex M is locked here...
  /* take a number; */
  mynumber = takenumber;
  takenumber++;
  while (mynumber != servednumber)
      pthread_cond_wait (&self.C, &M);
  ...mutex M is locked again here...

another customer leaving waiting chair:

  servednumber++;
  for (every customer at door)
    pthread_cond_signal (&customer.C);

What is wrong with this?

• Don't we end up needing a queue anyway?
• If so, then why bother with the numbers?
• What happens when the counters overflow?

Explanation of pthread_cond_wait

pthread_cond_wait (&C, &M) has the effect of:

   pthread_mutex_unlock (&M);
   sleeps until some random wakeup
     or pthread_cond_signal is called for C
   pthread_mutex_lock (&M);

but the first tww steps are ATOMIC

Application to Ferry Example

1. identify the entities involved,
   their components,
   their attributes -- [given in the assignment]
2. distinguish active entities (processes)
   from passive entities (data structures) -- [two choices: (a) just the passengers; (b) passengers + ferry operator]
3. identify important states of the entities -- [given in the assignment]
4. identify the events/actions that drive the system -- [given in the assignment: the four function calls]
5. elaborate and refine the actions, using pseudo-code -- [your job]
6. identify points at which the actions require a process to wait -- [your job]
7. specify the logical condition for which the process is waiting -- [your job]
8. identify who is responsible for signaling the corresponding wakeups -- [your job]
9. make sure there is a wakeup signaling action for every wait action -- [your job]
10. protect the critical sections with a (single) mutex
    viewing the entire problem as one monitor -- [trivial: lock at beginning of each the four exported functions, and unlock just before return]
11. expand the wait operations into calls to pthread_cond_wait -- [simpel, if you use one CV per thread]
12. expand the signal operations into calls to pthread_cond_signal -- [simple]
13. refine the logical wait conditions into specific data structures -- [your job]
14. keep refining until you have a program written in C -- [your job]

int
ferry_shore_volunteer () {
  passenger_ptr self = get_current_thread_record();
  pthread_mutex_lock (&M);
  if not_in_queue (self, shore_queue[self->side])
    put_in_queue (self, shore_queue [self->side]);
  ferry_update_state ();
  while (self->should_wait) pthread_cond_wait (&(self->CV), &M);
  pthread_mutex_unlock (&M);
  if (self->pulling) return 0;
  else return 1;
}

int
ferry_board_volunteer () {
  passenger_ptr self = get_current_thread_record();
  pthread_mutex_lock (&M);
  if not_in_queue (self, boat_queue)
     put_in_queue (self, boat_queue);
  ferry_update_state ();
  while (self->should_wait) pthread_cond_wait (&(self->CV), &M);
  pthread_mutex_unlock (&M);
  if (self->pulling) return 0;
  else return 1;
}

void
ferry_update_state (passenger_ptr self) {
  int state_changed = 1;
  while (state_changed) {
     switch (ferry.state) {
     ...
     ... if discover a thread t should wake up, 
         pthread_cond_signal (&(t->CV));
     ...
     }
  }
}

This just a pseudo-code sketch of one way of coding a solution to this problem. Please don't slavishly try to copy the above.