En 1965 Dijkstra planteó y resolvió un problema de sincronización llamado el problema de la cena de los filósofos, que se puede enunciar como sigue. Cinco filósofos se sientan a la mesa, cada uno con un plato de espaghetti. El espaghetti es tan escurridizo que un filósofo necesita dos tenedores para comerlo. Entre cada dos platos hay un tenedor. En la figura 4.15 se muestra la mesa.

La vida de un filósofo consta de periodos alternos de comer y pensar. Cuando un filósofo tiene hambre, intenta obtener un tenedor para su mano derecha, y otro para su mano izquierda, cogiendo uno a la vez y en cualquier orden. Si logra obtener los dos tenedores, come un rato y después deja los tenedores y continúa pensando. La pregunta clave es: ¿ puede el lector escribir un programa para cada filósofo que permita comer equitativamente a los filósofos y no se interbloquee ?

La figura 4.16 muestra una solución obvia. El procedimiento coger_tenedor espera hasta que el tenedor especificado esté disponible y lo coge. Por desgracia la solución obvia es incorrecta. Supongamos que los cinco filósofos cogen sus tenedores izquierdos de forma simultánea. Ninguno podría coger su tenedor derecho, lo que produciría un interbloqueo.

Se podría modificar el programa de forma que después de coger el tenedor izquierdo, el programa verificara si el tenedor derecho está disponible. Si no lo está, el filósofo deja el izquierdo, espera cierto tiempo y vuelve a repetir el proceso. Esta propuesta también falla, aunque por razones distintas. Con un poco de mala suerte todos los filósofos podrían empezar el algoritmo de forma simultánea, por lo que cogerían sus tenedores izquierdos, verían que los derechos no están disponibles, esperarían, volverían a coger sus tenedores izquierdos simultáneamente, etc. eternamente. Esto implica un aplazamiento indefinido.

El lector podría pensar: "si los filósofos esperaran un tiempo arbitrario, en vez del mismo tiempo, después de que no pudieran coger el tenedor derecho, la probabilidad de que todo quedara bloqueado, incluso una hora, sería muy pequeña". Esta observación es correcta, pero en ciertas aplicaciones se desea una solución que funcione siempre, y no que pueda funcionar bien con gran probabilidad. (Piense en el control de seguridad de una planta nuclear).

Una mejora a la figura 4.16, que no tiene interbloqueos ni aplazamiento indefinido, es la protección de los cinco enunciados siguientes a la llamada al procedimiento pensar mediante un semáforo binario exmut. Antes de empezar a coger los tenedores, un filósofo haría un wait sobre exmut. Desde el punto de vista teórico esta solución es adecuada. Desde el punto de vista práctico presenta un error de eficiencia: en todo instante existirá a lo sumo un filósofo comiendo. Si se dispone de cinco tenedores, se debería permitir que dos filósofos comieran al mismo tiempo.

La solución que aparece en la figura 4.17 es correcta, y permite el máximo paralelismo para un número arbitrario de filósofos. Utiliza un vector, estado, para llevar un registro de la actividad de un filósofo: si está comiento, pensando o hambriento (estado que indica que quiere coger los tenedores). Un filósofo puede comer únicamente si los vecinos no están comiendo. Los vecinos del i-ésimo filósofo se definen en las macros IZQ y DER. En otras palabras, si i= 2, entonces IZQ = 1, y DER = 3.

El programa utiliza un vector de semáforos, uno por filósofo, de forma que los filósofos hambrientos puedan bloquearse si los tenedores necesarios están ocupados. Observe que cada proceso ejecuta el procedimiento filósofo como programa principal, pero los demás procedimientos, coger_tenedores, dejar_tenedores y prueba, son procedimientos ordinarios y no procesos separados.

El problema de la cena de los filósofos es útil para modelar procesos que compiten por el acceso exclusivo a un número limitado de recursos, como una unidad de cinta u otro dispositivo de E/S. Otro problema famoso es el de los lectores y escritores (Courtois et al., 1971), que modela el acceso a una base de datos. Supóngase una base de datos, con muchos procesos que compiten por leer y escribir en ella. Se puede permitir que varios procesos lean de la base de datos al mismo tiempo, pero si uno de los procesos está escribiendo (es decir, modificando) la base de datos, ninguno de los demás debería tener acceso a ésta, ni siquiera los lectores. La pregunta es ¿ cómo programaría los lectores y escritores ? La solución se muestra en la figura 4.18.

En esta solución, el primer lector que obtiene el acceso a la base de datos realiza un wait sobre el semáforo bd. Los lectores siguientes sólo incrementan un contador, nl. Al salir los lectores, éstos decrementan el contador, y el último en salir realiza un signal sobre el semáforo, lo que permite entrar a un escritor bloqueado, si existe.

Una hipótesis implícita en esta solución es que los lectores tienen prioridad sobre los escritores. Si surge un escritor mientras varios lectores se encuentran en la base de datos el escritor debe esperar. Pero si aparecen nuevos lectores, y queda al menos un lector accediendo a la base de datos, el escritor deberá esperar hasta que no haya más lectores interesados en la base de datos.

  ENLACE A LA SIMULACIÓN LECTORES-ESCRITORES (Productor-Consumidor)