Editing Sleeping barber problem

{{Short description|Software concurrency problem}}
In [[computer science]], the '''sleeping barber problem''' is a classic [[inter-process communication]] and [[synchronization]] problem that illustrates the complexities that arise when there are multiple [[operating system]] [[Process (computing)|processes]].<ref>{{cite book |author1=John H. Reynolds |title=Proceedings of the Winter Simulation Conference |chapter=Linda arouses a Sleeping Barber |doi=10.1109/WSC.2002.1166471 |chapter-url=http://charm.cs.uiuc.edu/cs498lvk/prog_models/linda/sleeping-barber.pdf |access-date=8 January 2022|publisher=IEEE |location=San Diego, CA|date=December 2002|volume=2 |pages=1804–1808 |isbn=0-7803-7614-5 |s2cid=62584541 }}</ref>

The problem was originally proposed in 1965 by computer science pioneer [[Edsger Dijkstra]],<ref name="little">{{cite book |author1=Allen B. Downey |title=The Little Book of Semaphores |date=2016 |publisher=Green Tea Press |page=121 |edition=2.2.1 |url=https://greenteapress.com/semaphores/LittleBookOfSemaphores.pdf |access-date=8 January 2022}}</ref> who used it to make the point that general semaphores are often superfluous.<ref name="ewd"/>

==Problem statement==

Imagine a hypothetical barbershop with one barber, one barber chair, and a waiting room with ''n'' chairs (''n'' may be 0) for waiting customers. The following rules apply:<ref>{{cite book |author1=Andrew S. Tanenbaum |author1-link=Andrew S. Tanenbaum |title=Modern Operating Systems |date=2001 |publisher=Pearson |location=Upper Saddle River, NJ |isbn=9780130313584 |page=129 |edition=2nd |url=http://www.microlinkcolleges.net/elib/files/undergraduate/Management/MODERN%20%20OPERATINGSYSTEMSSECOND%20EDITIONby%20Andrew%20S.%20Tanenbaum.pdf |access-date=8 January 2022 |archive-date=8 January 2022 |archive-url=https://web.archive.org/web/20220108235906/http://www.microlinkcolleges.net/elib/files/undergraduate/Management/MODERN%20%20OPERATINGSYSTEMSSECOND%20EDITIONby%20Andrew%20S.%20Tanenbaum.pdf |url-status=dead }}</ref>
* If there are no customers, the barber falls asleep in the chair
* A customer must wake the barber if he is asleep
* If a customer arrives while the barber is working, the customer leaves if all chairs are occupied and sits in an empty chair if it's available
* When the barber finishes a haircut, he inspects the waiting room to see if there are any waiting customers and falls asleep if there are none<ref name="ewd">{{cite book |author1=Edsger W. Dijkstra |author1-link=Edsger W. Dijkstra |title=Technical Report EWD-123: Cooperating Sequential Processes |date=1965 |publisher=Eindhoven University of Technology |location=Eindhoven, The Netherlands |page=38 |url=https://www.cs.utexas.edu/users/EWD/transcriptions/EWD01xx/EWD123.html |access-date=8 January 2022}}</ref><ref>[http://www.cs.utexas.edu/users/EWD/transcriptions/EWD01xx/EWD123.html ''Cooperating Sequential processes''] by E.W. Dijkstra. Technical Report EWD-123, 1965, Eindhoven University of Technology, The Netherlands.</ref>

There are two main complications. First, there is a risk that a [[race condition]], where the barber sleeps while a customer waits for the barber to get them for a haircut, arises because all of the actions—checking the waiting room, entering the shop, taking a waiting room chair—take a certain amount of time. Specifically, a customer may arrive to find the barber cutting hair so they return to the waiting room to take a seat but while walking back to the waiting room the barber finishes the haircut and goes to the waiting room, which he finds empty (because the customer walks slowly or went to the restroom) and thus goes to sleep in the barber chair. Second, another problem may occur when two customers arrive at the same time when there is only one empty seat in the waiting room and both try to sit in the single chair; only the first person to get to the chair will be able to sit.

A ''multiple sleeping barbers problem'' has the additional complexity of coordinating several barbers among the waiting customers.<ref>{{cite web |last1=Fukuda |first1=Munehiro |title=Program 2: The Sleeping-Barbers Problem |url=http://courses.washington.edu/css503/prog/prog2.pdf |website=University of Washington |access-date=8 January 2022}}</ref>

==Solutions==
There are several possible solutions, but all solutions require a [[mutex]], which ensures that only one of the participants can change state at once. The barber must acquire the room status mutex 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 a waiting room or barber chair, and also when they leave the shop because no seats were available. This would take care of both of the problems mentioned above. A number of [[semaphore (programming)|semaphores]] is also required to indicate the state of the system. For example, one might store the number of people in the waiting room.

=== Implementation ===
The following [[pseudocode]] guarantees synchronization between barber and customer and is [[Deadlock (computer science)|deadlock]] free, but may lead to [[Resource starvation|starvation]] of a customer. The problem of starvation can be solved with a [[FIFO (computing and electronics)|first-in first-out (FIFO)]] [[Queue (abstract data type)|queue]]. The [[Semaphore (programming)|semaphore]] would provide two functions: <code>wait()</code> and <code>signal()</code>, which in terms of [[C (programming language)|C code]] would correspond to <code>P()</code> and <code>V()</code>, respectively.{{citation needed|date=January 2022}}

<syntaxhighlight lang="python">
# The first two are mutexes (only 0 or 1 possible)
Semaphore barberReady = 0
Semaphore accessWRSeats = 1     # if 1, the number of seats in the waiting room can be incremented or decremented
Semaphore custReady = 0         # the number of customers currently in the waiting room, ready to be served
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 += 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.)

def Customer():
  while true:                   # Run in an infinite loop to simulate multiple customers.
    wait(accessWRSeats)         # Try to get access to the waiting room chairs.
    if numberOfFreeWRSeats > 0: # If there are any free seats:
      numberOfFreeWRSeats -= 1  #   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.)
</syntaxhighlight>

== See also ==
* [[Dining philosophers problem]]
* [[Cigarette smokers problem]]
* [[Producers-consumers problem]]
* [[Readers–writers problem]]

==References==
{{reflist}}

{{Concurrent computing}}

{{Use dmy dates|date=February 2021}}
[[Category:Concurrency (computer science)]]
[[Category:Edsger W. Dijkstra]]
[[Category:Articles with example pseudocode]]
[[Category:Problems in computer science]]