El problema de los fumadores de cigarrillos es un problema de sincronización en informática descrito originalmente en 1971 por Suhas S. Patil [1] .
Inicialmente, hay tres grandes fumadores sentados en una mesa. Cada uno de ellos tiene acceso a una cantidad infinita de uno de los tres componentes: un fumador tiene tabaco , el segundo tiene papel y el tercero fósforos . Los tres componentes son necesarios para fabricar y fumar cigarrillos.
También, además de los fumadores, hay un cantinero que les ayuda a hacer cigarrillos: selecciona de manera no determinista a dos fumadores, toma un componente de sus existencias y los pone sobre la mesa. El tercer fumador toma los ingredientes de la mesa y los utiliza para hacer un cigarrillo, que fuma durante un rato. En este momento, el cantinero, al ver la mesa vacía, vuelve a seleccionar dos fumadores al azar y pone sus componentes sobre la mesa. El proceso se repite infinitamente.
Los fumadores, según la condición del problema, son honestos: no ocultan los ingredientes que les da el cantinero, sólo lian un cigarrillo cuando terminan de fumar el anterior. Si el cantinero pone, por ejemplo, tabaco y papel sobre la mesa mientras el proveedor de fósforos fuma, entonces el tabaco y el papel permanecerán intactos sobre la mesa hasta que el fumador de fósforos termine su cigarrillo y solo entonces tome el tabaco y el papel.
Según el argumento de Patil, el problema ilustra las limitaciones de los semáforos de Dijkstra , ya que es imposible asegurar que el proceso continúe indefinidamente bajo las siguientes condiciones:
Según los críticos del trabajo de Patil, la segunda limitación es excesiva y hace imposible resolver cualquier problema no trivial.
Si descartamos la segunda condición, el problema se puede resolver usando semáforos simples ( mutexes ).
Este problema, sujeto a las condiciones, se resuelve en sistemas multiprocesador usando programación paralela .