El problema de los filósofos comensales

El problema se diseñó para ilustrar los desafíos de evitar el bloqueo , 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, consideremos una propuesta en la que se instruye a cada filósofo a comportarse de la siguiente manera:

• Piensa a menos que el tenedor izquierdo esté disponible; cuando lo esté, tómalo;
• Piensa a menos que tengas disponible el tenedor adecuado; cuando lo tengas, tómalo;
• Cuando se sujetan ambos tenedores, se come durante un tiempo determinado;
• deja el tenedor izquierdo;
• deja el tenedor derecho;
• Repite desde el principio.

Con estas instrucciones, puede darse la situación de que cada filósofo sostenga el tenedor a su izquierda; en ese caso, todos quedarán atascados para siempre, esperando a que el otro tenedor esté disponible: se trata de un punto muerto.

La escasez de recursos , la exclusión mutua y el bloqueo mutuo son otros tipos de problemas de secuencia y acceso.

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 en C++20 de la solución de Dijkstra con cambios de Andrew S. Tanenbaum :

#include <chrono> #include <iostream> #include <mutex> #include <random> #include <semaphore> #include <thread>constexpr const size_t N = 5 ; // número de filósofos (y tenedores) enum class State { THINKING = 0 , // el filósofo está PENSANDO HUNGRY = 1 , // el filósofo está intentando conseguir tenedores EATING = 2 , // el filósofo está COMIENDO };size_t inline left ( size_t i ) { // número del vecino izquierdo del filósofo i return ( i - 1 + N ) % N ; // N se añade en el caso de que i - 1 sea negativo }size_t inline right ( size_t i ) { // número del vecino derecho del filósofo i return ( i + 1 ) % N ; }Estado estado [ N ]; // matriz para realizar un seguimiento del estado both_forks_available de todosstd :: mutex critical_region_mtx ; // exclusión mutua para regiones críticas para // (recoger y soltar los tenedores) std :: mutex output_mtx ; // para cout sincronizado (imprimir el estado PENSANDO/HAMBRIENTO/COMIENDO)// matriz de semáforos binarios, un semáforo por filósofo. // Adquirir cada semáforo significa que el filósofo i ha regresado de la función take_forks, es decir, ha adquirido (bloqueado) dos horquillas. // Comenzando en el estado 0/falso, lo que significa que ambas horquillas se consideran no disponibles. 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 } };size_t my_rand ( size_t min , size_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 se libera el semáforo del filósofo i. // Esto le da al filósofo i permiso para continuar más allá de la última línea de take_forks { // i: número de 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 (); // Ambos tenedores se declaran disponibles para el filósofo i } }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 " << duration << " ms \n " ; } std :: this_thread :: sleep_for ( std :: chrono :: milliseconds ( duration )); }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 está en State::HUNGRY { std :: lock_guard < std :: mutex > lk ( output_mtx ); // sección crítica para impresión ininterrumpida std :: cout << " \t\t " << i << " está en State::HUNGRY \n " ; } test ( i ); // intentar liberar el semáforo del filósofo i, es decir, adquirir (un permiso para) 2 bifurcaciones } // salir de la región crítica both_forks_available [ i ].acquire ( ); // esperar (bloqueado) si ambas bifurcaciones no están disponibles actualmente }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á comiendo " << duration << "ms \n " ; } std :: this_thread :: sleep_for ( std :: chrono :: milliseconds ( 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 )); // intentar liberar el semáforo del vecino izquierdo para él test ( right ( i )); // intentar liberar el semáforo del vecino derecho para él // salir de la región crítica saliendo de la función }void filósofo ( size_t i ) { while ( true ) { // repetir indefinidamente pensar ( i ); // filósofo es Estado::PENSANDO tomar_tenedores ( i ); // adquirir dos tenedores o ser bloqueado comer ( i ); // ¡qué rico, espaguetis! poner_tenedores ( i ); // volver a poner ambos tenedores en la mesa y comprobar si los vecinos pueden comer } }int main () { std :: cout << "dp_14 \n " ;std :: jthread t0 ([ & ] { filósofo ( 0 ); }); // [&] significa que cada variable fuera de la lambda subsiguiente std :: jthread t1 ([ & ] { filósofo ( 1 ); }); // es capturada 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 interbloqueos.

Esta solución elimina 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 ninguna unidad de trabajo utilizará simultáneamente dos recursos que no estén relacionados por orden. Aquí, los recursos (tenedores) se numerarán del 1 al 5, y cada unidad de trabajo (filósofo) siempre tomará primero el tenedor con el número más bajo y luego el de mayor número, de entre los dos tenedores que planea usar. El orden en que cada filósofo deja los tenedores no importa. En este caso, si cuatro de los cinco filósofos toman simultáneamente sus tenedores con números más bajos, solo el tenedor con el número más alto permanecerá sobre la mesa, por lo que el quinto filósofo no podrá tomar ningún tenedor. Además, solo un filósofo tendrá acceso a ese tenedor con el número más alto, por lo que podrá comer usando dos tenedores. Intuitivamente, esto puede entenderse como tener a un filósofo "zurdo" en la mesa, quien, a diferencia de todos los demás filósofos, toma su tenedor de la izquierda primero.

Si bien la solución de jerarquía de recursos evita los interbloqueos, 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 posee 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 un gran número de registros de bases de datos no funcionarían de manera eficiente si se les exigiera liberar todos los registros de mayor numeración 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 basada en la jerarquía de recursos no es justa . Si el filósofo 1 tarda en coger un tenedor, y el filósofo 2 es rápido para pensar y recoger sus tenedores, entonces el filósofo 1 nunca podrá coger ambos. Una solución justa debe garantizar que cada filósofo comerá, independientemente de la lentitud con la que se mueva en comparación con los demás.

El siguiente código fuente 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 de negocio . ^{[ 6 ]}

Para GCC: compilar con

g++ src.cpp -std = c++11 -pthread 

#include <iostream> #include <chrono> #include <mutex> #include <thread> #include <random> #include <ctime>usando el espacio de nombres std ;int myrand ( int min , int max ) { static mt19937 rnd ( time ( nullptr )); return uniform_int_distribution <> ( min , max )( rnd ); }void filósofo ( int ph , mutex & ma , mutex & mb , mutex & mo ) { for (;;) { // evita que el hilo termine int duración = myrand ( 200 , 800 ); { // Bloque { } limita el alcance del bloqueo lock_guard < mutex > gmo ( mo ); cout << ph << " piensa " << duración << "ms \n " ; } this_thread :: sleep_for ( chrono :: milliseconds ( 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 el segundo fork aquí, pero no debería ser necesario. lock_guard < mutex > gmb ( mb ); duración = myrand ( 200 , 800 ); { lock_guard < mutex > gmo ( mo ); cout << " \t\t\t\t " << ph << " come " << duration << "ms \n " ; } this_thread :: sleep_for ( chrono :: milliseconds ( duration )); } }int main () { cout << "Dining Philosophers C++11 with Resource hierarchy \n " ; mutex m1 , m2 , m3 , m4 , m5 ; // 5 forks son 5 mutexes mutex mo ; // para una salida adecuada // 5 filósofos son 5 hilos thread t1 ([ & ] { filósofo ( 1 , m1 , m2 , mo );}); thread t2 ([ & ] { filósofo ( 2 , m2 , m3 , mo );}); thread t3 ([ & ] { filósofo ( 3 , m3 , m4 , mo );}); thread t4 ([ & ] { filósofo ( 4 , m4 , m5 , mo );}); thread t5 ([ & ] { filósofo ( 5 , m1 , m5 , mo );}); // Forzar una jerarquía de recursos t1 . join (); // evita que los hilos terminen t2.join ( ) ; t3.join ( ) ; t4.join ( ); t5.join ( ) ; }

Otro enfoque consiste en garantizar que un filósofo solo pueda tomar ambos tenedores o ninguno, introduciendo un árbitro que reemplace la espera circular, por ejemplo, un camarero. Para tomar los tenedores, el filósofo debe pedir permiso al camarero. El camarero solo da permiso a un filósofo a la vez hasta que este haya tomado 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 resultar en una reducción del paralelismo: 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 satisfecho esta petición, incluso si todavía hay tenedores disponibles para ellos.

Una solución propuesta por William Stallings ^{[ 7 ]} consiste en permitir que un máximo de n-1 filósofos se sienten a la vez. El último filósofo tendría que esperar (por ejemplo, mediante un semáforo) a que alguien termine de comer antes de "sentarse" y solicitar acceso a cualquier tenedor. Esto evita la espera circular, garantizando que al menos un filósofo siempre pueda obtener 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 comensales que permite que agentes arbitrarios (numerados P1 , ..., Pn _{) compitan por un número arbitrario de recursos, a diferencia de la solución de Dijkstra. Además ,} es 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 comuniquen entre sí" (debido a los mensajes de solicitud).

1. Para cada par de filósofos que compiten por un recurso, crea un tenedor y dáselo al filósofo con el ID más bajo ( n para el agente P _n ). Cada tenedor puede estar sucio o limpio. Inicialmente, todos los tenedores están sucios.
2. Cuando un filósofo quiere utilizar un conjunto de recursos ( por ejemplo , comer), debe obtener los tenedores de sus vecinos que compiten por ellos. Para todos los tenedores que no posee, envía un mensaje de solicitud.
3. Cuando un filósofo con un tenedor recibe una solicitud, lo conserva si está limpio, pero lo entrega si está sucio. Si el filósofo envía el tenedor, lo limpia antes de hacerlo.
4. Después de que un filósofo termina de comer, todos sus tenedores quedan sucios. Si otro filósofo le había pedido uno de los tenedores, el filósofo que acaba de terminar de comer lo limpia y se lo envía.

Esta solución también permite un alto grado de concurrencia y resolverá un problema de tamaño arbitrariamente grande.

También resuelve el problema de la escasez de nutrientes. Las etiquetas de limpio/sucio dan preferencia a los procesos más necesitados de nutrientes y perjudican a los que acaban de recibirlos. Su solución podría compararse con una en la que a los filósofos no se les permite comer dos veces seguidas sin dejar que otros usen los tenedores entretanto. La solución de Chandy y Misra es más flexible, pero tiene cierta tendencia 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. Demuestran que este sistema puede describir un grafo dirigido acíclico y, de ser así, las operaciones de su protocolo no pueden convertirlo en cíclico. Esto garantiza que no se produzca un interbloqueo al negar la espera circular. Sin embargo, si el sistema se inicializa en un estado perfectamente simétrico, como si todos los filósofos sostuvieran sus bifurcaciones del lado izquierdo, entonces el grafo es cíclico desde el principio y su solución no puede evitar un interbloqueo. Inicializar el sistema de manera que los filósofos con identificadores más bajos tengan bifurcaciones sucias garantiza que el grafo sea inicialmente acíclico.