Problemas clásicos de condiciones de competencia

Problema de la cena de los filósofos

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 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?

El problema de los lectores y los escritores

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.