Peterson-Algorithmus

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 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 && (turn == 1)) {} // busy waiting
// <kritischer Abschnitt>
flag0 = false;
// ...

// Prozess #1
// ...
flag1 = true;
turn = 0;
while (flag0 && (turn == 0)) {} // busy waiting
// <kritischer Abschnitt>
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.