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

• Nasledujúci pseudo-kód garantuje synchronizáciu medzi holičom a zákazníkom pričom zaručuje nemožnosť uviaznutia. Môže však viesť k vyhladovaniu zákazníka. P() – získať zdroj a V() – uvoľniť zdroj, sú funkcie zaobstarané semaformi.

• Potrebujeme (ako už bolo vyššie spomenuté):

 + Semaphore Customers = 0
 + Semaphore Barber = 0
 + Semaphore accessSeats (mutex) = 1
 + int NumberOfFreeSeats = N  //celkový počet kresiel

• Holič (vlákno/proces):

 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
 }

• Zákazník (vlákno/proces):

 P(accessSeats)                // pokúša sa dostať prístup k stoličkám
 if (NumberOfFreeSeats > 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á
 }

Referencie

• Modern Operating Systems (2nd Edition) by Andrew S. Tanenbaum (ISBN 0-13-031358-0)
• The Little Book of Semaphores by Allen B. Downey, http://greenteapress.com/semaphores
• Cooperating sequential processes by E.W. Dijkstra. Technical Report EWD-123, 1965, Technological University, Eindhoven, The Netherlands.

Pozri aj

• Problém fajčiarov cigariet