Problemet med cigarettrökare är ett synkroniseringsproblem inom datavetenskap som ursprungligen beskrevs 1971 av Suhas S. Patil [1] .
Till en början sitter det tre storrökare vid ett bord. Var och en av dem har tillgång till en oändlig mängd av en av de tre komponenterna: en rökare har tobak , den andra har papper och den tredje har tändstickor . Alla tre komponenterna behövs för att tillverka och röka cigaretter.
Förutom rökare finns det också en bartender som hjälper dem att tillverka cigaretter: han väljer ut två rökare på ett icke- deterministiskt sätt, tar en komponent från deras lager och lägger dem på bordet. Den tredje rökaren tar ingredienserna från bordet och använder dem för att göra en cigarett, som han röker en stund. Vid denna tidpunkt väljer bartendern, som ser bordet tomt, återigen två rökare slumpmässigt och lägger deras komponenter på bordet. Processen upprepas i det oändliga.
Rökare, beroende på problemets tillstånd, är ärliga: de döljer inte ingredienserna som bartendern ger ut - de rullar bara en cigarett när de är klara med att röka den föregående. Om bartendern lägger till exempel tobak och papper på bordet medan tändsticksleverantören röker, så kommer tobaken och papperet att ligga orörda på bordet tills tändsticksrökaren avslutar sin cigarett och först därefter tar tobaken och papperet.
Enligt Patils argument illustrerar problemet begränsningarna i Dijkstras semaforer , eftersom det är omöjligt att säkerställa att processen fortsätter på obestämd tid under följande förhållanden:
Enligt kritiker av Patils arbete är den andra begränsningen överdriven och gör det omöjligt att lösa något icke-trivialt problem.
Om vi förkastar det andra villkoret kan problemet lösas genom att använda enstaka semaforer ( mutexes ).
Detta problem, med förbehåll för villkoren, löses på multiprocessorsystem som använder parallell programmering .