Hola a todos, hoy os voy a explicar como resolver el famoso problema de la cena de los filósofos.
El problema de la cena de los filósofos, es un famoso ejercicio relacionado con la sincronización de procesos.
El enunciado es el siguiente:
Cinco filósofos se sientan alrededor de una mesa y pasan su vida cenando y pensando. Cada filósofo tiene un plato de fideos y un tenedor a la izquierda de su plato. Para comer los fideos son necesarios dos tenedores y cada filósofo sólo puede tomar los que están a su izquierda y derecha. Si cualquier filósofo toma un tenedor y el otro está ocupado, se quedará esperando, con el tenedor en la mano, hasta que pueda tomar el otro tenedor, para luego empezar a comer.
Si dos filósofos adyacentes intentan tomar el mismo tenedor a una vez, se produce una condición de carrera: ambos compiten por tomar el mismo tenedor, y uno de ellos se queda sin comer.
Si todos los filósofos toman el tenedor que está a su derecha al mismo tiempo, entonces todos se quedarán esperando eternamente, porque alguien debe liberar el tenedor que les falta. Nadie lo hará porque todos se encuentran en la misma situación (esperando que alguno deje sus tenedores). Entonces los filósofos se morirán de hambre. Este bloqueo mutuo se denomina interbloqueo o deadlock.
El problema consiste en encontrar un algoritmo que permita que los filósofos nunca se mueran de hambre.
Empecemos por partes. Para este ejercicio yo necesitaré 3 clases:
- Mesa: será nuestra clase monitor, contiene los tenedores que debemos manejar (array de booleanos) y en ella haremos las operaciones de coger y dejar los tenedores.
- Filósofo: clase que extiende de la clase Thread y realiza las tareas del filósofo, pensar y comer.
- Principal: crea los 5 filósofos y empieza la aplicación.
En la clase Mesa, tendremos como atributo un array de booleanos que representan a los tenedores. Por ejemplo, cuando el tenedor de la posición 0 este a true, significa que esta libre.
En el constructor, inicializaremos el array, según el numero de tenedores deseados, en nuestro caso 5.
public class Mesa {
private boolean[] tenedores;
public Mesa(int numTenedores){
this.tenedores = new boolean[numTenedores];
}
}
Cuando un filósofo quiera coger el tenedor de la izquierda y de la derecha, tendremos que decirle cual es la posición concretamente (mirar la imagen de arriba).
El tenedor de su izquierda, coincide con el índice del filósofo.
El tenedor de su derecha, es una posición menos del índice del filósofo. En el caso del 0, obtendremos el ultimo índice del array.
public class Mesa {
private boolean[] tenedores;
public Mesa(int numTenedores){
this.tenedores = new boolean[numTenedores];
}
public int tenedorIzquierda(int i){
return i;
}
public int tenedorDerecha(int i){
if(i == 0){
return this.tenedores.length - 1;
}else{
return i - 1;
}
}
}
En algún momento, tenemos que hacer parar al proceso para empezar a comer y liberarlos cuando termine.
A la hora de coger los tenedores, comprobaremos si el tenedor de la izquierda o derecha están ocupados, de ser así, esperaremos con wait(). Sino están ocupados, pondremos a true las dos posiciones del array.
Al dejar los tenedores, pondremos a false ambos tenedores que ocupa el filósofo y notificaremos a todos aquellos procesos que estuvieran parados en el anterior método para que vuelvan a comprobar los tenedores.
public class Mesa {
private boolean[] tenedores;
public Mesa(int numTenedores){
this.tenedores = new boolean[numTenedores];
}
public int tenedorIzquierda(int i){
return i;
}
public int tenedorDerecha(int i){
if(i == 0){
return this.tenedores.length - 1;
}else{
return i - 1;
}
}
public synchronized void cogerTenedores(int comensal){
while(tenedores[tenedorIzquierda(comensal)] || tenedores[tenedorDerecha(comensal)]){
try {
wait();
} catch (InterruptedException ex) {
Logger.getLogger(Mesa.class.getName()).log(Level.SEVERE, null, ex);
}
}
tenedores[tenedorIzquierda(comensal)] = true;
tenedores[tenedorDerecha(comensal)] = true;
}
public synchronized void dejarTenedores(int comensal){
tenedores[tenedorIzquierda(comensal)] = false;
tenedores[tenedorDerecha(comensal)] = false;
notifyAll();
}
}
En la clase Filósofo, tendremos como atributos:
- Instancia de la clase Mesa: usado para gestionar los tenedores.
- Índice del filosofo: el índice usado para los arrays de tenedores.
- Comensal: el número del filósofo, usado para mostrar en consola.
public class Filosofo extends Thread {
private Mesa mesa;
private int comensal;
private int indiceComensal;
public Filosofo(Mesa m, int comensal){
this.mesa = m;
this.comensal = comensal;
this.indiceComensal = comensal - 1;
}
}
Como hemos comentado, los filósofos comen y piensan, que simplemente lo representaremos como una espera de x segundos.
public class Filosofo extends Thread {
private Mesa mesa;
private int comensal;
private int indiceComensal;
public Filosofo(Mesa m, int comensal){
this.mesa = m;
this.comensal = comensal;
this.indiceComensal = comensal - 1;
}
public void pensando(){
System.out.println("Filosofo " + comensal + " esta pensando");
try {
sleep((long) (Math.random() * 4000));
} catch (InterruptedException ex) { }
}
public void comiendo(){
System.out.println("Filosofo " + comensal + " esta comiendo");
try {
sleep((long) (Math.random() * 4000));
} catch (InterruptedException ex) { }
}
}
Recordemos que está clase hereda de Thread, por lo que necesitamos crear un método run, donde realizaremos la vida del filósofo.
public class Filosofo extends Thread {
private Mesa mesa;
private int comensal;
private int indiceComensal;
public Filosofo(Mesa m, int comensal){
this.mesa = m;
this.comensal = comensal;
this.indiceComensal = comensal - 1;
}
public void run(){
while(true){
this.pensando();
this.mesa.cogerTenedores(this.indiceComensal);
this.comiendo();
System.out.println("Filosofo " + comensal + " deja de comer, tenedores libres " + (this.mesa.tenedorIzquierda(this.indiceComensal) + 1) + ", " + (this.mesa.tenedorDerecha(this.indiceComensal) + 1) );
this.mesa.dejarTenedores(this.indiceComensal);
}
}
public void pensando(){
System.out.println("Filosofo " + comensal + " esta pensando");
try {
sleep((long) (Math.random() * 4000));
} catch (InterruptedException ex) { }
}
public void comiendo(){
System.out.println("Filosofo " + comensal + " esta comiendo");
try {
sleep((long) (Math.random() * 4000));
} catch (InterruptedException ex) { }
}
}
En la clase ejecutable, simplemente crearemos una mesa y 5 filósofos. Arrancamos los hilos.
public class Principal {
public static void main(String[] args) {
Mesa m = new Mesa(5);
for (int i = 1; i <= 5; i++) {
Filosofo f = new Filosofo(m, i);
f.start();
}
}
}
Un ejemplo de ejecución sería este:
Importante, no tiene porque verse siempre igual, ya que depende de los procesos.
Os dejo un video donde lo comento todo paso a paso:
Espero que os sea de ayuda. Si tenéis dudas, preguntad. Estamos para ayudarte.
Hola buenas me ha gustado mucho tu video, pero a mi me da un error
El comensal 7 esta hablando mientras espera
Exception in thread «Thread-0» java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 5
at Comensales dentro de mesa, puesto que me salen mas comensales de los que le he puesto y no me deja aplicar el método Logger.getLogger(Mesa.class.getName()).log(Level.SEVERE, null, ex); alguna solucion?? MUCHAS GRACIAS DE ANTEMANO POR EL VIDEO <3