In
computer science, the sleeping barber problem is a classic inter-process
communication and synchronization problem between multiple operating system
processes. The problem is analogous to that of keeping a barber working when
there are customers, resting when there are none, and doing so in an orderly manner.
The Sleeping Barber Problem is often attributed to Edsger Dijkstra (1965), one of the pioneers in computer science.
Problem Statement
 |
| Sleeping Barber problem |
 |
| Flow chart for Sleeping barber problem |
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.
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 naïve 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.
Boundary Cases
à 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.
à 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.
Implementation
semaphore.sem_wait()
locks the semaphore.sem_post() unlocks it.
Semaphore
Customers = 0;
Semaphore
Barber = 0;
Mutex
accessSeats = 1;
int NumberOfFreeSeats = N;
Barber {
while(1) {
/* waits for a customer (sleeps). */
sem_wait(Customers);
/* mutex to protect the number of
available seats.*/
sem_wait(accessSeats);
/* a chair gets free.*/
NumberOfFreeSeats++;
/* bring customer for haircut.*/
sem_post(Barber);
/* release the mutex on the chair.*/
sem_post(accessSeats);
/* barber is cutting hair.*/
}
}
Customer {
while(1) {
/* protects seats so only 1 thread
tries to sit in a chair if that's the case.*/
sem_wait(accessSeats);
if(NumberOfFreeSeats
> 0) {
/* sitting down.*/
NumberOfFreeSeats--;
/* notify the barber. */
sem_post(Customers);
/* release the lock */
sem_post(accessSeats);
/* wait in the waiting room if
barber is busy. */
sem_wait(Barber);
// customer is having hair cut
} else {
/* release the lock */
sem_post(accessSeats);
// customer leaves
}
}
}
A multiple sleeping barbers problem has the additional complexity of coordinating several barbers among the waiting customers.
References:
No comments:
Post a Comment