Sistema operativo

El problema de la cena de filósofos

En 1965, Dijkstra planteó y resolvió un problema de sincronización al que llamó problema de la cena de filósofos. Desde entonces, quienquiera que haya inventado una primitiva de sincronización más se ha sentido obligado a demostrar lo maravillosa que es mostrando la forma tan elegante en que resuelve el problema de la cena de filósofos. El problema tiene unplanteamiento muy sencillo. Cinco filósofos están sentados alrededor de una mesa circular. Cada filósofo tiene ante sí un plato de espagueti. El espagueti estan resbaloso que un filósofo necesita dos tenedores para comerlo. Entre cada par de platos hay un tenedor. La disposición de la mesa se ilustra en la Fig. 2-16.

La vida de un filósofo consiste en periodos alternantes de comer y pensar.(Esto es una abstracción, incluso en el caso de un filósofo, pero las demás actividades no son pertinentes aquí.) Cuando un filósofo siente hambre, trata de adquirir sus tenedores izquierdo y derecho, uno a la vez, en cualquier orden. Si logra adquirir dos tenedores, comerá durante un rato, luego pondrá los tenedores en la mesa y seguirá pensando. La pregunta clave es: ¿podemos escribir un programapara cada filósofo que haga lo que se supone que debe hacer y nunca se entrampe? (Se ha señalado que el requisito de los dos tenedores es un tanto artificial; tal vez deberíamos cambiar de la comida italiana a la china, sustituyendo el espagueti por arroz y los tenedores por palillos chinos.) La Fig. 2-17 muestra la solución obvia. El procedimiento take_fork (tomar tenedor) espera hasta que eltenedor especificado está disponible y luego se apodera de él. Desafortunadamente, la solución obvia está equivocada. Supongamos que todos los filósofos toman su tenedor izquierdo simultáneamente. Ninguno podrá tomar su tenedor derecho, y tendremos un bloqueo mutuo. Podríamos modificar el programa de modo que, después de tomar el tenedor izquierdo, el programa verifique si el tenedor derecho estádisponible. Si no es así, el filósofo soltará su tenedor izquierdo, esperará cierto tiempo, y repetirá el proceso. Esta propuesta también fracasa, aunque por una razón distinta. Con un poco de mala suerte, todos los filósofos podrían iniciar el algoritmo simultáneamente, tomar su tenedor izquierdo, ver que su tenedor derecho no está disponible, dejar su tenedor izquierdo, esperar, tomar su tenedorizquierdo otra vez de manera simultánea, y así eternamente. Una situación así, en la que todos los programas continúan ejecutándose de manera indefinida pero no logran avanzar se denomina inanición (adopta este calificativo aun cuando el problema no ocurra en un restaurante italiano o chino). Ahora podríamos pensar: “si los filósofos esperan un tiempo aleatorio en lugar del
mismo tiempo después defracasar en su intento por .disponer del tenedor derecho, la posibilidad de que sus acciones continuaran coordinadas durante siquiera una hora es excesivamente pequeña”. Esto es cierto, pero en algunas aplicaciones preferiríamos una solución que siempre funcione y que no tenga posibilidad de fallar debido a una serie improbable de números aleatorios. (Pensemos en el control de seguridad en unaplanta de energía nuclear.) Una mejora de la Fig. 2-17 que no está sujeta a bloqueo ni inanición consiste en proteger las cinco instrucciones que siguen a la llamada a think (pensar) con un semáforo binario. Antes de comenzar a conseguir tenedores, un filósofo ejecutaría DOWN con mutex. Después de dejar los tenedores en la mesa, ejecutaría up con mutex. Desde un punto de vista teórico, esta soluciónes adecuada. En la práctica, empero, tiene un problema de rendimiento: sólo un filósofo puede estar comiendo en un instante dado. Si hay cinco tenedores disponibles, deberíamos estar en condiciones de permitir que dos filósofos comieran al mismo tiempo. La solución que se presenta en la Fig. 2-18 es correcta y también admite un paralelismo máximo con un número arbitrario de filósofos. Se utiliza...