Problém kuřáků cigaret

Problém kuřáků cigaret je problém souběžného řízení (anglicky concurrency problem), který původně popsal v roce 1971 S. S. Patil.

Popis problému

Předpokládejme, že cigareta vyžaduje tři ingredience, aby mohla být vykouřena:

1. tabák
2. papír
3. zápalky

Dále předpokládejme, že kolem stolu jsou tři kuřáci, z nichž každý má nekonečné zásoby jedné ze tří ingrediencí – jeden kuřák má nekonečné zásoby tabáku, další má nekonečné zásoby papíru a třetí má nekonečné zásoby zápalek.

Předpokládejme také, že je zde rozhodčí nekuřák. Rozhodčí umožňuje kuřákovi vyrobit si cigaretu tak, že si vybere naslepo (nedeterministicky) dva kuřáky, vezme jednu položku z jejich zdrojů a umístí tyto položky na stůl. Následně upozorní třetího kuřáka, že provedl tuto akci. Třetí kuřák vezme věci ze stolu a použije je (spolu se svým vlastním zdrojem) pro výrobu cigarety, kterou bude následně chvíli kouřit. Mezitím rozhodčí rozhodne, že stůl je opět prázdný, znovu náhodně vybere dva kuřáky a umístí jejich věci na stůl. Tento proces pokračuje donekonečna.

Kuřáci si neshromažďují věci ze stolu; kuřák si začne opět balit další cigaretu, pouze pokud již dokouřil poslední. Pokud by rozhodčí položil tabák a papír na stůl, zatímco muž se zápalkami kouří, tabák a papír zůstanou nedotčeny na stole, dokud tento kuřák nedokouří svou cigaretu a nesebere je.

Problém sestává ze simulování všech čtyř rolí na úrovni softwarového programu, s použitím pouze určitého množství synchronizace proměnných. V Patilově původní formulaci byly jediné povolené synchronizační proměnné semafory a žádný ze čtyř programů neměl dovoleno obsahovat podmíněné skoky – podmíněno bylo jen čekání vyplývající z operací wait u semaforů.

Polemika

Patilova polemika spočívala v tom, že Dijkstrovy semafory byly omezené. Použil problém kuřáků cigaret, aby ilustroval názor, že tento problém nemůže být ošetřen pouze semafory. Patil ale vložil do své polemiky velká omezení:

1. kód prostředku není modifikovatelný
2. v řešení není možné použít podmínkové příkazy ani pole semaforů

S oběma omezeními je problém kuřáků cigaret neřešitelný.

První omezení dává smysl, jak řekl Downey v The Little Book of Semaphores^[1], protože kdyby prostředek reprezentoval operační systém, bylo by neakceptovatelné, aby byl měněn pokaždé, když se objeví nová aplikace. Na druhou stranu, jak již podotkl David Parnas, druhé omezení by činilo téměř každý netriviální problém neřešitelným:

Nicméně důležité je, že toto zkoumání Dijkstrových primitiv nezjistí jejich sílu pomocí umělých omezení. Pod slovem umělý myslíme omezení, která nemohou být zdůvodněna v praktických ohledech. Podle názoru tohoto autora jsou omezení zakazující podmínky nebo pole semaforů umělá. Na druhé straně, zakázat aktivní čekání je poměrně realistické.

Řešení

Pokud bychom odstranili druhé z Patilových omezení, problém kuřáků cigaret by se stal řešitelným použitím binárních semaforů neboli mutexů. Nadefinujme pole binárních semaforů A, kde každý semafor bude patřit jinému z kuřáků a také jeden binární semafor pro stůl, který označíme T. Na začátku inicializujete všechny semafory kuřáků na 0 a semafor stolu na 1. Kód pro rozhodčí bude následující:

while true ( 
wait (T); 
vyber kuřáky i a j nedeterministicky, kde třetí z kuřáků bude k 
signal (A [k]); 
) 

kód pro kuřáka i:

while true ( 
wait (A [i]); 
udělej cigaretu 
signal (T);
vykuř cigaretu 
)

Literatura

• 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

Reference

Související články

• Problém producenta a spotřebitele
• Problém obědvajících filosofů
• Problém spícího holiče
• Problém čtenářů a písařů