En informática , el problema de los filósofos comedores es un problema de ejemplo que se utiliza a menudo en el diseño de algoritmos concurrentes para ilustrar problemas de sincronización y técnicas para resolverlos.
Fue formulado originalmente en 1965 por Edsger Dijkstra como un ejercicio de examen para estudiantes, presentado en términos de computadoras que competían por el acceso a los periféricos de la unidad de cinta . Poco después, Tony Hoare le dio al problema su forma actual. [1] [2] [3] [4]
Cinco filósofos cenan juntos en la misma mesa. Cada filósofo tiene su propio plato en la mesa. Hay un tenedor entre cada plato. El plato servido es una especie de espagueti que debe comerse con dos tenedores. Cada filósofo solo puede pensar y comer alternativamente. Además, un filósofo solo puede comer sus espaguetis cuando tiene un tenedor izquierdo y uno derecho. Por lo tanto, dos tenedores solo estarán disponibles cuando sus dos vecinos más cercanos estén pensando, no comiendo. Después de que un filósofo individual termine de comer, dejará ambos tenedores. El problema es cómo diseñar un régimen (un algoritmo concurrente ) tal que ningún filósofo muera de hambre; es decir , cada uno puede continuar para siempre alternando entre comer y pensar, suponiendo que ningún filósofo puede saber cuándo los demás pueden querer comer o pensar (una cuestión de información incompleta ).
El problema fue diseñado para ilustrar los desafíos que supone evitar un punto muerto , un estado del sistema en el que no es posible ningún progreso. Para ver que una solución adecuada a este problema no es obvia, considere una propuesta en la que se le indica a cada filósofo que se comporte de la siguiente manera:
Con estas instrucciones, puede darse la situación en que cada filósofo sostenga el tenedor a su izquierda; en esa situación, todos quedarán estancados para siempre, esperando que el otro tenedor esté disponible: es un punto muerto.
La falta de recursos , la exclusión mutua y el bloqueo activo son otros tipos de problemas de secuencia y acceso.
Estas cuatro condiciones son necesarias para que se produzca un punto muerto: exclusión mutua (ningún fork puede ser utilizado simultáneamente por varios filósofos), posesión de recursos (los filósofos retienen un fork mientras esperan el segundo), no prelación (ningún filósofo puede tomar un fork de otro) y espera circular (cada filósofo puede estar esperando al filósofo que está a su izquierda). Una solución debe negar al menos una de esas cuatro condiciones. En la práctica, negar la exclusión mutua o la no prelación de alguna manera puede dar una solución válida, pero la mayoría de los tratamientos teóricos suponen que esas suposiciones no son negociables, y en su lugar atacan la posesión de recursos o la espera circular (a menudo ambas).
La solución de Dijkstra niega la retención de recursos; los filósofos toman atómicamente ambas bifurcaciones o esperan, sin retener nunca exactamente una bifurcación fuera de una sección crítica. Para lograr esto, la solución de Dijkstra utiliza un mutex , un semáforo por filósofo y una variable de estado por filósofo. Esta solución es más compleja que la solución de jerarquía de recursos. [5] [4] Esta es una versión C++20 de la solución de Dijkstra con los cambios de Tanenbaum:
#include <chrono> #include <iostream> #include <mutex> #include <random> #include <semáforo> #include <thread> constexpr const size_t N = 5 ; // número de filósofos (y tenedores) enum class State { PENSAR = 0 , // el filósofo está PENSAR HAMBRE = 1 , // el filósofo está tratando de conseguir tenedores COMER = 2 , // el filósofo está COMIENDO }; size_t inline left ( size_t i ) { // número del vecino izquierdo del filósofo i, para quien ambas bifurcaciones están disponibles return ( i - 1 + N ) % N ; // N se agrega para el caso en que i - 1 es negativo } size_t inline right ( size_t i ) { // número del vecino derecho del filósofo i, para quien ambas bifurcaciones están disponibles return ( i + 1 ) % N ; } Estado estado [ N ]; // matriz para realizar un seguimiento del estado both_forks_available de todos std :: mutex critical_region_mtx ; // exclusión mutua para regiones críticas para // (tomar y dejar los tenedores) std :: mutex output_mtx ; // para cout sincronizado (imprimir estado PENSANDO/HAMBRE/COMIENDO) // matriz de semáforos binarios, un semáforo por filósofo. // El semáforo adquirido significa que el filósofo i ha adquirido (bloqueado) dos bifurcaciones std :: binary_semaphore both_forks_available [ N ] { std :: binary_semaphore { 0 }, std :: binary_semaphore { 0 } , std :: binary_semaphore { 0 }, std :: binary_semaphore { 0 }, std :: binary_semaphore { 0 } }; tamaño_t my_rand ( tamaño_t min , tamaño_t max ) { static std :: mt19937 rnd ( std :: time ( nullptr )); return std :: uniform_int_distribution <> ( min , max )( rnd ); } void test ( size_t i ) // si el filósofo i tiene hambre y ambos vecinos no están comiendo entonces come { // i: número del filósofo, de 0 a N-1 if ( state [ i ] == State :: HUNGRY && state [ left ( i )] != State :: EATING && state [ right ( i )] != State :: EATING ) { state [ i ] = State :: EATING ; both_forks_available [ i ] .release (); // los tenedores ya no son necesarios para esta sesión de comer } } void think ( size_t i ) { size_t duration = my_rand ( 400 , 800 ); { std :: lock_guard < std :: mutex > lk ( output_mtx ); // sección crítica para impresión ininterrumpida std :: cout << i << "está pensando" << duración << "ms \n " ; } std :: this_thread :: sleep_for ( std :: chrono :: milisegundos ( duración )); } void take_forks ( size_t i ) { { std :: lock_guard < std :: mutex > lk { critical_region_mtx }; // entrar en la región crítica state [ i ] = State :: HUNGRY ; // registrar el hecho de que el filósofo i es State::HUNGRY { std :: lock_guard < std :: mutex > lk ( output_mtx ); // sección crítica para impresión ininterrumpida std :: cout << " \t\t " << i << " is State::HUNGRY \n " ; } test ( i ); // intentar adquirir (un permiso para) 2 forks } // salir de la región crítica both_forks_available [ i ]. acquire (); // bloquear si no se adquirieron forks } void eat ( size_t i ) { size_t duration = my_rand ( 400 , 800 ); { std :: lock_guard < std :: mutex > lk ( output_mtx ); // sección crítica para impresión ininterrumpida std :: cout << " \t\t\t\t " << i << " está consumiendo " << duración << "ms \n " ; } std :: this_thread :: sleep_for ( std :: chrono :: milisegundos ( duration )); } void put_forks ( size_t i ) { std :: lock_guard < std :: mutex > lk { critical_region_mtx }; // entrar en la región crítica state [ i ] = State :: THINKING ; // el filósofo ha terminado State::EATING test ( left ( i )); // ver si el vecino izquierdo ahora puede comer test ( right ( i )); // ver si el vecino derecho ahora puede comer // salir de la región crítica saliendo de la función } void filósofo ( tamaño_t i ) { while ( verdadero ) { // repetir para siempre pensar ( i ); // filósofo es Estado::PENSANDO tomar_tenedores ( i ); // adquirir dos tenedores o bloquear comer ( i ); // yum-yum, espaguetis poner_tenedores ( i ); // poner ambos tenedores de nuevo en la mesa y comprobar si los vecinos pueden comer } } int principal () { std :: cout << "dp_14 \n " ; std :: jthread t0 ([ & ] { filósofo ( 0 ); }); // [&] significa cada variable fuera de la lambda resultante std :: jthread t1 ([ & ] { filósofo ( 1 ); }); // es capturado por referencia std :: jthread t2 ([ & ] { filósofo ( 2 ); }); std :: jthread t3 ([ & ] { filósofo ( 3 ); }); std :: jthread t4 ([ & ] { filósofo ( 4 ); }); } La función test() y su uso en take_forks() y put_forks() hacen que la solución de Dijkstra esté libre de bloqueos.
Esta solución niega la espera circular al asignar un orden parcial a los recursos (los tenedores, en este caso), y establece la convención de que todos los recursos se solicitarán en orden, y que nunca dos recursos no relacionados por orden serán utilizados por una sola unidad de trabajo al mismo tiempo. Aquí, los recursos (tenedores) se numerarán del 1 al 5 y cada unidad de trabajo (filósofo) siempre cogerá primero el tenedor de número inferior, y luego el de número superior, de entre los dos tenedores que piensa utilizar. El orden en que cada filósofo deje los tenedores no importa. En este caso, si cuatro de los cinco filósofos cogen simultáneamente sus tenedores de número inferior, sólo el tenedor de número superior permanecerá sobre la mesa, por lo que el quinto filósofo no podrá coger ningún tenedor. Además, sólo un filósofo tendrá acceso a ese tenedor de número superior, por lo que podrá comer utilizando dos tenedores. Intuitivamente, esto se puede pensar como tener un filósofo "zurdo" en la mesa, quien, a diferencia de todos los demás filósofos, toma primero su tenedor de la izquierda.
Si bien la solución de jerarquía de recursos evita los bloqueos, no siempre es práctica, especialmente cuando la lista de recursos necesarios no se conoce completamente de antemano. Por ejemplo, si una unidad de trabajo contiene los recursos 3 y 5 y luego determina que necesita el recurso 2, debe liberar el 5, luego el 3 antes de adquirir el 2 y luego debe volver a adquirir el 3 y el 5 en ese orden. Los programas informáticos que acceden a una gran cantidad de registros de bases de datos no se ejecutarían de manera eficiente si se les exigiera liberar todos los registros con números más altos antes de acceder a un nuevo registro, lo que hace que el método sea poco práctico para ese propósito. [2]
La solución de la jerarquía de recursos no es justa . Si el filósofo 1 es lento para tomar un tenedor, y si el filósofo 2 es rápido para pensar y volver a recoger sus tenedores, entonces el filósofo 1 nunca podrá recoger ambos tenedores. Una solución justa debe garantizar que cada filósofo termine comiendo, sin importar cuán lento se mueva ese filósofo en relación con los demás.
El código fuente siguiente es una implementación en C++11 de la solución de jerarquía de recursos para cinco filósofos. La función sleep_for() simula el tiempo que normalmente se dedica a la lógica empresarial. [6]
Para GCC: compilar con
g++ src.cpp -std = c++11 -lpthread#include <iostream> #include <chrono> #include <mutex> #include <thread> #include <random> #include <ctime> utilizando el espacio de nombres std ; int myrand ( int min , int max ) { static mt19937 rnd ( tiempo ( nullptr )); devolver distribución_int_uniforme <> ( min , max )( rnd ); } void filósofo ( int ph , mutex & ma , mutex & mb , mutex & mo ) { for (;;) { // evitar que el hilo termine int duration = myrand ( 200 , 800 ); { // Bloquear { } limita el alcance del bloqueo lock_guard < mutex > gmo ( mo ); cout << ph << " piensa " << duración << "ms \n " ; } this_thread :: sleep_for ( chrono :: milisegundos ( duración )); { lock_guard < mutex > gmo ( mo ); cout << " \t\t " << ph << " tiene hambre \n " ; } lock_guard < mutex > gma ( ma ); // sleep_for() Se puede agregar un retraso antes de buscar la segunda bifurcación aquí, pero no debería ser obligatorio. lock_guard < mutex > gmb ( mb ); duración = myrand ( 200 , 800 ); { lock_guard < mutex > gmo ( mo ); cout << " \t\t\t\t " << ph << " eats " << duración << "ms \n " ; } este_hilo :: sleep_for ( chrono :: milisegundos ( duración )); } } int main () { cout << "cenando Filósofos C++11 con jerarquía de recursos \n " ; mutex m1 , m2 , m3 , m4 , m5 ; // 5 bifurcaciones son 5 mutexes mutex mo ; // para una salida adecuada // 5 filósofos son 5 subprocesos subproceso t1 ([ & ] { filósofo ( 1 , m1 , m2 , mo );}); subproceso t2 ([ & ] { filósofo ( 2 , m2 , m3 , mo );}); subproceso t3 ([ & ] { filósofo ( 3 , m3 , m4 , mo );}); subproceso t4 ([ & ] { filósofo ( 4 , m4 , m5 , mo );}); subproceso t5 ([ & ] { filósofo ( 5 , m1 , m5 , mo );}); // Fuerza una jerarquía de recursos t1 . join (); // evitar que los hilos terminen t2 . join (); t3 . join (); t4 . join (); t5 . join (); } Otro enfoque consiste en garantizar que un filósofo sólo pueda coger ambos tenedores o ninguno introduciendo un árbitro que sustituya la espera circular, por ejemplo, un camarero. Para coger los tenedores, un filósofo debe pedir permiso al camarero. El camarero da permiso sólo a un filósofo a la vez hasta que el filósofo haya cogido ambos tenedores. Siempre se permite dejar un tenedor. El camarero puede implementarse como un mutex. Además de introducir una nueva entidad central (el camarero), este enfoque puede dar lugar a un paralelismo reducido: si un filósofo está comiendo y uno de sus vecinos pide los tenedores, todos los demás filósofos deben esperar hasta que se haya cumplido esta petición, incluso si todavía hay tenedores disponibles para ellos.
Una solución propuesta por William Stallings [7] es permitir que un máximo de n-1 filósofos se sienten en cualquier momento. El último filósofo tendría que esperar (por ejemplo, utilizando un semáforo) a que alguien termine de cenar antes de "sentarse" y solicitar acceso a cualquier tenedor. Esto niega la espera circular, garantizando que al menos un filósofo siempre pueda adquirir ambos tenedores, lo que permite que el sistema avance.
En 1984, K. Mani Chandy y J. Misra [8] propusieron una solución diferente al problema de los filósofos que cenan, que permite que agentes arbitrarios (numerados P 1 , ..., P n ) compitan por una cantidad arbitraria de recursos, a diferencia de la solución de Dijkstra. También está completamente distribuida y no requiere una autoridad central después de la inicialización. Sin embargo, viola el requisito de que "los filósofos no se hablan entre sí" (debido a los mensajes de solicitud).
Esta solución también permite un alto grado de concurrencia y resolverá un problema arbitrariamente grande.
También resuelve el problema de la inanición. Las etiquetas de limpio/sucio actúan como una forma de dar preferencia a los procesos más "hambrientos" y una desventaja para los procesos que acaban de "comer". Se podría comparar su solución con una en la que a los filósofos no se les permite comer dos veces seguidas sin dejar que otros usen los tenedores entre una comida y otra. La solución de Chandy y Misra es más flexible que eso, pero tiene un elemento que tiende en esa dirección.
En su análisis, derivan un sistema de niveles de preferencia a partir de la distribución de las bifurcaciones y sus estados limpio/sucio. Muestran que este sistema puede describir un grafo acíclico dirigido y, de ser así, las operaciones en su protocolo no pueden convertir ese grafo en uno cíclico. Esto garantiza que no se pueda producir un bloqueo al negar la espera circular. Sin embargo, si el sistema se inicializa en un estado perfectamente simétrico, como todos los filósofos que mantienen sus bifurcaciones del lado izquierdo, entonces el grafo es cíclico desde el principio y su solución no puede evitar un bloqueo. Inicializar el sistema de modo que los filósofos con ID más bajos tengan bifurcaciones sucias garantiza que el grafo sea inicialmente acíclico.