Problema de los Filósofos Chinos
El planteamiento del problema de los filósofos chinos es el siguiente:
Hay cinco filósofos chinos sentados en una mesa circular , en frente de cada uno de los filósofos hay un plato de espagueti. Las tareas básicas de los filósofos son; pensar , y comer en este orden, aunque para cualquier persona razonable lo aconsejable sería la secuencia inversa.
El problema reside en que los filósofos cuentan únicamente con cinco tenedores como muestra la siguiente figura tomada del libro "Sistemas Operativos: Diseño e Implementación" del profesor Andrew S. Tanenbaum.
Una solución óptima se considerará aquella que permita el que él número máximo de filósofos pueda alimentarse a la vez, es decir, maximizar la concurrencia (dos a la vez supuestamente para el caso de 5 filósofos) y que no permita que se produzcan ciclos en el grafo que representa las peticiones y concesiones de los tenedores.
En pocas palabras, debemos evitar que se produzca en nuestra solución:
-Interbloqueo (los filósofos compiten por un mismo tenedor y a su vez
retienen otro que es solicitado a su vez por otros de una forma
circular).
-Inanición o postergación indefinida (que haya algún filósofo que nunca llegue a alimentarse aun habiéndose evitado el bloqueo).
Las condiciones de forma resumida, para que se de interbloqueo en un sistema no distribuido son las siguientes:
-Exclusión Mutua (Asignación exclusiva del recurso solicitado por el proceso).
-Retención y Espera (Un proceso tiene que ser capaz de retener los recursos asignados de manera que pueda esperar a conseguir el resto
y llegar a cumplir sus condiciones de ejecución).
-No Apropiación (Ni el sistema ni otro proceso puede tomar posesión de los recursos de un procesos sin que hayan sido previamente
liberados después de haber finalizado el actual propietario).
-Espera Circular (Dos o más procesos deben esperar por un recurso que es propiedad del siguiente en una estructura circular en el que el último procesos de la cadena espera por un recurso asignado al primero de ellos).
La inanición es posible que surja cuando alguna de las condiciones anteriores que debemos romper para evitar el interbloqueo haga que alguno de los filósofos jamás llegue a ejecutarse ya que nunca pueda obtener los dos tenedores necesarios.
Para poder elegir alguna técnica eficiente podemos consultar algún libro de programación concurrente o de sistemas operativos. De todas formas y como consejo, alguna solución puede estar basada en establecer alguna condición extra al problema en algún filósofo o tenedor pero eso hace que el problema varíe en su enunciado , así que considero que es mejor ceñirse al original.
De todas las soluciones al problema de los filósofos chinos a las que he tenido acceso es sin duda la propuesta por el profesor Andrew S. Tanenbaum es posiblemente la mejor, no sólo en rendimiento, sino que también conceptualmente.
En mi opinión, los defectos o las dificultades que se pueden encontrar hora de acercarse a esta solución son dos:
1)Aquellas entidades que conocíamos como tenedores situados a izquierda y a derecha del filósofo ya no existen como tales, sino que se considera el par como un sólo recurso condicionado por las acciones de los filósofos adyacentes. Aun así las ventajas de adoptar esta visión son 2.
1.1 En el caso de que consideraríamos los tenedores como recursos hardware, estos no tendría un código asociado, quedando todo el peso del código y de la gestión de los procesos relegada en ellos mismos o en planificador en caso de existir . (Esto podría ser el caso de planteamientos basados en modelos similares al exokernel, o quizá de algún otro desarrollo de Niklaus Wirth, pero esto es quizá alejarse del problema).
1.2 Es exactamente igual en que orden son tomados ambos tenedores y el orden en que han sido dejados, ya que sólo es tomado el par en una sola secuencia.
2)Los filósofos a la hora de soltar los tenedores influyen directamente sobre las acciones del resto de filósofos adyancentes. No se debería dejar que los procesos una vez acabados decidieran directamente sobre el futuro del resto, aunque en este caso no se trate de apropiación.
He desarrollado una variante, cuya principal diferencia es el uso de un mecanismo de genaración de números aleatorios para decidir en el caso de cada filósofo qué tenedor será tomado previamente, el izquierdo o el derecho, y lo mismo a la hora de soltarlos.
El principal inconveniente a la hora de usar el método de apropiación. En este caso, hacer que los filósofos suelten el tenedor retenido en caso de que estubiera el otro ocupado , es que el grafo que representa las solicitudes y asignaciones de tenedores podría repetir la forma de cilo en un sólo sentido del estado anterior, dando como resultado la no deseada inanición para todos los filósofos.
En esta variante, el grafo no se repetirá jamás de forma indefinida, la concurrencia es alta y se ejecutan dos filósofos al mismo tiempo que el caso de cinco es el máximo posible sin que se produzca "abrazo mortal".
Andrew S. Tanenbaum propuso usar la generación de números aleatorios para los tiempos de duración de las acciones pensar y comer como una solución poco fiable aunque factible para un corto tiempo de ejecución, en este caso, la generación de números aleatorios se usa simplemente para decidir entre izquierda y derecha.
El listado siguiente corresponde al código perteneceinte a a la solución propuesta, el lenguaje utilizado ha sido java y el código de prueba ha sido generado por el compilador gjc, usando como 'backend' gcc."
package concurrente.filosofos;
/*Clase Principal del programa*/
public class Filosofos{
public static void main( String args[] )
{
Tenedor tenedor[]=new Tenedor[5];
/*Instancias de los 5 tenedores */
tenedor[0]=new Tenedor(0);
tenedor[1]=new Tenedor(1);
tenedor[2]=new Tenedor(2);
tenedor[3]=new Tenedor(3);
tenedor[4]=new Tenedor(4);
Filosofo filosofo[]=new Filosofo[5];
/*instancias de los cinco filosofos*/
filosofo[0]=new Filosofo(0,tenedor[0],tenedor[1]);
filosofo[1]=new Filosofo(1,tenedor[1],tenedor[2]);
filosofo[2]=new Filosofo(2,tenedor[2],tenedor[3]);
filosofo[3]=new Filosofo(3,tenedor[3],tenedor[4]);
filosofo[4]=new Filosofo(4,tenedor[4],tenedor[0]);
/*Comienza la ejecucion de los filosofos*/
filosofo[0].start();
filosofo[1].start();
filosofo[2].start();
filosofo[3].start();
filosofo[4].start();
}
}
package concurrente.filosofos;
package concurrente.filosofos;
import java.lang.*;
import java.util.Random;
public class Filosofo extends Thread {
private int identificativo;
private Tenedor izquierda;
private Tenedor derecha;
private Random random;
private boolean izquierdatomado;
private boolean derechatomado;
private int elegido;
private boolean flag;
Filosofo(int identificativo_, Tenedor izquierda_, Tenedor derecha_)
{
identificativo=identificativo_;
izquierda=izquierda_;
derecha=derecha_;
random = new Random();
}
public void pensar()
{
try
{
this.sleep(10000);
}catch(InterruptedException ie)
{
}
}
public void comer()
{
try
{
System.out.println("comiendo...");
System.out.println(identificativo);
this.sleep(10000);
System.out.println("terminando de comer...");
System.out.println(identificativo);
}catch(InterruptedException ie)
{
}
}
public void run()
{
while(true)
{
this.pensar();
flag=false;
elegido=random.nextInt(2);
if(elegido==0)
{
if(!izquierda.esocupado())
{
izquierda.tomar();
izquierdatomado=true;
}
else if(!derecha.esocupado())
{
derecha.tomar();
derechatomado=true;
}
}
else if(elegido==1)
{
if(!derecha.esocupado())
{
derecha.tomar();
derechatomado=true;
}
else if(!izquierda.esocupado())
{
izquierda.tomar();
izquierdatomado=true;
}
}
if(izquierdatomado==true)
{
if(!derecha.esocupado())
{
derecha.tomar();
derechatomado=true;
flag=true;
}
else
{
izquierda.soltar();
izquierdatomado=false;
}
}
if(derechatomado==true && !flag)
{
if(!izquierda.esocupado())
{
izquierda.tomar();
izquierdatomado=true;
}
else
{
derecha.soltar();
derechatomado=false;
}
}
if(derechatomado && izquierdatomado)
{
this.comer();
elegido=random.nextInt(2);
if(elegido==0)
{
izquierda.soltar();
izquierdatomado=false;
derecha.soltar();
derechatomado=false;
}
else
{
derecha.soltar();
derechatomado=false;
izquierda.soltar();
izquierdatomado=false;
}
}
}
}
}
package concurrente.filosofos;
package concurrente.filosofos;
/* Clase Tenedor */
public class Tenedor {
private boolean ocupado=false;
private int identificativo;
Tenedor(int identificativo_)
{
identificativo = identificativo_;
}
/*Accion de soltar tenedor*/
synchronized void dejar()
{
ocupado=false;
notify();
}
/*Comprobar si el tenedor esta ocupado*/
synchronized boolean esocupado()
{
if(ocupado)
{
return true;
}
else
{
return false;
}
}
/*Accion de tomar el tenedor*/
synchronized void tomar()
{
ocupado=true;
}
void soltar()
{
ocupado=false;
}
}
Si esto tiene alguna utilidad para tí, lo encuentras interesante o tienes el suficiente tiempo, me encantaría recibir una postal de tu ciudad a la siguiente dirección.
Germán Carrera
Depto. de Matematicas, Est. y Comput.
Facultad de Ciencias
Universidad de Cantabria
39005-Santander
Spain