Algoritmo de Dekker para 3 procesos se bloquea

publicado por: Anonymous

Buenas a todos, quiero implementar el famoso Algoritmo de Dekker para solventar el problema de la exclusión mutual para 3 procesos en vez de 2. Tengo 3 procesos cualquiera P, Q y R, cada proceso tiene su variable booleana indicando si quiere o no entrar en la sección crítica. Supongamos que P quiere entrar en la sección crítica: primero comprueba si es el turno de alguno de los otros procesos que quieren entrar en la sección crítica, si es así, espera hasta que sea su turno, que es entonces cuando entrará a realizar el incremento.
El problema creo que lo tengo al ceder el turno luego, ¿debería tener en cuenta que un proceso haya terminado?

  • Para 2000000 iteraciones el programa no acaba, se bloquea.
  • Para 200 iteraciones el programa termina a veces, dando el resultado esperado, pero otras veces se bloquea también.

Mi código es el siguiente:

public class algDekker {
    /* Iteraciones que dará cada hilo */
    static final int iteraciones = 2000000;
    /* Recurso compartido */
    static volatile int enteroCompartido = 0;
    /* Representa el deseo del hilo P de entrar en la seccion critica */
    static volatile boolean wantp = false;
    /* Representa el deseo del hilo Q de entrar en la seccion critica */  
    static volatile boolean wantq = false;
    /* Representa el deseo del hilo R de entrar en la seccion critica */  
    static volatile boolean wantr = false;
    /* Representa de quien es el turno */
    static volatile int turn = 1;

   /**
    * Clase que modela un proceso cualquiera P
    * 
    */
    class P extends Thread {
        public void run() {
            for (int i=0; i<iteraciones; ++i) {
                /* Seccion no critica */
                wantp = true;
                while (wantq || wantr) {
                    if (turn == 2 || turn == 3) {
                        wantp = false;
                        while (turn == 2 || turn == 3)
                            Thread.yield();
                        wantp = true;
                    }
                }

                /* Seccion critica */
                ++enteroCompartido;
                /* Fin Seccion critica */

                turn = 2;
                wantp = false;
            }
        }
    }

    /**
     * Clase que modela un proceso cualquiera Q
     * 
     */
    class Q extends Thread {
        public void run() {
            for (int i=0; i<iteraciones; ++i) {
                /* Seccion no critica */
                wantq = true;
                while (wantp || wantr) {
                    if (turn == 1 || turn == 3) {
                        wantq = false;
                        while (turn == 1 || turn == 3)
                             Thread.yield();
                        wantq = true;
                    }
                }

                /* Seccion critica */
                --enteroCompartido;
                /* Fin Seccion critica */

                turn = 3;
                wantq = false;
            }
        }
    }

    /**
     * Clase que modela un proceso cualquiera R
     * 
     */
    class R extends Thread {
        public void run() {
            for (int i=0; i<iteraciones; ++i) {
                /* Seccion no critica */
                wantr = true;
                while (wantp || wantq) {
                    if (turn == 1 || turn == 2) {
                        wantr = false;
                        while (turn == 1 || turn == 2)
                            Thread.yield();
                        wantr = true;
                    }
                }

                /* Seccion critica */
                ++enteroCompartido;
                /* Fin Seccion critica */

                turn = 1;
                wantr = false;
            }
        }
    }

     /**
     * Constructor de algDekker
     */
    algDekker() {
        Thread p = new P();
        Thread q = new Q();
        Thread r = new R();
        p.start();
        q.start();
        r.start();

        try {
            p.join();
            q.join();
            r.join();
            System.out.println("El valor del recurso compartido es " +  enteroCompartido);
            System.out.println("Deberia ser 2000000.");
        } catch (InterruptedException e) {}
    }

    public static void main(String[] args) {
        new algDekker();
    }
}

solución

Por definición, el Algoritmo de Dekker funciona solamente con 2 hilos:

El algoritmo de Dekker es un algoritmo de programación concurrente para exclusión mutua, que permite a dos procesos o hilos de ejecución compartir un recurso sin conflictos

(el resaltado es mio)

Si analizas su funcionamiento, te darás cuenta de esta característica (o limitación) del algoritmo.

Respondido por: Anonymous

Leave a Reply

Your email address will not be published. Required fields are marked *