A cigarettázók problémája egy szinkronizációs probléma a számítástechnikában, amelyet eredetileg 1971 -ben írt le Suhas S. Patil [1] .
Kezdetben három erős dohányos ül egy asztalnál. Mindegyikük végtelen mennyiségben fér hozzá a három összetevő egyikéhez: az egyik dohányosnak dohánya van , a másiknak papír , a harmadiknak pedig gyufa . Mindhárom összetevő szükséges a cigaretta készítéséhez és elszívásához.
A dohányosok mellett van egy pultos is, aki segít nekik cigarettát készíteni: nem- determinisztikusan kiválaszt két dohányost, kivesz egy komponenst a készletéből, és az asztalra teszi. A harmadik dohányos előveszi az asztalról a hozzávalókat, és cigarettát készít belőle, amit egy ideig elszív. Ekkor a csapos üres asztalt látva ismét véletlenszerűen választ ki két dohányost, és az asztalra teszi a hozzájuk tartozó alkatrészeket. A folyamat vég nélkül ismétlődik.
A dohányosok a probléma állapotának megfelelően őszinték: nem titkolják el a pultos által kiadott hozzávalókat - csak akkor sodornak cigarettát, amikor befejezték az előző elszívást. Ha a csapos például dohányt és papírt tesz az asztalra, miközben a gyufaszállító dohányzik, akkor a dohány és a papír érintetlenül marad az asztalon, amíg a gyufafüst el nem fogyasztja a cigarettáját, és csak ezután veszi el a dohányt és a papírt.
Patil érvelése szerint a probléma jól illusztrálja Dijkstra szemaforjainak korlátait , mivel lehetetlen biztosítani, hogy a folyamat a végtelenségig folytatódjon a következő feltételek mellett:
Patil munkásságának kritikusai szerint a második korlát túlzó, és lehetetlenné teszi bármely nem triviális probléma megoldását.
Ha a második feltételt elvetjük, a probléma megoldható egyetlen szemaforok ( mutexe ) használatával.
Ezt a problémát a feltételektől függően többprocesszoros rendszereken párhuzamos programozással oldják meg .