86:, 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.
105:, 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
907:
623:
642:
728:
75:
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
78:
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
816:
934:
778:
944:
109:
is also required to indicate the state of the system. For example, one might store the number of people in the waiting room.
811:
801:
721:
806:
636:
529:
130:
751:
911:
877:
714:
506:
939:
887:
872:
867:
595:
485:
480:
470:
122:
28:
666:
133:
671:
by E.W. Dijkstra. Technical Report EWD-123, 1965, Eindhoven
University of Technology, The Netherlands.
862:
761:
475:
149:
561:
137:
106:
766:
57:
Imagine a hypothetical barbershop with one barber, one barber chair, and a waiting room with
737:
93:
has the additional complexity of coordinating several barbers among the waiting customers.
8:
756:
619:
126:
39:
591:
535:
682:
632:
525:
539:
826:
793:
517:
36:
20:
783:
773:
192:# if 1, the number of seats in the waiting room can be incremented or decremented
46:
32:
882:
83:
49:, who used it to make the point that general semaphores are often superfluous.
928:
841:
521:
35:
problem that illustrates the complexities that arise when there are multiple
821:
600:. Eindhoven, The Netherlands: Eindhoven University of Technology. p. 38
273:# Awake - try to get access to modify # of available seats, otherwise sleep.
831:
207:# the number of customers currently in the waiting room, ready to be served
857:
45:
The problem was originally proposed in 1965 by computer science pioneer
706:
118:
399:# notify the barber, who's waiting until there is a customer
101:
There are several possible solutions, but all solutions require a
258:# Try to acquire a customer - if none is available, go to sleep.
82:
There are two main complications. First, there is a risk that a
69:
If there are no customers, the barber falls asleep in the chair
631:(2nd ed.). Upper Saddle River, NJ: Pearson. p. 129.
129:
of a customer. The problem of starvation can be solved with a
121:
guarantees synchronization between barber and customer and is
102:
65:
may be 0) for waiting customers. The following rules apply:
836:
597:
Technical Report EWD-123: Cooperating
Sequential Processes
456:# but don't forget to release the lock on the seats!
339:# Run in an infinite loop to simulate multiple customers.
516:. Vol. 2. San Diego, CA: IEEE. pp. 1804–1808.
618:
441:# otherwise, there are no free seats; tough luck --
590:
165:# The first two are mutexes (only 0 or 1 possible)
926:
504:
315:# Don't need the lock on the chairs anymore.
559:
514:Proceedings of the Winter Simulation Conference
354:# Try to get access to the waiting room chairs.
72:A customer must wake the barber if he is asleep
569:(2.2.1 ed.). Green Tea Press. p. 121
722:
414:# don't need to lock the chairs anymore
222:# total number of seats in the waiting room
729:
715:
683:"Program 2: The Sleeping-Barbers Problem"
736:
927:
285:# One waiting room chair becomes free.
710:
586:
584:
553:
52:
13:
680:
581:
505:John H. Reynolds (December 2002).
429:# wait until the barber is ready
14:
956:
507:"Linda arouses a Sleeping Barber"
112:
91:multiple sleeping barbers problem
906:
905:
668:Cooperating Sequential processes
935:Concurrency (computer science)
912:Category: Concurrent computing
674:
660:
612:
498:
372:# If there are any free seats:
1:
563:The Little Book of Semaphores
491:
140:would provide two functions:
945:Problems in computer science
459:# (Leave without a haircut.)
96:
16:Software concurrency problem
7:
873:Dining philosophers problem
481:Producers-consumers problem
471:Dining philosophers problem
464:
29:inter-process communication
10:
961:
762:Concurrent data structures
243:# Run in an infinite loop.
901:
878:Producer–consumer problem
863:Cigarette smokers problem
850:
792:
744:
476:Cigarette smokers problem
131:first-in first-out (FIFO)
690:University of Washington
625:Modern Operating Systems
560:Allen B. Downey (2016).
522:10.1109/WSC.2002.1166471
162:
893:Sleeping barber problem
888:Readers–writers problem
486:Readers–writers problem
432:# (Have hair cut here.)
384:# sit down in a chair
25:sleeping barber problem
767:Concurrent hash tables
125:free, but may lead to
738:Concurrent computing
300:# I am ready to cut.
152:would correspond to
148:, which in terms of
757:Concurrency control
620:Andrew S. Tanenbaum
375:numberOfFreeWRSeats
360:numberOfFreeWRSeats
276:numberOfFreeWRSeats
213:numberOfFreeWRSeats
940:Edsger W. Dijkstra
681:Fukuda, Munehiro.
592:Edsger W. Dijkstra
318:# (Cut hair here.)
920:
919:
648:on 8 January 2022
53:Problem statement
952:
909:
908:
851:Classic problems
827:Ambient calculus
774:Concurrent users
731:
724:
717:
708:
707:
701:
700:
698:
696:
687:
678:
672:
664:
658:
657:
655:
653:
647:
641:. Archived from
630:
616:
610:
609:
607:
605:
588:
579:
578:
576:
574:
568:
557:
551:
550:
548:
546:
511:
502:
460:
457:
454:
451:
448:
445:
442:
439:
436:
433:
430:
427:
424:
421:
418:
415:
412:
409:
406:
403:
400:
397:
394:
391:
388:
385:
382:
379:
376:
373:
370:
367:
364:
361:
358:
355:
352:
349:
346:
343:
340:
337:
334:
331:
328:
325:
322:
319:
316:
313:
310:
307:
304:
301:
298:
295:
292:
289:
286:
283:
280:
277:
274:
271:
268:
265:
262:
259:
256:
253:
250:
247:
244:
241:
238:
235:
232:
229:
226:
223:
220:
217:
214:
211:
208:
205:
202:
199:
196:
193:
190:
187:
184:
181:
178:
175:
172:
169:
166:
160:, respectively.
159:
155:
147:
143:
37:operating system
21:computer science
960:
959:
955:
954:
953:
951:
950:
949:
925:
924:
921:
916:
897:
846:
794:Process calculi
788:
784:Linearizability
740:
735:
705:
704:
694:
692:
685:
679:
675:
665:
661:
651:
649:
645:
639:
628:
617:
613:
603:
601:
589:
582:
572:
570:
566:
558:
554:
544:
542:
532:
509:
503:
499:
494:
467:
462:
461:
458:
455:
452:
449:
446:
443:
440:
437:
434:
431:
428:
425:
422:
419:
416:
413:
410:
407:
404:
401:
398:
395:
392:
389:
386:
383:
380:
377:
374:
371:
368:
365:
362:
359:
356:
353:
350:
347:
344:
341:
338:
335:
332:
329:
326:
323:
320:
317:
314:
311:
308:
305:
302:
299:
296:
293:
290:
287:
284:
281:
278:
275:
272:
269:
266:
263:
260:
257:
254:
251:
248:
245:
242:
239:
236:
233:
230:
227:
224:
221:
218:
215:
212:
209:
206:
203:
200:
197:
194:
191:
188:
185:
182:
179:
176:
173:
170:
167:
164:
157:
153:
145:
141:
115:
99:
55:
47:Edsger Dijkstra
33:synchronization
17:
12:
11:
5:
958:
948:
947:
942:
937:
918:
917:
915:
914:
902:
899:
898:
896:
895:
890:
885:
883:Race condition
880:
875:
870:
865:
860:
854:
852:
848:
847:
845:
844:
839:
834:
829:
824:
819:
814:
809:
804:
798:
796:
790:
789:
787:
786:
781:
776:
771:
770:
769:
759:
754:
748:
746:
742:
741:
734:
733:
726:
719:
711:
703:
702:
673:
659:
637:
611:
580:
552:
530:
496:
495:
493:
490:
489:
488:
483:
478:
473:
466:
463:
163:
117:The following
114:
113:Implementation
111:
98:
95:
84:race condition
80:
79:
76:
73:
70:
54:
51:
15:
9:
6:
4:
3:
2:
957:
946:
943:
941:
938:
936:
933:
932:
930:
923:
913:
904:
903:
900:
894:
891:
889:
886:
884:
881:
879:
876:
874:
871:
869:
866:
864:
861:
859:
856:
855:
853:
849:
843:
842:Join-calculus
840:
838:
835:
833:
830:
828:
825:
823:
820:
818:
815:
813:
810:
808:
805:
803:
800:
799:
797:
795:
791:
785:
782:
780:
779:Indeterminacy
777:
775:
772:
768:
765:
764:
763:
760:
758:
755:
753:
750:
749:
747:
743:
739:
732:
727:
725:
720:
718:
713:
712:
709:
691:
684:
677:
670:
669:
663:
644:
640:
638:9780130313584
634:
627:
626:
621:
615:
599:
598:
593:
587:
585:
565:
564:
556:
541:
537:
533:
531:0-7803-7614-5
527:
523:
519:
515:
508:
501:
497:
487:
484:
482:
479:
477:
474:
472:
469:
468:
450:accessWRSeats
408:accessWRSeats
348:accessWRSeats
309:accessWRSeats
267:accessWRSeats
183:accessWRSeats
161:
151:
139:
135:
132:
128:
124:
120:
110:
108:
104:
94:
92:
87:
85:
77:
74:
71:
68:
67:
66:
64:
60:
50:
48:
43:
41:
38:
34:
30:
27:is a classic
26:
22:
922:
892:
832:API-Calculus
693:. Retrieved
689:
676:
667:
662:
650:. Retrieved
643:the original
624:
614:
602:. Retrieved
596:
571:. Retrieved
562:
555:
543:. Retrieved
513:
500:
116:
100:
90:
88:
81:
62:
58:
56:
44:
24:
18:
858:ABA problem
752:Concurrency
423:barberReady
294:barberReady
171:barberReady
929:Categories
822:Ď€-calculus
492:References
127:starvation
119:pseudocode
107:semaphores
695:8 January
652:8 January
604:8 January
573:8 January
545:8 January
393:custReady
252:custReady
198:custReady
195:Semaphore
180:Semaphore
168:Semaphore
138:semaphore
97:Solutions
40:processes
868:Deadlock
622:(2001).
594:(1965).
540:62584541
465:See also
324:Customer
146:signal()
123:deadlock
61:chairs (
745:General
910:
635:
538:
528:
444:signal
402:signal
387:signal
303:signal
288:signal
228:Barber
150:C code
142:wait()
136:. The
23:, the
817:LOTOS
686:(PDF)
646:(PDF)
629:(PDF)
567:(PDF)
536:S2CID
510:(PDF)
330:while
234:while
134:queue
103:mutex
837:PEPA
697:2022
654:2022
633:ISBN
606:2022
575:2022
547:2022
526:ISBN
435:else
417:wait
363:>
342:wait
333:true
261:wait
246:wait
237:true
156:and
144:and
31:and
812:ACP
807:CCS
802:CSP
518:doi
327:():
321:def
231:():
225:def
210:int
158:V()
154:P()
19:In
931::
688:.
583:^
534:.
524:.
512:.
378:-=
357:if
279:+=
89:A
42:.
730:e
723:t
716:v
699:.
656:.
608:.
577:.
549:.
520::
453:)
447:(
438::
426:)
420:(
411:)
405:(
396:)
390:(
381:1
369::
366:0
351:)
345:(
336::
312:)
306:(
297:)
291:(
282:1
270:)
264:(
255:)
249:(
240::
219:N
216:=
204:0
201:=
189:1
186:=
177:0
174:=
63:n
59:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.