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 Sleeping Barber Problem is often attributed to Edsger Dijkstra (1965), one of the pioneers in computer science. A multiple sleeping barbers problem has the additional complexity of coordinating several barbers among the waiting customers.

Property Value
dbo:abstract
  • 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 analogy is based upon a hypothetical barber shop with one barber. The barber has one barber chair and a waiting room with a number of chairs in it. When the barber finishes cutting a customer's hair, he dismisses the customer and then goes to the waiting room to see if there are other customers waiting. If there are, he brings one of them back to the chair and cuts his hair. If there are no other customers waiting, he returns to his chair and sleeps in it. Each customer, when he arrives, looks to see what the barber is doing. If the barber is sleeping, then the customer wakes him up and sits in the chair. If the barber is cutting hair, then the customer goes to the waiting room. If there is a free chair in the waiting room, the customer sits in it and waits his turn. If there is no free chair, then the customer leaves. Based on a naïve analysis, the above description 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 he is on his way, the barber finishes the haircut he is doing and goes to check the waiting room. Since there is no one there (the customer not having arrived yet), he goes back to his chair and sleeps. The barber is now waiting for a customer and the customer is waiting for the barber. In another example, 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. The Sleeping Barber Problem is often attributed to Edsger Dijkstra (1965), one of the pioneers in computer science. 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 this mutual exclusion before checking for customers and release it when he begins either to sleep or cut hair. A customer must acquire it before entering the shop and release it once he is sitting in either a waiting room chair or the barber chair, and also when he leaves 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. (en)
  • En ciencias de la computación, el problema del barbero durmiente es un problema de sincronización. El problema consiste en una barbería en la que trabaja un barbero que tiene un único sillón de barbero y varias sillas para esperar. Cuando no hay clientes, el barbero se sienta en una silla y se duerme. Cuando llega un nuevo cliente, éste o bien despierta al barbero o —si el barbero está afeitando a otro cliente— se sienta en una silla (o se va si todas las sillas están ocupadas por clientes esperando). El problema consiste en realizar la actividad del barbero sin que ocurran condiciones de carrera. La solución implica el uso de semáforos y objetos de exclusión mutua para proteger la sección crítica. Un semáforo es una variable protegida (o tipo abstracto de datos) que constituye el método clásico para restringir o permitir el acceso a recursos compartidos (por ejemplo, un recurso de almacenamiento) en un entorno de multiprocesamiento. Fueron inventados por Edsger Dijkstra y se usaron por primera vez en el sistema operativo THEOS. En electrónica y en programación concurrente, se conoce como condición de carrera al error que se produce en programas o circuitos lógicos que no se han construido adecuadamente para su ejecución simultánea con otros procesos. (es)
  • 計算機科学における居眠り床屋問題(sleeping barber problem)とは、典型的なプロセス間通信およびプロセス間での同期に関する問題である。客がいる限り働いたまま、客がいなければ休んだままということを繰り返す理容師に例えられることからついた名称。理容師と客の挙動で、前述したプロセス間の問題を表現する。 (ja)
  • Problem śpiącego golibrody (ang. sleeping barber problem) – klasyczny informatyczny problem komunikacji i synchronizacji pomiędzy kilkoma procesami. Można go przedstawić za pomocą analogii do pracy golibrody, który odpoczywa w gabinecie, gdy nie ma klientów, i obsługuje ich, gdy się pojawiają. (pl)
  • В информатике проблема спящего парикмахера — классическая задача синхронизации и межпроцессного взаимодействия (interprocess communication) в многозадачной операционной системе. Проблема заключается в обеспечении того, чтобы парикмахер работал, когда есть клиенты и отдыхал, когда клиентов нет. (ru)
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 363196 (xsd:integer)
dbo:wikiPageRevisionID
  • 742522552 (xsd:integer)
dct:subject
http://purl.org/linguistics/gold/hypernym
rdf:type
rdfs:comment
  • 計算機科学における居眠り床屋問題(sleeping barber problem)とは、典型的なプロセス間通信およびプロセス間での同期に関する問題である。客がいる限り働いたまま、客がいなければ休んだままということを繰り返す理容師に例えられることからついた名称。理容師と客の挙動で、前述したプロセス間の問題を表現する。 (ja)
  • Problem śpiącego golibrody (ang. sleeping barber problem) – klasyczny informatyczny problem komunikacji i synchronizacji pomiędzy kilkoma procesami. Można go przedstawić za pomocą analogii do pracy golibrody, który odpoczywa w gabinecie, gdy nie ma klientów, i obsługuje ich, gdy się pojawiają. (pl)
  • В информатике проблема спящего парикмахера — классическая задача синхронизации и межпроцессного взаимодействия (interprocess communication) в многозадачной операционной системе. Проблема заключается в обеспечении того, чтобы парикмахер работал, когда есть клиенты и отдыхал, когда клиентов нет. (ru)
  • 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 Sleeping Barber Problem is often attributed to Edsger Dijkstra (1965), one of the pioneers in computer science. A multiple sleeping barbers problem has the additional complexity of coordinating several barbers among the waiting customers. (en)
  • En ciencias de la computación, el problema del barbero durmiente es un problema de sincronización. El problema consiste en una barbería en la que trabaja un barbero que tiene un único sillón de barbero y varias sillas para esperar. Cuando no hay clientes, el barbero se sienta en una silla y se duerme. Cuando llega un nuevo cliente, éste o bien despierta al barbero o —si el barbero está afeitando a otro cliente— se sienta en una silla (o se va si todas las sillas están ocupadas por clientes esperando). El problema consiste en realizar la actividad del barbero sin que ocurran condiciones de carrera. La solución implica el uso de semáforos y objetos de exclusión mutua para proteger la sección crítica. (es)
rdfs:label
  • Sleeping barber problem (en)
  • Problema del barbero durmiente (es)
  • 居眠り床屋問題 (ja)
  • Problem śpiącego golibrody (pl)
  • Проблема спящего парикмахера (ru)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of
is foaf:primaryTopic of