Peterson-Algorithmus: Wechselseitiger Ausschluss für zwei Prozesse

Der Peterson-Algorithmus (auch Petersons Lösung, 1981 von Gary L. Peterson veröffentlicht) ist ein klassischer Algorithmus der parallelen Programmierung. Der kritische Abschnitt ist für genau zwei Prozesse oder Threads gesichert – allein mit gewöhnlichem gemeinsamen Speicher, also ohne besondere Hardware-Anweisungen.

Idee: Zwei Flaggen und eine Zugriffs-Variable

Der Algorithmus verwaltet zwei Arrays von Booleans (flag[0], flag[1]) und eine Variable turn. flag[i] zeigt an, dass Prozess i den kritischen Abschnitt betreten möchte. turn entscheidet im Konfliktfall, wer zuerst dran ist – das macht das Verfahren fair: Kein Prozess wartet unbegrenzt (Bounded Waiting).

// Prozess i (0 oder 1), j = der jeweils andere Prozess
flag[i] = true;
turn = j;
while (flag[j] && turn == j) {
    // aktiv warten (Busy Waiting)
}
// kritischer Abschnitt
// ...
flag[i] = false; // fertig

Der Algorithmus erfüllt die drei klassischen Anforderungen: Mutual Exclusion (höchstens ein Prozess im kritischen Abschnitt), Progress (wenn der Abschnitt frei ist, kommt ein wartender Prozess hinein) und Bounded Waiting (kein Prozess wird verhungern). Ohne besondere Hardware-Anweisungen entsteht dabei keine Race Condition. Der Algorithmus zeigt die Grundidee, auf der heutige atomare Operationen aufbauen, und ist eine Vereinfachung des älteren Dekker-Algorithmus.

Grenzen in der Praxis

• Zwei Teilnehmer: Die Grundform funktioniert nur für genau zwei Prozesse. Eine Verallgemeinerung auf N Prozesse ist möglich, wird aber schnell komplex.
• Aktives Warten: Der wartende Prozess dreht in einer Schleife und verbrennt damit CPU-Zeit – ein klassisches Busy Waiting. Moderne Alternativen wie Mutex oder eine Bedingungsvariable blockieren den Thread stattdessen.
• Speichermodell: Auf heutigen Prozessoren und mit optimierenden Compilern müssen die Variablen als volatile/atomar deklariert oder durch Memory Barriers geschützt werden, sonst kann die Hardware Zugriffe umsortieren und der Beweis bricht.

Bedeutung

Der Peterson-Algorithmus ist bis heute ein wichtiges Lehrbuchbeispiel: Er zeigt, dass gegenseitiger Ausschluss allein mit elementaren Speicheroperationen konstruierbar ist. In der Praxis verwenden Betriebssysteme und Laufzeiten aber sperrende Primitive wie ein Spinlock oder echte Mutexe – der Peterson-Algorithmus liefert dafür das konzeptionelle Fundament und die Grundlage für Thread-Sicherheit in modernen Synchronisationsbausteinen.

Verwandte Grundlagen: Nebenläufigkeit, Livelock, Deadlock.