Aufgabe

Aufgabe zum Vortrag „Verifikationsverfahren für parallele Programme – partielle Korrektheit“
Wechselseitiger Ausschluss: Petersons Algorithmus
Im folgenden betrachten wir Petersons Algorithmus zum wechselseitigen Ausschluss. Zwei Threads
mit gemeinsamen Speicher wollen auf einen kritischen Abschnitt zugreifen. Es soll sich zu jedem
Zeitpunkt maximal ein Thread in diesem Abschnitt befinden.
Das besondere an diesem Algorithmus, dass er keine hardwareseitige Unterstützung (z.B. test-andset-Operationen) benötigt. Die einzig atomare Operation ist ein einzelner Lese- oder Schreibzugriff
im Speicher.
Init:
flag1 = false;
flag2 = false;
start(Thread 1);
start(Thread 2);
Thread 1:
while (true) {
Thread 2:
while (true) {
// nicht-kritischer Abschnitt
// nicht-kritischer Abschnitt
flag1 = true;
loser = 1;
while(flag2 && loser == 1) {};
flag2 = true;
loser = 2;
while(flag1 && loser == 2) {};
// kritischer Abschnitt
// kritischer Abschnitt
flag1 = false;
};
flag2 = false;
};
Aufgabe:
Was ist die Bedeutung der gemeinsamen Variablen "flag1", "flag2" und "loser"? Beschreibe die
Funktionsweise des Algorithmus und argumentiere informell, wie der wechselseitige Ausschluss
garantiert wird.
Hinweis: Die Auswertung der Bedingung in der while-Schleife ist nicht atomar! Es kann also
vorkommen, dass in Thread 1 zwischen dem Auswerten von "flag2" und "loser == 1" beliebig viele
Operationen von Thread 2 ausgeführt werden.

Download Report