Problém spiaceho holiča

V počítačovej vede je problém spiaceho holiča klasický medziprocesovo-komunikačný a synchronizačný problém, ktorý sa vyskytuje pri viacnásobných procesoch operačného systému. Problém spočíva v nasledujúcich 2 stavoch: udržať holiča v pracovnom stave, keď sú zákazníci a nechať ho odpočívať keď nie sú žiadni. Toto celé treba robiť organizovaným spôsobom. Holič a jeho zákazníci reprezentujú vyššie uvedené procesy.
Problém.
Analógia je založená na hypotetickom holičstve s jedným holičom, holiacou stoličkou a určitým množstvom stoličiek pre čakajúcich zákazníkov. Keď v holičstve nie sú zákazníci, holič sedí vo svojej stoličke a spí. Hneď ako dorazí zákazník, buď zobudí holiča, alebo keď holič momentálne strihá niekoho vlasy, usadí sa na jednu z prázdnych stoličiek. Pokiaľ by boli všetky zo stoličiek obsadené, práve prichádzajúci zákazník jednoducho odíde.
Problém pozostáva zo snahy o koordinovanie tejto aktivity so snahou vyhnúť sa akémukoľvek súbehu, a v tomto smere je podobný mnohým zaraďovacím problémom. V skutočnosti, je to klasický príklad (dvojnásobného) problému schôdzky.
Neimplementovanie riadneho riešenia môže viesť ku obvyklým medziprocesovo-komunikačným problémom: vyhladovaniu a uviaznutiu. Napríklad, holič by mohol skončiť čakajúci na zákazníka a zákazník zároveň čakajúci na holiča, čo by vyústilo do uviaznutia. Alternatívne, zákazníci sa nemôžu rozhodnúť k pristúpeniu ku holičovi v organizovanom spôsobe, čo by viedlo k vyhladovaniu procesov, keďže niektorí zákazníci sa nikdy nedostanú ku šanci oholenia sa, aj keď boli čakajúcimi.
Problém spiaceho holiča je často prisudzovaný Edsgerovi Dijkstrovi (1965), jednému z priekopníkov v elementárnom programovaní.
Riešenie.
Najbežnejšie riešenie zahrňuje použitie troch semaforov: jeden pre ľubovoľných čakajúcich zákazníkov, jeden pre holiča (aby sme videli, či je nečinný) a tzv. mutex. Hneď ako príde zákazník, pokúsi sa nadobudnúť mutex a čaká pokiaľ nebude úspešný. Vtedy zákazník skontroluje, či preňho existuje nejaká voľná stolička (buď jedna zo stoličiek pre čakajúcich, alebo holičova stolička) a pokiaľ žiadna z týchto nie je voľná, odíde. Opačne zákazník zaujme miesto – čiže redukuje množstvo dostupných (a kritický úsek). Zákazník začne nato prostredníctvom semaforu signalizovať holičovi, aby sa zobudil, a mutex je vypustený, aby dovolil ostatným zákazníkom (alebo holičovi) nadobudnúť ho. Pokiaľ holič nie je voľný, zákazník čaká. Holič sedí v neustálej čakajúcej slučke, zobúdzaný každým čakajúcim zákazníkom. Pokiaľ sa zobudí, dá vedieť čakajúcim zákazníkom prostredníctvom jeho semaforu, že môže jedného z nich oholiť.
Tento problém zahŕňa iba jediného holiča, a aj preto je nazývaný "problém jediného spiaceho holiča". "Problém viacerých spiacich holičov" je podobný v implementácii a aj pascami, avšak vzniká tu navyše zložitosť koordinácie niekoľkých holičov, ktorí sú obklopených čakajúcimi zákazníkmi.
Implementácia.
 + Semaphore Customers = 0
 + Semaphore Barber = 0
 + Semaphore accessSeats (mutex) = 1
 + int NumberOfFreeSeats = N //celkový počet kresiel
 while (true) { // beží v nekonečnej slučke
 P(Customers) // pokúša sa zaobstarať si zákazníka - ak žiadny nie je k dispozícii ide spať
 P(accessSeats) // v tomto čase on bol prebudený - chce modifikovať počet dostupných kresiel
 NumberOfFreeSeats++ // jedna stolička zostane voľná
 V(Barber) // holič je pripravený strihať
 V(accessSeats) // nepotrebujeme viacej zámok na stoličkách
 (...) // tu holič strihá vlasy
 P(accessSeats) // pokúša sa dostať prístup k stoličkám
 if (NumberOfFreeSeats &gt; 0) { // ak existujú nejaké voľné kreslá
 NumberOfFreeSeats-- // sadnutie si na stoličku
 V(Customers) // oznamuje holičovi, ktorý čaká, že je tam zákazník
 V(accessSeats) // nemusí viacej zamknúť stoličky
 P(Barber) // teraz je tento zákazník na rade, ale čaká, ak má holič veľa práce
 (...) // tu je zákazník strihaný
 } else { // nie sú žiadne voľné kreslá, zákazník odchádza bez ostrihania
 V(accessSeats) // ale nezabudne uvoľniť zámok na kreslá