Problém fajčiarov cigariet

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]);
}

kód pre fajčiara i:

while true {
    wait(A[i]);
    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

Problém spiaceho holiča