Upload
georg-helbing
View
118
Download
2
Embed Size (px)
Citation preview
RW-Systemarchitekur Kap. 111
Kapitel 11Deadlocks
RW-Systemarchitekur Kap. 112
Überblick Betriebssysteme
6 Einführung
7 Prozesse, Fäden (threads), Scheduling
8. Speicherverwaltung
9 Dateisysteme
10 Nebenläufigkeit und wechselseitiger Ausschluss
11 Deadlocks11.1 Einführung
11.2 Der Bankiers-Algorithmus
11.3 Deadlock-Vermeidung
12 historisches
13 aktuelle Forschung
RW-Systemarchitekur Kap. 113
11.1 Einführung: Deadlocks – die Beteiligten und die Ursachen
• Prozesse brauchen Ressourcen,
• manche Ressourcen exklusiv,
• ein möglicher Ablauf:– Prozess besitzt schon Ressourcen,
– möchte weitere akquirieren
– evtl. im Besitz von pk
– benötigt evtl. auch rJ
– Resultat:
pi rj
rj pi
pi rm
rm pk
pk rjpi
rmrj
pk
RW-Systemarchitekur Kap. 114
Ressourcen und Anforderungsstrategien
Ressourcen• sind exklusiv oder nicht exklusiv – exklusiv erfordert
wechselseitigen Ausschluss beim Zugriff,• sind präemptiv, d.h. können nach Zuteilung entzogen werden,
oder nicht präemptiv,• werden
1. angefordert – sind sie belegt, wird Prozess blockiert,2. benutzt,3. freigegeben
• können auf einmal oder sequentiell nacheinander angefordert werden; geschlossene Anforderung verringert ausgenützten Pseudoparallelismus, führt im Extremfall zu sequentieller Ausführung.
RW-Systemarchitekur Kap. 115
Deadlocks
• Definition: Eine Menge von Prozessen befindet sich in einem Deadlock-Zustand, wenn jeder Prozess aus der Menge auf ein Ereignis wartet, das nur ein anderer Prozess aus der Menge auslösen kann.
• Hier: EreignisFreigabe einerRessource – deshalbRessourcen-Deadlock
12
34
RW-Systemarchitekur Kap. 116
Ein möglicher Deadlock
• Sequentielle Anforderung exklusiver Ressourcen ohne Möglichkeit der Freigabe bereits zugeteilter.
• Hier kann es, muss aber nicht zu einer Deadlock-Situation kommen!
• Hängt ab von der relativen Geschwindigkeit der beiden Prozesse, das nennt man einen kritischen Wettlauf (race condition).
/* Prozess 0 */…Fordere Ressource 1 an…Fordere Ressource 2 an…Benutze beide Ressourcen…
/* Prozess 1 */…Fordere Ressource 2 an…Fordere Ressource 1 an…Benutze beide Ressourcen…
RW-Systemarchitekur Kap. 117
Voraussetzungen für Deadlocks• Folgende Voraussetzungen müssen erfüllt sein, damit ein
Deadlock auftreten kann:1. Wechselseitiger Ausschluss: Jede Ressource ist entweder verfügbar
oder genau einem Prozess zugeordnet.2. Hold-and-wait-Bedingung: Prozesse, die schon Ressourcen
reserviert haben, können noch weitere Ressourcen anfordern.3. Ununterbrechbarkeit: Ressourcen, die einem Prozess bewilligt
wurden, können nicht wieder entzogen werden.4. Zyklische Wartebedingung: Es muss eine zyklische Kette von
Prozessen geben, von denen jeder auf eine Ressource wartet, die dem nächsten Prozess in der Kette gehört.
• Die ersten drei betreffen die BS-Strategie, die letzte beschreibt eine entstandene Situation.
• Leider sind in realen Betriebssystemen diese Bedingungen üblicherweise erfüllt.
RW-Systemarchitekur Kap. 118
Modellierung von Ressourcenbelegungen und Ressourcenanforderungen
• Ressourcenbelegungen und Ressourcenanforderungen können durch einen so genannten Ressourcen-Zuteilungs-Graphen dargestellt werden.
• Es gibt 2 Arten von Knoten:– Kreise repräsentieren Prozesse pi:
– Quadrate repräsentieren Ressourcen rj:
• Eine Kante von einer Ressource rj zu einem Prozess pi bedeutet: Ressource rj wird von Prozess pi belegt.
• Eine Kante von einem Prozess pi zu einer Ressource rj bedeutet: Prozess pi hat Ressource rj angefordert, aber noch nicht erhalten.
pi
rj pi
rj
pi rj
RW-Systemarchitekur Kap. 119
Modellierung von Ressourcenbelegungen und Ressourcenanforderungen
• Ein Zyklus in dem Graphen existiert genau dann, wenn man von einem Knoten ausgehend über eine Folge von Kanten wieder zu dem Knoten zurückkommt:
• Zyklen im Belegungs-Anforderungsgraphen repräsentieren Deadlocks!
p1
r2r1
p2
RW-Systemarchitekur Kap. 1110
Beispiel – Abarbeitungsfolge 1
• Prozesse p1, p2, p3, Ressourcen R, S, T
– Prozess p1: Anforderung R, Anforderung S, Freigabe R, Freigabe S
– Prozess p2: Anforderung S, Anforderung T, Freigabe S, Freigabe T
– Prozess p3: Anforderung T, Anforderung R, Freigabe T, Freigabe R
p1 p2 p3
R S T
1. p1 belegt R.
p1 p2 p3
R S T
2. p2 belegt S.
p1 p2 p3
R S T
3. p3 belegt T.
p1 p2 p3
R S T
4. p1 verlangt S.
p1 p2 p3
R S T
5. p2 verlangt T.
p1 p2 p3
R S T
6. p3 verlangt R.
Deadlock!
RW-Systemarchitekur Kap. 1111
Beispiel – Abarbeitungsfolge 2
• Prozesse p1, p2, p3, Ressourcen R, S, T
– Prozess p1: Anforderung R, Anforderung S, Freigabe R, Freigabe S
– Prozess p2: Anforderung S, Anforderung T, Freigabe S, Freigabe T
– Prozess p3: Anforderung T, Anforderung R, Freigabe T, Freigabe R
p1 p2 p3
R S T
1. p1 belegt R.
p1 p2 p3
R S T
2. p3 belegt T.
p1 p2 p3
R S T
3. p1 belegt S.
p1 p2 p3
R S T
4. p3 verlangt R.
p1 p2 p3
R S T
5. p1 gibt R frei.
p1 p2 p3
R S T
6. p1 gibt S frei.
Kein Deadlock!
RW-Systemarchitekur Kap. 1112
Deadlock-Vermeidung (1)FortschrittProzess p2
FortschrittProzess p1
Drucker
Plotter
Drucker
Plotter
I1 I2 I3 I4
I5
I6
I7
I8
Beide Prozesse beendet
Start
Beide benötigen Drucker
Beide benötigen Plotter
t
Deadlock unvermeidbar!
Was ist ein sicherer Zustand?1. es gibt eine deadlock-freie
Fortsetzung2. alle Fortsetzungen sind
deadlock-frei
RW-Systemarchitekur Kap. 1113
Deadlock-Vermeidung (2)FortschrittProzess p2
FortschrittProzess p1Drucker
Plotter
Drucker
Plotter
I1 I2 I3 I4
I5
I6
I7
I8
Beide Prozesse beendet
Start
Beide benötigen Drucker
Beide benötigen Plotter
t
RW-Systemarchitekur Kap. 1114
11.2 Verhindern von Deadlocks: Bankieralgorithmus
• Bankier-Algorithmus von Dijkstra (1965) verhindert Deadlocks im System.
– Scheduling (Prozessorzuteilung an Prozesse) in einer Weise, dass keine Deadlocks auftreten können.
• Voraussetzungen:– Es ist im voraus bekannt, welche und wie viele Ressourcen die einzelnen
Prozesse (maximal) anfordern werden.– Diese maximale Anforderung übersteigt für keinen Prozess die zur Verfügung
stehenden Ressourcen.• Nach der 2. Voraussetzung gibt es auf jeden Fall einen Ablauf, bei
dem es kein Problem mit fehlenden Ressourcen / Deadlocks gibt:– Führe einfach alle Prozesse nacheinander aus.– Nach Ablauf eines Prozesses gibt dieser sicherlich alle seine Ressourcen frei.
• Grundidee des Bankieralgorithmus:– Versuche möglichst viel „Pseudo-Parallelismus“ zu erreichen (keine streng
sequentielle Abarbeitung der Prozesse)– Riskiere dabei aber an keinem Punkt eine potentielle Deadlock-Situation!
RW-Systemarchitekur Kap. 1115
Bankieralgorithmus (1)
• Vorgehen:– Überführe das System immer nur in sichere Zuteilungs-Zustände! – Ein Zuteilungs-Zustand ist sicher, wenn
• es auf jeden Fall eine deadlockfreie „Restausführung“ aller Prozesse gibt,• d.h. eine Anordnung der Prozesse <P1, P2, …, Pn>, so dass die
Ressourcenanforderungen von Pi mittels der eigenen, der verfügbaren und der von den Pj für j<i belegten befriedigt werden können.
• insbesondere wenn die Prozesse ihre restlichen Anforderungen auf einen Schlag stellen und Freigaben erst bei Prozessbeendigung durchführen.
– Sonst: Zustand ist unsicher.
• Nach Voraussetzung ist der Startzustand sicher!
• Beachte: Ein unsicherer Zustand muss nicht notwendigerweise zu einem Deadlock führen (Überapproximation).
• Worin steckt die Überapproximation?
RW-Systemarchitekur Kap. 1116
Bankieralgorithmus (2)
• Der Bankieralgorithmus – prüft also bei jeder Ressourcenanforderung eines Prozesses p i, ob
das System bei Erfüllung der Anforderung in einen unsicheren Zustand kommt.
– Falls ja: Erfülle Anforderung nicht, stelle Prozess pi zurück und mache mit einem anderen Prozess weiter.
• Dadurch garantiert der Bankieralgorithmus in jedem Fall eine deadlockfreie Ausführung.
RW-Systemarchitekur Kap. 1117
Bankieralgorithmus – Eine einzige Ressourcenklasse (1)
• Noch zu zeigen: Wie wird auf sicheren Zustand geprüft?
• Zunächst:Nehme an, dass es eine einzige Ressourcenklasse gibt, die aber mehrere Ressourcen enthalten kann– Bsp.:
• Es gibt 10 verschiedene Drucker.
• Wenn alle 10 Drucker durch Prozesse belegt sind, dann wird kein weiterer vergeben.
• Ein Prozess kann mehrere Drucker anfordern, aber nur bis zu einer bestimmten Maximalzahl · 10
RW-Systemarchitekur Kap. 1118
Bankieralgorithmus – Eine einzige Ressourcenklasse (2)
Gegeben:• n Prozesse p1, …, pn, die Ressourcen aus einer einzigen Klasse anfordern• Anzahl zur Verfügung stehender Ressourcen: V 2 N• Für jeden Prozess pi gibt es
– eine maximale Anzahl Mi von Ressourcen, die der Prozess anfordern wird,– eine Anzahl von Ressourcen Ei , die der Prozess zu einem bestimmten Zeitpunkt
schon erhalten hat,– eine Anzahl von Ressourcen, die der Prozess nach diesem Zeitpunkt noch maximal
anfordern wird: Ai = Mi - Ei
• Die Anzahl der freien Ressourcen zu diesem Zeitpunkt ergibt sich zu F = V - i=1
n Ei
• Es gilt weiterhin:– Mi · V 81 · i · n– Ei · Mi 81 · i · n
RW-Systemarchitekur Kap. 1119
Bankieralgorithmus – Eine einzige Ressourcenklasse (3)
Beispiel:
• Es gibt V = 10 Instanzen einer Ressource.
• 3 Prozesse p1, p2, p3
• Maximale Anforderungen:
• Zustand zum Zeitpunkt t:
• Frage: Ist dies ein sicherer Zustand?
Mi
p1 9
p2 4
p3 7
Ei Ai
p1 3 6
p2 2 2
p3 2 5
F = 10 – 7 = 3
RW-Systemarchitekur Kap. 1120
Bankieralgorithmus – Eine einzige Ressourcenklasse (4)
Nachweis, dass es sich um einen sicheren Zustand handelt:
F = 10 – 7 = 3
Ei Ai Mi
p1 3 6 9
p2 2 2 4
p3 2 5 7
Führe zunächst ausschließlich Prozess p2 aus
F = 10 – 9 = 1
Ei Ai Mi
p1 3 6 9
p2 4 0 4
p3 2 5 7 F = 10 – 5 = 5
Ei Ai Mi
p1 3 6 9
p2 0 - -
p3 2 5 7
Freigabe durch
Prozess p2
F = 10 – 10 = 0
Ei Ai Mi
p1 3 6 9
p2 0 - -
p3 7 0 7 F = 10 – 3 = 7
Ei Ai Mi
p1 3 6 9
p2 0 - -
p3 0 - -
Jetzt kann Prozess 1 zu Ende gebracht werden!
Freigabe durch
Prozess p3
Führe ausschließlich Prozess p3 aus
RW-Systemarchitekur Kap. 1121
Bankieralgorithmus – Eine einzige Ressourcenklasse (5)
Weise nun zunächst Prozess p1 eine weitere Ressource zu:
Ist dieser Zustand immer noch sicher?
Zur Erinnerung: – Ein Zustand ist sicher, wenn es auf jeden Fall eine deadlockfreie
„Restausführung“ aller Prozesse gibt, auch wenn die Prozesse ihre restlichen Anforderungen auf einen Schlag stellen und Freigaben erst bei Prozessbeendigung durchführen.
F = 10 – 7 = 3
Ei Ai Mi
p1 3 6 9
p2 2 2 4
p3 2 5 7 F = 10 – 8 = 2
Ei Ai Mi
p1 4 5 9
p2 2 2 4
p3 2 5 7
RW-Systemarchitekur Kap. 1122
Bankieralgorithmus – Eine einzige Ressourcenklasse (6)
Antwort: Der Zustand ist nicht sicher.
• Nimmt man den worst case an, dass alle Prozesse ihre Ressourcen künftig auf einen Schlag anfordern, so kann man Prozesse p1 und p3 nicht ausführen. ) Führe Prozess p2 aus.
F = 10 – 8 = 2
Ei Ai Mi
p1 4 5 9
p2 2 2 4
p3 2 5 7
RW-Systemarchitekur Kap. 1123
Bankieralgorithmus – Eine einzige Ressourcenklasse (7)
Nachweis, dass es sich um einen unsicheren Zustand handelt:
• Mit den jetzt zur Verfügung stehenden 4 freien Ressourcen lassen sich weder Prozess p1 noch Prozess p3 ausführen, wenn sie ihre Ressourcenanforderungen sofort stellen und vor Prozessbeendigung nichts freigeben.
) Der Zustand ist unsicher.
F = 10 – 8 = 2
Ei Ai Mi
p1 4 5 9
p2 2 2 4
p3 2 5 7
Führe Prozess p2 bis zum Ende aus
F = 10 – 10 = 0
Ei Ai Mi
p1 4 5 9
p2 4 0 4
p3 2 5 7 F = 10 – 6 = 4
Ei Ai Mi
p1 4 5 9
p2 0 - -
p3 2 5 7
Freigabe durch
Prozess p2
RW-Systemarchitekur Kap. 1124
Bankieralgorithmus – Eine einzige Ressourcenklasse (8)
• Überprüfung auf sicheren Zustand:– Teste, ob es einen Prozess gibt, dessen Anforderungen alle mit
den verfügbaren Ressourcen erfüllt werden können.– Nimm an, dass dieser Prozess ausgeführt wird und alle seine
Ressourcen danach freigegeben werden.– Teste, ob es nun einen anderen Prozess gibt, dessen
Ressourcenanforderung erfüllt wird und verfahre mit diesem Prozess gleichermaßen.
– Der Zustand ist sicher, wenn auf diese Weise alle Prozesse „virtuell“ zu Ende gebracht werden können.
– Sonst ist der Zustand unsicher.
RW-Systemarchitekur Kap. 1125
Bankieralgorithmus – Eine einzige Ressourcenklasse (9)
• Bemerkung:– Im Allgemeinen kann es mehrere Prozesse geben, die virtuell ausgeführt werden
können.– Das Endergebnis ist aber immer das Gleiche!– Grund:
• Nach virtueller Prozessausführung und Freigabe aller Ressourcen eines Prozesses p i können höchstens mehr Ressourcen zur Verfügung stehen.
• ) Alle Prozesse pj, die vorher ausführbar waren, sind nach Ausführung von p i auf jeden Fall immer noch ausführbar.
• Würde sich nach einer Ressourcenanforderung ein unsicherer Zustand ergeben, dann wird die Anforderung nicht erfüllt und der Prozess wird blockiert
• Ansonsten wird die Ressourcenanforderung erfüllt.
• In der Praxis führt der Bankier-Algorithmus daher die Prozesse im Allgemeinen nicht sequentiell aus, sondern quasi-parallel!
• Die Tests auf Sicherheit von Zuständen beschränken die Quasi-Parallelität allerdings in gewisser Weise – mit dem Vorteil, dass Deadlocks garantiert verhindert werden.
RW-Systemarchitekur Kap. 1126
Bankieralgorithmus – Mehrere Ressourcenklassen (1)
• Mehrere Ressourcenklassen, z.B. Drucker, Plotter, …• Gegeben:
– n Prozesse p1, …, pn, die Ressourcen aus Klassen K1, …, Km anfordern
– Anzahl zur Verfügung stehender Ressourcen aus Klasse Kk: Vk 2 N (1 · k · m)) Vektor verfügbarer Ressourcen (V1, …, Vm)
– Für jeden Prozess pi und jede Ressourcenklasse Kk gibt es
• eine maximale Anzahl Mik von Ressourcen der Klasse Kk, die der Prozess pi anfordern wird ) Maximalanforderungsmatrix
M11 M12 M13 … M1m
M21 M22 M23 … M2m
Mn1 Mn2 Mn3 … Mnm
Zeile i gibt Maximalanforderungen von Prozess i an.
… … … …
RW-Systemarchitekur Kap. 1127
Bankieralgorithmus – Mehrere Ressourcenklassen (2)
…• eine Anzahl Eik von Ressourcen der Klasse Kk, die der Prozess pi zu
einem bestimmten Zeitpunkt schon erhalten hat ) Belegungsmatrix
• eine Anzahl von Ressourcen der Klasse Kk, die der Prozess pi nach diesem Zeitpunkt noch maximal anfordern wird: Aik = Mik - Eik ) Restanforderungsmatrix
E11 E12 E13 … E1m
E21 E22 E23 … E2m
En1 En2 En3 … Enm
Zeile i gibt an, welche Ressourcen Prozess i schon erhalten hat.
… … … …
A11 A12 A13 … A1m
A21 A22 A23 … A2m
An1 An2 An3 … Anm
Zeile i gibt an, welche Ressourcen Prozess i maximal noch anfordern wird.
… … … …
RW-Systemarchitekur Kap. 1128
Bankieralgorithmus – Mehrere Ressourcenklassen (3)
– Die Anzahl der freien Ressourcen der Klasse Kk zu diesem Zeitpunkt ergibt sich zu Fk = Vk - i=1
n Eik
) Ressourcenrestvektor (F1, …, Fm)
– Es gilt weiterhin:• Eik · Mik · Vk 8 1 · i · n, 1 · k · m
– Bankier-Algorithmus für mehrere Ressourcenklassen funktioniert analog zum Bankier-Algorithmus für eine Ressourcenklasse.
• Einziger Unterschied: Vergleich natürlicher Zahlen ersetzt durch Vergleich von Vektoren natürlicher Zahlen
• Für zwei Vektoren (v1, …, vm), (w1, …, wm) 2 Nm gilt (v1, …, vm) · (w1, …, wm) gdw. vi · wi 81 · i · m
RW-Systemarchitekur Kap. 1129
Bankieralgorithmus – Mehrere Ressourcenklassen (4)
Überprüfung auf sicheren Zustand:• Teste, ob es einen Prozess pi gibt, dessen Anforderungen alle mit den
verfügbaren Ressourcen erfüllt werden können, d.h. teste, ob es eine Zeile i in Anforderungsmatrix gibt, die kleiner ist als der Ressourcenrestvektor: (Ai1, …, Aim) · (F1,…, Fm)(das ist nötig, da wir den worst case annehmen, dass ein Prozess alle restlichen Ressourcen auf einen Schlag anfordert und Ressourcen erst am Schluss freigibt)
• Markiere den Prozess pi
• Nimm an, dass dieser Prozess ausgeführt wird und alle seine Ressourcen danach freigibt, d.h. addiere (Ei1, …, Eim) zu (F1,…, Fm).
• Teste, ob es nun einen anderen Prozess pj gibt, dessen Ressourcenanforderung erfüllt wird (Aj1, …, Ajm) · (F1,…, Fm) und verfahre mit diesem Prozess genauso.
• Der Zustand ist sicher, wenn auf diese Weise alle Prozesse markiert worden sind, d.h. „virtuell“ zu Ende gebracht werden konnten.
• Sonst ist der Zustand unsicher und die nicht markierten Prozesse sind an dem potentiellen Deadlock beteiligt.
RW-Systemarchitekur Kap. 1130
Bankieralgorithmus – Mehrere Ressourcenklassen (5)
• Beispiel: – Vektor verfügbarer Ressourcen: V = (4 2 3 1)
– Maximalanforderungsmatrix M:
– Aktuelle Belegungsmatrix E:
– Aktuelle Restanforderungsmatrix A:
– Ressourcenrestvektor F = (2 1 0 0)
Bandlaufwerke
Scanner
CD-ROM
Plotter
2 0 1 1 Prozess 1
3 0 1 1 Prozess 2
2 2 2 0 Prozess 3
0 0 1 0 Prozess 1
2 0 0 1 Prozess 2
0 1 2 0 Prozess 3
2 0 0 1 Prozess 1
1 0 1 0 Prozess 2
2 1 0 0 Prozess 3
RW-Systemarchitekur Kap. 1131
Bankieralgorithmus – Mehrere Ressourcenklassen (6)
• Frage: Befinden wir uns in einem sicheren Zustand?
• ) Bankier-Algorithmus
RW-Systemarchitekur Kap. 1132
Bankieralgorithmus – Mehrere Ressourcenklassen (7)
• Beispiel: – Vektor verfügbarer Ressourcen: V = (4 2 3 1)
– Maximalanforderungsmatrix M:
– Aktuelle Belegungsmatrix E:
– Aktuelle Restanforderungsmatrix A:
– Ressourcenrestvektor F = (2 1 0 0)
Bandlaufwerke
Scanner
CD-ROM
Plotter
2 0 1 1 Prozess 1
3 0 1 1 Prozess 2
2 2 2 0 Prozess 3
0 0 1 0 Prozess 1
2 0 0 1 Prozess 2
0 1 2 0 Prozess 3
2 0 0 1 Prozess 1
1 0 1 0 Prozess 2
2 1 0 0 Prozess 3Nur 3. Zeile A3 = (2 1 0 0) der Restanforderungsmatrix ist kleiner gleich Ressourcenrestvektor F = (2 1 0 0).
RW-Systemarchitekur Kap. 1133
Bankieralgorithmus – Mehrere Ressourcenklassen (7)
• Beispiel: – Vektor verfügbarer Ressourcen: V = (4 2 3 1)
– Maximalanforderungsmatrix M:
– Aktuelle Belegungsmatrix E:
– Aktuelle Restanforderungsmatrix A:
– Ressourcenrestvektor F = (0 0 0 0)
Bandlaufwerke
Scanner
CD-ROM
Plotter
2 0 1 1 Prozess 1
3 0 1 1 Prozess 2
2 2 2 0 Prozess 3
0 0 1 0 Prozess 1
2 0 0 1 Prozess 2
2 2 2 0 Prozess 3
2 0 0 1 Prozess 1
1 0 1 0 Prozess 2
0 0 0 0 Prozess 3„Ausführung“ von Prozess 3
RW-Systemarchitekur Kap. 1134
Bankieralgorithmus – Mehrere Ressourcenklassen (7)
• Beispiel: – Vektor verfügbarer Ressourcen: V = (4 2 3 1)
– Maximalanforderungsmatrix M:
– Aktuelle Belegungsmatrix E:
– Aktuelle Restanforderungsmatrix A:
– Ressourcenrestvektor F = (2 2 2 0)
Bandlaufwerke
Scanner
CD-ROM
Plotter
2 0 1 1 Prozess 1
3 0 1 1 Prozess 2
2 2 2 0 Prozess 3
0 0 1 0 Prozess 1
2 0 0 1 Prozess 2
0 0 0 0 Prozess 3
2 0 0 1 Prozess 1
1 0 1 0 Prozess 2
- - - - Prozess 3Ressourcenfreigabe
RW-Systemarchitekur Kap. 1135
Bankieralgorithmus – Mehrere Ressourcenklassen (7)
• Beispiel: – Vektor verfügbarer Ressourcen: V = (4 2 3 1)
– Maximalanforderungsmatrix M:
– Aktuelle Belegungsmatrix E:
– Aktuelle Restanforderungsmatrix A:
– Ressourcenrestvektor F = (2 2 2 0)
Bandlaufwerke
Scanner
CD-ROM
Plotter
2 0 1 1 Prozess 1
3 0 1 1 Prozess 2
2 2 2 0 Prozess 3
0 0 1 0 Prozess 1
2 0 0 1 Prozess 2
0 0 0 0 Prozess 3
2 0 0 1 Prozess 1
1 0 1 0 Prozess 2
- - - - Prozess 3Nur 2. Zeile A2 = (1 0 1 0) der Restanforderungsmatrix kleiner gleich Ressourcenrestvektor F = (2 2 2 0).
RW-Systemarchitekur Kap. 1136
Bankieralgorithmus – Mehrere Ressourcenklassen (7)
• Beispiel: – Vektor verfügbarer Ressourcen: V = (4 2 3 1)
– Maximalanforderungsmatrix M:
– Aktuelle Belegungsmatrix E:
– Aktuelle Restanforderungsmatrix A:
– Ressourcenrestvektor F = (1 2 1 0)
Bandlaufwerke
Scanner
CD-ROM
Plotter
2 0 1 1 Prozess 1
3 0 1 1 Prozess 2
2 2 2 0 Prozess 3
0 0 1 0 Prozess 1
3 0 1 1 Prozess 2
0 0 0 0 Prozess 3
2 0 0 1 Prozess 1
0 0 0 0 Prozess 2
- - - - Prozess 3„Ausführung“ von Prozess 2
RW-Systemarchitekur Kap. 1137
Bankieralgorithmus – Mehrere Ressourcenklassen (7)
• Beispiel: – Vektor verfügbarer Ressourcen: V = (4 2 3 1)
– Maximalanforderungsmatrix M:
– Aktuelle Belegungsmatrix E:
– Aktuelle Restanforderungsmatrix A:
– Ressourcenrestvektor F = (4 2 2 1)
Bandlaufwerke
Scanner
CD-ROM
Plotter
2 0 1 1 Prozess 1
3 0 1 1 Prozess 2
2 2 2 0 Prozess 3
0 0 1 0 Prozess 1
0 0 0 0 Prozess 2
0 0 0 0 Prozess 3
2 0 0 1 Prozess 1
- - - - Prozess 2
- - - - Prozess 3Ressourcenfreigabe
RW-Systemarchitekur Kap. 1138
Bankieralgorithmus – Mehrere Ressourcenklassen (7)
• Beispiel: – Vektor verfügbarer Ressourcen: V = (4 2 3 1)
– Maximalanforderungsmatrix M:
– Aktuelle Belegungsmatrix E:
– Aktuelle Restanforderungsmatrix A:
– Ressourcenrestvektor F = (2 2 2 0)
Bandlaufwerke
Scanner
CD-ROM
Plotter
2 0 1 1 Prozess 1
3 0 1 1 Prozess 2
2 2 2 0 Prozess 3
2 0 1 1 Prozess 1
0 0 0 0 Prozess 2
0 0 0 0 Prozess 3
0 0 0 0 Prozess 1
- - - - Prozess 2
- - - - Prozess 3„Ausführung“ von Prozess 1
RW-Systemarchitekur Kap. 1139
Bankieralgorithmus – Mehrere Ressourcenklassen (7)
• Beispiel: – Vektor verfügbarer Ressourcen: V = (4 2 3 1)
– Maximalanforderungsmatrix M:
– Aktuelle Belegungsmatrix E:
– Aktuelle Restanforderungsmatrix A:
– Ressourcenrestvektor F = (4 2 3 1)
Bandlaufwerke
Scanner
CD-ROM
Plotter
2 0 1 1 Prozess 1
3 0 1 1 Prozess 2
2 2 2 0 Prozess 3
0 0 0 0 Prozess 1
0 0 0 0 Prozess 2
0 0 0 0 Prozess 3
- - - - Prozess 1
- - - - Prozess 2
- - - - Prozess 3Ressourcenfreigabe
RW-Systemarchitekur Kap. 1140
Bankieralgorithmus – Mehrere Ressourcenklassen (8)
• Frage: Befinden wir uns in einem sicheren Zustand?
• Bankier-Algorithmus:) Zustand ist sicher.
RW-Systemarchitekur Kap. 1141
Bankieralgorithmus – Mehrere Ressourcenklassen (9)• Beispiel:
– Vektor verfügbarer Ressourcen: V = (4 2 3 1)– Maximalanforderungsmatrix M:
– Aktuelle Belegungsmatrix E:
– Aktuelle Restanforderungsmatrix A:
– Ressourcenrestvektor F = (2 1 0 0)• Darf man in diesem Zustand dem 2. Prozess die Anforderung nach einem weiteren
Bandlaufwerk erfüllen?• Nein, das führt zu einem unsicheren Zustand!
Bandlaufwerke
Scanner
CD-ROM
Plotter
2 0 1 1 Prozess 13 0 1 1 Prozess 2
2 2 2 0 Prozess 3
0 0 1 0 Prozess 1
2 0 0 1 Prozess 2
0 1 2 0 Prozess 3
2 0 0 1 Prozess 1
1 0 1 0 Prozess 2
2 1 0 0 Prozess 3
RW-Systemarchitekur Kap. 1142
Bankieralgorithmus - Analyse
• Ist mit dem Bankieralgorithmus das Deadlock-Problem restlos gelöst?• Leider nein, da
– Prozesse können meist nicht im voraus eine verlässliche Obergrenze für ihre Ressourcenanforderungen geben (zumindest nicht exakt genug, so dass das System nicht durch Überschätzung des Ressourcenbedarfs zu ineffizienter Ausführung gezwungen wird)
– Garantierte Obergrenzen würden häufig sogar die Anzahl der verfügbaren Ressourcen übersteigen, aber durch ständiges Zuweisen und Freigeben von Ressourcen stellt dies trotzdem kein Problem dar
– Üblicherweise werden Prozesse dynamisch neu erzeugt werden und sind nicht statisch vorhanden
– Ressourcen können auch plötzlich verschwinden (z.B. Bandlaufwerke fallen aus)
) Bankier-Algorithmus ist in der Theorie schön, löst aber nicht alle praktischen Probleme.
) Zur Deadlock-Verhinderung sind Informationen über zukünftige Ressourcen-Anforderungen nötig, die nicht bekannt sind!
RW-Systemarchitekur Kap. 1143
Deadlock-Vermeidung durch Negieren der Deadlock-Voraussetzungen
• Voraussetzungen für Deadlocks1. Wechselseitiger Ausschluss: Jede Ressource ist entweder verfügbar
oder genau einem Prozess zugeordnet.2. Hold-and-wait-Bedingung: Prozesse, die schon Ressourcen
reserviert haben, können noch weitere Ressourcen anfordern.3. Ununterbrechbarkeit: Ressourcen, die einem Prozess bewilligt
wurden, können nicht gewaltsam wieder entzogen werden.4. Zyklische Wartebedingung: Es muss eine zyklische Kette von
Prozessen geben, von denen jeder auf eine Ressource wartet, die dem nächsten Prozess in der Kette gehört.
• Reale Systeme versuchen nach Möglichkeit diese Bedingungen ganz oder teilweise außer Kraft zu setzen, um Deadlocks zu vermeiden.
RW-Systemarchitekur Kap. 1144
Negieren des wechselseitigen Ausschlusses (1)
• Wechselseitiger Ausschluss: Jede Ressource ist entweder verfügbar oder genau einem Prozess zugeordnet.
• Auf wechselseitigen Ausschluss kann man nicht verzichten.– Gleichzeitiges Drucken zweier Prozesse auf dem gleichen Drucker???
• In gewissen Situationen lässt sich wechselseitiger Ausschluss aber einschränken.
• Bsp.: Drucken– Spooling: Prozesse drucken nicht direkt auf den Drucker, sondern in ein
globales Spooling-Verzeichnis
– Es gibt einen ständig laufenden Prozess (Drucker-Dämon), der als einziger den Drucker reserviert und Dateien aus dem Spooling-Verzeichnis der Reihe nach druckt.
– Keine Deadlock-Probleme aufgrund Drucker-Zugriff, da nur ein einziger Prozess auf den Drucker zugreift.
– Das funktioniert perfekt, wenn Speicher im Spooling-Verzeichnis unbegrenzt ist.
RW-Systemarchitekur Kap. 1145
Negieren des wechselseitigen Ausschlussess (2)
• Bsp.: Drucken– …– In Realität: Deadlock-Probleme, wenn Speicher im Spooling-
Verzeichnis begrenzt / zu gering (Konkurrenz um Plattenplatz)– Szenario:
• 2 Prozesse füllen Spooling-Speicher je zur Hälfte, sind noch nicht fertig mit Drucken
• Aus Effizienzgründen normalerweise Druckbeginn erst, wenn Dateien komplett ins Spooling-Verzeichnis gedruckt.
• Keiner der beiden Prozesse wird fertig! ) Deadlock
• Allgemeines Prinzip:– Teile Ressourcen nur zu, wenn unbedingt nötig– Möglichst wenig Prozesse sollen Ressource selbst anfordern dürfen
RW-Systemarchitekur Kap. 1146
Negieren der Hold-and-Wait-Bedingung
• Hold-and-wait-Bedingung: Prozesse, die schon Ressourcen reserviert haben, können noch weitere Ressourcen anfordern.
• Lösungsansätze zur Auflösung der Hold-and-wait-Bedingung:– Prozesse müssen benötigte Ressourcen immer auf einmal und im
voraus anfordern.• Teilweise benutzt bei Betriebssystemen von Großrechnern
• Funktioniert nicht, wenn Prozesse Ressourcenbedarf nicht im voraus kennen.
• (siehe Bankier-Algorithmus)
• Keine effiziente Ressourcennutzung, da Ressourcen unnötig lange belegt
– Vor Ressourcenanforderung werden alle Ressourcen kurzzeitig freigegeben, dann zusammen mit der neuen Ressource neu angefordert.
RW-Systemarchitekur Kap. 1147
Negieren der Ununterbrechbarkeit
• Ununterbrechbarkeit: Ressourcen, die einem Prozess bewilligt wurden, können nicht gewaltsam wieder entzogen werden.
• Kaum zu realisieren, dass Ressourcennutzung jederzeit ohne Schaden von außen unterbrochen werden kann.
RW-Systemarchitekur Kap. 1148
Negieren der zyklische Wartebedingung
• Zyklische Wartebedingung: Es muss eine zyklische Kette von Prozessen geben, von denen jeder auf eine Ressource wartet, die dem nächsten Prozess in der Kette gehört.
• Lösungsansätze zur Beseitigung der zyklischen Wartebedingung:– Jeder Prozess kann nur eine Ressource auf einmal belegen.
• Vorgehen in vielen Fällen unannehmbar
– Ressourcen werden durchnummeriert. Reihenfolge der Ressourcenanforderung darf nur in aufsteigender Reihenfolge erfolgen.
• Belegungs-Anforderunggraph kann dann nicht zyklisch werden.
• Schwierigkeit, eine Ordnung zu finden, die allen Anforderungen gerecht wird
RW-Systemarchitekur Kap. 1149
Zusammenfassung
• Deadlock-Verhinderung ist schwierig, da dazu im allgemeinen Informationen über zukünftige Ressourcen-Anforderungen nötig sind, die nicht bekannt sind!
• Deadlock-Freiheit kann zwar prinzipiell erreicht werden, häufig jedoch um den Preis starker Effizienz-Verluste
• Häufig verzichtet man in der Praxis daher auf absolute Garantien für Deadlock-Freiheit.
• Warum geht bei solchen Systemen trotzdem meistens nichts schief?Weil sie nicht an ihrem Ressourcen-Limit betrieben werden.