El problema de concurrencia del agente y los fumadores resuelto en Java

Escrito por picodotdev el .
java planeta-codigo programacion
Comentarios

Java

Junto con los ejemplos de la cena de los filósofos y la barbería el de los fumadores es otro ejemplo clásico que se estudia en las asignaturas de sistemas operativos. Estos ejemplos necesitan de mecanismos de sincronización y concurrencia para su correcto funcionamiento al haber varios procesos y recursos compartidos que los procesos intentan utilizar de forma concurrente pero que no se debe permitir utilizando notificaciones entre procesos o algunas primitivas de sincronización, concurrencia e hilos que posee Java como mutex, locks o semáforos.

El caso de los fumadores consiste en un grupo de fumadores que para fumar necesitan los ingredientes que les faltan para hacer un cigarrillo y fumárselo, poseen un ingrediente en cantidades ilimitadas pero les faltan otros dos. El agente posee cantidades ilimitadas de todos los ingredientes que son papel, tabaco y cerillas pero solo deja en una mesa dos de estos ingredientes a la vez. Cada fumador posee un ingrediente distinto de los tres necesarios y según los ingredientes que deje el agente uno de los fumadores podrá fumar con los dos ingredientes que el agente deja.

El agente y los fumadores representan en la realidad a procesos y los ingredientes a los recursos de un sistema. La dificultad radica en sincronizar los agentes y fumadores para que el agente cuando deje ingredientes en la mesa el fumador correcto fume cuando.

A primera vista podríamos intentar que cada uno de los fumadores tomase cada uno de los ingredientes que le falta y se pusiese a fumar representando un ingrediente como un semáforo, sin embargo, esta solución puede producir un bloqueo si uno de los otros fumadores que no pueden fumar según los ingredientes que ha dejado el agente le quitan al que podría fumar uno de los ingredientes que necesita. Por ejemplo, un caso de bloqueo sería el caso de que el agente deje en la mesa los ingredientes de tabaco y cerillas el fumador que podría fumar sería el 1 pero si el fumador 2 es más rápido y se ejecuta antes tomando el tabaco el fumador 1 se quedaría esperando a tomar tabaco y el fumador 2 también por no haber dejado el agente papel sino cerillas.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
// Smoker 1
public void run() {
   tobbaco.take()
   match.take()
}

// Smoker 2
public void run() {
   tobbaco.take()
   paper.take()
}

// Smoker 3
public void run() {
   paper.take()
   match.take()
}

Para la solución hay que optar por otra estrategia, en el ejemplo de código he creado tres clases que representa a cada una de las entidades, una clase Agent, una clase Smoker y una clase Table, adicionalmente una clase Pusher que se encargará de despertar al Smoker correcto según los ingredientes de la mesa. Todas las clases implementan la interfaz Runnable para convertir cada una de las instancias en un hilo de ejecución. Cuando un agente deja ingredientes en la mesa se notifica a todos los incitadores o pushers para indicarles que hay ingredientes listos, el pusher adquiere el ingrediente que tiene asignado para tomar y comprueba cual es el único ingrediente que falta en la mesa, si no lo sabe porque falten varios ingredientes indica que en la mesa está su ingrediente y deja el trabajo de despertar al fumador al siguiente pusher. El pusher que sepa que dos ingredientes hay en la mesa despierta al fumador que puede fumar con el ingrediente que tiene y los dos que hay en la mesa. El fumador se pone a fumar y cuando termina se indica al agente que genere otros dos ingredientes.

1
2
3
4
5
package io.github.picodotdev.blogbitix.javaconcurrency.agent;

public enum Component {
     MATCH, TOBACCO, PAPER
}
 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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
package io.github.picodotdev.blogbitix.javaconcurrency.agent;

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

import java.util.*;
import java.util.concurrent.Semaphore;

public class Table implements Runnable {

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

    private Agent agent;
    private List<Smoker> smokers;
    private List<Pusher> pushers;
    private EnumMap<Component, Semaphore> components;
    private EnumMap<Component, Boolean> hasComponent;

    public Table() {
        this.agent = new Agent(this);
        this.smokers = new ArrayList<>();
        this.pushers = new ArrayList<>();
        this.components = new EnumMap<>(Component.class);
        this.hasComponent = new EnumMap<>(Component.class);
        for (Component component : Component.values()) {
            Smoker smoker = new Smoker(this, component);
            smokers.add(smoker);

            Pusher pusher = new Pusher(this, component);
            pushers.add(pusher);

            components.put(component, new Semaphore(0));
            hasComponent.put(component, Boolean.FALSE);
        }
    }

    public Boolean hasComponent(Component component) {
        return hasComponent.get(component);
    }

    public void setComponent(Component component) {
        hasComponent.put(component, Boolean.TRUE);
    }
    
    public void take(Component component) throws InterruptedException {
        components.get(component).acquire();
    }

    public EnumSet<Component> getComponents() {
        EnumSet<Component> components = EnumSet.noneOf(Component.class);
        for (Map.Entry<Component, Boolean> entry : hasComponent.entrySet()) {
            if (entry.getValue()) {
                components.add(entry.getKey());
            }
        }
        return components;
    }

    public void putComponents(EnumSet<Component> components) {
        logger.info("Agent generated {}", components);
        for (Component component : Component.values()) {
            hasComponent.put(component, Boolean.FALSE);
        }
        for (Component component : components) {
            this.components.get(component).release();
        }
    }

    public void awakeAgent() {
        agent.awake();
    }

    public void awakeSmoker(Component component) throws InterruptedException {
        for (Smoker smoker: smokers) {
            if (smoker.hasComponent(component)) {
                smoker.awake();
                break;
            }
        }
    }

    public void run() {
        new Thread(agent).start();
        for (Smoker smoker : smokers) {
            new Thread(smoker).start();
        }
        for (Pusher pusher : pushers) {
            new Thread(pusher).start();
        }
    }
}
 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
package io.github.picodotdev.blogbitix.javaconcurrency.agent;

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

import java.util.concurrent.Semaphore;

public class Smoker implements Runnable {

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

    private Table table;
    private Component component;
    private Semaphore components;
    
    public Smoker(Table table, Component component) {
        this.table = table;
        this.component = component;
        this.components = new Semaphore(0);
    }

    public Component getComponent() {
        return component;
    }

    public boolean hasComponent(Component component) {
        return this.component == component;
    }
    
    public void smoke() throws InterruptedException {
        logger.info("Smoker {} smoking during {}ms", component, 3000);
        Thread.sleep(3000);
    }

    public void awake() {
        components.release();
    }
    
    private void awaitComponents() throws InterruptedException {
        components.acquire();
    }
    
    public void run() {
        while (true) {
            try {
                awaitComponents();
                smoke();
                table.awakeAgent();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }
}
 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.agent;

import java.util.EnumSet;
import java.util.Random;
import java.util.concurrent.Semaphore;

public class Agent implements Runnable {

    private Table table;
    private Random random;
    private Semaphore semaphore;

    public Agent(Table table) {
        this.table = table;
        this.random = new Random();
        this.semaphore = new Semaphore(1);
    }
    
    public EnumSet<Component> nextComponents() {
        EnumSet<Component> components = EnumSet.allOf(Component.class);
        Component[] array = components.toArray(new Component[0]);
        int i = random.nextInt(array.length);
        components.remove(array[i]);
        return components;
    }
    
    public void putComponents() {
         table.putComponents(nextComponents());
    }

    public void sleep() throws InterruptedException {
        semaphore.acquire();
    }

    public void awake() {
        semaphore.release();
    }
    
    public void run() {
        while (true) {
            try {
                sleep();
                putComponents();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }
}
 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
package io.github.picodotdev.blogbitix.javaconcurrency.agent;

import java.util.EnumSet;
import java.util.concurrent.locks.ReentrantLock;

public class Pusher implements Runnable {

    private static ReentrantLock lock;

    private Table table;
    private Component component;

    static {
        lock = new ReentrantLock();
    }

    public Pusher(Table table, Component component) {
        this.table = table;
        this.component = component;
    }

    public void run() {
        while (true) {
            try {
                table.take(component);
                lock.lock();

                table.setComponent(component);
                EnumSet<Component> components = EnumSet.complementOf(table.getComponents());

                if (components.size() == 1) {
                    table.awakeSmoker(components.iterator().next());
                }
                lock.unlock();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
package io.github.picodotdev.blogbitix.javaconcurrency.agent;

public class Main {

    public static void main(String[] args) {
        new Thread(new Table()).start();
    }
}
Ejemplo de concurrencia del agente y los fumadores

En el siguiente documento con varios de los problemas de concurrencia y sincronización está muy bien explicado la solución a este problema de los fumadores y de los otros casos. En algunos otros sitios este caso lo convierten en un problema de sincronización en vez de uno de concurrencia.

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 el comando ./gradlew run.