Dekker-Algorithmus

Der Dekker-Algorithmus ist die älteste bekannte vollständige Lösung 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. 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:

// Willensbekundungen, den kritischen Abschnitt betreten zu wollen volatile boolean wants_to_enter[2] = { false, false }; // letzter Thread, bei Konflikten der jeweils wartende Thread volatile int last_thread = 1; // Initialisierung kann mit 0 oder 1 erfolgen
// Thread 0 wants_to_enter[0] = true; while (wants_to_enter[1]) { if (last_thread == 0) { //° wants_to_enter[0] = false; while (last_thread == 0) ; wants_to_enter[0] = true; } } // hier kritischen Abschnitt einfügen last_thread = 0; wants_to_enter[0] = false;	// Thread 1 wants_to_enter[1] = true; while (wants_to_enter[0]) { if (last_thread == 1) { //° wants_to_enter[1] = false; while (last_thread == 1) ; wants_to_enter[1] = true; } } // hier kritischen Abschnitt einfügen last_thread = 1; wants_to_enter[1] = false;
// °) Im Fall, dass // * ein Thread den kritischen Abschnitt betreten möchte, // * der andere Thread diesen aber auch betreten möchte oder betreten hat, // * lässt der Thread, der das letzte Mal zum Zuge gekommen ist // - dem anderen Thread die Vorfahrt und setzt seinen Eintrittswunsch so lange zurück // - bis der andere fertig ist // * pocht der Thread, der das letzte Mal nicht zum Zuge gekommen ist // - auf die Erteilung der Semaphore // * Neben dem Ausbalancieren der Eintrittschancen ist zusätzlich geklärt // - wer zurückzutreten und zu warten hat und damit die Richtung der Signalisierung

Funktionsweise

Der Dekker-Algorithmus für zwei Prozesse arbeitet mit drei Variablen. Zwei geben den Wunsch des Betretens des kritischen Abschnitts an wants_to_enter, eine den letzten benutzenden Thread last_thread. Der letzte benutzende Thread trägt sich noch am Ende des kritischen Abschnitts als letzten benutzenden Thread ein und stellt sich damit bei einem Konflikt hinten an.

Für ihn sieht beim nächsten Aufruf, wenn der andere noch nicht zum Zuge gekommen ist, das Eintreten so aus:

wants_to_enter[me] = true;
while (wants_to_enter[other]) {
    wants_to_enter[me] = false;  // Rückstellung
    while (last_thread == me)    // Warte, bis der andere durch ist °)
        ;
    wants_to_enter[me] = true;
}
...
wants_to_enter[me] = false;      // Löst °°)

Für den anderen Thread (man beachte, das me und other jeweils dem other und me des anderen Threads entsprechen):

wants_to_enter[me] = true;
while (wants_to_enter[other])  // Poche auf meine Anforderung, °°)
    ;
...
last_thread = me;              // Löst °)

Bedeutung

Im Gegensatz zu früher gefundenen Lösungen zur dezentralen Steuerung arbeitet der Dekker-Algorithmus aufgrund der Variable last_thread 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. 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.