Algoritmo de Dekker para 3 procesos se bloquea

Iniciado por Repikas, 18 Noviembre 2016, 17:25 PM

0 Miembros y 1 Visitante están viendo este tema.

Repikas

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?

Sé que el Algoritmo de Dekker funciona bien sólo para 2 procesos, pero en vez de darme una salida errónea se me bloquea el programa y es ahí donde sé que el código tiene algún fallo.


  • 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 sección critica */
   static volatile boolean wantp = false;
   /* Representa el deseo del hilo Q de entrar en la sección critica */  
   static volatile boolean wantq = false;
   /* Representa el deseo del hilo R de entrar en la sección 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) {
               /* sección no critica */
               wantp = true;
               while (wantq || wantr) {
                   if (turn == 2 || turn == 3) {
                       wantp = false;
                       while (turn == 2 || turn == 3)
                           Thread.yield();
                       wantp = true;
                   }
               }

               /* sección critica */
               ++enteroCompartido;
               /* Fin sección 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) {
               /* sección no critica */
               wantq = true;
               while (wantp || wantr) {
                   if (turn == 1 || turn == 3) {
                       wantq = false;
                       while (turn == 1 || turn == 3)
                            Thread.yield();
                       wantq = true;
                   }
               }

               /* sección critica */
               --enteroCompartido;
               /* Fin sección 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) {
               /* sección no critica */
               wantr = true;
               while (wantp || wantq) {
                   if (turn == 1 || turn == 2) {
                       wantr = false;
                       while (turn == 1 || turn == 2)
                           Thread.yield();
                       wantr = true;
                   }
               }

               /* sección critica */
               ++enteroCompartido;
               /* Fin sección 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();
   }
}