OS_04

Permanentes Blockieren einer Menge von Prozessen, die um Ressourcen konkurrieren oder miteinander kommunizieren

• Zyklischer Ressourcenkonflikt zwischen zwei oder mehreren Prozessen

• Es gibt keine universelle Lösung des Problems

Die drei Voraussetzungen des Systems:

1. Mutual Exclusion

   – exklusiver Zugriff auf Ressourcen

2. Hold and Wait

   – Prozess kann Ressourcen halten, während er auf andere Ressourcen wartet

3. No Preemption

   – zugewiesene Ressourcen werden den Prozessen nicht weggenommen

Auftreten einer bestimmten Ereignisfolge:

1. Circular Wait

   – Geschlossene Kette von Prozessen, von denen jeder Prozess mindestens eine Ressource hält, die von einem anderen Prozess benötigt wird

Wenn Bedingungen 1 bis 3 gelten, kann es nicht aufgelöst werden.

Folge => Deadlock

• Deadlock Prevention

• Deadlock Avoidance

• Deadlock Detection

Das verhindern einer der 4 Deadlock-Bedingungen:

-> Betriebssystemdesign, das Deadlocks ausschließt

Ressourcenreservierungen, die zu Deadlock führen könnten, werden nicht gewährt

• Ressourcenanforderungen werden immer gewährt, sofern Ressourcen vorhanden sind

• Periodisches Überprüfen, ob ein Deadlock vorliegt und ggf. Recovery

Indirect Deadlock Prevention:

• Verhinderung einer der Bedingungen 1 bis 3

Direct Deadlock Prevention:

• Verhinderung des Circular Wait

• Mutual Exclusion

• Hold and Wait

• No Preemption

Sie kann nicht unterbunden werden

• Prozesse fordern alle Ressourcen auf einmal an

• Blockieren, bis alle Ressourcen vorhanden sind

➭ Lange Verzögerungen der Prozesse möglich

➭ Schlechte Nutzung allokierter Ressourcen

➭ Prozess braucht Wissen über Ressourcen, die er verwenden wird

1. Prozess gibt Ressourcen frei, wenn er eine weitere Ressource nicht bekommt.

   -> fordert Ressourcen zu einem späteren Zeitpunkt wieder an

2. Anforderung eines Prozesses führt dazu, dass ein anderer Prozess Ressourcen freigeben muss

(Anwendbar für Ressourcen, deren Zustand leicht gespeichert und später wieder hergestellt werden kann (z.B. Prozessor, beim Blockieren bei wait))

1. Strikte lineare Ordnung O für Ressourcenarten

   z.B. O(Tape Drives) = 2, O(Disk Drives) = 4

2. Erste Anforderung: Prozess fordert eine Anzahl von Ressourcen der Art Ri an (alle müssen in einem Schritt angefordert werden)

3. In der Folge werden für den Prozess nur Anforderungen von Ressourcen der Art Rk mit O(Rk) > O(Ri) zugelassen

ein Prozess wird nicht gestartet, wenn seine Anforderungen zu einem Deadlock führen könnten, d.h wenn:

eine Ressourcenanforderung eines Prozesses wird verwehrt, wenn dadurch ein Deadlock entstehen könnte

Ressourcenbedarf der Prozesse muss bekannt sein

Annahme, dass alle Prozesse ihre Ressourcen gleichzeitig anfordern

=> Einschränkung der Parallelität

Eine Ressourcenbelegung der Prozesse, charakterisiert durch Vektoren u. Matrizen

Safe State:

es existiert eine Folge von Schritten, mit der der Algorithmus alle Prozesse als “finished” markiert in den Endzustand bringt.

Unsafe State:

es existiert keine solche Schrittfolge.

Mit Tests, ob aktuelle Ressourcenanforderungen Q_ki von Prozess Pk erfüllt werden sollen:

Ressourcenanforderungen werden immer gewährt, sofern Ressourcen vorhanden sind

(Deadlocküberprüfung z.B. bei jeder Ressourcenanforderung => CPU-intensiv)

Vo der Optimistischen Annahme, dass Prozesse keine zusätzlichen Ressourcen für ihre Fertigstellung benötigen

• Wenn diese Annahme nicht stimmt, kann es später zu einem Deadlock kommen

• dieser Deadlock wird beim nächsten Aufruf des Deadlock Detection Algorithmus erkannt

• Abbrechen aller betroffenen Prozesse (häufig angewandte Strategie)

• Rollback aller beteiligten Prozesse bis zu einem definierten Aufsetzpunkt (Deadlock kann sich wiederholen)

• Abbrechen einzelner beteiligter Prozesse, solange bis der Deadlock beseitigt ist (wiederholtes Aufrufen des Detection Alg.)

• Ressourcen werden Prozessen schrittweise entzogen und an andere Prozesse vergeben, bis kein Deadlock mehr vorliegt