imported>Renardo la vulpo: die Variable "turn" aus dem englischen Artikel heißt hier "last_thread"

2024-03-20T18:25:50Z

die Variable "turn" aus dem englischen Artikel heißt hier "last_thread"

Neue Seite

Der '''Dekker-Algorithmus''' ist die älteste bekannte vollständige Lösung<ref>E. W. Dijkstra: "Cooperating sequential processes", Technological University, Eindhoven, The Netherlands, September 1965</ref> des Problems, den wechselseitigen Ausschluss ([[Mutex]]) in der dezentralen Steuerung von [[Prozess (Computer)|Prozessen]] ([[Prozesssynchronisation]]) zu gewährleisten. Er vermeidet gegenseitiges Blockieren ([[Deadlock (Informatik)|Deadlock]]) und gewährleistet, dass stets genau ein Prozess in einen [[Kritischer Abschnitt|kritischen Abschnitt]] gelangen kann ([[Sequentialisierung]]). Der Algorithmus wurde 1965 von dem niederländischen Mathematiker [[Theodorus Dekker]] formuliert.<ref>Joe Duffy: "Concurrent Programming on Windows", Addison-Wesley Professional, 2008</ref> 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:
{|
|-
|colspan="2"|
<syntaxhighlight lang="c">
// 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
</syntaxhighlight>
|-
|
<syntaxhighlight lang="c">
// 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;
</syntaxhighlight>
|
<syntaxhighlight lang="c">
// 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;
</syntaxhighlight>
|-
|colspan="2" style="font-size:90%"|
<syntaxhighlight lang="c">
// °) 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
</syntaxhighlight>
|}

== Funktionsweise ==
Der Dekker-Algorithmus für zwei Prozesse arbeitet mit drei Variablen.
Zwei geben den Wunsch des Betretens des kritischen Abschnitts an <code>wants_to_enter</code>, eine den letzten benutzenden Thread <code>last_thread</code>.
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:
<syntaxhighlight lang="c">
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 °°)
</syntaxhighlight>

Für den anderen Thread (man beachte, das <code>me</code> und <code>other</code> jeweils dem <code>other</code> und <code>me</code> des anderen Threads entsprechen):
<syntaxhighlight lang="c">
wants_to_enter[me] = true;
while (wants_to_enter[other]) // Poche auf meine Anforderung, °°)
;
...
last_thread = me; // Löst °)
</syntaxhighlight>

== Bedeutung ==
Im Gegensatz zu früher gefundenen Lösungen zur dezentralen Steuerung arbeitet der Dekker-Algorithmus aufgrund der Variable <code>last_thread</code> 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.<ref>E. W. Dijkstra: "Solution of a Problem in Concurrent Programming Control", Communications of the ACM, Volume 8 Issue 9, 1965, S. 569</ref>
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 [[Aktives Warten|Busy waiting]].

== Einzelnachweise ==
<references />

[[Kategorie:Algorithmus]]
[[Kategorie:Betriebssystemtheorie]]

Dekker-Algorithmus - Versionsgeschichte

imported>Renardo la vulpo: die Variable "turn" aus dem englischen Artikel heißt hier "last_thread"