Solución al problema de los filósofos comensales con la biblioteca Asynchronous Agents

La librería Asynchronous Agents de Visual C++ 2010 permite dar solución al problema de los filósofos comensales sin utilizar semáforos, monitores, bloqueos ni nada de esto directamente, sino simplemente utilizando un sistema de paso de mensajes síncronos y asíncronos. Esto facilita mucho la implementación puesto que podemos centrarnos en las abstracciones del problema y despreocuparnos bastante de los problemas de concurrencia y bloqueo mutuo.

Los filósofos comensales

Empecemos repasando el problema de los filósofos comensales. Recordemos que este problema planteado por Djikstra planteaba una mesa a la cual se sienta un determinado número de filósofos que se pasan el tiempo pensando o comiendo, de forma alternativa, de un gran bol de arroz que se encuentra situado en el centro de la mesa. Para ello, los filósofos necesitan tomar un par de palillos, uno que se encuentra a su izquierda y otro a su derecha. El problema es que no hay palillos para todos, de manera que a cada lado de cada filósofo se encuentra solamente un palillo. Hasta que un filósofo no tiene los dos palillos no puede empezar a comer. Cuando un filósofo desea pensar, deja cada palillo a cada lado, y deja de comer. El problema del bloqueo mutuo en este planteamiento viene si todos los filósofos cogen uno de los palillos, puesto que jamás podrán coger el otro palillo, que está ocupado por otro filósofo, produciéndose una espera indefinida. ¿Cómo coordinamos a los filósofos para que puedan comer y pensar sin problema?

Cómo resolver el problema con Asynchronous Agents

En este problema, los filósofos serían hilos independientes que tratan de acceder a un recurso compartido, representado por los palillos. Cada filósofo solamente tiene constancia de los dos palillos que hay a ambos lados de su plato, siendo el resto invisibles para él.

El problema así puede ser resuelto con cuatro entidades:

  • Una clase Chopstick, que representa a cada uno de los palillos situados en la mesa.
  • Una clase ChopstickProvider, que se encarga de mantener los palillos en la mesa y asignárselos a los filósofos.
  • Una clase Philosopher que es responsable de pensar y comer y es consciente solamente de dos ChopstickProviders.
  • Una clase Table que representa a la mesa y que contiene un conjunto de Philosopher, otro de Chopstick y otro de ChopstickProvider.

Es posible que a la hora de la implementación nos demos cuenta de que alguna de estas clases puede ser colapsada en una estructura de datos o algo más sencillo, dependiendo de la funcionalidad que pueda proveer.

Evitaremos de aquí en adelante todo detalle de implementación, limitándonos simplemente a decir cómo podemos utilizar la biblioteca Asynchronous Agents para resolver el problema de los filósofos comensales.

Envío de mensajes

Los ChopstickProviders pueden ser implementados utilizando colas de llamadas:

  • Concurrency::send para enviar un mensaje a una cola o buffer de mensajes; se espera un ACK del envío.
  • Concurrency::receive para recibir un mensaje; se bloquea hasta que recibe un mensaje.
  • Concurrency::asend, como send pero asíncrono.
  • Concurrency::try_receive, como receive pero no se bloquea hasta que haya un mensaje en la cola.

Los filósofos

Pueden ser implementados como agentes, derivar de una clase abstracta llamada Concurrency::agent, e implementar el método run(). Durante el ciclo de Comer() y Pensar() se puede realizar una espera aleatoria o cualquier otra cosa.

La sincronización

Viene provista de la llamada Concurrency::join, que puede soportar distintos tipos de fuentes de mensajes o solamente el mismo tipo de fuente; además puede realizar un uso glotón de los mensajes que llegan (consumiéndolos a medida que llegan) o no (esperando a que todos los mensajes requeridos lleguen). Es fácil ver que para esta solución necesitamos utilizar la alternativa de un simple tipo de fuente y no glotona, precisamente para evitar el problema del bloqueo mutuo.

Los detalles de la implementación de esta solución se encuentran en el artículo que se referencia debajo.


Referencias:

“Solving the Dining Philosophers Problem With Asynchronous Agents”
Rick Molloy
MSDN Magazine
June 2009

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s