En informática , el problema de los filósofos gastronómicos 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 compiten por el acceso a los periféricos de las unidades de cinta . Poco después, Tony Hoare 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 que se sirve es una especie de espagueti que se come con dos tenedores. Cada filósofo sólo puede pensar y comer alternativamente. Además, un filósofo sólo puede comerse sus espaguetis si tiene tanto el tenedor izquierdo como el derecho. Por lo tanto, dos tenedores sólo 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 no muera de hambre; es decir , cada uno puede seguir alternando eternamente entre comer y pensar, asumiendo que ningún filósofo puede saber cuándo otros querrán comer o pensar (una cuestión de información incompleta ).
El problema fue diseñado para ilustrar los desafíos de evitar el 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, consideremos una propuesta en la que se instruye a cada filósofo a comportarse de la siguiente manera:
Con estas instrucciones puede darse la situación de que cada filósofo sostenga el tenedor a su izquierda; en esa situación, todos quedarán atrapados para siempre, esperando que la otra bifurcación esté disponible: es un punto muerto.
La falta de recursos , la exclusión mutua y el bloqueo en vivo son otros tipos de problemas de secuencia y acceso.
Estas cuatro condiciones son necesarias para que ocurra un punto muerto: exclusión mutua (ninguna bifurcación puede ser utilizada simultáneamente por múltiples filósofos), retención de recursos (los filósofos sostienen una bifurcación mientras esperan la segunda), no preferencia (ningún filósofo puede tomar una bifurcación). de otro), y espera circular (cada filósofo puede estar esperando al filósofo de 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 preferencia de algún modo puede dar una solución válida, pero la mayoría de los tratamientos teóricos asumen que esos supuestos no son negociables, y en lugar de ello atacan la retención de recursos o la espera circular (a menudo ambas).
La solución de Dijkstra niega la tenencia de recursos; los filósofos toman atómicamente ambos tenedores o esperan, sin sostener nunca exactamente un tenedor 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 <semaphore> #include <thread> constexpr tamaño constante_t N = 5 ; // número de filósofos (y tenedores) enum class State { PENSAMIENTO = 0 , // el filósofo está PENSANDO HAMBRE = 1 , // el filósofo está tratando de conseguir tenedores COMIENDO = 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 ; // Se agrega N 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 de ambos_forks_disponibles de todos std :: mutex critic_region_mtx ; // exclusión mutua para regiones críticas para // (recoger y dejar los tenedores) std :: mutex output_mtx ; // para cout sincronizado (imprimiendo el estado PENSAR/HAMBRE/COMER) // conjunto de semáforos binarios, un semáforo por filósofo. // Semáforo adquirido significa que el filósofo i ha adquirido (bloqueado) dos bifurcaciones std :: binario_semaphore ambos_forks_disponibles [ N ] { std :: binario_semaphore { 0 }, std :: binario_semaphore { 0 }, std :: binario_semaphore { 0 }, std :: semáforo_binario { 0 }, estándar :: semáforo_binario { 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 ); } prueba vacía ( size_t i ) // si el filósofo i tiene hambre y ambos vecinos no comen, entonces come { // i: número de filósofo, de 0 a N-1 if ( estado [ i ] == Estado :: HAMBRE && estado [ izquierda ( i )] != Estado :: COMER && estado [ derecha ( i )] != Estado :: COMER ) { estado [ i ] = Estado :: COMER ; ambos_forks_disponibles [ i ]. liberar (); // ya no se necesitan tenedores para esta sesión de comida } } pensamiento vacío ( tamaño_t i ) { tamaño_t duración = my_rand ( 400 , 800 ); { std :: lock_guard < std :: mutex > lk ( salida_mtx ); // sección crítica para impresión ininterrumpida std :: cout << i << " está pensando " << duración << "ms \n " ; } std :: this_thread :: sleep_for ( std :: crono :: milisegundos ( duración )); } void take_forks ( size_t i ) { { std :: lock_guard < std :: mutex > lk { critic_region_mtx }; // ingresa el estado de la región crítica [ i ] = Estado :: HAMBRIENTO ; // registra el hecho de que el filósofo i es State::HANGRY { std :: lock_guard < std :: mutex > lk ( output_mtx ); // sección crítica para impresión ininterrumpida std :: cout << " \t\t " << i << " es State::HANGRY \n " ; } prueba ( yo ); // intenta adquirir (un permiso para) 2 bifurcaciones } // sale de la región crítica ambas_forks_disponibles [ i ]. adquirir (); // bloquear si no se adquirieron las bifurcaciones } void comer ( tamaño_t i ) { tamaño_t duración = my_rand ( 400 , 800 ); { std :: lock_guard < std :: mutex > lk ( salida_mtx ); // sección crítica para impresión ininterrumpida std :: cout << " \t\t\t\t " << i << " está comiendo " << duración << "ms \n " ; } std :: this_thread :: sleep_for ( std :: crono :: milisegundos ( duración )); } void put_forks ( size_t i ) { std :: lock_guard < std :: mutex > lk { critic_region_mtx }; // ingresa al estado de la región crítica [ i ] = Estado :: PENSAMIENTO ; // el filósofo ha terminado la prueba State::Eating ( left ( i )); // ver si el vecino izquierdo ahora puede comer test ( right ( i )); // ver si el vecino correcto ahora puede comer // salir de la región crítica saliendo de la función } filósofo vacío ( size_t i ) { while ( true ) { // repetir para siempre pensar ( i ); // el filósofo es Estado::PENSAMIENTO take_forks ( i ); // adquirir dos tenedores o bloquear comer ( i ); // yum-yum, espaguetis put_forks ( i ); // vuelve a poner ambos tenedores en la mesa y comprueba si los vecinos pueden comer } } int main () { std :: cout << "dp_14 \n " ; std :: jthread t0 ([ & ] { filósofo ( 0 ); }); // [&] significa cada variable fuera del lambda std resultante :: jthread t1 ([ & ] { filósofo ( 1 ); }); // se captura 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 (las bifurcaciones, 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 un solo 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 elegirá primero el tenedor con el número más bajo y luego el con el número más alto, de entre los dos tenedores que planea usar. No importa el orden en que cada filósofo deja los tenedores. En este caso, si cuatro de los cinco filósofos cogen simultáneamente sus tenedores con el número más bajo, sólo quedará sobre la mesa el tenedor con el número más alto, 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 con el número más alto, por lo que podrá comer con dos tenedores. Intuitivamente se puede pensar que esto es como si hubiera un filósofo "zurdo" en la mesa, quien – a diferencia de todos los demás filósofos – toma su tenedor primero por la izquierda.
Si bien la solución de jerarquía de recursos evita puntos muertos, 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 5, luego 3 antes de adquirir 2, y luego debe volver a adquirir 3 y 5 en ese orden. Los programas informáticos que acceden a un gran número de registros de bases de datos no se ejecutarían eficientemente si se les exigiera publicar todos los registros con números más altos antes de acceder a un nuevo registro, lo que hace que el método no sea práctico para ese propósito. [2]
La solución de la jerarquía de recursos no es justa . Si el filósofo 1 tarda en tomar un tenedor, y si el filósofo 2 piensa rápidamente y vuelve a levantar sus tenedores, entonces el filósofo 1 nunca podrá tomar ambos tenedores. Una solución justa debe garantizar que cada filósofo eventualmente coma, sin importar cuán lento se mueva en relació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 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> usando el espacio de nombres estándar ; int myrand ( int min , int max ) { estático mt19937 rnd ( tiempo ( nullptr )); devolver uniform_int_distribution <> ( mínimo , máximo ) ( rnd ); } filósofo vacío ( int ph , mutex & ma , mutex & mb , mutex & mo ) { for (;;) { // evita que el hilo termine int duración = 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 ( crono :: milisegundos ( duración )); { lock_guard < mutex > gmo ( mes ); cout << " \t\t " << ph << " tiene hambre \n " ; } lock_guard < mutex > gma ( ma ); // sleep_for() Se puede agregar aquí un retraso antes de buscar una segunda bifurcación, pero no debería ser necesario. lock_guard < mutex > gmb ( mb ); duración = myrand ( 200 , 800 ); { lock_guard < mutex > gmo ( mes ); cout << " \t\t\t\t " << ph << " come " << duración << "ms \n " ; } this_thread :: sleep_for ( crono :: milisegundos ( duración )); } } int main () { cout << "comedor de filósofos C++ 11 con jerarquía de recursos \n " ; exclusión mutua m1 , m2 , m3 , m4 , m5 ; // 5 bifurcaciones son 5 mutex mutex mo ; // para una salida adecuada // 5 filósofos son 5 subprocesos thread t1 ([ & ] { filósofo ( 1 , m1 , m2 , mo );}); hilo t2 ([ & ] { filósofo ( 2 , m2 , m3 , mo );}); hilo t3 ([ & ] { filósofo ( 3 , m3 , m4 , mo );}); hilo t4 ([ & ] { filósofo ( 4 , m4 , m5 , mo );}); hilo t5 ([ & ] { filósofo ( 5 , m1 , m5 , mo );}); // Forzar una jerarquía de recursos t1 . unirse (); // evita que los hilos terminen t2 . unirse (); t3 . unirse (); t4 . unirse (); t5 . unirse (); } Otro enfoque es garantizar que un filósofo sólo pueda tomar ambos tenedores o ninguno, introduciendo un árbitro para reemplazar la espera circular, por ejemplo, un camarero. Para coger los tenedores, un filósofo debe pedir permiso al camarero. El camarero sólo da permiso a un filósofo a la vez hasta que el filósofo haya cogido ambos tenedores. Siempre está permitido dejar el tenedor. El camarero se puede implementar 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 los tenedores para ellos todavía están disponibles.
Una solución presentada 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, usando 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 ambas bifurcaciones, permitiendo que el sistema progrese.
En 1984, K. Mani Chandy y J. Misra [8] propusieron una solución diferente al problema de los filósofos gastronómicos para permitir que agentes arbitrarios (numerados P 1 , ..., P n ) compitieran por un número arbitrario de recursos, a diferencia de La solución de Dijkstra. También está completamente distribuido y no requiere autoridad central después de la inicialización. Sin embargo, viola el requisito de que "los filósofos no se hablen 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 del hambre. Las etiquetas 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 aquella en la que a los filósofos no se les permite comer dos veces seguidas sin permitir que otros usen los tenedores en el medio. 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 los tenedores y sus estados limpios/sucios. Muestran que este sistema puede describir un gráfico acíclico dirigido y, de ser así, las operaciones en su protocolo no pueden convertir ese gráfico en uno cíclico. Esto garantiza que no se produzca un punto muerto al negar la espera circular. Sin embargo, si el sistema se inicializa a un estado perfectamente simétrico, como todos los filósofos sostienen sus bifurcaciones del lado izquierdo, entonces el gráfico es cíclico al principio y su solución no puede evitar un punto muerto. Inicializar el sistema para que los filósofos con ID más bajos tengan bifurcaciones sucias garantiza que el gráfico sea inicialmente acíclico.