Problém kuřáků cigaret je synchronizační problém v informatice původně popsaný v roce 1971 Suhasem S. Patilem [1] .
Zpočátku u stolu sedí tři silní kuřáci. Každý z nich má přístup k nekonečnému množství jedné ze tří složek: jeden kuřák má tabák , druhý papír a třetí zápalky . Všechny tři složky jsou potřebné k výrobě a kouření cigaret.
Kromě kuřáků je tu také barman, který jim pomáhá vyrábět cigarety: nedeterministicky vybere dva kuřáky, vezme jednu složku ze zásob a položí je na stůl. Třetí kuřák vezme ze stolu ingredience a použije je k výrobě cigarety, kterou chvíli kouří. V tomto okamžiku barman, když vidí, že stůl je prázdný, opět náhodně vybere dva kuřáky a položí jejich součásti na stůl. Proces se donekonečna opakuje.
Kuřáci jsou podle stavu problému poctiví: ingredience vydávané barmanem neschovávají – cigaretu si ubalí, až když dokouří předchozí. Pokud barman položí na stůl například tabák a papír, zatímco dodavatel zápalek kouří, pak tabák a papír zůstanou na stole nedotčené, dokud kuřák zápalek nedokouří cigaretu a teprve potom si tabák a papír vezme.
Podle Patilova argumentu problém ilustruje omezení Dijkstrových semaforů , protože není možné zajistit, aby proces pokračoval donekonečna za následujících podmínek:
Podle kritiků Patilova díla je druhé omezení přehnané a znemožňuje vyřešit jakýkoli netriviální problém.
Pokud zahodíme druhou podmínku, lze problém vyřešit použitím jednoduchých semaforů ( mutexů ).
Tento problém je za splnění podmínek řešen na víceprocesorových systémech pomocí paralelního programování .