Dekker-Algorithmus

Dekker-Algorithmus

Der Dekker-Algorithmus (nach Theodorus Dekker) ist wie der Peterson-Algorithmus eine vollständige Lösung des Problems, den wechselseitigen Ausschluss (Mutex) in der dezentralen Steuerung von Prozessen (Prozesssynchronisation) zu gewährleisten. Er vermeidet gegenseitiges Blockieren (Deadlocks) und gewährleistet, dass stets genau ein Prozess in einen kritischen Abschnitt gelangen kann (Sequentialisierung).

Inhaltsverzeichnis

Schema

Der Algorithmus kann mit folgendem C-Code schematisch beschrieben werden:

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

Funktionsweise

Der Dekker-Algorithmus für 2 Prozesse arbeitet mit 3 Variablen: 2 Flags und einer Variable turn. Für jeden Prozess existiert genau ein Flag. Ein gesetztes Flag (flag=true) signalisiert, dass sich der dazugehörige Prozess im kritischen Abschnitt befinden könnte, die Variable turn fungiert als eine Art Token.

Die Eintrittsbedingung für die Schleife ist das Flag des anderen Prozesses: Ist dieses gesetzt, befindet sich der andere Prozess entweder im kritischen Bereich oder ebenfalls in der Schleife. Sollte letzteres der Fall sein, entscheidet der Zustand von turn über den weiteren Verlauf. Enthält turn die Nummer des anderen Prozesses, wird das eigene Flag zurückgesetzt und gewartet bis turn die Nummer des eigenen Prozess hat. Damit erhält der andere Prozess die Möglichkeit, die Schleife zu verlassen (falls er sich darin befunden hat) und in den kritischen Abschnitt zu gelangen.

Nach dem kritischen Abschnitt des anderen Prozesses wird turn auf die Nummer des eigenen Prozesses gesetzt und das Flag des anderen Prozesses zurückgesetzt. Dadurch kann der eigene Prozess beide Warteschleifen verlassen und in seinen kritischen Abschnitt gelangen.

Beispiel

-> '''turn''' wird mit 0 initialisiert.
-> Prozess #0 bekommt den Prozessor: flag0 = true;
-> Prozess #1 bekommt den Prozessor: flag1 = true;
-> Prozess #0 bekommt den Prozessor: Eintritt in die Schleife
-> Prozess #1 bekommt den Prozessor: Eintritt in die Schleife
-> Prozess #0 bekommt den Prozessor: Die Bedingung turn != 0 wird nicht erfüllt
-> Prozess #1 bekommt den Prozessor: Die Bedingung turn != 1 wird erfüllt
-> Prozess #0 bekommt den Prozessor: Erneuter Eintritt in die Schleife, da flag1 gesetzt
-> Prozess #1 bekommt den Prozessor: flag1 = false;
-> Prozess #0 bekommt den Prozessor: Die Bedingung turn != 0 wird nicht erfüllt
-> Prozess #1 bekommt den Prozessor: Die Bedingung turn != 1 wird erfüllt
-> Prozess #0 bekommt den Prozessor: Eintritt in den kritischen Abschnitt, da flag1 nicht gesetzt
-> Prozess #0 bekommt den Prozessor: turn = 1;
-> Prozess #1 bekommt den Prozessor: flag1 = true;
-> Prozess #0 bekommt den Prozessor: flag0 = false;
-> Prozess #1 bekommt den Prozessor: Die Bedingung turn != 1 wird nicht erfüllt
-> Prozess #0 bekommt den Prozessor: Rücksprung zu Marke P0, flag0 = true
-> Prozess #1 bekommt den Prozessor: Eintritt in den kritischen Abschnitt, da flag0 nicht gesetzt
-> Prozess #0 bekommt den Prozessor: Eintritt in die Schleife
-> Prozess #1 bekommt den Prozessor: turn = 0;
-> Prozess #0 bekommt den Prozessor: Die Bedingung turn != 0 wird nicht erfüllt
-> Prozess #1 bekommt den Prozessor: flag1 = false;
-> Prozess #0 bekommt den Prozessor: Eintritt in den kritischen Abschnitt, da flag1 nicht gesetzt, turn = 1;
-> Prozess #1 bekommt den Prozessor: Rücksprung zu Marke P1, flag1 = true

Bedeutung

Im Gegensatz zu anderen Lösungen zur dezentralen Steuerung arbeitet der Dekker-Algorithmus aufgrund der Variable turn auch dann korrekt, wenn das Scheduling abwechselnd zwischen beiden Prozessen hin und her springt. Eine Vereinfachung findet sich im ebenfalls korrekt arbeitenden Peterson-Algorithmus. Der Nachteil der dezentralen Steuerung bleibt bestehen: Wartende Prozesse geben den Prozessor nicht ab, sondern beanspruchen ihn durch Busy waiting.

Problem

Der Algorithmus von Dekker löst das Problem des wechselseitigen Ausschlusses nur teilweise. Terminiert ein Prozess im unkritischen Bereich, so kann auch der andere höchstens noch einmal den kritischen Bereich betreten und ist dann blockiert. Dies verstößt gegen die "Progress"-Eigenschaft, welche besagt: "Befindet sich kein Prozess im kritischen Bereich, aber es gibt einen Kandidaten für diesen Bereich, so hängt die Entscheidung, welcher Prozess ihn betreten darf, nur von diesem Kandidaten ab und fällt in endlicher Zeit." Diese Eigenschaft ist offensichtlich nicht erfüllt! Daher kann der Algorithmus nicht als eine vollständige Lösung angesehen werden. (Für vollständige Lösungen müssen die Eigenschaften: Mutual exclusion, Progress und Bounded Waiting erfüllt sein.)


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Dekker — ist der Familienname folgender Personen: Albert Dekker (eigentlich Albert van Ecke; 1905–1968), US amerikanischer Filmschauspieler und Kommunalpolitiker Cees Dekker (* 1959), niederländischer Nanowissenschaftler Desmond Dekker (1941–2006),… …   Deutsch Wikipedia

  • Algorithmus von Peterson — Der Peterson Algorithmus (nach Larry Peterson) ist eine vollständige Lösung des Problems des wechselseitigen Ausschlusses (Mutex) in der dezentralen Steuerung von Prozessen (Prozessynchronisation). Er gewährleistet, dass stets nur ein Prozess in… …   Deutsch Wikipedia

  • Peterson-Algorithmus — Der Peterson Algorithmus (nach Larry Peterson) ist eine vollständige Lösung des Problems des wechselseitigen Ausschlusses (Mutex) in der dezentralen Steuerung von Prozessen (Prozessynchronisation). Er gewährleistet, dass stets nur ein Prozess in… …   Deutsch Wikipedia

  • Gegenseitiger Ausschluss — Der Begriff Wechselseitiger Ausschluss bzw. Mutex (Abk. für engl. mutual exclusion, auf deutsch etwa wechselseitiger Ausschluss) bezeichnet eine Gruppe von Verfahren, mit denen das Problem des kritischen Abschnitts gelöst wird. Mutex Verfahren… …   Deutsch Wikipedia

  • Wechselseitiger Ausschluss — Der Begriff Wechselseitiger Ausschluss bzw. Mutex (Abk. für engl. mutual exclusion, auf deutsch etwa wechselseitiger Ausschluss) bezeichnet eine Gruppe von Verfahren, mit denen das Problem des kritischen Abschnitts gelöst wird. Mutex Verfahren… …   Deutsch Wikipedia

  • Dining philosophers problem — Aufbau des Philosophenproblems Es handelt sich bei dem Philosophenproblem (engl. Dining Philosophers Problem) um ein Fallbeispiel aus dem Bereich der Theoretischen Informatik. Dabei soll das Problem der Nebenläufigkeit erklärt werden, und die… …   Deutsch Wikipedia

  • Sequenzialisierung — Unter Sequentialisierung oder Sequenzialisierung versteht man das Schaffen einer Ordnung für eine Menge von Aktionen entlang der Kausalordnung, die z. B. durch einen Funktionsbaum gegeben ist. Der Sinn ist es, eine Reihenfolge zu finden, in der… …   Deutsch Wikipedia

  • Speisende Philosophen — Aufbau des Philosophenproblems Es handelt sich bei dem Philosophenproblem (engl. Dining Philosophers Problem) um ein Fallbeispiel aus dem Bereich der Theoretischen Informatik. Dabei soll das Problem der Nebenläufigkeit erklärt werden, und die… …   Deutsch Wikipedia

  • Mutex — Der Begriff Wechselseitiger Ausschluss bzw. Mutex (Abk. für engl. mutual exclusion) bezeichnet eine Gruppe von Verfahren, mit denen das Problem des kritischen Abschnitts gelöst wird. Mutex Verfahren verhindern, dass nebenläufige Prozesse bzw.… …   Deutsch Wikipedia

  • Philosophenproblem — Aufbau des Philosophenproblems Beim Philosophenproblem (engl. Dining Philosophers Problem) handelt es sich um ein Fallbeispiel aus dem Bereich der Theoretischen Informatik. Damit soll das Problem der Nebenläufigkeit erklärt werden und die Gefahr… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”