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

Kategória:Informatika