Problém spiaceho holiča

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

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[upraviť | upraviť zdroj]

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í. Akonáhle 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[upraviť | upraviť zdroj]

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. Ako náhle 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[upraviť | upraviť zdroj]

  • 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 a V 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 holič má veľa práce
   //tu je zákazník strihaný
 } else { //nie sú žiadne voľné kreslá
   //ťažké šťastie
   V(accessSeats) //ale nezabudne uvoľniť zámok na kreslá
   //zákazník odchádza bez ostrihania
 }

Referencie[upraviť | upraviť zdroj]

Pozri aj[upraviť | upraviť zdroj]