RW-Systemarchitektur Kap. 101

Kapitel 10Nebenläufigkeit und

wechselseitiger Ausschluss

RW-Systemarchitektur Kap. 102

Überblick Betriebssysteme6 Einführung

7 Prozesse, Fäden (threads), Scheduling

8. Speicherverwaltung

9 Dateisysteme

10 Nebenläufigkeit und wechselseitiger Ausschluss

10.1 Softwarelösungen für wechselseitigen Ausschluss

10.2 Wechselseitiger Ausschluss in Hardware

10.3 Wechselseitiger Ausschluss ins Betriebssystem integriert

11 Deadlocks

12 historisches

13 aktuelle Forschung

RW-Systemarchitektur Kap. 103

Nebenläufigkeit

• Größere Softwaresysteme sind häufig realisiert als eine Menge von nebenläufigen Prozessen.

• Nebenläufigkeit = „potentieller Parallelismus“– Nebenläufige Prozesses können parallel auf mehreren Prozessoren ausgeführt

werden.– Sie können aber auch „pseudo-parallel“ auf einem Prozessor ausgeführt werden.

• Grundlegende Fragestellungen:– Zugriff auf gemeinsame Ressourcen?– Koordination, Kommunikation

• Bei Zugriff auf gemeinsame Ressourcen muss häufig exklusiver Zugriff durch wechselseitiger Ausschluss garantiert werden!

• Hier:– Softwarelösungen– Hardware-Lösungen– Integration ins Betriebssystem

RW-Systemarchitektur Kap. 104

Ein einfaches Beispiel

Annahme: 2 Threads führen (u.a.) diesen Code aus.• Threads haben einen gemeinsamen Adressraum.

) Variable chin ist eine gemeinsame Ressource!Mögliche Ausführungsreihenfolge:

– Thread 1 liest Zeichen, wird unterbrochen ) Thread 2 – Thread 2 führt Prozedur komplett aus.– Thread 1 führt Rest der Prozedur aus.

void echo(){

chin = getchar(); /* Zeichen einlesen, speichern in Variable chin

*/putchar (chin);

/* Zeichen ausgeben */}

Problem: Semantik verändert sich mit dem Thread-Schedule!

Unterbrechung hat Effekt auf gemeinsame Variable.

RW-Systemarchitektur Kap. 105

Produzenten-Konsumenten-Problem

• Paradigma für kooperierende Prozesse:

• Prozess producer produziert Information, welche von einem Prozess consumer konsumiert wird.

• Zwischen producer und consumer gibt es einen zyklischen Puffer buffer fester Größe.

Gemeinsamer Puffer

#define BUFFER_SIZE 10

typedef struct {

. . .

} item;

item buffer[BUFFER_SIZE];

int in = 0;

int out = 0;

RW-Systemarchitektur Kap. 106

Beschränkter Puffer – Insert() und Remove()

while (true) { /* Produziere ein Element */

while (((in = (in + 1) % BUFFER_SIZE) == out) ; /* do nothing -- no free buffers */

buffer[in] = item; in = (in + 1) % BUFFER SIZE; }

while (true) { while (in == out) ; /* tue nichts – nichts im

Puffer */ /* entferne ein Element aus

Puffer */ item = buffer[out]; out = (out + 1) % BUFFER SIZE;return item;

}

buffer

in out

producer consumer

RW-Systemarchitektur Kap. 107

Produzent-Konsument mit beschränktem Puffer – Was geht schief?

• Geschwindigkeit Produzent > Geschwindigkeit Konsument Pufferinhalte werden überschrieben.

• Geschwindigkeit Produzent < Geschwindigkeit Konsument Konsument liest leere Pufferfelder

• Korrektheit hängt von der relativen Geschwindigkeit der beiden Threads zueinander ab – nur korrekt bei gleicher Geschwindigkeit und „günstiger Initialisierung“.

RW-Systemarchitektur Kap. 109

Nebenläufigkeit

• Grundlegende Fragen bei Nebenläufigkeit:– Betriebssystem muss Ressourcen der aktiven Prozesse verwalten.– Es muss wechselseitigen Ausschluss bei gemeinsamen Ressourcen

garantieren können.– Die Korrektheit des Ergebnisses muss unabhängig von der relativen

Ausführungsgeschwindigkeit der einzelnen Prozesse sein.

• Kontrollprobleme:– Wechselseitiger Ausschluss, d.h. jeweils nur ein Prozess im „kritischen

Abschnitt“ (= der Teil des Programms, der auf gemeinsame, exklusive Ressourcen zugreift)

– Verhindere Deadlocks (Blockierung aller Prozesse)– Verhindere Livelocks (Prozess nicht blockiert, macht aber keinen

Fortschritt).

RW-Systemarchitektur Kap. 1010

Anforderungen an wechselseitigen Ausschluss

1. Höchstens ein Prozess im kritischen Abschnitt.

2. Jeder Prozess hält sich nur endliche Zeit im kritischen Abschnitt auf.

3. Wenn ein Prozess in den kritischen Abschnitt will, so muss er nur endliche Zeit darauf warten.

4. Wenn kein Prozess im kritischen Abschnitt ist, so wird ein interessierter Prozess ohne Verzögerung akzeptiert.

5. Alles funktioniert unabhängig von der relativen Ausführungsgeschwindigkeit der Prozesse.

RW-Systemarchitektur Kap. 1011

10.1 Softwarelösungen für wechselseitigen Ausschluss

• Hier:– 5 verschiedene Lösungsversuche für wechselseitigen

Ausschluss– Analyse der einzelnen Lösungen

• Letzter Versuch entspricht der Lösung von Peterson (1981)

• Lösung von Peterson ist eine Vereinfachung des Algorithmus von Dekker (Anfang der 60er Jahre).

RW-Systemarchitektur Kap. 1012

Versuch 1• Voraussetzung:

– 2 Prozesse konkurrieren um eine Ressource– Gemeinsame Variable turn besagt, wer dran ist.– turn ist mit beliebigem Wert initialisiert.

/* Prozess 0 */repeat { while (turn 0) tue nichts; /* kritischer Abschnitt */ turn := 1; /* nichtkrit. Abschnitt */ }

/* Prozess 1 */repeat { while (turn 1) tue nichts; /* kritischer Abschnitt */ turn := 0; /* nichtkrit. Abschnitt */ }

RW-Systemarchitektur Kap. 1013

Versuch 1: Analyse

• Vorteil:– Wechselseitiger Ausschluss ist garantiert.

• Nachteil:– „Busy waiting“ = aktives Warten

(„while (turn 0) tue nichts;”) ) Verschwendung von Rechenzeit beim Warten

– Nur abwechselnder Zugriff auf kritischen Abschnitt

• Beispiel für kritische Situation:– Prozess 0 ist schnell, Prozess 1 ist langsam (sehr langer nicht-

kritischer Abschnitt)– …– Bedingung 4 ist nicht erfüllt!

RW-Systemarchitektur Kap. 1014

Versuch 2

• Jetzt 2 gemeinsame Variablen zur Kommunikation:– Prozess 0 schreibt auf ready[0], liest beide– Prozess 1 schreibt auf ready[1], liest beide– Bedeutung von ready[i] = true:

Prozess i will in den kritischen Abschnitt– Initialisierung: ready[0] := false; ready[1] := false;

/* Prozess 0 */repeat { while (ready[1] = true) tue nichts; ready[0] := true; /* kritischer Abschnitt */ ready[0] := false; /* nichtkrit. Abschnitt */ }

/* Prozess 1 */repeat { while (ready[0] = true) tue nichts; ready[1] := true; /* kritischer Abschnitt */ ready[1] := false; /* nichtkrit. Abschnitt */ }

RW-Systemarchitektur Kap. 1015

Versuch 2: Analyse

• Vorteil: Auch nicht-alternierender Zugriff auf kritischen Abschnitt

• Nachteile:– „Busy waiting“ („while (ready[i] true) tue nichts;”)

– Wechselseitiger Ausschluss nicht garantiert!!

• Beispiel für Fehlersituation :– ready[0] = ready[1] = false– Prozess 0 schließt Schleife („while (ready[1] true) tue

nichts;”) ab, gibt CPU ab

– Prozess 1 schließt Schleife („while (ready[0] true) tue nichts;”) ab

– Jetzt können beide Prozesse ungehindert den kritischen Abschnitt betreten:• Prozess 1 betritt kritischen Abschnitt, gibt CPU ab• Prozess 0 betritt kritischen Abschnitt

RW-Systemarchitektur Kap. 1016

Versuch 3

• Anforderung des kritischen Abschnittes wird vorgezogen, um das gezeigte Problem zu verhindern:

/* Prozess 0 */repeat { ready[0] := true; while (ready[1] = true) tue nichts; /* kritischer Abschnitt */ ready[0] := false; /* nichtkrit. Abschnitt */ }

/* Prozess 1 */repeat { ready[1] := true; while (ready[0] = true) tue nichts; /* kritischer Abschnitt */ ready[1] := false; /* nichtkrit. Abschnitt */ }

RW-Systemarchitektur Kap. 1017

Versuch 3: Analyse• Vorteil:

– Auch nicht-alternierender Zugriff auf kritischen Abschnitt– Wechselseitiger Ausschluss garantiert!

• Nachteil:– „Busy waiting“ („while (ready[i] true) tue nichts;”)

• Es kann aber trotzdem ein Problem auftreten:– ready[0] = ready[1] = false– Prozess 0 setzt ready[0] := true und gibt CPU ab– Prozess 1 setzt ready[1] := true– Jetzt werden beide Prozesse ihre Schleife

„while (ready[i] true) tue nichts;” nie verlassen!

– Eine solche Situation nennt man Livelock.

RW-Systemarchitektur Kap. 1018

Wechselseitiger Ausschluss

…

• Ergebnis:– Anforderung zu früh ) Livelock

– Anforderung zu spät ) kein wechselseitiger Ausschluss, “kritischer Wettlauf” (race condition)

RW-Systemarchitektur Kap. 1019

4. Versuch• „Nichtstun“ in Schleife wird ersetzt durch zeitweilige

Zurücknahme der Anforderung, um es anderen Prozessen zu erlauben, die Ressource zu belegen:

/* Prozess 0 */repeat { ready[0] := true; while (ready[1] = true) { ready[0] := false; /* zufäll.Verzög. */; ready[0] := true; } /* kritischer Abschnitt */ ready[0] := false; /* nichtkrit. Abschnitt */ }

/* Prozess 1 */repeat { ready[1] := true; while (ready[0] = true) { ready[1] := false; /* zufäll.Verzög. */; ready[1] := true; } /* kritischer Abschnitt */ ready[1] := false; /* nichtkrit. Abschnitt */ }

RW-Systemarchitektur Kap. 1020

Versuch 4: Analyse

• Vorteil:– Auch nicht-alternierender Zugriff auf kritischen Abschnitt– Wegen zufälliger Verzögerung nur geringe Wahrscheinlichkeit für

Deadlock.

• Nachteil:– „Busy waiting“ – Deadlock nach wie vor möglich!– Unsaubere Lösung!– Verhalten ist schlecht vorhersagbar– Es gibt Situationen, in denen

• es nie voran geht oder• es für sehr lange Zeit nicht voran geht

– Nach Beobachtung eines unerwünschten Verhaltens tritt dieses möglicherweise über sehr lange Zeit nicht mehr auf ) kritische Wettläufe (race condition)!

RW-Systemarchitektur Kap. 1021

Versuch 5• 3 gemeinsame Variablen: turn, ready[0], ready[1]• Initialisierung: ready[0] := false; ready[1] := false;

turn beliebig

• Variable turn bestimmt, welcher Prozess dran ist.

/* Prozess 0 */repeat { ready[0] := true; turn := 1; while (ready[1] = true &&

turn = 1) tue nichts; /* kritischer Abschnitt */ ready[0] := false; /* nichtkrit. Abschnitt */ }

/* Prozess 1 */repeat { ready[1] := true; turn := 0; while (ready[0] = true &&

turn = 0) tue nichts; /* kritischer Abschnitt */ ready[1] := false; /* nichtkrit. Abschnitt */ }

RW-Systemarchitektur Kap. 1022

5. Versuch: Analyse (1)• Deadlock:

– Kein Deadlock möglich wegen Variable turn!– turn kann nicht gleichzeitig 0 und 1 sein.

• Wechselseitiger Ausschluss:– Nur einer von beiden interessiert: der andere darf eintreten,– Beide interessiert: der darf eintreten, auf den turn zeigt

• Nicht-alternierender Zugriff:– Möglich, weil ready[i] = false, wenn Prozess i in nicht-kritischem

Abschnitt.

RW-Systemarchitektur Kap. 1023

5. Versuch: Analyse (2)

• Vorteile:– Nicht-alternierender Zugriff auf den kritischen Abschnitt– Wechselseitiger Ausschluss garantiert– Kein Deadlock

• Nachteil:– Aktives Warten

• Versuch 5 entspricht Petersons Algorithmus für wechselseitigen Ausschluss (1981).

• Verallgemeinerbar auf n Prozesse (wesentlich komplizierter!).

RW-Systemarchitektur Kap. 1024

Wechselseitiger Ausschluss in Software – Was haben wir bisher gelernt?

• Wechselseitiger Ausschluss ist in Software schwer zu realisieren.• Alles was einfacher ist als Petersons Algorithmus ist

höchstwahrscheinlich falsch.– Beweise des Gegenteils sind durchaus willkommen …

• Fehler durch kritische Wettläufe, subtile Fehler• Formale Beweise sind unabdingbar!

• Software-Lösungen für wechselseitigen Ausschluss benötigen aktives Warten.

• Effizientere Lösungen sind möglich durch– Hardware-Unterstützung

– Ins Betriebssystem integrierte Lösungen