2.b. Synchronisation - Gegenseitiger Ausschluss

2. Synchronisation

b. Gegenseitiger Ausschluss (mutual exclusion / „mutex“)

Der gegenseitige Ausschluss bezeichnet das wichtigste Problem der Prozesssynchronisierung. Es besagt, dass eine Aktivität A1 eines Prozesses P1 und eine Aktivität A2 von Prozess P2 sich gegenseitig ausschließen, wenn A1 und A2 sich nicht zeitlich überlappen dürfen.
Ein bekanntes Beispiel ist die Kontoführung in einer Bank. Hier wird davon ausgegangen, dass mehrere Bankangestellte gleichzeitig auf die Konten zugreifen, so dass Probleme mit dem zeitlichen Ablauf der Buchungen entstehen können. Z.B.:

Konto 1000 des Kunden X hat einen Kontostand von 1000 €.
Angestellter 1 einer Bank überweist auf dieses Konto einen Betrag von 1000 €. Angestellter 2 derselben Bank bucht zur gleichen Zeit 500 € von dem Konto ab. Bei Nichtbeachtung der Synchronisierungsproblematik würde der neue Kontostand entweder 2000 € oder 500 € lauten, das Ergebnis ist nicht vorhersehbar.

Dieser unterschiedliche Ausgang der Operationen wird auch als „Race Condition“ bezeichnet. Darunter versteht man allgemein die Festlegung, dass ein nebenläufig ausgeführtes Programm immer zu demselben Ergebnis kommen muss, wenn die Vorbedingungen übereinstimmen.
Um ein Auftreten von Race Conditions zu vermeiden, wird das Prinzip des kritischen Abschnittes eingeführt.

Kritischer Abschnitt
Der kritische Abschnitt bezeichnet denjenigen Teil des Programms, bei dem das Programm auf gemeinsam genutzte Variablen schreibend zugreift oder ein bestimmtes Betriebsmittel nutzt.
Ein Beispiel in abstraktem Code für die Verwendung des kritischen Abschnittes und den Problemen, die sich daraus ergeben:

Eine gemeinsam genutzte Variable: int AnDerReihe

AnDerReihe = 1;

Prozess 1:

while (true) {
   while (AnDerReihe == 2) {
      nichts tun;
   }
kritischer Abschnitt1;
AnDerReihe = 2;
…
}

Prozess 2:

while (true) {
   while (AnDerReihe == 1) {
     nichts tun;
   }
kritischer Abschnitt2;
AnDerReihe = 1;
…
}

Es ergeben sich Probleme bei diesem Programm, insofern, dass ein Prozess, der häufig in seinen kritischen Abschnitt eintreten möchte, daran gehindert wird, wenn der andere Prozess diesen Bereich nur sehr selten betritt. Außerdem kann bei unvollständiger Abarbeitung des kritischen Abschnittes der andere Prozess nicht die Arbeit wieder aufnehmen.

Dieser Algorithmus wird verfeinert, so dass jeder Prozess ein eigenes Flag zum Eintritt in den kritischen Bereich erhält.

Flags, ob kritischer Bereich betreten: boolean KAfrei1, KAfrei2 = true;
Prozess 1: while (true) { while (not KAfrei2) { nichts tun; } KAfrei1 = false; kritischer Abschnitt1; KAfrei1 = true; … }	Prozess 2: while (true) { while (not KAfrei1) { nichts tun; } KAfrei2 = false; kritischer Abschnitt2; KAfrei2 = true; … }

Auch diese Lösung kann nicht endgültig sein, da hier die grundlegende Forderung für die Synchronisierung von Prozessen nach nur einem Prozess im kritischen Abschnitt verletzt wird.

Im nächsten Schritt sollen die Prozesse bereits vor der Prüfung auf einen anderen Prozess in seinem kritischen Bereich ihren Wunsch auf Eintritt per Flag setzen. Damit es hier nicht zu einem Deadlock kommt, werden die Prozesse so abgeändert, dass sie einen Moment warten, wenn der andere Prozess seinen kritischen Abschnitt durchläuft.

Flags, ob kritischer Bereich betreten: boolean KAfrei1, KAfrei2 = true;
Prozess 1: while (true) { KAfrei1 = false; while (not KAfrei2) { KAfrei1 = true; einen Moment nichts tun; KAfrei1 = false; } kritischer Abschnitt1; KAfrei1 = true; … }	Prozess 2: while (true) { KAfrei2 = false; while (not KAfrei1) { KAfrei2 = true; einen Moment nichts tun; KAfrei2 = false; } kritischer Abschnitt2; KAfrei2 = true; … }

Dieser Ansatz führt zwar nicht zum Deadlock, dafür aber zu einem weiteren Synchronisierungsproblem, dem Livelock. Der Zustand des Livelock wird auch als „Starvation“, also Aushungern, oder als Aussperrung bezeichnet. Hierbei sind die Prozesse zu „höflich“ bei der Anforderung des Betretens des kritischen Abschnitts, das Kriterium der fairen Verteilung von Ressourcen wird verletzt.

Um auch den Livelock zu eliminieren wird bei dem obigen Ansatz eine Art „Schiedsrichtervariable“ eingeführt, die im Zweifelsfall über den in den kritischen Abschnitt einzutretenden Prozess entscheidet. Den folgenden Algorithmus bezeichnet man auch als „Dekker-Algorithmus“:

Flags, ob kritischer Bereich betreten: boolean KAfrei1, KAfrei2 = true; Schiedsrichtervariable: int AnDerReihe = 1;
Prozess 1: while (true) { KAfrei1 = false; while (not KAfrei2) { if (AnDerReihe == 2) { KAfrei1 = true; while (AnDerReihe == 2) { nichts tun; } KAfrei1 = false; } } kritischer Abschnitt1; AnDerReihe = 2; KAfrei1 = true; … }	Prozess 2: while (true) { KAfrei2 = false; while (not KAfrei1) { if (AnDerReihe == 1) { KAfrei2 = true; while (AnDerReihe == 1) { nichts tun; } KAfrei2 = false; } } kritischer Abschnitt2; AnDerReihe = 1; KAfrei2 = true; … }

Dieser Algorithmus erfüllt alle geforderten Bedingungen, verwendet aber „aktives Warten“ zur Synchronisation. Beim aktiven Warten wird der Prozessor unnötig belastet durch das Überprüfen einer Bedingung. Ein solcher Vorgang wird auch „Busy Waiting“ oder „Spinlock“ genannt.

Eine weitere Variante ist der Peterson-Algorithmus, der das Problem des gegenseitigen Ausschlusses löst, aber dafür ebenfalls aktives Warten verwendet.

Flags, ob kritischer Bereich betreten: boolean KAfrei1, KAfrei2 = true; Schiedsrichtervariable: int AnDerReihe = 1;
Prozess 1: while (true) { KAfrei1 = false; AnDerReihe = 2; while ((AnDerReihe == 2) && (KAfrei2 == true)) { nichts tun; } kritischer Abschnitt1; KAfrei1 = true; }	Prozess 2: while (true) { KAfrei2 = false; AnDerReihe = 1; while ((AnDerReihe == 1) && (KAfrei1 == true)) { nichts tun; } kritischer Abschnitt2; KAfrei2 = true; }