El problema de concurrencia de la cena de los filósofos resuelto con Java

Escrito por el 25/02/2018.
java planeta-codigo programacion
Enlace permanente Comentarios

Java

En un artículo de introducción sobre la programación concurrente en Java explicaba cuales eran la facilidades que proporciona este lenguaje para la programación concurrente en múltiples hilos. En él exponía dos ejemplos clásicos que se estudian en las asignaturas de sistemas operativos, uno de ellos era el de la cena de los filósofos donde varios filósofos sentados en una tabla durante una cena se dedican a pensar y cuando tienen hambre comen usando para ello dos tenedores que comparten con sus compañeros que se sientan a la izquierda y derecha.

Dado que dos filósofos no puede utilizar el mismo tenedor a la vez hay que implementar sincronización a la hora de utilizarlos. En la realidad un filósofo representa a un proceso y un tenedor representa a un recurso compartido de uso exclusivo.

La solución del ejemplo que ponía en el artículo anterior no era completamente correcto ya que un filósofo si tiene mala suerte podría quedarse sin comer o sin comer durante mucho tiempo, debido a que en esa implementación el filósofo intentaba coger los tenedores y si no podía desistía si alguno de sus compañeros los estuviese utilizando. Las reglas que ha de cumplir una solución a un problema de concurrencia para considerarse válida son:

Exclusión mutua: Si un proceso se está ejecutando en su sección crítica ningún otro proceso se puede estar ejecutando en la suya.
Progreso: Si ningún proceso se está ejecutando en su sección crítica y hay otros procesos que desean entrar en las suyas, entonces solo aquellos procesos que no se está ejecutando en su sección restante pueden participar en la decisión del cuál será el siguiente en entrar en la sección crítica, y esta selección no puede postergarse indefinidamente.
Espera limitada: Debe haber un límite en el número de veces que se permite que los demás procesos entren en su sección crítica después de que un proceso haya efectuado una solicitud para entrar en la suya y antes de que se conceda esa solicitud.

En la implementación de este ejemplo evitaré que un filósofo pueda quedarse sin comer. La razón de que un filósofo desistiera de coger uno de los tenedores que necesita si uno de sus compañeros ya lo tuviese era para evitar un bloqueo circular en el caso de que todos los filósofos al mismo tiempo cogiesen su tenedor izquierdo, en esta situación ninguno de ellos podría coger su tenedor derecho y se quedarían todos esperando indefinidamente, se produciría un bloqueo indefinido o deadlock.

Para evitar un bloqueo indefinido una de las siguientes reglas no se ha de cumplir:

Exclusión mutua: Por lo menos un recurso debe retenerse en modo no compartido; es decir, sólo un proceso a la vez puede usar el recurso. Si otro proceso solicita el recurso, deberá esperar hasta que se haya liberado.
Retención y espera: Debe haber un proceso que retenga por lo menos un recurso y espere adquirir otros recursos retenidos por otros procesos.
No apropiación: Los recursos no se pueden quitar; es decir, un recurso solo puede ser liberado voluntariamente por el proceso que lo retiene, después de que haya cumplido su tarea.
Espera circular: Debe haber un conjunto { P0, P1, …, Pn } de procesos en espera tales que P0 espera un recurso retenido por P1, P1 espera un recurso retenido por P2, … Pn-1 espera un recurso retenido por On, y Pn espera un recurso retenido por P0.

En esta implementación he optado por hacer que el último filósofo en vez de ser diestro sea zurdo de modo que primero intente coger el tenedor izquierdo y luego el derecho, con este simple cambio la espera circular ya no puede producirse y con ello el bloqueo indefinido.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


package io.github.picodotdev.blogbitix.javaconcurrency.philosophers2;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

public class Main {

    private static Logger logger = LoggerFactory.getLogger(io.github.picodotdev.blogbitix.javaconcurrency.philosophers.Main.class);

    public static void main(String[] args) throws Exception {
        logger.info("Setuping dinner...");
        Table table = new Table(5);
        Thread dinner = new Thread(table);

        logger.info("Starting dinner...");
        dinner.start();
        dinner.join();
    }
}

Main.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50


package io.github.picodotdev.blogbitix.javaconcurrency.philosophers2;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Random;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class Table implements Runnable {

    private List<Fork> forks;
    private List<Philosopher> philosophers;
    private Iterator<Long> times;

    public Table(int numPhilosophers) {
        if (numPhilosophers < 2) {
            throw new IllegalArgumentException("There should be more than one philosopher");
        }

        this.forks = new ArrayList<>();
        this.philosophers = new ArrayList<>();
        this.times = new Random().longs(2000, 7000).iterator();

        for (int i = 0; i < numPhilosophers; ++i) {
            Fork f = new Fork();
            forks.add(f);
        }
        for (int i = 0; i < numPhilosophers; ++i) {
            int n = (i + 1) % numPhilosophers;
            Fork left = forks.get(i);
            Fork right = forks.get(n);
            boolean isLeftHanded = (n == 0);

            Philosopher p = new Philosopher("Philosopher " + (i + 1),this, left, right, isLeftHanded);
            philosophers.add(p);
        }
    }

    public synchronized long getTime() {
        return times.next();
    }

    public void run() {
        ExecutorService executorService = Executors.newFixedThreadPool(philosophers.size());
        for (Philosopher p : philosophers) {
            executorService.submit(p);
        }
    }
}

Table.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


package io.github.picodotdev.blogbitix.javaconcurrency.philosophers2;

import java.util.concurrent.locks.ReentrantLock;

public class Fork {

    private ReentrantLock lock;

    public Fork() {
        this.lock = new ReentrantLock();
    }

    public void take() {
        lock.lock();
    }

    public void drop() {
        if (!isHeld())
            return;
        lock.unlock();
    }

    public boolean isHeld() {
        return lock.isHeldByCurrentThread();
    }
}

Fork.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72


package io.github.picodotdev.blogbitix.javaconcurrency.philosophers2;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

public class Philosopher implements Runnable {

    private static Logger logger = LoggerFactory.getLogger(Philosopher.class);

    private String name;
    private Table table;
    private Fork right;
    private Fork left;
    private boolean isLeftHanded;

    public Philosopher(String name, Table table, Fork left, Fork right, boolean isLeftHanded) {
        this.name = name;
        this.table = table;
        this.right = right;
        this.left = left;
        this.isLeftHanded = isLeftHanded;
    }

    public void think() throws InterruptedException {
        long time = table.getTime();
        logger.info("{} thinking during {}ms", name, time);
        spendTime(time);
    }

    public void eat() throws InterruptedException {
        takeForks();
        long time = table.getTime();
        logger.info("{} eating during {}ms", name, time);
        spendTime(time);
        dropForks();
    }

    public void run() {
        while (true) {
            try {
                think();
                eat();
            } catch (Exception e) {
                logger.error(e.getMessage(), e);
            }
        }
    }

    private void takeForks() {
        if (isLeftHanded) {
            left.take();
            right.take();
        } else {
            right.take();
            left.take();
        }
    }

    private void dropForks() {
        if (isLeftHanded) {
            left.drop();
            right.drop();
        } else {
            right.drop();
            left.drop();
        }
    }

    private void spendTime(long time) throws InterruptedException {
        Thread.sleep(time);
    }
}

Philosopher.java

El código fuente completo del ejemplo puedes descargarlo del repositorio de ejemplos de Blog Bitix alojado en GitHub y probarlo en tu equipo ejecutando siguiente comando:
./gradlew run

Referencia: