Algorithmus von Peterson

Der Algorithmus von Peterson (auch bekannt als die kanadischen Prozesse) ist eine Lösung des Problems des wechselseitigen Ausschlusses (Mutex) in der dezentralen Steuerung von Prozessen (Prozesssynchronisation). Er wurde 1981 von Gary L. Peterson formuliert und gewährleistet, dass stets nur ein Prozess in einen kritischen Abschnitt gelangen kann (Sequentialisierung). In der hier beschriebenen Form kann er nur 2 Prozesse wechselseitig ausschließen.

Ablaufschema

In C-Code kann der Algorithmus von Peterson wie folgt dargestellt werden:

#define FALSE 0
#define TRUE 1
#define N 2 // Anzahl der Prozesse

volatile int turn; // Gibt an, wer gerade an der Reihe ist
volatile int interested[N]; // Alle Werte mit 0 (FALSE) initialisieren

void enter_region(int process)
{
  int other; // Prozessnummer des anderen Prozesses
  other = 1 - process; // Der andere Prozess
  interested[process] = TRUE; // Interesse zeigen
  turn = other; // Flag setzen

  while (interested[other] == TRUE && turn == other); // Leeranweisung (Aktives Warten)
}

void leave_region(int process) // Prozess, der die kritische Region verlässt
{
  interested[process] = FALSE; // Zeigt den Ausstieg aus dem kritischen Bereich an
}

Funktionsweise

Bevor eine kritische Region betreten wird, ruft jeder Prozess enter_region(int process) mit seiner eigenen Prozessnummer, 0 oder 1, als Parameter auf. Der Eintritt in die kritische Region wird damit so lange verzögert, bis er sicher ist. Sobald ein Prozess die kritische Region wieder verlässt ruft er leave_region(int process) mit seiner eigenen Prozessnummer als Parameter auf. Jetzt kann ein anderer Prozess die kritische Region betreten, sofern er das möchte.

Beispiel 1

1. Es befindet sich kein Prozess in der kritischen Region.
2. Der Prozess mit der Prozessnummer 0 ruft enter_region(int process) mit seiner Prozessnummer 0 als Parameter auf.
3. Durch das Setzen von interested[process] = TRUE, wobei process = 0, zeigt dieser Prozess sein Interesse an, die kritische Region zu betreten.
4. Mittels turn = other gibt er dem anderen Prozess die Gelegenheit, bei Interesse die kritische Region zu betreten.
5. Da der Prozess mit der Prozessnummer 1 nicht interessiert ist, die kritische Region zu betreten, kehrt die Funktion enter_region(int process) ohne das Ausführen der while-Schleife sofort zurück. Damit betritt der Prozess mit der Prozessnummer 0 die kritische Region.
6. Bekundet der Prozess mit der Prozessnummer 1 jetzt Interesse daran, die kritische Region zu betreten, muss er so lange warten, bis der Prozess mit der Prozessnummer 0 leave_region(int process) mit seiner eigenen Prozessnummer als Parameter aufruft, um die kritische Region zu verlassen.

Beispiel 2

1. Zwei Prozesse rufen fast gleichzeitig enter_region(int process) mit ihren Prozessnummern als Parameter auf. Somit werden beide Komponenten des interested-Array auf TRUE gesetzt.
2. Einer der beiden Prozesse (sagen wir, der Prozess mit der Prozessnummer 1) speichert den Wert der Variable turn als letzter und setzt ihn somit auf 0 (turn = other).
3. Der Prozess mit der Prozessnummer 0 führt somit die while-Schleife nicht aus und retourniert sofort.
4. Der Prozess mit der Prozessnummer 0 betritt die kritische Region.
5. Der Prozess mit der Prozessnummer 1 muss nun warten, da sowohl interested[other] auf TRUE steht, als auch turn = other. Er wartet so lange, bis der Prozess mit der Prozessnummer 0 leave_region(int process) aufgerufen hat, seine interested-Komponente zurück auf FALSE setzt, und die kritische Region somit wieder 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 Aktives Warten.

Gebraucht wird ein Algorithmus wie der Peterson-Algorithmus eigentlich nur zur Realisierung von wechselseitigem Ausschluss auf einem Computersystem mit zwei Prozessoren, die keine Instruktion wie Test-and-set oder Compare-and-swap haben. Heutige Prozessoren haben dies aber normalerweise. In einer Hochsprache benutzt man ausschließlich vorhandene Sprachelemente wie Semaphore oder Methoden und Anweisungsfolgen, die als "synchronized" deklariert werden. Dies hat den Vorteil, dass ein wartender Thread blockiert, d. h. den Prozessor für andere Aufgaben freigibt.

Es ist möglich, den Peterson-Algorithmus zu verallgemeinern, so dass das Problem des wechselseitigen Ausschlusses von n parallelen Prozessen gelöst werden kann.

Siehe auch

• Dekker-Algorithmus