Filosofos Comensales

PROBLEMAS CLÁSICOS. EL PROBLEMA DE LOS FILÓSOFOS COMENSALES. Cinco filósofos pasan su vida pensando y comiendo. Los filósofos comparten una mesa circular rodeada por cinco sillas, una para cada uno de ellos. En el centro de la mesa se encuentra una fuente de arroz, y también sobre la mesa hay cinco palillos chinos. Cuando un filósofo piensa, no interactúa con sus colegas. Ocasionalmente, unfilósofo tiene hambre y trata de coger los dos palillos que están más cerca de él (los palillos colocados entre él y sus vecinos de la derecha y de la izquierda). Un filósofo sólo puede coger un palillo a la vez y, obviamente, no puede ser el que está en la mano de un vecino. Cuando un filósofo hambriento tiene sus dos palillos al mismo tiempo come sin soltarlos. Cuando termina de comer, coloca ambospalillos sobre la mesa y comienza a pensar otra vez. La situación de los Filósofos comensales. El problema de los filósofos comensales se considera un problema de sincronización clásico, pero no por su importancia práctica sino porque es un ejemplo de una gran clase de problemas de control de concurrencia. Una solución sencilla consiste en representar cada palillo con un semáforo. Un filósofo tratade coger el palillo ejecutando una operación wait en ese semáforo; suelta sus palillos ejecutando signal en los semáforos correspondientes. Así, los datos compartidos son: var palillo:array [0..4] of semáforo; donde todos los elementos de palillo reciben un valor inicial de 1. A continuación se presenta un programa que simula esta situación.
program Filo01; (* Filosofos comensales - semáforosversión 1 *) const N = 5; var palillo : array [1..N] of semaphore; (* binario *) I : integer; process type filosofos(numero : integer); begin repeat writeln('Pensando el ',numero); sleep(random(5)); (* PENSANDO *) wait(palillo[numero]); wait(palillo[(numero mod N) + 1]); writeln('Comiendo el ',numero); sleep(random(5)); (* COMIENDO *) signal(palillo[numero]); signal(palillo[(numero mod N) + 1]);forever end; (* filosofos *) var procfil: array[1..N] of filosofos; begin for I := 1 to N do initial(palillo[I],1); cobegin for I := 1 to N do procfil[I](I); coend end.

1

- Pascal-FC for IBM PC compatibles - Compiler Version P5.2 G L Davies & A Burns, University of Bradford Compiling filo01 ... Compilation complete - Interpreter Version P5.3 Program filo01 ... execution begins ... PensandoPensando Pensando Pensando Comiendo Pensando Pensando Comiendo Comiendo Comiendo Pensando Pensando el el el el el el el el el el el el 1 5 2 3 1 4 1 2 4 1 2 1Pensando el 4Comiendo el 5 2 5 3 4 5 1 2 4 4 5 1 3 5 1 5 2 3

3

Comiendo el Comiendo el Pensando el Comiendo el 3 Pensando el Comiendo el Pensando el 1 Comiendo el Pensando el Comiendo el Pensando el Pensando el Comiendo el 3 Pensando elComiendo el Pensando el Pensando el Comiendo el Comiendo el Comiendo el Pensando el Pensando el Comiendo el Pensando el

4 2

2

Aunque esta solución garantiza que dos vecinos no pueden comer simultáneamente, hay que rechazarla porque existe la posibilidad de crear un bloqueo mutuo. Suponga que los cinco filósofos tienen hambre al mismo tiempo y cada uno coge el palillo que está a su izquierda;todos los elementos del arreglo palillo serán iguales a cero. Cuando cada filósofo trata de coger el palillo a su derecha, su ejecución se aplazará eternamente. A continuación se presentan varias posibles soluciones, con diferentes algoritmos y con diferentes elementos del lenguaje para la sincronización de procesos. Se aclara que cualquier solución satisfactoria para este problema debe eliminarla posibilidad de que uno de ellos muera de hambre. Una solución libre de bloqueos mutuos no la elimina necesariamente. Permitir que cuatro filósofos como máximo, se sienten a comer al mismo tiempo. 2

program Filo02; (* Filósofos comensales - semáforos versión 2 *) const N = 5; var palillo : array [1..N] of semaphore; (* binario *) sillaslibre : semaphore; (* general *) I : integer; process...