Sleeping barber problem

Last updated

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.

Contents

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

Definition

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

Each customer, when they arrive, looks to see what the barber is doing. If the barber is sleeping, the customer wakes him up and sits in the cutting room chair. If the barber is cutting hair, the customer stays in the waiting room. If there is a free chair in the waiting room, the customer sits in it and waits their turn. If there is no free chair, the customer leaves.

Problems arising

Based on a naïve analysis, the above decisions 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 they're on their way, the barber finishes their current haircut and goes to check the waiting room. Since there is no one there (maybe the waiting room is far away and the barber walks faster passing the customer, or maybe the customer went to the restroom or was going towards the chair and the barber thought he was leaving), so the barber goes back to their chair and sleeps. The barber is now waiting for a customer, but the customer is waiting for the barber.

In another situation, 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.

Solutions

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/enforce this mutual exclusion (of room status) before checking for customers and release it when they begin either to sleep or cut hair. A customer must acquire it before entering the shop and release it once they are sitting in either a waiting room chair or the barber chair, and also when they leave the shop because no seats were available. This eliminates both of the problems mentioned in the previous section. A number of semaphores is 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 pseudocode guarantees synchronization between barber and customer and is deadlock free, but may lead to starvation of a customer. The problem of starvation can be solved by utilizing a queue where customers are added as they arrive, so that barber can serve them on a first come first served basis (FIFO => First In, First Out) The functions wait() and signal() are functions provided by the semaphores. In c-code notation, a wait() is a P() and a signal() is a V().

# The first two are mutexes (only 0 or 1 possible)SemaphorebarberReady=0SemaphoreaccessWRSeats=1# if 1, the number of seats in the waiting room can be incremented or decrementedSemaphorecustReady=0# the number of customers currently in the waiting room, ready to be servedintnumberOfFreeWRSeats=N# total number of seats in the waiting roomdefBarber():whiletrue:# 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+=1# 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.)defCustomer():whiletrue:# Run in an infinite loop to simulate multiple customers.wait(accessWRSeats)# Try to get access to the waiting room chairs.ifnumberOfFreeWRSeats>0:# If there are any free seats:numberOfFreeWRSeats-=1#   sit down in a chairsignal(custReady)#   notify the barber, who's waiting until there is a customersignal(accessWRSeats)#   don't need to lock the chairs anymorewait(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

Related Research Articles

Mutual exclusion property of concurrency control, which is instituted for the purpose of preventing race conditions

In computer science, mutual exclusion is a property of concurrency control, which is instituted for the purpose of preventing race conditions. It is the requirement that one thread of execution never enters its critical section at the same time that another concurrent thread of execution enters its own critical section, which refers to an interval of time during which a thread of execution accesses a shared resource, such as shared memory.

Barber person whose occupation is mainly to cut, dress, groom, style and shave males hair

A barber is a person whose occupation is mainly to cut, dress, groom, style and shave men's and boys' hair. A barber's place of work is known as a "barbershop" or a "barber's". Barbershops are also places of social interaction and public discourse. In some instances, barbershops are also public forums. They are the locations of open debates, voicing public concerns, and engaging citizens in discussions about contemporary issues.

In computer science, a semaphore is a variable or abstract data type used to control access to a common resource by multiple processes in a concurrent system such as a multitasking operating system. A semaphore is simply a variable. This variable is used to solve critical section problems and to achieve process synchronization in the multi processing environment. A trivial semaphore is a plain variable that is changed depending on programmer-defined conditions.

Queue area Places where people queue or "line up" for goods or services

Queue areas are places in which people queue for goods or services. Such a group of people is known as a queue or line, and the people are said to be waiting or standing in a queue or in line, respectively. Occasionally, both the British and American terms are combined to form the term "queue line".

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.

General Purpose Simulation System (GPSS) is a discrete time simulation general-purpose programming language, where a simulation clock advances in discrete steps. A system is modelled as transactions enter the system and are passed from one service to another. It is used primarily as a process flow oriented simulation language; this is particularly well-suited for problems such as a factory.

In concurrent programming, a monitor is a synchronization construct that allows threads to have both mutual exclusion and the ability to wait (block) for a certain condition to become false. Monitors also have a mechanism for signaling other threads that their condition has been met. A monitor consists of a mutex (lock) object and condition variables. A condition variable is basically a container of threads that are waiting for a certain condition. Monitors provide a mechanism for threads to temporarily give up exclusive access in order to wait for some condition to be met, before regaining exclusive access and resuming their task.

Floyd Lawson

Floyd Lawson is a fictional character on the American sitcom The Andy Griffith Show, who was likely inspired by barbers in Andy Griffith's real-life hometown of Mount Airy, North Carolina. One barber named Russell Hiatt (1924-2016) was known as "the real-life Floyd". Hiatt may have cut Andy Griffith's hair while Griffith was young and living in Mount Airy, and was still cutting hair daily at "Floyd's City Barber Shop" in downtown Mount Airy until several years before his death on May 3, 2016. Griffith denied that Hiatt was the inspiration for Floyd Lawson, however, saying, "A barber up there says he cut my hair when I was a child. Hell, he'll have to be 115 years old."

Flattop hairstyle

A "flattop" is a type of short haircut where the hair on the top of the head is usually standing upright and cut to form a flat-appearing deck. This deck may be level, or it may be upward or downward sloping. This type of haircut is usually performed with electric clippers, either freehand or using the clipper-over-comb method.

Cut Your Hair 1994 single by Pavement

"Cut Your Hair" is a song by American rock band Pavement from their second album, Crooked Rain, Crooked Rain. It was written by Pavement songwriter and lead singer Stephen Malkmus. The song snidely attacks the importance of image in the music industry. In one verse, Malkmus sarcastically recites a fictitious ad looking for a musician to join a band: "advertising looks and chops a must/ no big hair".

The cigarette smokers problem is a concurrency problem in computer science, originally described in 1971 by Suhas Patil.

In computer science, the readers-writers problems are examples of a common computing problem in concurrency. There are at least three variations of the problems, which deal with situations in which many threads try to access the same shared resource at one time. Some threads may read and some may write, with the constraint that no thread may access the shared resource for either reading or writing while another thread is in the act of writing to it.. A readers-writer lock is a data structure that solves one or more of the readers-writers problems.

In computer science, synchronization refers to one of two distinct but related concepts: synchronization of processes, and synchronization of data. Process synchronization refers to the idea that multiple processes are to join up or handshake at a certain point, in order to reach an agreement or commit to a certain sequence of action. Data synchronization refers to the idea of keeping multiple copies of a dataset in coherence with one another, or to maintain data integrity. Process synchronization primitives are commonly used to implement data synchronization.

"The Barber" is the 72nd episode of the NBC sitcom Seinfeld. It is the eighth episode of the fifth season, and first aired on November 11, 1993.

In computing, the producer–consumer problem is a classic example of a multi-process synchronization problem. The problem describes two processes, the producer and the consumer, who share a common, fixed-size buffer used as a queue. The producer's job is to generate data, put it into the buffer, and start again. At the same time, the consumer is consuming the data, one piece at a time. The problem is to make sure that the producer won't try to add data into the buffer if it's full and that the consumer won't try to remove data from an empty buffer.

<i>The Barber of Seville</i> (1944 film) 1944 film by Shamus Culhane

The Barber of Seville is the tenth animated cartoon short subject in the Woody Woodpecker series. Released theatrically on April 22, 1944, the film was produced by Walter Lantz Productions and distributed by Universal Pictures.

<i>Yanky Clippers</i> 1929 film by Walter Lantz, Tom Palmer

Yanky Clippers is a silent animated film starring Oswald the Lucky Rabbit. It is among the few shorts created during the Winkler period known to exist. The cartoon is also Oswald's last silent film.

<i>The Busy Barber</i> 1932 film by Walter Lantz

The Busy Barber, also known as Busy Barbers in some reissues, is a short animated film by Walter Lantz Productions, starring Oswald the Lucky Rabbit. It is the 64th Oswald short by Lantz and the 116th in the entire series.

Regular haircut Simple hairstyle popular among males

A regular haircut is a men's and boys' hairstyle that has hair long enough to comb on top, a defined or deconstructed side part, and a short, semi-short, medium, long, or extra long back and sides. The style is also known by other names including taper cut, regular taper cut, side-part and standard haircut; as well as short back and sides, business-man cut and professional cut, subject to varying national, regional, and local interpretations of the specific taper for the back and sides.

Shanghai-style barber shops in Hong Kong

Shanghai-Style Barber Shop is a barber shop opened by a group of Shanghai barbers coming to Hong Kong mainly in the 1950s to give classical Shanghai haircuts. It is popular in Hong Kong among higher class people in the period of 1950s-1970s, offering a range of classical haircut until today. Other than hair-cutting, Shanghai style barber shops provide different unique services include trimming, massaging, nails clipping, etc. Despite the sunset of Shanghai style barber shop in Hong Kong in the modern days, it still attracts loyal customers, especially among males, and costs around HK$70 for a haircut and shave using traditional clippers.

References