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 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.


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 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… …   Deutsch Wikipedia

  • Dekker-Algorithmus — Der Dekker Algorithmus (nach Theodorus Dekker) ist wie der Peterson Algorithmus eine vollständige Lösung des Problems, den wechselseitigen Ausschluss (Mutex) in der dezentralen Steuerung von Prozessen (Prozesssynchronisation) zu gewährleisten. Er …   Deutsch Wikipedia

  • Vernetztes System — Ein Verteiltes System ist nach der Definition von Andrew Tanenbaum ein Zusammenschluss unabhängiger Computer, der sich für den Benutzer als ein einzelnes System präsentiert. Peter Löhr definiert es etwas grundlegender als „eine Menge… …   Deutsch Wikipedia

  • Verteilte Systeme — Ein Verteiltes System ist nach der Definition von Andrew Tanenbaum ein Zusammenschluss unabhängiger Computer, der sich für den Benutzer als ein einzelnes System präsentiert. Peter Löhr definiert es etwas grundlegender als „eine Menge… …   Deutsch Wikipedia

  • Dining philosophers problem — Aufbau des Philosophenproblems Es handelt sich bei dem Philosophenproblem (engl. Dining Philosophers Problem) um ein Fallbeispiel aus dem Bereich der Theoretischen Informatik. Dabei soll das Problem der Nebenläufigkeit erklärt werden, und die… …   Deutsch Wikipedia

  • Speisende Philosophen — Aufbau des Philosophenproblems Es handelt sich bei dem Philosophenproblem (engl. Dining Philosophers Problem) um ein Fallbeispiel aus dem Bereich der Theoretischen Informatik. Dabei soll das Problem der Nebenläufigkeit erklärt werden, und die… …   Deutsch Wikipedia

  • Verteiltes System — Ein Verteiltes System ist nach der Definition von Andrew Tanenbaum ein Zusammenschluss unabhängiger Computer, der sich für den Benutzer als ein einzelnes System präsentiert. Peter Löhr definiert es etwas grundlegender als „eine Menge… …   Deutsch Wikipedia

  • Gegenseitiger Ausschluss — Der Begriff Wechselseitiger Ausschluss bzw. Mutex (Abk. für engl. mutual exclusion, auf deutsch etwa wechselseitiger Ausschluss) bezeichnet eine Gruppe von Verfahren, mit denen das Problem des kritischen Abschnitts gelöst wird. Mutex Verfahren… …   Deutsch Wikipedia

  • Wechselseitiger Ausschluss — Der Begriff Wechselseitiger Ausschluss bzw. Mutex (Abk. für engl. mutual exclusion, auf deutsch etwa wechselseitiger Ausschluss) bezeichnet eine Gruppe von Verfahren, mit denen das Problem des kritischen Abschnitts gelöst wird. Mutex Verfahren… …   Deutsch Wikipedia

  • Sequenzialisierung — Unter Sequentialisierung oder Sequenzialisierung versteht man das Schaffen einer Ordnung für eine Menge von Aktionen entlang der Kausalordnung, die z. B. durch einen Funktionsbaum gegeben ist. Der Sinn ist es, eine Reihenfolge zu finden, in der… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”