Algorithmus von Peterson
aus Wikipedia, der freien Enzyklopädie
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 vermeidet gegenseitiges Blockieren (Deadlocks) und gewährleistet, dass stets nur ein Prozess in einen kritischen Abschnitt gelangen kann (Sequentialisierung). In der hier beschriebenen Form kann er aber nur 2 Prozesse wechselseitig ausschliessen.
[Bearbeiten] Schema
Der Algorithmus kann mit folgendem Pseudo-C-Code schematisch beschrieben werden:
// globale Variablendeklaration boolean flag0 = false, flag1 = false; int turn; // Prozess #0 // ... flag0 = true; turn = 1; while (flag1 && (turn == 1)) {} // busy waiting // <kritischer Abschnitt> flag0 = false; // ... // Prozess #1 // ... flag1 = true; turn = 0; while (flag0 && (turn == 0)) {} // busy waiting // <kritischer Abschnitt> flag1 = false; // ...
[Bearbeiten] Funktionsweise
Wenn Prozess #0 als erster startet, setzt er flag0
auf true
, anschließend turn
auf 1
. Da flag1
mit false
initialisiert ist, wird die Bedingung der while
-Schleife nicht erfüllt und Prozess #0 gelangt in den kritischen Abschnitt.
Wird währenddessen Prozess #1 gestartet, setzt dieser flag1
auf true
und turn
auf 0
. flag0
ist vorher bereits von Prozess #0 auf true
gesetzt worden. Damit ist die Bedingung für die while
-Schleife von Prozess #1 erfüllt, so dass dieser warten muss. Erst, wenn Prozess #0 den kritischen Abschnitt verlässt, wird flag0
false
, und Prozess #1 gelangt in seinen kritischen Abschnitt.
Wird Prozess #0 indessen neu gestartet, setzt er turn
wieder auf 1
und muss warten, bis Prozess #1 seinen kritischen Abschnitt verlassen hat.
[Bearbeiten] Bedeutung
Der Peterson-Algorithmus ist simpler als der Dekker-Algorithmus, der das Problem des wechselseitigen Ausschlusses ebenfalls löst. Dennoch erbt er den bedeutenden Nachteil der dezentralen Steuerung: Wartende Prozesse geben den Prozessor nicht ab, sondern beanspruchen ihn durch Busy waiting.
Es ist möglich, den Peterson-Algorithmus zu verallgemeinern, so dass das Problem des wechselseitigen Ausschlusses von n parallelen Prozessen gelöst werden kann.