imported>Fzagoev: Leerzeichen vor Strichpunkt entfernt

2023-05-05T20:15:48Z

Leerzeichen vor Strichpunkt entfernt

Neue Seite

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 [[Prozess (Computer)|Prozessen]] ([[Prozesssynchronisation]]). Er wurde 1981 von [[Gary L. Peterson]] formuliert<ref>G. L. Peterson: "Myths About the Mutual Exclusion Problem", ''Information Processing Letters'' 12(3) 1981, 115–116</ref> und gewährleistet, dass stets nur ein Prozess in einen [[Kritischer Abschnitt|kritischen Abschnitt]] gelangen kann ([[Sequentialisierung]]). In der hier beschriebenen Form kann er nur 2 Prozesse wechselseitig ausschließen.

== Ablaufschema ==
In [[C (Programmiersprache)|C]]-Code kann der Algorithmus von Peterson wie folgt dargestellt werden:<ref>[[Andrew S. Tanenbaum]]: ''Moderne Betriebssysteme''. 3., aktualisierte Auflage. Pearson Studium, ISBN 978-3-8273-7342-7</ref>

<syntaxhighlight lang="c">
#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
}
</syntaxhighlight>

== Funktionsweise ==
Bevor eine kritische Region betreten wird, ruft jeder Prozess <code>enter_region(int process)</code> 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 <code>leave_region(int process)</code> mit seiner eigenen Prozessnummer als Parameter auf. Jetzt kann ein anderer Prozess die kritische Region betreten, sofern er das möchte.

=== Beispiel 1 ===
# Es befindet sich kein Prozess in der kritischen Region.
# Der Prozess mit der Prozessnummer 0 ruft <code>enter_region(int process)</code> mit seiner Prozessnummer 0 als Parameter auf.
# Durch das Setzen von <code>interested[process] = TRUE</code>, wobei <code>process = 0</code>, zeigt dieser Prozess sein Interesse an, die kritische Region zu betreten.
# Mittels <code>turn = other</code> gibt er dem anderen Prozess die Gelegenheit, bei Interesse die kritische Region zu betreten.
# Da der Prozess mit der Prozessnummer 1 nicht interessiert ist, die kritische Region zu betreten, kehrt die Funktion <code>enter_region(int process)</code> ohne das Ausführen der <code>while</code>-Schleife sofort zurück. Damit betritt der Prozess mit der Prozessnummer 0 die kritische Region.
# 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 <code>leave_region(int process)</code> mit seiner eigenen Prozessnummer als Parameter aufruft, um die kritische Region zu verlassen.

=== Beispiel 2 ===
# Zwei Prozesse rufen fast gleichzeitig <code>enter_region(int process)</code> mit ihren Prozessnummern als Parameter auf. Somit werden beide Komponenten des <code>interested</code>-Array auf TRUE gesetzt.
# Einer der beiden Prozesse (sagen wir, der Prozess mit der Prozessnummer 1) speichert den Wert der Variable <code>turn</code> als letzter und setzt ihn somit auf 0 (<code>turn = other</code>).
# Der Prozess mit der Prozessnummer 0 führt somit die <code>while</code>-Schleife nicht aus und retourniert sofort.
# Der Prozess mit der Prozessnummer 0 betritt die kritische Region.
# Der Prozess mit der Prozessnummer 1 muss nun warten, da sowohl <code>interested[other]</code> auf TRUE steht, als auch <code>turn = other</code>. Er wartet so lange, bis der Prozess mit der Prozessnummer 0 <code>leave_region(int process)</code> aufgerufen hat, seine <code>interested</code>-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 [[Mutex|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 [[Semaphor (Informatik)|Semaphore]] oder Methoden und Anweisungsfolgen, die als "synchronized" deklariert werden. Dies hat den Vorteil, dass ein wartender [[Thread (Informatik)|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]]

== Einzelnachweise ==
<references />

[[Kategorie:Algorithmus|Peterson]]
[[Kategorie:Betriebssystemtheorie]]

Algorithmus von Peterson - Versionsgeschichte

imported>Fzagoev: Leerzeichen vor Strichpunkt entfernt