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 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 ausschließen.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 && (turn1)) {} // busy waiting
0)) {} // busy waiting
//
flag0 = false;
// ...
// Prozess #1
// ...
flag1 = true;
turn = 0;
while (flag0 && (turn
//
flag1 = false;
// ...
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.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:
//initialisieren
flag[i]:= false;
flag[j]:= false;
Prozess Pi
loop
flag[i]:= true;
turn :=j;
while(flag[j] && turn == j){}
flag[i]:=false;
end loop
