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
Problém obedujúcich filozofov (dining philosophers problem) je myšlienkový experiment, ktorý sa používa na overenie správnej činnosti správy procesov. Formuloval ho Edsger Dijkstra v roku 1965. Každý operačný systém má správu procesov, čo je vlastne algoritmus, ktorý riadi vznik, zánik a plánovanie procesov (bežiacich programov) v operačnom systéme.
Opis problému
Predstavme si okrúhly stôl, na ktorom je po obvode položených 5 tanierov. Medzi každými dvoma taniermi je jedna čínska palička, spolu je ich teda 5. Ďalej si predstavme, že za týmto stolom sedí 5 filozofov, každý za svojím tanierom. Filozof predstavuje nejaký proces. Filozof môže vykonávať dve činnosti - buď obeduje alebo filozofuje. Aby mohol obedovať, musí si zobrať dve čínske paličky. Ak chce filozofovať, nedrží ani jednu paličku.
Keď filozofi (procesy) spolu nekomunikujú alebo komunikujú nesprávne, každý sa môže rozhodnúť, že vezme napríklad ľavú paličku. Teraz chce každý z nich zobrať pravú paličku, no tá je obsadená, takže filozof nemôže ani obedovať, ani filozofovať. Takýto stav sa nazýva uviaznutie (deadlock). Musí buď počkať, kým sa palička uvoľní, alebo paličku položiť a skúsiť to neskôr znova.
Iným kritickým stavom je vyhladovanie (starvation), ktoré nastáva, keď sa filozof nedostane po určitom čase k jedeniu (resp. proces k zdrojom). Nastáva napríklad pri veľmi rýchlych intervaloch jedenia a filozofovania.
Vyhladovanie by mohlo tiež nastať nezávisle od deadlock-u, ak je filozof neschopný získať obidve vidličky počas istého časového úseku. Napríklad môžeme uvažovať pravidlo, že filozof pustí jednu držanú vidličku z ruky za 5 minút od jej odchytenia a čaká ďalších 5 minút na to, aby urobil ďalší pokus najesť sa. Táto schéma eliminuje možnosť deadlock-u (systém sa vždy môže dostať do iného stavu), ale stále trpí problémom livelock-u. Keď totiž všetci filozofi položia naraz vidličky a potom si ich za 5 minút opäť vezmú, situácia sa opakuje, znovu majú po jednej vidličke všetci filozofi.
Nedostatok voľných vidličiek je analógia ku zamykaniu zdieľaných prostriedkov v reálnom počítačovom programovaní, situácia známa, ako súbežnosť. Zamykanie prostriedku je bežná technika, ako zaistiť konzistenciu konkrétneho zdroja v čase. Keď zdroj, s ktorým program pracuje, už je zamknutý iným programom, program čaká dovtedy, pokým nie je odomknutý. Ak niektoré programy vyžadujú zamykanie zdrojov, môže nastať deadlock, závisiac na okolnostiach. Napríklad, jeden program potrebuje dva súbory na spracovanie. Keď dva také programy uzamknú každý jeden z týchto súborov, obidva budú čakať na to, aby ten druhý uvoľnil zdroj, ktorý má k dispozícii, čo sa nikdy nestane.
Vo všeobecnosti je problém obedujúcich filozofov bežný abstraktným problémom používaným na vysvetlenie rozdielnych otázok, ktoré sa objavia v záležitosti vzájomnej výlučnosti, ako hlavnej myšlienky daného problému. Napríklad, ako je vysvetlené aj v prípade deadlock/livelock.
Riešenia
Riešenie s čašníkom
Jednoduché riešenie sa dá dosiahnuť zavedením čašníka pri stole. Čašník určí, kto si paličky zoberie, čo v podstate vyrieši problém rozhodovania. Pretože si uvedomuje, ktoré paličky sú použité, je schopný rozhodnúť a zabrániť tak deadlock-u. Nakoľko na stole zostala v prípade 5 filozofov ešte jedna palička, je zrejmé, že nasledovať v jedení bude ten filozof, ktorý sa stal jej dočasným majiteľom. Tomu potom čašník prisúdi paličku, ktorú akurát obsluhuje vedľa sediaci filozof.
Predstavme si, že to funguje nasledovne: Označme si filozofov podľa hodinových ručičiek od A po E. Ak A a C jedia, tak sú použité 4 vidličky. B nemá k dispozícii žiadnu paličku, pokiaľ D a E majú medzi sebou jednu nevyužitú paličku. Povedzme, že D chce jesť. Ak by si filozof túto paličku zobral, môže nastať deadlock. V našom prípade však o tom rozhoduje čašník, ktorý vie, že treba počkať na uvoľnenie ďalšej paličky, aby sa neskôr mohol aspoň jeden filozof naobedovať.
Riešenie s hierarchiou zdrojov
Ďalšie jednoduché riešenie dostaneme vyhradením čiastočného poradia, alebo hierarchie pre zdroje (v tomto prípade paličky), a zriadením konvencie, že všetky zdroje budú dosahované v určitom poradí a v opačnom poradí uvoľnené. V našom prípade budú zdroje (paličky) číslované od 1 po 5 v nejakom poradí a každý filozof si vždy zoberie najskôr paličku s menším číslom a až potom paličku s väčším číslom. Potom vždy položí najskôr paličku s vyšším číslom, nasledovanú paličkou s menším číslom. Ak teda 5 filozofov simultánne zdvihnú paličku s menším číslom, tak zostane na stole palička s najväčším číslom, takže 5. filozof bude bez paličky. Navyše iba jeden z filozofov bude mať prístup k obom paličkám. Keď doje, položí obe paličky, pričom tú paličku s nižším číslom položí skôr, čo umožní, aby sa najedol filozof sediaci vedľa neho.
Toto riešenie i napriek vyhýbaniu sa deadlock-om nie je veľmi praktické, špeciálne v prípade, ak nepoznáme vopred používanú množinu zdrojov. Napríklad, ak program drží zdroje 3, 5 a potrebuje ešte zdroj 2, musí vypustiť zdroj 5, potom 3, aby mohol požiadať o 2 a opäť požiadať o zdroje 3 a 5 v tomto poradí. Práve preto je tento spôsob veľmi neefektívny.
Chandyho - Misrovo Riešenie
V roku 1984, K. Mani Chandy a J. Misra navrhli iné riešenie problému obedujúcich filozofov, aby povolili ľubovoľnému počtu programov (očíslovaných P1, ..., Pn) bojovať o ľubovoľný počet zdrojov (očíslovaných R1, ..., Rm). Na rozdiel od Dijkstrovho riešenia, môžu byť tieto označenia ľubovoľné. Teda nejde o naozajstný problém obedujúcich filozofov, pretože vyžaduje ich vzájomné komunikovanie.
- Pre každý pár filozofov bojujúcich o zdroj vytvor vidličku a daj ju filozofovi s nižším ID. Každá vidlička môže byť buď špinavá, alebo čistá. Na začiatku je každá vidlička špinavá.
- V prípade, že chce filozof použiť množinu zdrojov, musí dostať vidličky od svojich súperiacich susedov. Pre všetky také vidličky pošle žiadanku.
- Filozof, ktorý dostane takúto požiadavku si vidličku nechá, ak je čistá a v opačnom prípade ju prenechá žiadajúcemu filozofovi. Predtým, ako túto vidličku pošle filozofovi, ju najskôr očistí.
- Potom, ako filozof doje, všetky jeho vidličky sú špinavé. Ak nejaký filozof predtým požiadal o vidličku, filozof, ktorý ju momentálne vlastní, ju očistí a pošle.
Toto riešenie povoľuje veľké množstvo súbežných programov a vyrieši ľubovoľne veľký problém domnievajúc sa, že každé vlákno potrebuje práve jeden zdroj v čase.
Pozri aj
Externé odkazy
- Problém obedujúcich filozofov - interaktívny Java applet Archivované 2011-08-11 na Wayback Machine (po anglicky) (po francúzsky) (po nemecky)
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.
Antény
Chemické zdroje elektriny
Chladenie v elektrotechnike
Elektrická sústava automobilu
Elektrická trakcia
Elektrické prístroje
Elektrické súčiastky
Elektrické spotrebiče
Elektrické stroje
Čítanie (elektrotechnika)
Činný výkon
Štatistická dynamika
Živý vodič
Admitancia
Antiparalelné zapojenie
Asynchrónny motor
Blúdivý prúd
Bočník (elektrotechnika)
Diak (polovodičový prvok)
Displej s kvapalnými kryštálmi
Elektrická inštalácia
Elektrická rezonancia
Elektrická sila
Elektrická vodivosť
Elektrické zariadenie
Elektrický obvod
Elektrický zvonec
Elektroenergetika
Elektromer
Elektrometer
Elektromobil
Elektromotor
Elektromotorické napätie
Elektrotechnický náučný slovník
Elektrotechnika
Elektrotechnológia
Fázor
Faradayova klietka
Frekvencia (fyzika)
Graetzov mostík
Impedancia
Indukčnosť
Induktancia
Istič
Izolácia (elektrotechnika)
Izolant
Jadro vodiča
Jednobran
Jednosmerný prúd
Joulovo teplo
Katóda
Koaxiálny kábel
Kompenzácia účinníka
Konduktometria
Konektor (elektrotechnika)
Korónový výboj
Lanko (elektrotechnika)
Leptanie
Logické hradlo
Magnetická susceptibilita
Magnetizácia (veličina)
Merný elektrický odpor
Mobilné zariadenie
Napájací zdroj
Napäťový chránič
Napäťový násobič
Nortonova veta
Odpínač
Odpojovač
OLED
Olovený akumulátor
Paralelné zapojenie
Peltierov článok
Plošná hustota elektrického prúdu
Poistka (elektrotechnika)
Posuvný prúd
Prúdový chránič
Prenosové médium
Prieletový klystrón
Primárny elektrochemický článok
Reaktancia
Rekuperácia (dopravný prostriedok)
Relé
Reproduktorová výhybka
Rezistancia
Rozhranie (interface)
Sériové zapojenie
Seebeckov jav
Sekundárny elektrochemický článok
Settopbox
Skrat
Sonar
Spínač
Spínaný zdroj
Straty v mikropásikových vedeniach
Striedavý prúd
Stupeň ochrany krytom
Svetelná výbojka
Symetrizačný člen
Technická normalizácia
Tepelné relé
Tepelne vodivostný detektor
Termočlánok
Théveninova veta
Transformátor
Transformátor s fázovou reguláciou
Trojfázová sústava
Tuhá fáza (elektronika)
Tyratrón
Usmerňovač (elektrotechnika)
Uzemnenie
Uzol (vodiče)
Vírivý prúd
Výbojka
Varistor
Ventilátor
Vodič (elektrotechnika)
Voltov stĺp
Vstavaný systém
Zásuvka (elektrotechnika)
Zdroj (elektrotechnika)
Zisk antény
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