The Dining Philosophers Problem es un ejemplo clásico utilizado en informática para ilustrar problemas de sincronización en el desarrollo de algoritmos paralelos y técnicas para resolver estos problemas.
El problema fue formulado en 1965 por Edsger Dijkstra como un ejercicio de examen para estudiantes. Se tomó un ejemplo de acceso competitivo a una unidad de cinta . Pronto el problema fue formulado por Anthony Hoare en la forma en que se conoce hoy [1] [2] [3] .
Cinco filósofos silenciosos se sientan alrededor de una mesa redonda, con un plato de espagueti frente a cada filósofo. Los tenedores se encuentran sobre la mesa entre cada par de filósofos más cercanos.
Todo filósofo puede comer o pensar. Comer no está limitado por la cantidad de espagueti que queda; se implica un suministro infinito. Sin embargo, el filósofo solo puede comer cuando sostiene dos tenedores, tomados de la derecha y de la izquierda (una formulación alternativa del problema implica tazones de arroz y palillos en lugar de tazones de espaguetis y tenedores).
Cada filósofo puede tomar el tenedor más cercano (si hay uno disponible) o dejarlo si ya tiene uno en la mano. Recoger cada tenedor y devolverlo a la mesa son acciones separadas que deben realizarse una tras otra.
La cuestión de la tarea es desarrollar un modelo de comportamiento ( algoritmo paralelo ) en el que ninguno de los filósofos se muera de hambre, es decir, siempre alternará entre comer y pensar.
El problema está formulado de tal manera que ilustra el problema de evitar un punto muerto , un estado del sistema en el que el progreso es imposible.
Por ejemplo, se podría aconsejar a todos los filósofos que realicen el siguiente algoritmo:
Esta solución al problema es incorrecta: permite que el sistema alcance un estado de interbloqueo, donde cada filósofo ha tomado la bifurcación de la izquierda y está esperando que la bifurcación de la derecha se libere [4] .
El problema de escasez de recursos puede ocurrir independientemente del interbloqueo si uno de los filósofos no puede controlar las bifurcaciones izquierda y derecha debido a problemas de sincronización. Por ejemplo, se podría proponer una regla según la cual los filósofos deben volver a poner un tenedor sobre la mesa después de esperar cinco minutos a que haya otro disponible, y esperar otros cinco minutos antes de intentar tomar posesión de los tenedores nuevamente. Este esquema elimina la posibilidad de bloqueo (ya que el sistema siempre puede pasar a otro estado), pero aún existe la posibilidad de un "bucle" del sistema ( ing. livelock ), en el que el estado del sistema cambia, pero no realiza ningún trabajo útil. Por ejemplo, si los cinco filósofos se presentan en el comedor al mismo tiempo y cada uno toma el tenedor izquierdo al mismo tiempo, los filósofos esperarán cinco minutos con la esperanza de obtener el tenedor correcto, luego dejarán el tenedor izquierdo y esperarán. otros cinco minutos antes de intentar conseguir los tenedores.
La exclusión mutua es la idea principal del Problema de los Filósofos Comedores. Este problema es un escenario general y abstracto para explicar este tipo de problema. Los errores de los filósofos ilustran las dificultades que surgen en la programación real cuando múltiples programas requieren acceso exclusivo a recursos compartidos. Estas cuestiones se estudian en el campo de la computación paralela .
El objetivo original de Dijkstra al formular el problema del filósofo comedor era demostrar posibles problemas con dispositivos informáticos externos, como unidades de cinta [1] . Sin embargo, el alcance de esta tarea se extiende mucho más y las complejidades consideradas en la tarea surgen con mayor frecuencia cuando varios procesos intentan acceder a un conjunto de datos que se está actualizando.
Los sistemas que deben lidiar con una gran cantidad de procesos simultáneos (como los núcleos del sistema operativo ) utilizan miles de bloqueos y puntos de sincronización. Esto requiere un cumplimiento estricto de las metodologías y los protocolos si se quiere evitar los interbloqueos, el hambre y la corrupción de datos.
Una solución relativamente simple al problema se logra agregando un mesero cerca de la mesa. Los filósofos deben esperar el permiso del camarero antes de tomar el tenedor. Debido a que el mesero sabe cuántos tenedores están actualmente en uso, puede tomar decisiones sobre la distribución de los tenedores y así evitar que los filósofos lleguen a un punto muerto. Si cuatro de los cinco tenedores ya están en uso, el próximo filósofo que solicite un tenedor tendrá que esperar el permiso del camarero, que no se recibirá hasta que se suelte el tenedor. Se supone que el filósofo siempre intenta tomar primero la bifurcación de la izquierda y luego la de la derecha (o viceversa), lo que simplifica la lógica. El camarero funciona como un semáforo , concepto introducido por Dijkstra en 1965 [5] .
Para mostrar cómo funciona esta solución, supongamos que los filósofos están etiquetados de la A a la D en el sentido de las agujas del reloj. Si los filósofos A y B están comiendo, entonces están ocupados cuatro tenedores. El filósofo B se sienta entre A y C, de modo que ninguno de los tenedores está disponible para él. Al mismo tiempo, los filósofos D y D tienen acceso a un tenedor sin usar entre ellos. Supongamos que el filósofo G tiene hambre. Si inmediatamente toma un tenedor libre, entonces se hace posible el bloqueo mutuo de los filósofos. Si, en cambio, le pide permiso al camarero, le pide que espere, y puede estar seguro de que tan pronto como un par de tenedores esté libre, al menos un filósofo podrá tomar dos tenedores. Por lo tanto, el interbloqueo se vuelve imposible.
Otra solución simple se logra asignando un orden parcial a los recursos (bifurcaciones en este caso) y haciendo la convención de que los recursos se solicitan en ese orden y se devuelven en orden inverso. Además, no debe haber dos recursos fuera de servicio utilizados por la misma unidad de trabajo.
Supongamos que los recursos (tenedores) se numeren del 1 al 5, y cada unidad de trabajo (filósofo) siempre toma primero el tenedor con el número más bajo y luego el tenedor con el número más alto de los dos disponibles. A continuación, el filósofo deja primero el tenedor con el número más alto y luego el que tiene el número más pequeño. En este caso, si cuatro de cinco filósofos toman el tenedor con el número más bajo al mismo tiempo, el tenedor con el número más alto posible permanecerá sobre la mesa. Así, el quinto filósofo no podrá tomar un solo tenedor. Además, solo un filósofo tendrá acceso al tenedor con el número más alto, por lo que podrá comer con dos tenedores. Cuando haya terminado de usar los tenedores, pondrá primero sobre la mesa el tenedor con el número más alto, luego el más pequeño, permitiendo así que el otro filósofo recoja el tenedor que falta y comience a comer.
Esta solución fue sugerida por Dijkstra.
Si bien la jerarquía de recursos evita interbloqueos, esta solución no siempre es práctica, especialmente cuando la lista de recursos necesarios no se conoce de antemano. Por ejemplo, si una unidad de trabajo tiene los recursos 3 y 5 y decide que necesita el recurso 2, entonces debe liberar el recurso 5, luego el 3, luego tomar posesión del recurso 2 y tomar nuevamente los recursos 3 y 5. Los registros en una base de datos no funcionarían . eficientemente si necesitaban liberar todos los registros en superíndice antes de tomar posesión del nuevo registro. Esto hace que este método sea poco práctico.
El siguiente ejemplo muestra una solución en la que las bifurcaciones no se representan explícitamente. Los filósofos pueden comer si ninguno de sus vecinos come. Similar al sistema en el que los filósofos que no pueden agarrar el segundo tenedor deben dejar el primero antes de volver a intentarlo.
En ausencia de bloqueos relacionados con el tenedor, los filósofos deben asegurarse de que el comienzo de una comida no se base en información antigua sobre el estado de los vecinos. Por ejemplo: si el Filósofo B ve que A no está comiendo en un momento dado y luego se da la vuelta y mira a C, A podría comenzar a comer mientras el Filósofo B está mirando a C. Mediante el uso de un solo mutex , este problema se puede evitar. Este bloqueo no está relacionado con bifurcaciones, pero sí con la decisión de procedimientos que pueden cambiar el estado de los filósofos. Esto lo proporciona el monitor.
El algoritmo del monitor implementa un esquema de verificación, toma y colocación y comparte bloqueos mutuamente excluyentes. Tenga en cuenta que los filósofos que quieren comer no tendrán tenedores.
Si el monitor permite que actúe el filósofo que quiere comer, entonces el filósofo vuelve a tomar posesión del primer tenedor antes de tomar el segundo ya libre.
Al final de la comida actual, el filósofo notifica al monitor que ambos tenedores están libres.
Vale la pena señalar que este algoritmo de monitoreo no resuelve el problema del hambre. Por ejemplo, el filósofo B puede esperar indefinidamente su turno si los filósofos A y B tienen períodos de alimentación superpuestos. Para asegurarte también de que ningún filósofo pase hambre, puedes hacer un seguimiento de cuántas veces un filósofo hambriento no ha comido cuando sus vecinos ponen el tenedor sobre la mesa. Si el número de veces supera un cierto límite, dicho filósofo entrará en estado de inanición y el algoritmo del monitor forzará el procedimiento de adquisición de bifurcación, cumpliendo la condición de evitar la inanición de cualquiera de los vecinos.
El filósofo, incapaz de tomar los tenedores porque su vecino se está muriendo de hambre, está en un modo útil de esperar a que el vecino de su vecino termine de comer. Esta dependencia adicional reduce la concurrencia. Aumentar el valor del umbral de inanición reduce este efecto.