Dekker Algorithm for 3 processes is blocked

1

Good morning, I want to implement the famous Dekker Algorithm to solve the problem of mutual exclusion for 3 processes instead of 2. I have 3 processes, P, Q and R, each process has its Boolean variable indicating if it wants or Do not enter the critical section. Suppose that P wants to enter the critical section: first check if it is the turn of any of the other processes that want to enter the critical section, if so, wait until it is your turn, which is when you will enter to make the increase . The problem I think I have it when giving the turn later, should I keep in mind that a process has ended?

  • For 2000000 iterations the program does not end, it is blocked.
  • For 200 iterations the program ends sometimes, giving the expected result, but other times it also blocks.

My code is as follows:

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();
    }
}
    
asked by Repikas 18.11.2016 в 16:51
source

1 answer

1

By definition, the Dekker Algorithm only works with 2 threads:

  

The Dekker algorithm is a concurrent scheduling algorithm for mutual exclusion, which allows two processes or threads of execution to share a resource without conflicts

(the highlight is mine)

If you analyze its operation, you will notice this feature (or limitation) of the algorithm.

    
answered by 18.11.2016 / 17:25
source