Peterson-Algorithmus

Der Peterson-Algorithmus (benannt nach seinem Erfinder: Larry Peterson) ist ein Algorithmus, womit die zentrale Steuerung von Prozessen (Prozessynchronisation) gewährleistet ist. Der Sinn dieses Algorithmus ist, dass sich in der kritischen Section nur ein Prozess befindet. Möchte jetzt ein anderer Prozess auch in die kritischen Section, wird er ausgeschlossen und muss warten.

Pseudo C-Code des Algorithmus:

// globale Variablen
boolean flag1 = false, flag2 = false;
int turn;

// Prozess 1
// ...
flag1 = true;
turn = 1;
while (flag2 && (turn == 1)) {} // busy waiting
// <<kritischer Abschnitt>>
flag1 = false;
// ...

// Prozess 2
// ...
flag2 = true;
turn = 0;
while (flag1 && (turn == 0)) {} // busy waiting
// <<kritischer Abschnitt>>
flag1 = false;
// ...

Funktionsweise:

Der Algorithmus arbeitet mit drei Variablen, die zuerst deklariert werden. Zwei Variablen flag1 und flag2 wird der boolische Wert "false" zugewiesen. Wenn jetzt der erste Prozess 1 startet, wird flag1 auf true und turn auf 1 gesetzt. Somit ist die Bedingung in der while Schleife nicht erfüllt und der Prozess 1 kann in die kritische Section wandern. Sollte jetzt der Prozess 2 aktiv werden, während Prozess 1 sich in der kritischen Section befindet, wird flag2 auf true und turn auf 0 gesetzt. Die Bedingung in der while-Schleife ist erfüllt, weil im Prozess 1 flag1 auf true schon gesetzt wurde. Den Prozess 2 wird der Zugriff auf der kritischen Section verweigert und er muss warten. Erst wenn Prozess 1 die kritische Section verlässt, wird flag1 auf false gesetzt und Prozess 2 kann in die kritische Section.

Ein anderer, aber ein bisschen komplexer Algorithmus, der auch das Problem löst ist der Dekker-Algorithmus.