Deadlocks und Prozesssynchronisation in Betriebssystemen

Parbegin und Parend: Parallele Ausführung

Parbegin / Parend ist eine Struktur, die dazu dient, Parallelen zu definieren. Sie zeigt den Beginn und das Ende einer parallelen Ausführung an. Auswahl:

• Eine Erklärung, dass die sequenzielle Ausführung zwischen mehreren parallelen Ausführungs-Streams geteilt werden muss.

Seine allgemeine Form (nach Dijkstra) folgt:

parbegin Proposition 1; Proposition 2; ... Proposition n; parend

Mutex: Gegenseitiger Ausschluss

Mutex (Mutual Exclusion) tritt auf, wenn jeder Prozess den Datenaustausch anderer Prozesse verhindert, indem er den Zugriff für alle anderen gleichzeitig deaktiviert. Dies gilt, wenn ein Prozess auf freigegebene Daten zugreift. Prozesse mit Transaktionen, die nicht im Konflikt stehen, dürfen gleichzeitig fortfahren.

Kritische Abschnitte

Ein kritischer Abschnitt liegt vor, wenn ein Prozess auf freigegebene Daten zugreift. Wenn sich ein Prozess in einem kritischen Abschnitt befindet, gilt:

• Alle anderen Prozesse sind von ihren eigenen kritischen Abschnitten ausgeschlossen.
• Andere Prozesse können die Ausführung außerhalb ihrer kritischen Abschnitte fortsetzen.
• Wenn ein Prozess seinen kritischen Abschnitt verlässt, sollte der nächste wartende Prozess seinen eigenen kritischen Abschnitt betreten dürfen.
• Besonderer Leistungsstatus: Der Prozess hat exklusiven Zugriff auf gemeinsam genutzte Daten; alle anderen Prozesse, die diese Daten benötigen, bleiben in der Warteschleife.
• Ein Programm sollte nicht in seinem kritischen Abschnitt gesperrt werden; kritische Abschnitte müssen sorgfältig codiert werden.
• Nach der Beendigung (freiwillig oder unfreiwillig) muss das Betriebssystem den Mutex freigeben, damit andere Prozesse ihre kritischen Abschnitte betreten können.

Deadlock (Verklemmung)

Ein Deadlock tritt auf, wenn Prozesse auf ein bestimmtes Ereignis warten, das nicht eintritt. In einer Sackgasse befinden sich ein oder mehrere Prozesse in einer blockierten Situation.

Beispiel (PL/I-Stil): REVENGE: PROCEDURE OPTIONS (MAIN TASK); WAIT (EVENT); END REVENGE;

Traffic Deadlock: Ein Beispiel aus dem Straßenverkehr

Der bekannteste Standard im Straßenverkehr ist: An einer Kreuzung von vier Straßen muss das Auto von rechts Vorrang haben. Diese Regel funktioniert bei zwei oder drei Autos. Wenn jedoch vier Autos gleichzeitig ankommen, verzichtet jeder auf das Einfahren, was zu einer Sackgasse führt. Wenn alle die Regeln ignorieren und vorsichtig einfahren, besetzt jedes Auto einen Quadranten (Ressource), kann aber nicht weiterfahren, da die zweite benötigte Ressource bereits besetzt ist. Auch hier liegt ein Deadlock vor.

Deadlock bei einfachen Ressourcen

Viele Blockaden in Betriebssystemen entstehen durch die normale Zurückhaltung von Betriebsmitteln (Ressourcen, die seriell genutzt werden müssen):

• Ressourcen können nur von einem Benutzer gleichzeitig verwendet werden.
• Jeder Prozess wartet darauf, dass der andere eine Ressource freigibt.
• Die gehaltene Ressource wird erst freigestellt, wenn der Benutzer seinen Prozess abschließt.
• Ein Benutzer gibt seine erste Ressource nicht frei, bis er die nächste angeforderte Ressource erhalten hat.
• Es entsteht ein Circular Wait (zyklisches Warten).

Nachweis von Blockaden und unbestimmtes Aufschieben

Nachweis der Blockade: Es wird ermittelt, welche Prozesse und Ressourcen in einem Zyklus blockiert sind. Wenn keine Zyklen vorhanden sind, ist das System nicht gesperrt.

Unbestimmte Zeit verschoben (Starvation): Ein Zustand, in dem ein Prozess aufgrund von Planungsentscheidungen bei der Ressourcenallokation ständig übergangen wird.

Um dies zu vermeiden, nutzt man Aging (Alterung): Die Priorität eines Prozesses wird erhöht, während er auf eine Ressource wartet.

Interlock in Spool-Systemen

Spool-Systeme werden verwendet, um die Systemkapazität zu erhöhen, indem langsame Peripheriegeräte vom Programmablauf entkoppelt werden. Sie sind jedoch anfällig für Deadlocks:

• Ausgaben werden auf einer schnellen Festplatte zwischengespeichert, bis sie gedruckt werden können.
• Mehrere teilweise abgeschlossene Arbeiten, die Druckzeilen generieren, können sich gegenseitig blockieren, wenn der Speicherplatz vor Abschluss gefüllt ist.
• Die Wiederherstellung erfordert oft einen Systemneustart mit Datenverlust.
• Ein weniger drastischer Weg wäre das Löschen einzelner Aufträge, um Platz in der Spool-Datei zu schaffen.
• Das System legt bei der Generierung den Speicherplatz für die Spool-Datei fest.
• Zur Reduzierung der Deadlock-Wahrscheinlichkeit sollte der Speicherplatz deutlich größer als erwartet sein.
• Häufige Lösung: Der Spooler liest keine neuen Arbeiten mehr ein, wenn die Kapazität zu 75 % erschöpft ist.
• Moderne Systeme sind ausgefeilter: Sie beginnen mit dem Drucken, bevor der Auftrag vollständig ist, um Platz freizugeben.
• In vielen Systemen ist der Spool-Speicher dynamisch erweiterbar.

Die vier Bedingungen für einen Deadlock

Nach Coffman, Elphick und Shoshani müssen vier Bedingungen für eine Sackgasse erfüllt sein:

1. Gegenseitiger Ausschluss: Prozesse beanspruchen die alleinige Kontrolle über Ressourcen.
2. Hold and Wait: Prozesse halten Ressourcen und warten gleichzeitig auf zusätzliche Mittel.
3. Keine Preemption (Nicht-Unterbrechbarkeit): Ressourcen können den Prozessen nicht entzogen werden.
4. Circular Wait: Es existiert eine geschlossene Kette von Prozessen, die Ressourcen des jeweils nächsten anfordern.

Deadlock-Erholung

Mehrere Faktoren erschweren die Erholung von einer Sackgasse:

• Es ist oft unklar, ob das System tatsächlich abgestürzt ist.
• Das Suspendieren und spätere Wiederaufnehmen von Prozessen ist kostspielig und erfordert oft manuelle Eingriffe.
• Die Wiederherstellung bei großflächigen Deadlocks erfordert enormen Aufwand.

Priorisierung beim Entfernen von Prozessen

• Blockierte Prozesse haben oft keine klaren Prioritäten, was willkürliche Entscheidungen des Operators erfordert.
• Prioritäten können aufgrund von Fristen (Deadlines) momentan verfälscht sein.
• Die Ermittlung der optimalen Entscheidung zum Entfernen von Prozessen erfordert erheblichen Rechenaufwand.