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.
Obsah |
Problém [upraviť]
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ť]
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ť]
- 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ť]
- 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.
