Sleeping barber problem


Sleeping barber problem

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 barber and his customers represent aforementioned processes.

The problem

The analogy is based upon a hypothetical barber shop with one barber, one barber chair, and a number of chairs for waiting customers. When there are no customers, the barber sits in his chair and sleeps. As soon as a customer arrives, he either awakens the barber or, if the barber is cutting someone else's hair, sits down in one of the vacant chairs. If all of the chairs are occupied, the newly arrived customer simply leaves.

The problem arises with attempting to coordinate this activity without bringing about any race conditions, and in this way is similar to many queueing problems. In fact, it is a classic example of a (double) rendezvous problem.Not implementing a proper solution can lead to the usual inter-process communication problems of starvation and deadlock. For example, the barber could end up waiting on a customer and a customer waiting on the barber, resulting in deadlock. Alternatively, customers may not decide to approach the barber in an orderly manner, leading to process starvation as some customers never get the chance for a hair cut even though they have been waiting.

The Sleeping Barber Problem is often attributed to Edsger Dijkstra (1965), one of the pioneers in fundamental programming.

A solution

The most common solution involves using three semaphores: one for any waiting customers, one for the barber (to see if he is idle), and a mutex. When a customer arrives, he attempts to acquire the mutex, and waits until he has succeeded. The customer then checks to see if there is an empty chair for him (either one in the waiting room or the barber chair), and if none of these are empty, leaves. Otherwise the customer takes a seat – thus reducing the number available (a critical section). The customer then signals the barber to awaken through his semaphore, and the mutex is released to allow other customers (or the barber) the ability to acquire it. If the barber is not free, the customer then waits. The barber sits in a perpetual waiting loop, being awakened by any waiting customers. Once he is awoken, he signals the waiting customers through their semaphore, allowing them to get their hair cut one at a time.

This problem involves only one barber, and it is therefore also called the "single sleeping barber problem". A "multiple sleeping barbers problem" is similar in the nature of implementation and pitfalls, but 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 starvation of a customer. P and V are functions provided by the semaphores.

*You need (as mentioned above): + Semaphore Customers = 0 + Semaphore Barber = 0 + Semaphore accessSeats (mutex) = 1 + int NumberOfFreeSeats = N //total number of seats

*The Barber (Thread/Process): while(true) { //runs in an infinite loop P(Customers) //tries to acquire a customer - if none is available he goes to sleep P(accessSeats) //at this time he has been awakened - want to modify the number of available seats NumberOfFreeSeats++ //one chair gets free V(Barber) //the barber is ready to cut V(accessSeats) //we don't need the lock on the chairs anymore //here the barber is cutting hair }

*The Customer (Thread/Process): P(accessSeats) //tries to get access to the chairs if ( NumberOfFreeSeats > 0 ) { //if there are any free seats NumberOfFreeSeats-- //sitting down on a chair V(Customers) //notify the barber, who's waiting that there is a customer V(accessSeats) //don't need to lock the chairs anymore P(Barber) //now it's this customers turn, but wait if the barber is busy //here the customer is having his hair cut } else { //there are no free seats //tough luck V(accessSeats) //but don't forget to release the lock on the seats //customer leaves without a haircut }

References

* "Modern Operating Systems (2nd Edition)" by Andrew S. Tanenbaum (ISBN 0-13-031358-0)
* "The Little Book of Semaphores" by Allen B. Downey, http://greenteapress.com/semaphores
* [http://www.cs.utexas.edu/users/EWD/transcriptions/EWD01xx/EWD123.html "Cooperating sequential processes"] by E.W. Dijkstra. Technical Report EWD-123, 1965, Technological University, Eindhoven, The Netherlands.

See also

* Producers-consumers problem
* Dining philosophers problem
* Cigarette smokers problem
* Readers-writers problem


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Barber (disambiguation) — Professions*barber *barber surgeonPeopleNotable people whose last name is or was Barber include*Alden G. Barber Boy Scouts of America Scouting notable, awardee of the Bronze Wolf in 1975 *Andrea Barber (born 1976), U.S. actress *Anthony Barber,… …   Wikipedia

  • Producer-consumer problem — In computer science, the producer consumer problem (also known as the bounded buffer problem) is a classical example of a multi process synchronization problem. The problem describes two processes, the producer and the consumer, who share a… …   Wikipedia

  • Dining philosophers problem — In 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. It was originally formulated in 1965 by Edsger Dijkstra… …   Wikipedia

  • Readers-writers problem — In 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 …   Wikipedia

  • Rendezvous problem — The rendezvous dilemma is related to the prisoner s dilemma and can be formulated in this way::Two young people have a date in a park they have never been to before. Arriving separately in the park, they are both surprised to discover that it is… …   Wikipedia

  • Semaphore (programming) — For other uses, see Semaphore (disambiguation). 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… …   Wikipedia

  • Deadlock — This article is about the computer science concept. For other uses, see Deadlock (disambiguation). A deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. It is often… …   Wikipedia

  • List of paradoxes — This is a list of paradoxes, grouped thematically. Note that many of the listed paradoxes have a clear resolution see Quine s Classification of Paradoxes.Logical, non mathematical* Paradox of entailment: Inconsistent premises always make an… …   Wikipedia

  • performing arts — arts or skills that require public performance, as acting, singing, or dancing. [1945 50] * * * ▪ 2009 Introduction Music Classical.       The last vestiges of the Cold War seemed to thaw for a moment on Feb. 26, 2008, when the unfamiliar strains …   Universalium

  • The Young and the Restless minor characters — The following are characters from the American soap opera The Young and the Restless who are notable for their actions or relationships, but who do not warrant their own articles. Contents 1 Current Characters 1.1 Genevieve …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.