Sleeping barber problem
Encyclopedia
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.
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 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.
The Sleeping Barber Problem is often attributed to Edsger Dijkstra
(1965), one of the pioneers in computer science.
are also required to indicate the state of the system. For example, one might store the number of people in the waiting room.
A multiple sleeping barbers problem has the additional complexity of coordinating several barbers among the waiting customers.
Semaphore custReady = 0 # if 1, at least one customer is ready
Semaphore barberReady = 0
Semaphore accessWRSeats = 1 # if 1, the # of seats in the waiting room can be incremented or decremented
int numberOfFreeWRSeats = N # total number of seats in the waiting room
def Barber:
while true: # Run in an infinite loop.
wait(custReady) # Try to acquire a customer - if none is available, go to sleep.
wait(accessWRSeats) # Awake - try to get access to modify # of available seats, otherwise sleep.
numberOfFreeWRSeats++ # One waiting room chair becomes free.
signal(barberReady) # I am ready to cut.
signal(accessWRSeats) # Don't need the lock on the chairs anymore.
# (Cut hair here.)
def Customer:
while true: # Run in an infinite loop.
wait(accessWRSeats) # Try to get access to the waiting room chairs.
if numberOfFreeWRSeats > 0: # If there are any free seats:
numberOfFreeWRSeats-- # sit down in a chair
signal(custReady) # notify the barber, who's waiting until there is a customer
signal(accessWRSeats) # don't need to lock the chairs anymore
wait(barberReady) # wait until the barber is ready
# (Have hair cut here.)
else: # otherwise, there are no free seats; tough luck --
signal(accessWRSeats) # but don't forget to release the lock on the seats!
# (Leave without a haircut.)
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, the sleeping barber problem is a classic inter-process communication
Inter-process communication
In computing, Inter-process communication is a set of methods for the exchange of data among multiple threads in one or more processes. Processes may be running on one or more computers connected by a network. IPC methods are divided into methods for message passing, synchronization, shared...
and synchronization
Synchronization
Synchronization is timekeeping which requires the coordination of events to operate a system in unison. The familiar conductor of an orchestra serves to keep the orchestra in time....
problem between multiple operating system
Operating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...
processes
Process (computing)
In computing, a process is an instance of a computer program that is being executed. It contains the program code and its current activity. Depending on the operating system , a process may be made up of multiple threads of execution that execute instructions concurrently.A computer program is a...
. 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 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 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 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.
The Sleeping Barber Problem is often attributed to Edsger Dijkstra
Edsger Dijkstra
Edsger Wybe Dijkstra ; ) was a Dutch computer scientist. He received the 1972 Turing Award for fundamental contributions to developing programming languages, and was the Schlumberger Centennial Chair of Computer Sciences at The University of Texas at Austin from 1984 until 2000.Shortly before his...
(1965), one of the pioneers in computer science.
Solution
Many possible solutions are available. The key element of each is a mutex, which ensures that only one of the participants can change state at once. The barber must acquire this mutex exclusion before checking for customers and release it when he begins either to sleep or cut hair. A customer must acquire it before entering the shop and release it once he is sitting in either a waiting room chair or the barber chair. This eliminates both of the problems mentioned in the previous section. A number of semaphoresSemaphore (programming)
In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment....
are also required to indicate the state of the system. For example, one might store the number of people in the waiting room.
A multiple sleeping barbers problem has the additional complexity of coordinating several barbers among the waiting customers.
Implementation
- The following pseudo-code guarantees synchronization between barber and customer and is deadlock free, but may lead to starvationResource starvationIn computer science, starvation is a multitasking-related problem, where a process is perpetually denied necessary resources. Without those resources, the program can never finish its task....
of a customer. The functions wait (originally P, for the Dutch proberen = try) and signal (originally V, for the Dutch verhogen = raise) are functions provided by the semaphoresSemaphore (programming)In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment....
.
- These three are mutexes (only 0 or 1 possible)
Semaphore custReady = 0 # if 1, at least one customer is ready
Semaphore barberReady = 0
Semaphore accessWRSeats = 1 # if 1, the # of seats in the waiting room can be incremented or decremented
int numberOfFreeWRSeats = N # total number of seats in the waiting room
def Barber:
while true: # Run in an infinite loop.
wait(custReady) # Try to acquire a customer - if none is available, go to sleep.
wait(accessWRSeats) # Awake - try to get access to modify # of available seats, otherwise sleep.
numberOfFreeWRSeats++ # One waiting room chair becomes free.
signal(barberReady) # I am ready to cut.
signal(accessWRSeats) # Don't need the lock on the chairs anymore.
# (Cut hair here.)
def Customer:
while true: # Run in an infinite loop.
wait(accessWRSeats) # Try to get access to the waiting room chairs.
if numberOfFreeWRSeats > 0: # If there are any free seats:
numberOfFreeWRSeats-- # sit down in a chair
signal(custReady) # notify the barber, who's waiting until there is a customer
signal(accessWRSeats) # don't need to lock the chairs anymore
wait(barberReady) # wait until the barber is ready
# (Have hair cut here.)
else: # otherwise, there are no free seats; tough luck --
signal(accessWRSeats) # but don't forget to release the lock on the seats!
# (Leave without a haircut.)
See also
- Producers-consumers problem
- Dining philosophers problemDining philosophers problemIn computer science, the dining philosophers problem is an example problem often used in concurrent algorithm design to illustrate synchronization issues and techniques for resolving them....
- Cigarette smokers problemCigarette smokers problemThe cigarette smokers problem is a concurrency problem in computer science, originally described in 1971 by S. S. Patil.-Problem description:Assume a cigarette requires three ingredients to smoke:#Tobacco#Paper#A match...
- Readers-writers problemReaders-writers problemIn computer science, the first and second readers-writers problems are examples of a common computing problem in concurrency. The two problems deal with situations in which many threads must access the same shared memory at one time, some reading and some writing, with the natural constraint that...