Dekker-Algorithmus
Der Dekker-Algorithmus ist die älteste bekannte vollständige Lösung[1] des Problems, den wechselseitigen Ausschluss (Mutex) in der dezentralen Steuerung von Prozessen (Prozesssynchronisation) zu gewährleisten. Er vermeidet gegenseitiges Blockieren (Deadlock) und gewährleistet, dass stets genau ein Prozess in einen kritischen Abschnitt gelangen kann (Sequentialisierung). Der Algorithmus wurde 1965 von dem niederländischen Mathematiker Theodorus Dekker formuliert.[2] In der hier beschriebenen Form kann er aber nur zwei Prozesse wechselseitig ausschließen.
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 zwei Prozesse arbeitet mit drei Variablen: Zwei 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
Quelle:[3]
Bedeutung
Im Gegensatz zu früher gefundenen 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 generalisierte Lösung zur Synchronisation von N Prozessen wurde ebenfalls noch 1965 von Edsger W. Dijkstra gefunden.[4]
Eine Vereinfachung findet sich im ebenfalls korrekt arbeitenden Peterson-Algorithmus, der jedoch erst 16 Jahre später entwickelt wurde. Der Nachteil der dezentralen Steuerung bleibt bestehen: Wartende Prozesse geben den Prozessor nicht ab, sondern beanspruchen ihn durch Busy waiting.
Einzelnachweise
- E. W. Dijkstra: "Cooperating sequential processes", Technological University, Eindhoven, The Netherlands, September 1965
- Joe Duffy: "Concurrent Programming on Windows", Addison-Wesley Professional, 2008
- Sibsankar Haldar: "Operating Systems", Selbstverlag 2015, S. 218
- E. W. Dijkstra: "Solution of a Problem in Concurrent Programming Control", Communications of the ACM, Volume 8 Issue 9, 1965, S. 569