Theorie

N Prozesse sind in einem Deadlock, wenn sie Ressourcen halten und gleichzeitig auf Ressourcen warten, die von anderen Prozessen der Gruppe gehalten werden.

—> zyklische Wartebeziehung

• Gemeinsame Ressourcen mit exklusiver Nutzung eines Prozesses (mutual exclusion)

• Prozesse benötigen mehrere Ressourcen gleichzeitig (hold and wait)

• Keine vorzeitige Freigabe von bereits zugewiesenen Ressourcen (no preemption)

• Zirkuläre Wartezeit zwischen den Prozessen (circular wait)

1. Deadlocks ignorieren (Vogel-Strauß-Verfahren):

   • Deadlocks werden ignoriert oder manuell vom Benutzer gelöst.

     —> dabei kann es zu einem "Watchdog" kommen welcher gelegentlich ein System-Reset auslösen kann.

     —> Problematisch, aber in bestimmten Fällen sinnvoll.

2. Deadlocks erkennen (aber nicht automatisch lösen):

   • Die Anwendung erhält eine Fehlermeldung bei einem erkannten Deadlock.

     —> Keine automatische Lösung, erfordert manuellen Eingriff.

3. Deadlocks verhindern:

   • Konstruktive Vorsichtsmaßnahmen bei der Anforderung von Ressourcen.

     —> Teil der Programmentwicklung, um potenzielle Deadlocks zu vermeiden.

4. Deadlocks vermeiden:

   • Anpassung der Ressourcenanforderungsstrategie an die spezifische Situation.

     —> Laufzeitverhalten wird berücksichtigt, um Deadlocks zu vermeiden.

·        Erkennen von Zyklen im durch die Wartebeziehungen

aufgespannten Graph

·        Tiefensuche oder Breitensuche (Algo. & Daten.)

—> 1 erkannter Zyklus im Graph = Deadlock im System

Strategie: Alle Ressourcen gleichzeitig anfordern

Vorteile:

• Verhindert Deadlocks

• Einfacher Algorithmus

Nachteile:

• Anwendung muss alle Ressourcen, die sie irgendwann benötigt, im Voraus kennen

• Ressourcen werden möglicherweise ineffizient genutzt, da sie bereits am Anfang belegt werden, auch wenn sie erst später benötigt werden

Beispiel (Speisende Philosophen):

• Extremfall: Philosoph fordert zum Essen ALLE Gabeln gleichzeitig an und gibt sie danach alle wieder ab

• Verbesserung: Philosoph fordert kurzzeitig ALLE Gabeln nur für das Aufnehmen seiner beiden Gabeln an

• Noch bessere Variante: Philosoph prüft zuerst, ob BEIDE Gabeln frei sind

  • Wenn ja, nimmt er sich beide Gabeln und isst

  • Wenn nein, wartet er, bis beide Gabeln frei sind

Ziel: Durch gleichzeitiges Anfordern aller Ressourcen wird ein Deadlock vermieden, erfordert jedoch Kenntnisse über alle benötigten Ressourcen im Voraus. Verbesserungen können erreicht werden, indem nur die unmittelbar benötigten Ressourcen angefordert werden oder die Verfügbarkeit vor der Anforderung überprüft wird.

Alternative Methode: Ressourcen durchnummerieren und in aufsteigender Reihenfolge anfordern

Vorteil:

• Verhindert Deadlocks

• Einfacher Algorithmus

Nachteil:

• Anwendung muss so strukturiert sein, dass sie Ressourcen in dieser festgelegten Reihenfolge anfordern kann

• Nachträgliche Ressourcenanforderungen sind möglicherweise nicht möglich oder erfordern eine Neustrukturierung der Anwendung

Beispiel (Speisende Philosophen): Die Gabeln werden entsprechend ihrer Ordnungsnummer angefordert.

P0: Gabel 0, Gabel 1; P1: Gabel 1, Gabel 2; P2: Gabel 2, Gabel 3; P3: Gabel 3, Gabel 4; P4: Gabel 0, Gabel 4;

Ziel: Durch das Durchnummerieren und die aufsteigende Reihenfolge der Ressourcenanforderungen wird ein Deadlock vermieden. Die Anwendung muss jedoch entsprechend strukturiert sein, um die Anforderungen in der festgelegten Reihenfolge zu erfüllen.

Gegenseitigen Ausschluss unnötig machen durch Spooling:

• Betriebsmittel X wird einem speziellen Prozess als "Server" zugewiesen, der die Kontrolle darüber hat.

• Alle Zugriffe auf Betriebsmittel X erfolgen über diesen Spooler.

• Vorteil: Kein Deadlock möglich, solange die Warteschlange des Spoolers ausreichend groß ist.

• Nachteil: Die Methode ist nur begrenzt einsetzbar, z. B. für bestimmte Betriebsmittel wie Drucker. Nicht für alle Betriebsmittel geeignet.

Ziel: Durch die Verwendung eines Spoolers als Vermittler für den Zugriff auf ein Betriebsmittel kann der gegenseitige Ausschluss unnötig gemacht werden, was Deadlocks verhindert. Diese Methode ist jedoch nur für spezifische Betriebsmittel und Anwendungsfälle geeignet.

Hierarchische Verwendung von Synchronisationstypen:

• Synchronisationstypen werden hierarchisch eingesetzt, um Deadlocks zu vermeiden.

• Beispiel:

  • Auf der untersten Ebene gibt es kritische Abschnitte für grundlegende Funktionen des Programms mit kurzen Sperrzeiten, die nicht blockieren.

  • Möglicherweise gibt es mehrere Ebenen von kritischen Abschnitten, die nur in einer bestimmten Reihenfolge angefordert werden dürfen. Zum Beispiel eine kritische Region (CB) zur Modifizierung eines Kontrollblocks CB, über der eine kritische Region (Func) liegt, die Basisoperationen aufruft. Alle CB-Abschnitte werden nur von Func-Aufrufen verwendet.

  • Auf einer höheren Ebene werden Semaphor-Operationen verwendet, um Blockierungen bei leeren Puffern oder ähnlichen Situationen zu ermöglichen.

  • Wichtig ist jedoch, dass ein Semaphor nicht aufgerufen wird, während sich der Code in einem der kritischen Abschnitte befindet.

• Strukturierte Programmierung, Synchronisationsarchitektur und Sperrkonzepte sind allgemein wichtig.

Ziel: Durch die hierarchische Anwendung von Synchronisationstypen und die Strukturierung des Programmcodes werden Deadlocks vermieden. Wichtige Konzepte sind die Synchronisationsarchitektur und das Sperrkonzept.

Sicherheitsreserven-Strategie zur Vermeidung von Deadlocks:

• Grundidee: Bei jeder neuen Ressourcenanforderung eines Prozesses wird der Zustand danach überprüft, um sicherzustellen, dass kein Deadlock entsteht.

• Sicherer Zustand: Es existiert mindestens eine Scheduling-Reihenfolge, die selbst dann keinen Deadlock verursacht, wenn alle anderen Prozesse sofort ihre maximale Anzahl an Ressourcen anfordern.

• Unsicherer Zustand: Wenn alle Prozesse sofort ihre maximale Anzahl an Ressourcen anfordern würden, würde ein Deadlock entstehen.

• Es wird eine konservative Strategie verfolgt, indem Sicherheitsreserven eingehalten werden.

• Der Betriebsmittelgraph wird basierend auf der aktuellen Situation verwendet, um Vorhersagen zu treffen.

• Vorteile: Vermeidet Deadlocks, vermeidet die vorzeitige Zuweisung aller Ressourcen.

• Nachteil: Die Gesamtmenge der Ressourcenanforderungen muss bekannt sein.

Ziel: Durch die Anwendung der Sicherheitsreserven-Strategie wird sichergestellt, dass keine Deadlocks entstehen, während gleichzeitig die Ressourcenzuweisung effizient gehandhabt wird. Die Strategie erfordert jedoch Kenntnisse über die Gesamtmenge der Ressourcenanforderungen.

Dateisystem A (verkettete Liste ohne Tabelle): Anzahl der Blöcke = ceil(Dateigröße / Blockgröße)

Dateisystem B (verkettete Liste mit Tabelle): Anzahl der Blöcke = ceil(Dateigröße / Blockgröße) + 1

Erklärung:

• In Dateisystem A wird die Dateigröße durch die Blockgröße geteilt und auf die nächsthöhere ganze Zahl aufgerundet, um die Anzahl der Blöcke zu erhalten.

• In Dateisystem B wird ebenfalls die Dateigröße durch die Blockgröße geteilt und aufgerundet. Zusätzlich wird ein Block für die Tabelle hinzugefügt, um die Gesamtanzahl der Blöcke zu erhalten.