Dekker-Algorithmus

aus WB Wiki; freien Wissensdatenbank rund ums Thema Computer
Wechseln zu: Navigation, Suche

Der Dekker-Algorithmus (benannt nach Theodorus Dekker) ist ein Algorithmus, genau wie der Peterson-Algorithmus, der das Problem mit dem Eintritt von Prozessen in der kritischen Section löst. Dieser Algorithmus gewährleistet, das nur ein Prozess in der kritischen Section sich befindet.

Pseudo C-Code des Algorithmus

// globale Variablendeklaration
  boolean flag1 = false;
  boolean flag2 = false;
  int turn = 0;   
 
  // Prozess 1                          // Prozess 2
  p0: flag1 = true;                     p1: flag2 = true;
      '''while''' (flag2) {                       '''while''' (flag1) {
          '''if''' (turn != 0) {                      '''if''' (turn != 1) {
              flag1 = false;                        flag2 = false;
              '''while''' (turn != 0) {                   '''while''' (turn != 1) {
              }                                     }
              flag2 = true;                         flag2 = true;
           }                                    }
      }                                     }
 
      // kritischer Abschnitt              // kritischer Abschnitt
      turn = 1;                            turn = 0;
      flag1 = false;                       flag2 = false;

Funktionsweise

Dieser Algorithmus arbeitet wie der Peterson-Algorithmus mit drei Variablen. Mit Ausnahme das die turn Variable als Schlüssel fungiert. Die beiden Flaggen werden mit dem boolischen Wert false deklariert. Die turn Variable wird auf 0 gesetzt. Beide Prozesse setzen Ihre Flaggen auf true und treten somit in die while-Schleife ein, weil die Bedingung erfüllt ist. Aber bei der if-Verzweigung ist die Bedingung im Prozess 1 nicht mehr erfüllt. Prozess 2 setzt flag2 auf false. Jetzt versucht Prozess 1 einen erneuten Eintritt in die while-Schleife. Aber dies schlägt fehl, weil die Bedingung für den Schleifeneintritt nicht mehr erfüllt ist und somit wandert Prozess 1 in die kritische Section. Wenn Prozess 1 die kritische Section verlässt setzt er turn auf 1 und flag1 auf false. Man kann also sagen wenn turn auf 0 gesetzt ist wandert Prozess 1 in die kritische Section und wenn turn auf 1 gesetzt ist wandert Prozess 2 in die kritische Section.