The sleeping barber problem

An incorrect approach to this problem may lead to some issues like:

•  The barber could wait forever for a client and in the same time a client could wait forever for the barber
•  The clients may not respect their arrival order and this could lead to the fact that some of them

will never have the opportunity to sit on the barber's chair although they were waiting.

The problem analysis:

•  mutual exclusion(mutex): a client has to prevent another client to enter at the same time in the barbershop due to the fact that both of them will sit on the same chair and the barber would cut their hair at the same time
•  checking the state of the barber(sleep or awake)
•  checking the number of empty seats in the waiting room

This solution will use three semaphores:

•  clients: contains the number of clients that are in the waiting room
•  barbers: the number of barbers (0 or 1 ) who are idle, waiting for clients
•  mutex: which is used for mutual exclusion

It also uses a variable “wait” which counts the number of clients waiting, in fact it is a copy of clients and it is necessary because we cannot read the current value of a semaphore.

A possible solution can use nine semaphores for binary or general usage:

•  capacity: total number of chairs in the waiting room;
•  wait: number of waiting clients;
•  barbers: number of barbers;
•  hair_cutting: ensure us that a barber is performing only a task at once;
•  ready, done: specifies if there is a client ready or a client that is already hair cutted ;
•  payment: specifies if a payment is about to be done;
•  bill: specifies the end of the payment;
•  leave: specifies when the client leaves the barber's chair;

The Sleeping Barber Problem

The Problem

The problems are all related to the fact that the actions by both the barber and the customer (checking the waiting room, entering the shop, taking a waiting room chair, etc.) all take an unknown amount of time. For example, a customer may arrive and observe that the barber is cutting hair, so he goes to the waiting room. While he is on his way, the barber finishes the haircut he is doing and goes to check the waiting room. Since there is no one there (the customer not having arrived yet), he goes back to his chair and sleeps. The barber is now waiting for a customer and the customer is waiting for the barber. In another example, two customers may arrive at the same time when there happens to be a single seat in the waiting room. They observe that the barber is cutting hair, go to the waiting room, and both attempt to occupy the single chair.

Each customer, when he arrives, looks to see what the barber is doing. If the barber is sleeping, then the customer wakes him up and sits in the chair. If the barber is cutting hair, then the customer goes to the waiting room. If there is a free chair in the waiting room, the customer sits in it and waits his turn. If there is no free chair, then the customer leaves. Based on a naive analysis, the above description should ensure that the shop functions correctly, with the barber cutting the hair of anyone who arrives until there are no more customers, and then sleeping until the next customer arrives. In practice, there are a number of problems that can occur that are illustrative of general scheduling problems.

The analogy is based upon a hypothetical barber shop with one barber. The barber has one barber chair and a waiting room with a number of chairs in it. When the barber finishes cutting a customer's hair, he dismisses the customer and then goes to the waiting room to see if there are other customers waiting. If there are, he brings one of them back to the chair and cuts his hair. If there are no other customers waiting, he returns to his chair and sleeps in it.

References

The sleeping barber problem and the producer – consumer problem are somehow similar.

The producer – consumer problem uses a common shared memory area, where the producer

stores data and the consumer takes the data.

Tanenbaun A.S., “Modern Operating System”, 2nd Edition

Fortis F., “Sisteme de operare”, Editura Eubeea, 2005

The first issue appears when the producer wants to store some data in the memory area and this area is full and the second one when the consumer wants to read data from the memory area and this is empty.

Relationship with the Producer – Consumer Problem

When the waiting room is full, the clients are forced to leave the barbershop so process of adding new data in the memory area is suspended( just as in the producer-consumer case).

If the waiting room is empty, the barber would lie on the barber chair, doing nothing, taking a nap so the process of taking data from the memory area is suspended.

Real life applications:

-call-center;

-printers;

-the institution's ticket mechanism;

The solution for the first issue is to suspend the producer until the consumer takes at least one piece of data from the shared memory area and the solution for the second issue is to suspend the consumer until the producer stores new data in the memory area.

Actually, in the sleeping barber shop problem the role of the producer is played by the clients, the role of the consumer is played by the barber and the memory area is equivalent to the number of chairs in the waiting room.

Client's procedure

void client(void) {

down(&capacity);

enter_barbershop();

down(&wait);

wait_in_line();

down(&barbers);

leave_chair();

up(&wait);

prepare_haircut();

up(&ready);

down(&done);

finish_haircut();

down(&leave);

pay();

up(&payment);

down(&bill);

exit_barbershop();

up(&capacity);

}

Cashier's procedure

void casier(void) {

while (TRUE) {

down(&payment);

down(&hair_cutting);

accept_payment();

up(&hair_cutting);

up(&bill);

}

}

Barber's procedure

void barber(void) {

while (true) {

down(&ready);

down(&hair_cutting);

haircut();

up(&hair_cutting);

down(&leave);

up(barbers);

}

}

Semaphores

typedef int semaphore;

semaphore capacity=12;

semaphore wait=3;

semaphore barbers=3;

semaphore hair_cutting=3;

semaphore ready=0, done=0;

semaphore leave=0;

semaphore payment=0, bill=0;

The Solution

The problem can be generalized by considering more than one barber (multiple sleeping barbers problem).

Implementation

Remarks:

• There is no loop in the client's procedure because every client cuts his hair only once; in the barber's procedure there is a loop that ables the barber to take the next client
• The solution is from the book of A.S. Tanenbaum, Modern Operating Systems

Ovidiu Staniloiu

Adrian Secheres

Norberth Stancu

Constant and Global Variables

#define Chairs 5 /* number of chairs in the waiting room */

typedef int semaphore;

semaphore clients=0; /* number of clients waiting for service */

semaphore barber=0; /* number of barbers waiting for clients */

semaphore mutex=1; /* for mutual exclusion */

int wait=0; /* clients are waiting(not being cut) */

Barber's procedure

void barber(void)

{

while(TRUE)

{

down(&Clients); /* go to sleep if number of clients is 0 */

down(&mutex); /* acquire access to 'waiting' */

wait=wait-1; /* decrement count of waiting customers*/

up(&barbers); /* one barber is now ready to cut hair*/

up(&mutex); /*release 'wait'*/

cut_hair(); /*cut hair (outside critical region)*/

}

}

Client's procedure

void client(void)

{

down(&mutex); /*enter critical region*/

if(wait<Chairs){ /*if there are no free chairs, leave*/

wait=wait+1; /*increment count of waiting customers*/

up(&customers); /*wake up barber if necessary */

up(&mutex); /*release access to 'wait'*/

down(&barbers); /*go to sleep if number of free barbers is 0*/

get_haircut(); /*be seated and be serviced*/

}else{

up(&mutex); /*shop is full; do not wait*/

}

}