A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
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 aV()
– 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
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
Antropológia
Aplikované vedy
Bibliometria
Dejiny vedy
Encyklopédie
Filozofia vedy
Forenzné vedy
Humanitné vedy
Knižničná veda
Kryogenika
Kryptológia
Kulturológia
Literárna veda
Medzidisciplinárne oblasti
Metódy kvantitatívnej analýzy
Metavedy
Metodika
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk