De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda
Este artículo trata sobre el problema de la informática. Para problemas que pueden afectar a los fumadores de cigarrillos, consulte Efectos del tabaco en la salud .

El problema de los fumadores de cigarrillos es un problema de concurrencia en la informática , descrito originalmente en 1971 por Suhas Patil .

Descripción del problema [ editar ]

Suponga que un cigarrillo requiere tres ingredientes para hacer y fumar: tabaco, papel y fósforos. Hay tres fumadores alrededor de una mesa, cada uno de los cuales tiene un suministro infinito de uno de los tres ingredientes: un fumador tiene un suministro infinito de tabaco, otro tiene papel y el tercero tiene fósforos.

También hay un agente para no fumadores que permite a los fumadores fabricar sus cigarrillos seleccionando de forma arbitraria ( no determinista ) dos de los suministros para colocarlos sobre la mesa. El fumador que tiene el tercer suministro debe retirar los dos artículos de la mesa y usarlos (junto con el suyo propio) para hacer un cigarrillo, que fuma durante un tiempo. Una vez que el fumador ha terminado su cigarrillo, el agente coloca dos nuevos artículos al azar sobre la mesa. Este proceso continúa para siempre.

Se utilizan tres semáforos para representar los elementos de la mesa; el agente aumenta el semáforo apropiado para indicar que se ha colocado un artículo sobre la mesa, y los fumadores reducen el semáforo al retirar artículos. Además, cada fumador tiene un semáforo asociado que utiliza para indicarle al agente que el fumador en particular ha dejado de fumar; el agente tiene un proceso que espera en el semáforo de cada fumador para informarle que puede colocar los nuevos artículos sobre la mesa.

Una implementación de pseudocódigo simple del fumador que tiene el suministro de tabaco podría tener el siguiente aspecto:

def  fumador_tabaco ():  repetir :  papel . esperar ()  coincide . esperar ()  fumar ()  tabaco_fumador_done . señal ()

Sin embargo, esto puede llevar a un punto muerto; si el agente coloca papel y tabaco sobre la mesa, el fumador con tabaco puede quitar el papel y el fumador con fósforos puede tomar el tabaco, dejando a ambos sin poder hacer su cigarrillo. La solución es definir procesos y semáforos adicionales que eviten el interbloqueo, sin modificar el agente.

Argumento [ editar ]

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

  1. El código de agente no se puede modificar.
  2. La solución no puede usar declaraciones condicionales.

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

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. [3] Sin embargo, Parnas argumenta que la segunda restricción no está justificada:

Las limitaciones informadas por Patil son limitaciones de sus primitivas, pero no son limitaciones de las primitivas descritas por Dijkstra. ... Es importante, sin embargo, que tal investigación [de las primitivas de Dijkstra] no investigue el poder de estas primitivas bajo restricciones artificiales. Por artificial entendemos restricciones que no pueden justificarse por consideraciones prácticas. En opinión de este autor, las restricciones que prohíben los condicionales o las matrices de semáforos son artificiales. [2]

Referencias [ editar ]

  1. ^ Patil, Suhas S. (febrero de 1971). Limitaciones y capacidades de las primitivas de semáforo de Dijkstra para la coordinación entre procesos (informe técnico). MIT , Proyecto MAC , Grupo de Estructuras de Computación. Memo 57.
  2. ↑ a b Parnas, David L. (marzo de 1975). "Sobre una solución al problema de los fumadores de cigarrillos (sin declaraciones condicionales)" (PDF) . Comunicaciones de la ACM . 18 (3): 181–183. doi : 10.1145 / 360680.360709 .
  3. ^ Downey, Allen B. El pequeño libro de los semáforos (2ª ed.) . Consultado el 29 de junio de 2015 .