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 fajčiarov cigariet je problém, založený na súbežnosti, ktorý bol pôvodne popísaný v roku 1971 S. S. Patilom.
Opis problému
Predpokladajme, že cigareta vyžaduje tri ingrediencie, aby mohla byť vyfajčená:
Ďalej predpokladajme, že okolo stola sú traja ťažkí fajčiari, z ktorých každý má nekonečné zásoby jednej z troch ingrediencií – jeden fajčiar má nekonečné zásoby tabaku, ďalší má nekonečné zásoby papieru, a tretí má nekonečné zásoby zápaliek.
Predpokladajme tiež, že je tu nefajčiaci rozhodca. Rozhodca umožňuje fajčiarovi vyrobiť si cigaretu, tak, že si vyberie dvoch fajčiarov naslepo (nedeterministicky), zoberie jednu položku z ich zdrojov a umiestni tieto položky na stôl. Následne upozorní tretieho fajčiara, že vykonal túto akciu. Tretí fajčiar zoberie veci zo stola a použije ich (spolu s jeho vlastným zdrojom) na vyrobenie cigarety, ktorú bude následne chvíľu fajčiť. Medzitým, rozhodca vidiac, že stôl je opäť prázdny, znovu náhodne vyberie dvoch fajčiarov a umiestni ich veci na stôl. Tento proces pokračuje do nekonečna.
Fajčiari si nezhromažďujú veci zo stola; fajčiar si začne opäť rolovať ďalšiu cigaretu, iba pokiaľ už dofajčil poslednú. Pokiaľ by rozhodca položil tabak a papier na stôl, zatiaľ čo muž so zápalkami fajčí, tabak a papier zostanú nedotknuté na stole, dokým tento fajčiar nedofajčí svoju cigaretu a nezoberie ich.
Problém pozostáva zo simulovania všetkých štyroch rolí na úrovni softvérového programu, použitím len určitého množstva synchronizačných premenných. V Patilovej pôvodnej formulácii jediné synchronizačné premenné, ktoré boli povolené, boli semafory a žiadny zo štyroch programov nemal dovolené obsahovať podmienené skoky – jedine podmienené čakania vyplývajúce z wait
operácií semaforov.
Polemika
Patilova polemika spočívala v tom, že Edsger Dijkstrove semafory boli limitované. Použil problém fajčiarov cigariet, aby ilustroval tento názor tvrdiac, že tento problém nemôže byť ošetrený iba semaformi. Predsa len, Patil vložil veľké obmedzenia do svojej polemiky:
- Kód prostriedku nie je modifikovateľný.
- V riešení nie je možné použiť podmienkové príkazy, alebo pole semaforov.
S týmito dvoma obmedzeniami je problém fajčiarov cigariet neriešiteľný.
Prvé obmedzenie dáva zmysel, ako povedal Downey v The Little Book of Semaphores Archivované 2009-04-24 na Wayback Machine, pretože keby prostriedok reprezentoval operačný systém, mohlo by to byť neznesiteľné, pozmeniť ho zakaždým, keď by sa vyskytla nová aplikácia. Predsa len, ako už podotkol David Parnas, druhé z obmedzení nevytvára žiadny netriviálny problém, ktorý by sme nevedeli riešiť:
- Ale dôležité je, že toto skúmanie Dijkstrových primitív nezistí silu týchto primitív pod umelými obmedzeniami. Pod slovom umelý myslíme obmedzenia, ktoré nemôžu byť odôvodnené v praktických hľadiskách. Podľa názoru tohoto autora, obmedzenia zakazujúce, či už podmienky, alebo pole semaforov, sú umelé. Na druhej strane, zakázanie „činného čakania“ je pomerne realistické.
Riešenie
Pokiaľ by sme odstránili druhé z Patilových obmedzení, problém fajčiarov cigariet by sa stal riešiteľný použitím binárnych semaforov, alebo mutexov. Zadefinujme si pole binárnych semaforov ako A, kde každý semafor bude patriť inému z fajčiarov; a tiež jeden binárny semafor pre stôl, označme ho ako T. Na začiatku inicializujeme všetky semafory fajčiarov na 0 semafor stola na 1. Rozhodcov kód bude nasledovný:
while true { wait(T); vyber fajčiarov i a j nedeterministicky, kde tretí z fajčiarov bude k signal(A); }
kód pre fajčiara i:
while true { wait(A); vyrob cigaretu signal(T); vyfajči cigaretu }
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
- On a solution to the cigarette smokers' problem without conditional statements, by David Parnas, Communications of the ACM, 18:181-183, March 1975
- Limitations and capabilities of Dijkstra's semaphore primitives for coordination among processes, by Suhas Patil, technical report, MIT, 1971
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.
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