Problema de fumadores de cigarrillos

El problema de los fumadores es un problema clásico de concurrencia en informática, introducido por Suhas Patil en 1971. Ilustra los desafíos de sincronización en sistemas multiproceso, donde múltiples procesos (fumadores) compiten por recursos limitados (ingredientes) proporcionados por un único agente. El problema destaca por sus restricciones, como la inmutabilidad del comportamiento del agente y la prohibición de sentencias condicionales en las soluciones, que han sido objeto de críticas. ^{[ 1 ]}

El problema de Patil incluye una restricción "bastante arbitraria" ^{[ 1 ]} "de que el proceso que suministra los ingredientes no se puede cambiar y no se pueden usar declaraciones condicionales". ^{[ 2 ]}

Supongamos que para fabricar y fumar un cigarrillo se necesitan tres ingredientes: tabaco, papel y cerillas. Hay tres fumadores alrededor de una mesa, cada uno con una cantidad ilimitada de uno de los tres ingredientes : uno tiene tabaco ilimitado, otro papel y el tercero cerillas.

También hay un agente no fumador que permite a los fumadores fabricar sus cigarrillos seleccionando arbitrariamente ( de forma no determinista ) dos de los suministros para colocarlos sobre la mesa. El fumador que tenga el tercer suministro debe retirar los dos elementos de la mesa y usarlos (junto con su propio suministro) para fabricar un cigarrillo, que fuma durante un rato. Una vez que el fumador termina su cigarrillo, el agente coloca dos nuevos elementos al azar sobre la mesa. Este proceso continúa indefinidamente.

Se utilizan tres semáforos para representar los objetos sobre la mesa; el agente incrementa el semáforo correspondiente para indicar que se ha colocado un objeto, y los fumadores lo decrementan al retirar objetos. Además, cada fumador tiene un semáforo asociado que utiliza para indicar al agente que ha terminado de fumar; el agente dispone de un proceso que espera a que el semáforo de cada fumador le indique que puede colocar los nuevos objetos sobre la mesa.

Una implementación sencilla en pseudocódigo del fumador que tiene el suministro de tabaco podría ser la siguiente:

def tobacco_smoker (): repetir : papel . esperar () coincidencias . esperar () fumar () tobacco_smoker_hecho . señal ()

Sin embargo, esto puede provocar un bloqueo; si el agente coloca papel y tabaco sobre la mesa, el fumador con tabaco podría retirar el papel y el fumador con cerillas podría tomar el tabaco, impidiendo que ambos puedan preparar su cigarrillo. La solución consiste en definir procesos y semáforos adicionales que eviten el bloqueo, sin modificar al agente.

Patil impuso las siguientes restricciones al problema de los fumadores de cigarrillos:

1. El código del agente no es modificable.
2. La solución no permite el uso de sentencias condicionales.

Patil utilizó una demostración en términos de redes de Petri para afirmar que una solución al problema de los fumadores de cigarrillos utilizando las primitivas de semáforo de Edsger Dijkstra es imposible, y para sugerir que se necesita una primitiva más potente. ^{[ 3 ] [ 2 ]} Sin embargo, David Parnas demostró que la demostración de Patil es inadecuada si se utilizan matrices de semáforos, ofreciendo una solución que utiliza procesos auxiliares que realizan operaciones aritméticas para indicar al fumador apropiado que proceda. ^{[ 1 ]}

Según Allen B. Downey , la primera restricción tiene sentido, porque si el agente representa un sistema operativo , sería irrazonable o imposible modificarlo cada vez que apareciera una nueva aplicación. ^{[ 4 ]} Sin embargo, Parnas argumenta que la segunda restricción no está justificada:

Las limitaciones que menciona Patil son limitaciones de sus primitivas, pero no de las primitivas descritas por Dijkstra. … Sin embargo, es importante que dicha investigación [de las primitivas de Dijkstra] no analice el poder de estas primitivas bajo restricciones artificiales. Por artificiales entendemos restricciones que no pueden justificarse mediante consideraciones prácticas. En opinión de este autor, las restricciones que prohíben las condicionales o las matrices de semáforos son artificiales. ^{[ 1 ]}

• El problema de los filósofos comensales
• El problema de los lectores y escritores
• El problema de los barberos dormidos