CSS 503A (Spring 2021): Systems Programming

The Sleeping Barbers problem is a "toy problem" that illustrates some of the complexities of concurrency. The scene is a barber shop with one or more barbers and zero or more chairs in the waiting area. The barbers sleep in their chairs until a customer arrives to wake up one of the barbers.

The awoken barber cuts the customer's hair. Meanwhile other customers may arrive. If all the barbers are busy and there's an available chair in the waiting room, the arriving customer takes a number and sits in one of the waiting-room chairs.

If all the chairs are full, an arriving customer just leaves without taking a number.

When a barber finishes with the customer, the customer gives the barber payment and the barber collects the payment. The customer leaves satisfied. The barber then services the next customer if one is waiting. Otherwise, the barber goes back to sleep in his or her chair.

At the end of the simulation, the shop closes. No new customers arrive, but the barbers will continue to provide service to any waiting customers, until the last customer leaves and all the barbers have gone back to sleep.

You will write a C++ program using pthreads that simulates the Sleeping Barbers problem. The program will take six parameters in its argument vector: number of barbers, numbers of chairs in the waiting room, barber's average service time (in milliseconds ¹), standard deviation in service time, average customer arrival interval, and duration of the simulation (seconds).

Since there are so many parameters, you may find this RUN script more readable for invoking the barbers program.

Run the simulation for 5 minutes with average service time of 1200 milliseconds and standard deviation of 200ms. Assuming there are 3 barbers and customers arrive on average every 400ms, determine approximately how many waiting-room chairs are required to avoid turning away customers.

The actors in the system are the Shop, the Barbers, and the Customers,. The Barbers and the Shop persist for the duration of the simulation. The Customers are ephemeral.

Actors

While the solution will be implemented in C++ using the pthreads library, the concept of actors simplifies concurrency modeling.

The essential idea is that actors are objects on steroids. Each instance corresponds to a separate thread and does whatever it does concurrently with other actors. Actors communicate by sending messages to each other.

Typically, actor-based systems use a queue-like data structure to exchange the messages but message generation is usually wrapped in a message-specific function. Such functions are termed methods; this was the original concept behind object-oriented design.

For each kind of actor, create a C++ class that has a run method which will be executed in it's own thread All the actions of the actor are performed by the public run and any of its private helper functions.

All other public methods of the (receiving) actor class are called by other (sending) actors and simply communicate with the receiver. Since the sleeping barbers problem doesn't require the complexity of a message-queue system, the message methods of an actor can simply set state or flag variable(s) to indicate that a particular message has been sent (using appropriate low-level concurrency control). In other words, the actor class public methods (except for run) are called by other actors to send a message to the receiving actor.

It's important to be clear on the distinction between the actions of one actor and the actions of another actor.

Class Design

The Shop class should hold global state, including the list of sleeping barbers and the queue of waiting customers (at all times, at least one of these lists should be empty). The action of the shop will be to instantiate customers at random intervals.

The customer should check the shop for a sleeping barber or an empty waiting-room chair. This needs to be an atomic operation because we don't want a race condition between the barber finishing with a prior customer and going back to sleep, while the customer sees the barber is busy and takes a seat in the waiting room. The Shop should hold the mutex controlling the customer's selection of barber or waiting-room chair.

A skeleton program barbers-skel.cc has been provided. Use it, or don't use it as you see fit.

Notes & Hints

When the shop closes, no new customers arrive, but the barbers will continue service until there are no more waiting customers.

Use std::normal_distribution to compute the barber's service time for each customer. Clip the minimum service time to 80% of the barber's average service time.

The program will be creating short-lived customer threads, so it's important that they do not leak resources. One way is to add a Reaper or Undertaker actor that receives messages from expiring Customer threads. Alternatively, you can fold that functionality into the Shop thread.

A third, simpler way is to create the customer threads in detached mode and have the thread-start function delete the actor, something like this:

class Actor{/*...*/};

void *run(void *arg) {
  Actor *actor = reinterpret_cast<Actor *>(arg);
  actor->run();
  delete actor;
  return nullptr;
}


main() {
  // Create thread in detached mode.
}

Use usleep for microsecond-level pauses to simulate thread activity (i.e. barber cutting hair). It's often helpful to include units in the variable name, so you don't get confused between seconds, milliseconds, microseconds, and nanoseconds.

The entire program is small enough to fit into a single source file, but you may prefer dividing it among several files. Either way will be acceptable.

Don't forget to include your recommendation for waiting-room size in the README file.

Assignment 2: Sleeping Barbers

Background

Actors

Class Design

Notes & Hints

Footnotes