Peterson-Algorithmus - LinkFang.de





Algorithmus von Peterson

(Weitergeleitet von: Algorithmus_von_Peterson)

Der Algorithmus von Peterson 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[1] und 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.

Ablaufschema

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

#define FALSE 0
#define TRUE 1
#define N 2 // Anzahl der Prozesse
 
int turn; // Gibt an, wer gerade an der Reihe ist
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

Einzelnachweise

  1. G. L. Peterson: "Myths About the Mutual Exclusion Problem", Information Processing Letters 12(3) 1981, 115–116
  2. Andrew S. Tanenbaum: Moderne Betriebssysteme. 3., aktualisierte Auflage. Pearson Studium, ISBN 978-3-8273-7342-7

Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Algorithmus von Peterson (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.