Sleeping barber problem

Last updated

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 processes. [1]

Contents

The problem was originally proposed in 1965 by computer science pioneer Edsger Dijkstra, [2] who used it to make the point that general semaphores are often superfluous. [3]

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: [4]

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. [6]

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 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 free, but may lead to starvation of a customer. The problem of starvation can be solved with a first-in first-out (FIFO) queue. The semaphore would provide two functions: wait() and signal(), which in terms of C code would correspond to P() and V(), respectively.[ citation needed ]

# 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

<span class="mw-page-title-main">Edsger W. Dijkstra</span> Dutch computer scientist (1930–2002)

Edsger Wybe Dijkstra was a Dutch computer scientist, programmer, software engineer, and science essayist.

A real-time operating system (RTOS) is an operating system (OS) for real-time computing applications that processes data and events that have critically defined time constraints. An RTOS is distinct from a time-sharing operating system, such as Unix, which manages the sharing of system resources with a scheduler, data buffers, or fixed task prioritization in a multitasking or multiprogramming environment. Processing time requirements need to be fully understood and bound rather than just kept as a minimum. All processing must occur within the defined constraints. Real-time operating systems are event-driven and preemptive, meaning the OS can monitor the relevant priority of competing tasks, and make changes to the task priority. Event-driven systems switch between tasks based on their priorities, while time-sharing systems switch the task based on clock interrupts.

Dekker's algorithm is the first known correct solution to the mutual exclusion problem in concurrent programming where processes only communicate via shared memory. The solution is attributed to Dutch mathematician Th. J. Dekker by Edsger W. Dijkstra in an unpublished paper on sequential process descriptions and his manuscript on cooperating sequential processes. It allows two threads to share a single-use resource without conflict, using only shared memory for communication.

<span class="mw-page-title-main">Mutual exclusion</span> In computing, restricting data to be accessible by one thread at a time

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 a critical section while a concurrent thread of execution is already accessing said critical section, which refers to an interval of time during which a thread of execution accesses a shared resource or shared memory.

<span class="mw-page-title-main">Semaphore (programming)</span> Variable used in a concurrent system

In computer science, a semaphore is a variable or abstract data type used to control access to a common resource by multiple threads and avoid critical section problems in a concurrent system such as a multitasking operating system. Semaphores are a type of synchronization primitive. A trivial semaphore is a plain variable that is changed depending on programmer-defined conditions.

In computer science, a lock or mutex is a synchronization primitive: a mechanism that enforces limits on access to a resource when there are many threads of execution. A lock is designed to enforce a mutual exclusion concurrency control policy, and with a variety of possible methods there exists multiple unique implementations for different applications.

<span class="mw-page-title-main">Dining philosophers problem</span> Problem used to illustrate synchronization issues and techniques for resolving them

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.

<span class="mw-page-title-main">Crew cut</span> Haircut style

A crew cut is a type of haircut in which the upright hair on the top of the head is cut relatively short, graduated in length from the longest hair that forms a short pomp (pompadour) at the front hairline to the shortest at the back of the crown so that in side profile, so the outline of the top hair approaches the horizontal. Relative to the front view, and to varying degrees, the outline of the top hair can be arched or flattened at the short pomp front and rounded or flattened over the rest of the top to complement the front hairline, head shape, face shape and facial features. The hair on the sides and back of the head is usually tapered short, semi-short, or medium.

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 essentially is 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.

<span class="mw-page-title-main">Cut Your Hair</span> 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. The problem has been criticized for having "restrictions which cannot be justified by practical considerations."

In computer science, a readers–writer is a synchronization primitive that solves one of the readers–writers problems. An RW lock allows concurrent access for read-only operations, whereas write operations require exclusive access. This means that multiple threads can read the data in parallel but an exclusive lock is needed for writing or modifying data. When a writer is writing the data, all other writers and readers will be blocked until the writer is finished writing. A common use might be to control access to a data structure in memory that cannot be updated atomically and is invalid until the update is complete.

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 concurrent threads of execution try to access the same shared resource at one time.

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.

Banker's algorithm is a resource allocation and deadlock avoidance algorithm developed by Edsger Dijkstra that tests for safety by simulating the allocation of predetermined maximum possible amounts of all resources, and then makes an "s-state" check to test for possible deadlock conditions for all other pending activities, before deciding whether allocation should be allowed to continue.

In computing, the producer-consumer problem is a family of problems described by Edsger W. Dijkstra since 1965.

DioneOS is a multitasking preemptive, real-time operating system (RTOS). The system is designed for microcontrollers, originally released on 2 February 2011 for the Texas Instruments TI MSP430x, and then on 29 March 2013 for the ARM Cortex-M3. Target microcontroller platforms have limited resources, i.e., system clock frequency of tens of MHz, and memory amounts of tens to a few hundred kilobytes (KB). The RTOS is adapted to such conditions by providing a compact and efficient image. The efficiency term here means minimizing further central processing unit (CPU) load caused by system use. According to this definition, the system is more effective when it consumes less CPU time to execute its internal parts, e.g., managing threads.

<i>The Busy Barber</i> 1932 film

The Busy Barber 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.

"Goodnight Mr. Bean" is the thirteenth episode of the British television series Mr. Bean, produced by Tiger Aspect Productions and Thames Television for Central Independent Television. It was first broadcast on ITV on Tuesday, 31 October 1995.

References

  1. John H. Reynolds (December 2002). "Linda arouses a Sleeping Barber" (PDF). Proceedings of the Winter Simulation Conference. Vol. 2. San Diego, CA: IEEE. pp. 1804–1808. doi:10.1109/WSC.2002.1166471. ISBN   0-7803-7614-5. S2CID   62584541 . Retrieved 8 January 2022.
  2. Allen B. Downey (2016). The Little Book of Semaphores (PDF) (2.2.1 ed.). Green Tea Press. p. 121. Retrieved 8 January 2022.
  3. 1 2 Edsger W. Dijkstra (1965). Technical Report EWD-123: Cooperating Sequential Processes. Eindhoven, The Netherlands: Eindhoven University of Technology. p. 38. Retrieved 8 January 2022.
  4. Andrew S. Tanenbaum (2001). Modern Operating Systems (PDF) (2nd ed.). Upper Saddle River, NJ: Pearson. p. 129. ISBN   9780130313584 . Retrieved 8 January 2022.
  5. Cooperating Sequential processes by E.W. Dijkstra. Technical Report EWD-123, 1965, Eindhoven University of Technology, The Netherlands.
  6. Fukuda, Munehiro. "Program 2: The Sleeping-Barbers Problem" (PDF). University of Washington. Retrieved 8 January 2022.