Concept

Sleeping barber 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 processes. The problem was originally proposed in 1965 by computer science pioneer Edsger Dijkstra, who used it to make the point that general semaphores are often superfluous. 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: 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 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. There are several possible solutions, but all solutions require a mutex, which ensures that only one of the participants can change state at once.

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related lectures (1)
Dining Philosophers Problem
Discusses algorithms to prevent starvation and maximize philosophers eating simultaneously.
Related publications (11)

A Data-Driven Method for Computing Fixed-Structure Low-Order Controllers With H-infinity Performance

Alireza Karimi, Achille Nicoletti

Recently, a new data-driven method for robust control with H-infinity performance has been proposed. This method is based on convex optimization and converges to the optimal performance when the controller order increases. However, for low-order controller ...
IEEE2018

A Data-Driven Method for Computing Fixed-Structure Low-Order Controllers With H∞ Performance

Alireza Karimi, Achille Nicoletti

Recently, a new data-driven method for robust control with H∞ performance has been proposed. This method is based on convex optimization and converges to the optimal performance when the controller order increases. However, for low-order controllers, the p ...
Elsevier2018

A Data-Driven Method for Computing Fixed-Structure Low-Order Controllers With H∞ Performance

Alireza Karimi, Achille Nicoletti

Recently, a new data-driven method for robust control with H ∞ performance has been proposed. This method is based on convex optimization and converges to the optimal performance when the controller order increases. However, for low-order controllers, the ...
2018
Show more
Related concepts (3)
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 as a student exam exercise, presented in terms of computers competing for access to tape drive peripherals. Soon after, Tony Hoare gave the problem its present form. Five philosophers dine together at the same table. Each philosopher has their own plate at the table.
Cigarette smokers problem
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." Patil's problem includes a "quite arbitrary" "restriction that the process which supplies the ingredients cannot be changed and that no conditional statements may be used." Assume a cigarette requires three ingredients to make and smoke: tobacco, paper, and matches.
Semaphore (programming)
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 (for example, incremented or decremented, or toggled) depending on programmer-defined conditions.

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.