Betriebssysteme

Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Betriebssysteme - Deadlocks
→ [email protected]
Version: (8c45d65)
ARSnova 19226584
Alois Schütte
23. März 2016
1 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Inhaltsverzeichnis
Dieser Teil erörtert das Problem von Deadlocks (Verklemmungen):
Situationen, bei denen sich Prozesse gegenseitig sperren, weil sie auf
Ereignisse warten, die von einem anderen wartenden Prozess nicht
freigegeben werden können.
1 Überblick
2 Ignorieren des Problems
3 Deadlock-Erkennung und -Behebung
Ein Betriebsmittel je Klasse
Mehrere Betriebsmittel je Klasse
4 Deadlock-Verhinderung
Betriebsmittelflugbahnen
Sichere und unsichere Zustände
Bankier-Algorithmus für eine Betriebsmittelklasse
Bankier-Algorithmus für mehrere Betriebsmittelklassen
5 Deadlock-Vermeidung
2 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Überblick
Problemstellung
Eine Verklemmung (Deadlock) kann wie folgt definiert werden:
Eine Menge von Prozessen sperren sich gegenseitig, wenn jeder
Prozess der Menge auf ein Ereignis wartet, das nur durch einen
anderen Prozess der Menge ausgelöst werden kann.
Da alle am Deadlock beteiligten Prozesse warten, kann keiner ein Ereignis
auslösen, so dass ein anderer geweckt wird. Also warten alle beteiligten
Prozesse ewig.
Kennen Sie Beispiele ?
3 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Überblick
Problemstellung
Eine Verklemmung (Deadlock) kann wie folgt definiert werden:
Eine Menge von Prozessen sperren sich gegenseitig, wenn jeder
Prozess der Menge auf ein Ereignis wartet, das nur durch einen
anderen Prozess der Menge ausgelöst werden kann.
Da alle am Deadlock beteiligten Prozesse warten, kann keiner ein Ereignis
auslösen, so dass ein anderer geweckt wird. Also warten alle beteiligten
Prozesse ewig.
Kennen Sie Beispiele ?
3 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Überblick
Beispiel aus der realen Welt
Abbildung: 4 Autos an Kreuzung ohne Verkehrsschilder
Welche Beispiele für Deadlocks kennen Sie?
4 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Überblick
Beispiel aus der Programmierung: zwei Java Threads
Deadlock01.java
1
2
3
4
6
7
8
9
10
11
public static void main ( String [] args ) {
// resource objects to locks on
final Object resource1 = " Jennie " ;
final Object resource2 = " Hannah " ;
// first thread - it tries to lock Jennie then Hannah
Thread as = new Thread () {
public void run () {
// lock resource1
synchronized ( resource1 ) {
System . out . println ( " as : habe Jennie " );
// pause ...
try { Thread . sleep (50); }
catch ( I n t e r r u p t e d E x c e p t i o n e ) {}
13
14
15
// attempt to lock resource2
System . out . println ( " as : möchte noch Hannah " );
synchronized ( resource2 ) {
System . out . println ( " as : habe Hannah " );
}
17
18
19
20
21
}
22
}
23
24
};
5 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Überblick
// second thread - it tries to lock Hannah then Jennie
Thread bp = new Thread () {
public void run () {
// lock resource2
synchronized ( resource2 ) {
System . out . println ( " bp : habe Hannah " );
1
2
3
4
5
6
// pause ...
try { Thread . sleep (50); }
catch ( I n t e r r u p t e d E x c e p t i o n e ) {}
8
9
10
System . out . println ( " bp : möchte noch Jennie " );
synchronized ( resource1 ) {
System . out . println ( " bp : habe Jennie " );
}
12
13
14
15
}
16
}
17
18
};
20
// start threads - should deadlock and program will never exit
as . start ();
bp . start ();
21
22
}
23
24
}
6 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Überblick
Bedingungen für Deadlocks
Damit ein Deadlock entsteht, müssen alle vier folgenden Bedingungen
erfüllt sein:
1
Wechselseitiger Ausschluss:
Jedes Betriebsmittel wird entweder von genau einem Prozess belegt
oder es ist verfügbar.
7 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Überblick
Bedingungen für Deadlocks
Damit ein Deadlock entsteht, müssen alle vier folgenden Bedingungen
erfüllt sein:
1
Wechselseitiger Ausschluss:
Jedes Betriebsmittel wird entweder von genau einem Prozess belegt
oder es ist verfügbar.
2
Anforderung weitere Betriebsmittel:
Ein Prozess, der bereits Betriebsmittel belegt hat, kann weitere
Betriebsmittel anfordern.
7 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Überblick
Bedingungen für Deadlocks
Damit ein Deadlock entsteht, müssen alle vier folgenden Bedingungen
erfüllt sein:
1
Wechselseitiger Ausschluss:
Jedes Betriebsmittel wird entweder von genau einem Prozess belegt
oder es ist verfügbar.
2
Anforderung weitere Betriebsmittel:
Ein Prozess, der bereits Betriebsmittel belegt hat, kann weitere
Betriebsmittel anfordern.
3
Ununterbrechbarkeit:
Die von einem Prozess belegten Betriebsmittel können nicht von
außen entzogen werden; der Prozess selbst muss sie explizit
freigeben.
7 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Überblick
Bedingungen für Deadlocks
Damit ein Deadlock entsteht, müssen alle vier folgenden Bedingungen
erfüllt sein:
1
Wechselseitiger Ausschluss:
Jedes Betriebsmittel wird entweder von genau einem Prozess belegt
oder es ist verfügbar.
2
Anforderung weitere Betriebsmittel:
Ein Prozess, der bereits Betriebsmittel belegt hat, kann weitere
Betriebsmittel anfordern.
3
Ununterbrechbarkeit:
Die von einem Prozess belegten Betriebsmittel können nicht von
außen entzogen werden; der Prozess selbst muss sie explizit
freigeben.
4
Zyklische Wartebedingung:
Es muss eine zyklische Kette von Prozessen geben, so dass jeder
Prozess ein Betriebsmittel anfordert, dass vom nächsten Prozess der
Kette belegt ist.
7 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Überblick
Bedingungen für Deadlocks
Damit ein Deadlock entsteht, müssen alle vier folgenden Bedingungen
erfüllt sein:
1
Wechselseitiger Ausschluss:
Jedes Betriebsmittel wird entweder von genau einem Prozess belegt
oder es ist verfügbar.
2
Anforderung weitere Betriebsmittel:
Ein Prozess, der bereits Betriebsmittel belegt hat, kann weitere
Betriebsmittel anfordern.
3
Ununterbrechbarkeit:
Die von einem Prozess belegten Betriebsmittel können nicht von
außen entzogen werden; der Prozess selbst muss sie explizit
freigeben.
4
Zyklische Wartebedingung:
Es muss eine zyklische Kette von Prozessen geben, so dass jeder
Prozess ein Betriebsmittel anfordert, dass vom nächsten Prozess der
Kette belegt ist.
7 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Überblick
Betriebsmittel-Graphen
Man kann die Beziehung von Betriebsmitteln und Prozessen durch
bipartite gerichtete Graphen darstellen
• Die Knoten des Graphen sind unterteilt in:
8 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Überblick
Betriebsmittel-Graphen
Man kann die Beziehung von Betriebsmitteln und Prozessen durch
bipartite gerichtete Graphen darstellen
• Die Knoten des Graphen sind unterteilt in:
• Prozesse sind als Kreise dargestellt
8 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Überblick
Betriebsmittel-Graphen
Man kann die Beziehung von Betriebsmitteln und Prozessen durch
bipartite gerichtete Graphen darstellen
• Die Knoten des Graphen sind unterteilt in:
• Prozesse sind als Kreise dargestellt
• Betriebsmittel werden durch Rechtecke dargestellt
8 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Überblick
Betriebsmittel-Graphen
Man kann die Beziehung von Betriebsmitteln und Prozessen durch
bipartite gerichtete Graphen darstellen
• Die Knoten des Graphen sind unterteilt in:
• Prozesse sind als Kreise dargestellt
• Betriebsmittel werden durch Rechtecke dargestellt
• Eine Kanten von einem Betriebsmittel zu einem Prozess bedeutet,
dass der Prozess das Betriebsmittel belegt hat.
8 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Überblick
Betriebsmittel-Graphen
Man kann die Beziehung von Betriebsmitteln und Prozessen durch
bipartite gerichtete Graphen darstellen
• Die Knoten des Graphen sind unterteilt in:
• Prozesse sind als Kreise dargestellt
• Betriebsmittel werden durch Rechtecke dargestellt
• Eine Kanten von einem Betriebsmittel zu einem Prozess bedeutet,
dass der Prozess das Betriebsmittel belegt hat.
• Eine Kante von einem Prozess zu einem Betriebsmittel sagt aus,
dass der Prozess blockiert ist, weil er auf das Betriebsmittel wartet.
8 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Überblick
Betriebsmittel-Graphen
Man kann die Beziehung von Betriebsmitteln und Prozessen durch
bipartite gerichtete Graphen darstellen
• Die Knoten des Graphen sind unterteilt in:
• Prozesse sind als Kreise dargestellt
• Betriebsmittel werden durch Rechtecke dargestellt
• Eine Kanten von einem Betriebsmittel zu einem Prozess bedeutet,
dass der Prozess das Betriebsmittel belegt hat.
• Eine Kante von einem Prozess zu einem Betriebsmittel sagt aus,
dass der Prozess blockiert ist, weil er auf das Betriebsmittel wartet.
8 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Überblick
Beispiel für Betriebsmittelgraph
P1
P1
B2
Prozess P1
belegt
Betriebsmittel B1
B1
P2 wartet auf
Zuteilung von B2
B1
P2
Deadlock,
Zyklus
P1-B2-P2-P1
P1
B1
B2
P2
9 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Überblick
Betriebsmittel-Graphen sind Hilfsmittel für das Betriebssystem, um
Abfolgen von Anforderungen und Freigaben von Betriebsmitteln durch
Prozesse verwalten zu können, so dass Deadlocks nicht entstehen.
Gehen wir von folgender Situation aus:
• Es gibt drei Prozesse P1, P2 und P3
• Jeder Prozess fordert zwei Betriebsmittel an:
• P1 benötigt B1 und B2
• P2 benötigt B2 und B3
• P3 benötigt B3 und B1
Welche Situationen (Reihenfolge der Betriebsmittelzuteilung) führen zu
Deadlocks?
10 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Überblick
Keine Nebenläufigkeit, d.h. Betriebssystem wählt zuerst P1, dann P2
und am Schluss P3, wobei jeder Prozess vollständig abgearbeitet wird:
11 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Überblick
Keine Nebenläufigkeit, d.h. Betriebssystem wählt zuerst P1, dann P2
und am Schluss P3, wobei jeder Prozess vollständig abgearbeitet wird:
12 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Überblick
Keine Nebenläufigkeit, d.h. Betriebssystem wählt zuerst P1, dann P2
und am Schluss P3, wobei jeder Prozess vollständig abgearbeitet wird:
13 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Überblick
Nebenläufigkeit mit schlechter Reihenfolge:
P1
P1 fordert B1 an
P2 fordert B2 an
P3 fordert B3 an
P1 fordert B2 an
P2 fordert B3 an
B1
P1
B1
P3 fordert B1 an
Deadlock
P1
B1
P2
P3
B2
B3
P2
P3
B2
B3
P2
P3
B2
B3
14 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Überblick
Nebenläufigkeit mit geschickter Reihenfolge: Betriebsmittelgraph an Tafel
1
2
3
4
5
6
7
8
9
10
11
12
P1
P3
P1
P3
P1
P1
P3
P3
P2
P2
P2
P2
fordert B1 an
fordert B3 an
fordert B2 an
fordert B1 an
gibt B1 frei
gibt B2 frei
gibt B1 frei
gibt B3 frei
fordert B2 an
fordert B3 an
gibt B2 frei
gibt B3 frei
15 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Überblick
Strategien der Deadlock-Behandlung
Durch geschickte Auswahl der Prozesse können also
Deadlock-Situationen behandelt werden.
Man kann grundsätzlich vier Strategien unterscheiden:
1
Ignorieren des Problems (Strategie von Unix Systemen)
2
Erkennen und Beheben von Deadlocks
3
dynamische Verhinderung durch vorsichtige
Betriebsmittelzuteilung
4
Vermeidung durch Verbieten einer der 4 notwendigen Bedingungen
Im Folgenden werden diese Arten des Umgangs mit Deadlocks
verdeutlicht.
16 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Überblick
Strategien der Deadlock-Behandlung
Durch geschickte Auswahl der Prozesse können also
Deadlock-Situationen behandelt werden.
Man kann grundsätzlich vier Strategien unterscheiden:
1
Ignorieren des Problems (Strategie von Unix Systemen)
2
Erkennen und Beheben von Deadlocks
3
dynamische Verhinderung durch vorsichtige
Betriebsmittelzuteilung
4
Vermeidung durch Verbieten einer der 4 notwendigen Bedingungen
Im Folgenden werden diese Arten des Umgangs mit Deadlocks
verdeutlicht.
16 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Ignorieren des Problems
Vogel Strauß Algorithmus
Der Vogel-Strauß Algorithmus“ (Stecke Kopf in den Sand und verhalte
”
dich so, als gäbe es kein Problem) geht davon aus, dass
• Deadlocks eher selten auftreten,
• Systeme häufiger gebootet werden (wg. Fehlern, Wartung),
• Einbußen an Komfort durch Deadlock-Erkennung oder
-Verhinderung nicht akzeptabel sind.
• Performance (Prozesse schreiten langsam voran, wenn Betriebsmittel
angefragt wird) oder
• Bequemlichkeit (z.B. nur eine geöffnete Datei oder nur ein Prozess je
Programm erlaubt)
In Unix ist diese Strategie gewählt.
17 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Deadlock-Erkennung und -Behebung
Hier werden Deadlocks nicht verhindert, sondern erkannt und behoben.
Die Betriebsmittel werden in Klassen aufgeteilt, z.B.:
• Drucker
• Plotter,
• Bandlaufwerke,
• Netzwerkkarten.
Wir unterscheiden Verfahren, je nachdem ob ein oder mehrere
Betriebsmittel je Klasse im System verfügbar sind.
18 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Deadlock-Erkennung und -Behebung
Hier werden Deadlocks nicht verhindert, sondern erkannt und behoben.
Die Betriebsmittel werden in Klassen aufgeteilt, z.B.:
• Drucker
• Plotter,
• Bandlaufwerke,
• Netzwerkkarten.
Wir unterscheiden Verfahren, je nachdem ob ein oder mehrere
Betriebsmittel je Klasse im System verfügbar sind.
18 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Ein Betriebsmittel je Klasse
Ein Betriebsmittel je Klasse
Gehen wir von einem System mit 7 Prozessen (A-G) und 6
Betriebsmitteln (a-f) aus.
Die Betriebsmittelbelegungen und -anforderungen seien geben durch:
1
A belegt a und fordert b an
2
B belegt nichts und fordert c an
3
C belegt nichts und fordert b an
4
D belegt d und fordert b und c an
5
E belegt c und fordert e an
6
F belegt f und fordert b an
7
G belegt e und fordert d an
Frage / Problemstellung:
Befindet sich das System in einem Deadlock-Zustand, wenn ja,
welche Prozesse sind daran beteiligt?
19 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Ein Betriebsmittel je Klasse
Lösung
Ermittle Betriebsmittel-Graph, Teste auf Zykel
1
A belegt a und fordert b an
2
B belegt nichts und fordert
c an
3
C belegt nichts und fordert
b an
4
D belegt d und fordert b
und c an
5
E belegt c und fordert e an
6
F belegt f und fordert b an
7
G belegt e und fordert d an
B
a
A
C
b
D
F
d
f
G
c
E
e
20 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Ein Betriebsmittel je Klasse
Verfahren1 : Topologisches Sortieren von gerichteten Graphen
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
bool IsZyclic ( Digraph < TV , maxNodes > g ) {
// Testet , ob g Zykel hat
queue < int > q ;
// Schlange für A u s w a h l k a n d i d a t e n
int * indegree = new int [ g . GetMaxNodes ()];
int v = g . FirstVertex ();
while ( v != -1) {
indegree [ v ] = g . GetIndegree ( v ); // Eingangsgrade initi alisier en
if ( indegree [ v ] == 0) q . push ( v ); // Knoten mit idegree =0
v = g . NextVertex ( v );
// aufnehmen
}
while (! q . empty ()) {
// Solange bis Schlange leer
v = q . front ();
// nächster Knoten aus Schlange lesen
q . pop ();
// und aus Schlange entfernen
int w = g . FirstArc ( v );
// erste von v ausgehende Kante (v , w )
while ( w != -1) {
// für alle Nachfolger von v
indegree [ w ] - -;
// Eingangsgrad von w d ekremen tieren
if ( indegree [ w ] == 0) q . push ( w ); // Knoten mit idegree =0
w = g . NextArc (v , w );
// nächste Kante (v , w )
}
}
v = g . FirstVertex ();
while ( v != -1) {
// g hat Zykel , wenn es noch Knoten
if ( indegree [ v ] != 0) return true ; // mit Eingangsgrad != 0 gibt
v = g . NextVertex ( v );
}
return false ;
}
1 vgl.
PG2, www.fbi.h-da.de/˜a.schuette
21 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Ein Betriebsmittel je Klasse
Hörsaalübung
Verwenden Sie den Algorithmus ’Typologische Sortieren’ der letzten Folie
auf die u.a. Situation.
B
a
A
C
b
D
F
d
f
G
c
E
e
22 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Ein Betriebsmittel je Klasse
g hat Zykel : 1
Knoten :
0 : A , 1 : B , 2 : C , 3 : D, 4 : E , 5 : F , 6 : G ,
7: a , 8: b , 9: c , 10: d , 11: e , 12 : f 0
Adjazenz Matrix :
0 1 2 3 4 5 6 7 8 9 10 11 12
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
0| − − − − − − − − 1 − − − −
1| − − − − − − − − − 1 − − −
2| − − − − − − − − 1 − − − −
3| − − − − − − − − 1 1 − − −
4| − − − − − − − − − − − 1 −
5| − − − − − − − − 1 − − − −
6| − − − − − − − − − − 1 − −
7| 1 − − − − − − − − − − − −
8| − − − − − − − − − − − − −
9| − − − − 1 − − − − − − − −
10| − − − 1 − − − − − − − − −
11| − − − − − − 1 − − − − − −
12| − − − − − 1 − − − − − − −
B
a
A
C
b
D
F
d
f
G
c
E
e
Am Ende des Tests ist die Schlange leer und es gibt noch Knoten (roten),
die einen Eingangsgrad > 0 haben, sie bilden die Deadlock-Prozesse.
Der Aufwand ist recht groß: O(|Knoten| + |Kanten|).
Deshalb wird nicht bei jeder Anforderung eines Betriebsmittels auf
Zykelfreiheit geprüft, sondern etwa nur:
• alle k Minuten oder
• wenn die Prozessorlast unter festgesetzte Schwelle fällt.
23 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Ein Betriebsmittel je Klasse
g hat Zykel : 1
Knoten :
0 : A , 1 : B , 2 : C , 3 : D, 4 : E , 5 : F , 6 : G ,
7: a , 8: b , 9: c , 10: d , 11: e , 12 : f 0
Adjazenz Matrix :
0 1 2 3 4 5 6 7 8 9 10 11 12
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
0| − − − − − − − − 1 − − − −
1| − − − − − − − − − 1 − − −
2| − − − − − − − − 1 − − − −
3| − − − − − − − − 1 1 − − −
4| − − − − − − − − − − − 1 −
5| − − − − − − − − 1 − − − −
6| − − − − − − − − − − 1 − −
7| 1 − − − − − − − − − − − −
8| − − − − − − − − − − − − −
9| − − − − 1 − − − − − − − −
10| − − − 1 − − − − − − − − −
11| − − − − − − 1 − − − − − −
12| − − − − − 1 − − − − − − −
B
a
A
C
b
D
F
d
f
G
c
E
e
Am Ende des Tests ist die Schlange leer und es gibt noch Knoten (roten),
die einen Eingangsgrad > 0 haben, sie bilden die Deadlock-Prozesse.
Der Aufwand ist recht groß: O(|Knoten| + |Kanten|).
Deshalb wird nicht bei jeder Anforderung eines Betriebsmittels auf
Zykelfreiheit geprüft, sondern etwa nur:
• alle k Minuten oder
• wenn die Prozessorlast unter festgesetzte Schwelle fällt.
23 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Mehrere Betriebsmittel je Klasse
Wenn mehrere Instanzen einer Betriebsmittelklasse existieren, kann
folgender Matrix-basierter Ansatz gewählt werden.
• Sei V = (V1 , V2 , . . . Vm ) der Betriebsmittelvektor, wobei Vi die
Anzahl der vorhandenen Mittel der Klasse i angibt.
• Zu jedem Zeitpunkt sei R = (R1 , R2 , . . . Rm ) der
Betriebsmittelrestevektor der die nicht belegten Betriebsmittel
definiert.
24 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Mehrere Betriebsmittel je Klasse
Wenn mehrere Instanzen einer Betriebsmittelklasse existieren, kann
folgender Matrix-basierter Ansatz gewählt werden.
• Sei V = (V1 , V2 , . . . Vm ) der Betriebsmittelvektor, wobei Vi die
Anzahl der vorhandenen Mittel der Klasse i angibt.
• Zu jedem Zeitpunkt sei R = (R1 , R2 , . . . Rm ) der
Betriebsmittelrestevektor der die nicht belegten Betriebsmittel
definiert.
• Die beiden Matrizen B und A beschreiben die insgesamt belegten
und angeforderten Betriebsmittel der n Prozesse. Bij seien die vom
Prozess i belegten Betriebsmittel der Klasse j, Aij die von ihm
angeforderten.
24 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Mehrere Betriebsmittel je Klasse
Wenn mehrere Instanzen einer Betriebsmittelklasse existieren, kann
folgender Matrix-basierter Ansatz gewählt werden.
• Sei V = (V1 , V2 , . . . Vm ) der Betriebsmittelvektor, wobei Vi die
Anzahl der vorhandenen Mittel der Klasse i angibt.
• Zu jedem Zeitpunkt sei R = (R1 , R2 , . . . Rm ) der
Betriebsmittelrestevektor der die nicht belegten Betriebsmittel
definiert.
• Die beiden Matrizen B und A beschreiben die insgesamt belegten
und angeforderten Betriebsmittel der n Prozesse. Bij seien die vom
Prozess i belegten Betriebsmittel der Klasse j, Aij die von ihm
angeforderten.
• Da jedes Betriebsmittel entweder belegt oder verfügbar ist, gilt:
n
X
Bij + Rj = Vj
1=1
d.h. Anzahl der Mittel der Klasse j, die belegt sind und die noch
freien Mittel der Klasse j ergeben die insgesamt verfügbaren Mittel
der Klasse j.
24 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Mehrere Betriebsmittel je Klasse
Wenn mehrere Instanzen einer Betriebsmittelklasse existieren, kann
folgender Matrix-basierter Ansatz gewählt werden.
• Sei V = (V1 , V2 , . . . Vm ) der Betriebsmittelvektor, wobei Vi die
Anzahl der vorhandenen Mittel der Klasse i angibt.
• Zu jedem Zeitpunkt sei R = (R1 , R2 , . . . Rm ) der
Betriebsmittelrestevektor der die nicht belegten Betriebsmittel
definiert.
• Die beiden Matrizen B und A beschreiben die insgesamt belegten
und angeforderten Betriebsmittel der n Prozesse. Bij seien die vom
Prozess i belegten Betriebsmittel der Klasse j, Aij die von ihm
angeforderten.
• Da jedes Betriebsmittel entweder belegt oder verfügbar ist, gilt:
n
X
Bij + Rj = Vj
1=1
d.h. Anzahl der Mittel der Klasse j, die belegt sind und die noch
freien Mittel der Klasse j ergeben die insgesamt verfügbaren Mittel
der Klasse j.
24 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Plotter
Drucker
CD-ROM
Betriebsmittelvektor V = (
Betriebsmittelrestevektor R = (
Bandgerät
Beispiel
4
2
2
1
3
3
1
0
)
)



2 0 0 1
0 0 1 0
B =  2 0 0 1 A =  1 0 1 0 
0 1 2 0
2 1 0 0

Also belegt der Prozess 2 z.B. 2 Bandgeräte und ein CD-Rom Laufwerk und
möchte weiterhin ein weiteres Bandgerät und einen Drucker haben.
25 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Der Deadlockerkennungsalgorithmus basiert auf dem Vergleich von
Vektoren.
Die Relation ≤ für 2 Vektoren A und B sei definiert als:
A ≤ B gdw. für alle 0 ≤ i ≤ m gilt: Ai ≤ Bi
Also müssen alle Elemente von A kleiner oder gleich dem korrespondierenden
Element von B sein.
26 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Deadlockerkennungsalgorithmus
Voraussetzung: Jeder Prozess fordert alle Betriebsmittel auf einmal an.
Eine Markierung eines Prozesses bedeutet, dass er alle Ressourcen hat
und seine Ausführung beenden kann.
1
Anfänglich ist kein Prozess markiert.
27 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Deadlockerkennungsalgorithmus
Voraussetzung: Jeder Prozess fordert alle Betriebsmittel auf einmal an.
Eine Markierung eines Prozesses bedeutet, dass er alle Ressourcen hat
und seine Ausführung beenden kann.
1
Anfänglich ist kein Prozess markiert.
2
Wähle einen beliebigen unmarkierten Prozess Pi aus, für den gilt
Ai ≤ R
(also alle Anforderungen von Pi können befriedigt werden)
27 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Deadlockerkennungsalgorithmus
Voraussetzung: Jeder Prozess fordert alle Betriebsmittel auf einmal an.
Eine Markierung eines Prozesses bedeutet, dass er alle Ressourcen hat
und seine Ausführung beenden kann.
1
Anfänglich ist kein Prozess markiert.
2
Wähle einen beliebigen unmarkierten Prozess Pi aus, für den gilt
Ai ≤ R
(also alle Anforderungen von Pi können befriedigt werden)
27 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Deadlockerkennungsalgorithmus
Voraussetzung: Jeder Prozess fordert alle Betriebsmittel auf einmal an.
Eine Markierung eines Prozesses bedeutet, dass er alle Ressourcen hat
und seine Ausführung beenden kann.
1
Anfänglich ist kein Prozess markiert.
2
Wähle einen beliebigen unmarkierten Prozess Pi aus, für den gilt
Ai ≤ R
(also alle Anforderungen von Pi können befriedigt werden)
3
Falls ein solcher Prozess existiert, so bilde R = R + Bi
(er gibt ja alle Ressourcen wieder frei, wenn er terminiert),
markiere den Prozess und gehe zu Schritt 2
27 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Deadlockerkennungsalgorithmus
Voraussetzung: Jeder Prozess fordert alle Betriebsmittel auf einmal an.
Eine Markierung eines Prozesses bedeutet, dass er alle Ressourcen hat
und seine Ausführung beenden kann.
1
Anfänglich ist kein Prozess markiert.
2
Wähle einen beliebigen unmarkierten Prozess Pi aus, für den gilt
Ai ≤ R
(also alle Anforderungen von Pi können befriedigt werden)
3
Falls ein solcher Prozess existiert, so bilde R = R + Bi
(er gibt ja alle Ressourcen wieder frei, wenn er terminiert),
markiere den Prozess und gehe zu Schritt 2
27 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Deadlockerkennungsalgorithmus
Voraussetzung: Jeder Prozess fordert alle Betriebsmittel auf einmal an.
Eine Markierung eines Prozesses bedeutet, dass er alle Ressourcen hat
und seine Ausführung beenden kann.
1
Anfänglich ist kein Prozess markiert.
2
Wähle einen beliebigen unmarkierten Prozess Pi aus, für den gilt
Ai ≤ R
(also alle Anforderungen von Pi können befriedigt werden)
3
Falls ein solcher Prozess existiert, so bilde R = R + Bi
(er gibt ja alle Ressourcen wieder frei, wenn er terminiert),
markiere den Prozess und gehe zu Schritt 2
4
Andernfalls terminiere das Verfahren.
27 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Deadlockerkennungsalgorithmus
Voraussetzung: Jeder Prozess fordert alle Betriebsmittel auf einmal an.
Eine Markierung eines Prozesses bedeutet, dass er alle Ressourcen hat
und seine Ausführung beenden kann.
1
Anfänglich ist kein Prozess markiert.
2
Wähle einen beliebigen unmarkierten Prozess Pi aus, für den gilt
Ai ≤ R
(also alle Anforderungen von Pi können befriedigt werden)
3
Falls ein solcher Prozess existiert, so bilde R = R + Bi
(er gibt ja alle Ressourcen wieder frei, wenn er terminiert),
markiere den Prozess und gehe zu Schritt 2
4
Andernfalls terminiere das Verfahren.
27 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Deadlockerkennungsalgorithmus
Voraussetzung: Jeder Prozess fordert alle Betriebsmittel auf einmal an.
Eine Markierung eines Prozesses bedeutet, dass er alle Ressourcen hat
und seine Ausführung beenden kann.
1
Anfänglich ist kein Prozess markiert.
2
Wähle einen beliebigen unmarkierten Prozess Pi aus, für den gilt
Ai ≤ R
(also alle Anforderungen von Pi können befriedigt werden)
3
Falls ein solcher Prozess existiert, so bilde R = R + Bi
(er gibt ja alle Ressourcen wieder frei, wenn er terminiert),
markiere den Prozess und gehe zu Schritt 2
4
Andernfalls terminiere das Verfahren.
Terminiert das Verfahren und es existieren nicht markierte Prozesse, so
sind diese in einem Deadlock-Zustand.
27 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Deadlockerkennungsalgorithmus
Voraussetzung: Jeder Prozess fordert alle Betriebsmittel auf einmal an.
Eine Markierung eines Prozesses bedeutet, dass er alle Ressourcen hat
und seine Ausführung beenden kann.
1
Anfänglich ist kein Prozess markiert.
2
Wähle einen beliebigen unmarkierten Prozess Pi aus, für den gilt
Ai ≤ R
(also alle Anforderungen von Pi können befriedigt werden)
3
Falls ein solcher Prozess existiert, so bilde R = R + Bi
(er gibt ja alle Ressourcen wieder frei, wenn er terminiert),
markiere den Prozess und gehe zu Schritt 2
4
Andernfalls terminiere das Verfahren.
Terminiert das Verfahren und es existieren nicht markierte Prozesse, so
sind diese in einem Deadlock-Zustand.
27 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Beispiel

0
B =  2
0
1
0
0
1
1
0
2
Plotter
Drucker
CD-ROM
Betriebsmittelvektor V = (
Betriebsmittelrestevektor R = (
Algorithmus
Bandgerät
Ausgangssituation
4
2
2
1
3
0
1
0


0
2
1 A =  1
0
2
0
0
1
0
1
0

1
0 
0
)
)
1
Anfänglich ist kein Prozess markiert.
2
Wähle einen beliebigen unmarkierten Prozess Pi aus, für
den gilt Ai ≤ R
(also alle Anforderungen von Pi können befriedigt werden)
3
Falls ein solcher Prozess existiert, so bilde R = R + Bi
(er gibt ja alle Ressourcen wieder frei, wenn er terminiert),
markiere den Prozess und gehe zu Schritt 2
4
Andernfalls terminiere das Verfahren.
markierte Prozesse: {}
28 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Beispiel

0
B =  2
0
1
2
0
0
1
1
0
2
Plotter
Drucker
CD-ROM
Betriebsmittelvektor V = (
Betriebsmittelrestevektor R = (
Algorithmus
Bandgerät
Ausgangssituation
4
2
2
1
3
0
1
0


0
2
1 A =  1
0
2
0
0
1
0
1
0

1
0 
0
)
)
1
Anfänglich ist kein Prozess markiert.
2
Wähle einen beliebigen unmarkierten Prozess Pi aus, für
den gilt Ai ≤ R
(also alle Anforderungen von Pi können befriedigt werden)
3
Falls ein solcher Prozess existiert, so bilde R = R + Bi
(er gibt ja alle Ressourcen wieder frei, wenn er terminiert),
markiere den Prozess und gehe zu Schritt 2
4
Andernfalls terminiere das Verfahren.
markierte Prozesse: {}
nur P3 kann gewählt werden, denn A1 ≤ R nicht erfüllt erfüllt (CD Rom
fehlt), A2 ≤ R auch nicht erfüllt
28 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Beispiel

0
B =  2
0
1
2
0
0
1
1
0
2
Plotter
Drucker
CD-ROM
Betriebsmittelvektor V = (
Betriebsmittelrestevektor R = (
Algorithmus
Bandgerät
Ausgangssituation
4
2
2
1
3
0
1
0


0
2
1 A =  1
0
2
0
0
1
0
1
0

1
0 
0
)
)
1
Anfänglich ist kein Prozess markiert.
2
Wähle einen beliebigen unmarkierten Prozess Pi aus, für
den gilt Ai ≤ R
(also alle Anforderungen von Pi können befriedigt werden)
3
Falls ein solcher Prozess existiert, so bilde R = R + Bi
(er gibt ja alle Ressourcen wieder frei, wenn er terminiert),
markiere den Prozess und gehe zu Schritt 2
4
Andernfalls terminiere das Verfahren.
markierte Prozesse: {}
nur P3 kann gewählt werden, denn A1 ≤ R nicht erfüllt erfüllt (CD Rom
fehlt), A2 ≤ R auch nicht erfüllt
28 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Beispiel

0
B =  2
0
1
2
3
0
0
1
1
0
2
Plotter
Drucker
CD-ROM
Betriebsmittelvektor V = (
Betriebsmittelrestevektor R = (
Algorithmus
Bandgerät
Ausgangssituation
4
2
2
1
3
0
1
0


0
2
1 A =  1
0
2
0
0
1
0
1
0

1
0 
0
)
)
1
Anfänglich ist kein Prozess markiert.
2
Wähle einen beliebigen unmarkierten Prozess Pi aus, für
den gilt Ai ≤ R
(also alle Anforderungen von Pi können befriedigt werden)
3
Falls ein solcher Prozess existiert, so bilde R = R + Bi
(er gibt ja alle Ressourcen wieder frei, wenn er terminiert),
markiere den Prozess und gehe zu Schritt 2
4
Andernfalls terminiere das Verfahren.
markierte Prozesse: {}
nur P3 kann gewählt werden, denn A1 ≤ R nicht erfüllt erfüllt (CD Rom
fehlt), A2 ≤ R auch nicht erfüllt
P3 arbeitet, d.h. R = (0000) markierte Prozesse: {P3}, P3 terminiert, d.h.
alle Ressourcen von P3 werden freigegeben, damit ist R = (2220)
28 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Beispiel

0
B =  2
0
1
2
3
0
0
1
1
0
2
Plotter
Drucker
CD-ROM
Betriebsmittelvektor V = (
Betriebsmittelrestevektor R = (
Algorithmus
Bandgerät
Ausgangssituation
4
2
2
1
3
0
1
0


0
2
1 A =  1
0
2
0
0
1
0
1
0

1
0 
0
)
)
1
Anfänglich ist kein Prozess markiert.
2
Wähle einen beliebigen unmarkierten Prozess Pi aus, für
den gilt Ai ≤ R
(also alle Anforderungen von Pi können befriedigt werden)
3
Falls ein solcher Prozess existiert, so bilde R = R + Bi
(er gibt ja alle Ressourcen wieder frei, wenn er terminiert),
markiere den Prozess und gehe zu Schritt 2
4
Andernfalls terminiere das Verfahren.
markierte Prozesse: {}
nur P3 kann gewählt werden, denn A1 ≤ R nicht erfüllt erfüllt (CD Rom
fehlt), A2 ≤ R auch nicht erfüllt
P3 arbeitet, d.h. R = (0000) markierte Prozesse: {P3}, P3 terminiert, d.h.
alle Ressourcen von P3 werden freigegeben, damit ist R = (2220)
28 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Beispiel

0
B =  2
0
1
2
3
4
0
0
1
1
0
2
Plotter
Drucker
CD-ROM
Betriebsmittelvektor V = (
Betriebsmittelrestevektor R = (
Algorithmus
Bandgerät
Ausgangssituation
4
2
2
1
3
0
1
0


0
2
1 A =  1
0
2
0
0
1
0
1
0

1
0 
0
)
)
1
Anfänglich ist kein Prozess markiert.
2
Wähle einen beliebigen unmarkierten Prozess Pi aus, für
den gilt Ai ≤ R
(also alle Anforderungen von Pi können befriedigt werden)
3
Falls ein solcher Prozess existiert, so bilde R = R + Bi
(er gibt ja alle Ressourcen wieder frei, wenn er terminiert),
markiere den Prozess und gehe zu Schritt 2
4
Andernfalls terminiere das Verfahren.
markierte Prozesse: {}
nur P3 kann gewählt werden, denn A1 ≤ R nicht erfüllt erfüllt (CD Rom
fehlt), A2 ≤ R auch nicht erfüllt
P3 arbeitet, d.h. R = (0000) markierte Prozesse: {P3}, P3 terminiert, d.h.
alle Ressourcen von P3 werden freigegeben, damit ist R = (2220)
nun wird P2 ausgeführt, danach ist R = (4221) und P1 kann arbeiten,
markierte Prozesse: {P1, P2, P3} also kein Deadlock.
28 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Beispiel

0
B =  2
0
1
2
3
4
0
0
1
1
0
2
Plotter
Drucker
CD-ROM
Betriebsmittelvektor V = (
Betriebsmittelrestevektor R = (
Algorithmus
Bandgerät
Ausgangssituation
4
2
2
1
3
0
1
0


0
2
1 A =  1
0
2
0
0
1
0
1
0

1
0 
0
)
)
1
Anfänglich ist kein Prozess markiert.
2
Wähle einen beliebigen unmarkierten Prozess Pi aus, für
den gilt Ai ≤ R
(also alle Anforderungen von Pi können befriedigt werden)
3
Falls ein solcher Prozess existiert, so bilde R = R + Bi
(er gibt ja alle Ressourcen wieder frei, wenn er terminiert),
markiere den Prozess und gehe zu Schritt 2
4
Andernfalls terminiere das Verfahren.
markierte Prozesse: {}
nur P3 kann gewählt werden, denn A1 ≤ R nicht erfüllt erfüllt (CD Rom
fehlt), A2 ≤ R auch nicht erfüllt
P3 arbeitet, d.h. R = (0000) markierte Prozesse: {P3}, P3 terminiert, d.h.
alle Ressourcen von P3 werden freigegeben, damit ist R = (2220)
nun wird P2 ausgeführt, danach ist R = (4221) und P1 kann arbeiten,
markierte Prozesse: {P1, P2, P3} also kein Deadlock.
28 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Hörsaalübung
Was passiert in der u.a. Situation?
(Prozess 3 fordert zusätzlich noch ein CD-Rom Laufwerk an)

0
B =  2
0
0
0
1
1
0
2
Plotter
Drucker
CD-ROM
Betriebsmittelvektor V = (
Betriebsmittelrestevektor R = (
Algorithmus
Bandgerät
Ausgangssituation
4
2
2
1
3
0
1
0


0
2
1 A =  1
0
2
0
0
1
0
1
0

1
0 
1
)
)
1
Anfänglich ist kein Prozess markiert.
2
Wähle einen beliebigen unmarkierten Prozess Pi aus, für
den gilt Ai ≤ R
(also alle Anforderungen von Pi können befriedigt werden)
3
Falls ein solcher Prozess existiert, so bilde R = R + Bi
(er gibt ja alle Ressourcen wieder frei, wenn er terminiert),
markiere den Prozess und gehe zu Schritt 2
4
Andernfalls terminiere das Verfahren.
,→ Tafel
29 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Deadlock-Verhinderung
Die Voraussetzung bei der Deadlock-Erkennung war, dass ein Prozess
seine Betriebsmittel auf einen Schlag anfordert und zugeteilt bekommt.
Dies ist nicht realistisch, Betriebsmittel werden i.A. nacheinander
angefordert und freigegeben.
Das Betriebssystem muss dann entscheiden,
1
ob ein Betriebsmittel-Zuteilung sicher ist oder nicht
2
und nur im sicheren Fall die Zuteilung erlauben.
Deadlock-Verhinderungsalgorithmen basieren auf dem Konzept der
sicheren Zustände.
30 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Betriebsmittelflugbahnen
Betriebsmittelflugbahnen
2 Prozesse A und B, die je einen Drucker und einen Plotter benötigen.
• Jeder Punkt repräsentiert einen
gemeinsamen Zustand von A und B.
• Bevor A und B starten, sind wir im
Punkt p.
B
u
I8
sicher
Drucker
I7
unsicher
sicher
• Der Scheduler wählt A, wir gelangen
zu Punkt q; der Scheduler wählt B
und wir sind in r.
• Das BS darf keine Flugbahn durch
eine unsichere Region erlauben,
ansonsten kann ein Deadlock
entstehen (z.B. Punkt t).
• Zum Zeitpunkt t muss also das BS
I6
Plotter
sicher
I5
t
r
sicher
sicher
s
A
p
q
I1
I2
I3
I4
Drucker
Plotter
Abbildung: Betriebsmittelflugbahn mit 2
Prozessen A und B
entscheiden, B zu suspendieren bis A
beendet ist.
31 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Sichere und unsichere Zustände
Sichere und unsichere Zustände
Der Deadlock-Verhinderungsalgorithmus verwendet die bekannten
Betriebsmittelvektoren, um sichere Zustände zu erkennen.
Def: sicherer Zustand
Ein Zustand ist sicher, wenn er kein Deadlockzustand ist und es
ein Möglichkeit gibt, alle Anforderungen zu erfüllen, indem eine
geschickte Reihenfolge der Prozesse gewählt wird.
32 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Sichere und unsichere Zustände
Sichere und unsichere Zustände
Beispiel mit einer Betriebsmittelklasse
(10 Einheiten insgesamt verfügbar):
• Prozess A hat aktuell 3 Einheiten, er
benötigt insgesamt 9.
• Prozess B hat aktuell 2 Einheiten, er
benötigt insgesamt 4.
• Ist dies ein sicherer Zustand ?
A
B
C
akt max
3
9
2
4
2
7
frei: 3
33 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Sichere und unsichere Zustände
Zustand ist sicher
Es gibt eine Abfolge von Prozessen:
A
B
C
akt
max
3
9
2
4
2
7
(1) frei: 3
1
2
A
B
C
akt
max
3
9
4
4
2
7
(2) frei: 1
A
B
C
akt
max
3
9
0
2
7
(3) frei: 5
A
B
C
akt
max
3
9
0
7
7
(4) frei: 0
A
B
C
akt
max
3
9
0
0
(5) frei: 7
Ausgangssituation
B wird gewählt
34 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Sichere und unsichere Zustände
Zustand ist sicher
Es gibt eine Abfolge von Prozessen:
A
B
C
akt
max
3
9
2
4
2
7
(1) frei: 3
A
B
C
akt
max
3
9
4
4
2
7
(2) frei: 1
A
B
C
akt
max
3
9
0
2
7
(3) frei: 5
2
Ausgangssituation
B wird gewählt
3
B ist beendet, gibt Mittel frei
1
A
B
C
akt
max
3
9
0
7
7
(4) frei: 0
A
B
C
akt
max
3
9
0
0
(5) frei: 7
34 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Sichere und unsichere Zustände
Zustand ist sicher
Es gibt eine Abfolge von Prozessen:
A
B
C
akt
max
3
9
2
4
2
7
(1) frei: 3
A
B
C
akt
max
3
9
4
4
2
7
(2) frei: 1
A
B
C
akt
max
3
9
0
2
7
(3) frei: 5
2
Ausgangssituation
B wird gewählt
3
B ist beendet, gibt Mittel frei
4
Scheduler wählt C
1
A
B
C
akt
max
3
9
0
7
7
(4) frei: 0
A
B
C
akt
max
3
9
0
0
(5) frei: 7
34 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Sichere und unsichere Zustände
Zustand ist sicher
Es gibt eine Abfolge von Prozessen:
A
B
C
akt
max
3
9
2
4
2
7
(1) frei: 3
A
B
C
akt
max
3
9
4
4
2
7
(2) frei: 1
A
B
C
akt
max
3
9
0
2
7
(3) frei: 5
2
Ausgangssituation
B wird gewählt
3
B ist beendet, gibt Mittel frei
1
4
Scheduler wählt C
5
C ist beendet
A
B
C
akt
max
3
9
0
7
7
(4) frei: 0
A
B
C
akt
max
3
9
0
0
(5) frei: 7
34 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Sichere und unsichere Zustände
Zustand ist sicher
Es gibt eine Abfolge von Prozessen:
A
B
C
akt
max
3
9
2
4
2
7
(1) frei: 3
A
B
C
akt
max
3
9
4
4
2
7
(2) frei: 1
A
B
C
akt
max
3
9
0
2
7
(3) frei: 5
2
Ausgangssituation
B wird gewählt
3
B ist beendet, gibt Mittel frei
1
A
B
C
4
Scheduler wählt C
5
C ist beendet
6
nun kann A 6 weitere Einheiten bekommen.
akt
max
3
9
0
7
7
(4) frei: 0
A
B
C
akt
max
3
9
0
0
(5) frei: 7
Alle Prozesse konnten beendet werden: Ausgangszustand war sicher !
34 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Sichere und unsichere Zustände
Zustand ist sicher
Es gibt eine Abfolge von Prozessen:
A
B
C
akt
max
3
9
2
4
2
7
(1) frei: 3
A
B
C
akt
max
3
9
4
4
2
7
(2) frei: 1
A
B
C
akt
max
3
9
0
2
7
(3) frei: 5
2
Ausgangssituation
B wird gewählt
3
B ist beendet, gibt Mittel frei
1
A
B
C
4
Scheduler wählt C
5
C ist beendet
6
nun kann A 6 weitere Einheiten bekommen.
akt
max
3
9
0
7
7
(4) frei: 0
A
B
C
akt
max
3
9
0
0
(5) frei: 7
Alle Prozesse konnten beendet werden: Ausgangszustand war sicher !
34 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Sichere und unsichere Zustände
Beispiel für unsicheren Zustand
akt
max
3
9
2
4
2
7
(1) frei: 3
A
B
C
A
B
C
akt
max
4
9
2
4
2
7
(2) frei: 2
A
B
C
akt
max
4
9
4
4
2
7
(3) frei: 0
1
Ausgangssituation
2
Prozeß A fordert eine Einheit an, er wird ausgewählt.
Gibt es jetzt noch eine Folge ?
3
Versuchen wir B: B erhält alle Mittel
4
B gibt sie frei
A
B
C
akt
max
4
9
0
2
7
(4) frei: 4
Nur noch 4 Betriebsmittel, aber A und C benötigen 5 !
Der Schritt 1, (A eine Einheit geben war falsch!)
35 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Bankier-Algorithmus für eine Betriebsmittelklasse
Bankier-Algorithmus für eine Betriebsmittelklasse
Dijkstra hat 1965 den Bankier-Algorithmus vorgestellt.
• Der Bankier betreut Kunden (Prozesse), die jeweils einen
Kreditrahmen (maximale Betriebsmittel-Anforderung) eingeräumt
bekommen.
36 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Bankier-Algorithmus für eine Betriebsmittelklasse
Bankier-Algorithmus für eine Betriebsmittelklasse
Dijkstra hat 1965 den Bankier-Algorithmus vorgestellt.
• Der Bankier betreut Kunden (Prozesse), die jeweils einen
Kreditrahmen (maximale Betriebsmittel-Anforderung) eingeräumt
bekommen.
• Von Zeit zu Zeit kommt ein Kunde und beantragt ein Darlehen, das
den Kreditrahmen insgesamt über alle seine bereits erhaltenen
Zahlungen nicht übersteigt.
36 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Bankier-Algorithmus für eine Betriebsmittelklasse
Bankier-Algorithmus für eine Betriebsmittelklasse
Dijkstra hat 1965 den Bankier-Algorithmus vorgestellt.
• Der Bankier betreut Kunden (Prozesse), die jeweils einen
Kreditrahmen (maximale Betriebsmittel-Anforderung) eingeräumt
bekommen.
• Von Zeit zu Zeit kommt ein Kunde und beantragt ein Darlehen, das
den Kreditrahmen insgesamt über alle seine bereits erhaltenen
Zahlungen nicht übersteigt.
• Der Bankier kann einem Kunden den Kreditwunsch verweigern, wenn
die Gefahr besteht, dass die Bank unzureichende Reserven für
weitere Kunden hat, die es den Kunden ermöglichen, ihre bereits
erhaltenen Kredite zurückzahlen zu können.
36 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Bankier-Algorithmus für eine Betriebsmittelklasse
Bankier-Algorithmus für eine Betriebsmittelklasse
Dijkstra hat 1965 den Bankier-Algorithmus vorgestellt.
• Der Bankier betreut Kunden (Prozesse), die jeweils einen
Kreditrahmen (maximale Betriebsmittel-Anforderung) eingeräumt
bekommen.
• Von Zeit zu Zeit kommt ein Kunde und beantragt ein Darlehen, das
den Kreditrahmen insgesamt über alle seine bereits erhaltenen
Zahlungen nicht übersteigt.
• Der Bankier kann einem Kunden den Kreditwunsch verweigern, wenn
die Gefahr besteht, dass die Bank unzureichende Reserven für
weitere Kunden hat, die es den Kunden ermöglichen, ihre bereits
erhaltenen Kredite zurückzahlen zu können.
• Der Bankier prüft bei einem Darlehensantrag, ob die Zuteilung zu
einem sicheren Zustand führt. Ist das nicht der Fall, wird die
Zuteilung aufgeschoben, ansonsten gezahlt.
36 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Bankier-Algorithmus für eine Betriebsmittelklasse
Bankier-Algorithmus für eine Betriebsmittelklasse
Dijkstra hat 1965 den Bankier-Algorithmus vorgestellt.
• Der Bankier betreut Kunden (Prozesse), die jeweils einen
Kreditrahmen (maximale Betriebsmittel-Anforderung) eingeräumt
bekommen.
• Von Zeit zu Zeit kommt ein Kunde und beantragt ein Darlehen, das
den Kreditrahmen insgesamt über alle seine bereits erhaltenen
Zahlungen nicht übersteigt.
• Der Bankier kann einem Kunden den Kreditwunsch verweigern, wenn
die Gefahr besteht, dass die Bank unzureichende Reserven für
weitere Kunden hat, die es den Kunden ermöglichen, ihre bereits
erhaltenen Kredite zurückzahlen zu können.
• Der Bankier prüft bei einem Darlehensantrag, ob die Zuteilung zu
einem sicheren Zustand führt. Ist das nicht der Fall, wird die
Zuteilung aufgeschoben, ansonsten gezahlt.
36 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Bankier-Algorithmus für eine Betriebsmittelklasse
Bankier-Algorithmus: Überprüfung ob Zustand sicher ist
Die Überprüfung simuliert die Darlehensvergabe der Kunden. Wenn
alle Kunden dabei befriedigt werden können, ist der Zustand sicher und
der aktuelle Darlehensantrag wird gewährt.
• Zunächst wird geprüft, ob noch ausreichende Mittel für einige
Kunden zur Verfügung stehen.
37 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Bankier-Algorithmus für eine Betriebsmittelklasse
Bankier-Algorithmus: Überprüfung ob Zustand sicher ist
Die Überprüfung simuliert die Darlehensvergabe der Kunden. Wenn
alle Kunden dabei befriedigt werden können, ist der Zustand sicher und
der aktuelle Darlehensantrag wird gewährt.
• Zunächst wird geprüft, ob noch ausreichende Mittel für einige
Kunden zur Verfügung stehen.
• Dann wählt er den Kunden, bei dem der Kreditrahmen am
weitesten ausgeschöpft ist und simuliert dessen Zusage.
37 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Bankier-Algorithmus für eine Betriebsmittelklasse
Bankier-Algorithmus: Überprüfung ob Zustand sicher ist
Die Überprüfung simuliert die Darlehensvergabe der Kunden. Wenn
alle Kunden dabei befriedigt werden können, ist der Zustand sicher und
der aktuelle Darlehensantrag wird gewährt.
• Zunächst wird geprüft, ob noch ausreichende Mittel für einige
Kunden zur Verfügung stehen.
• Dann wählt er den Kunden, bei dem der Kreditrahmen am
weitesten ausgeschöpft ist und simuliert dessen Zusage.
• Dann wird der nächste Kunde simuliert.
37 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Bankier-Algorithmus für eine Betriebsmittelklasse
Bankier-Algorithmus: Überprüfung ob Zustand sicher ist
Die Überprüfung simuliert die Darlehensvergabe der Kunden. Wenn
alle Kunden dabei befriedigt werden können, ist der Zustand sicher und
der aktuelle Darlehensantrag wird gewährt.
• Zunächst wird geprüft, ob noch ausreichende Mittel für einige
Kunden zur Verfügung stehen.
• Dann wählt er den Kunden, bei dem der Kreditrahmen am
weitesten ausgeschöpft ist und simuliert dessen Zusage.
• Dann wird der nächste Kunde simuliert.
• Wenn letztlich alle Darlehen zurückgezahlt werden können, war der
Zustand sicher.
37 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Bankier-Algorithmus für eine Betriebsmittelklasse
Bankier-Algorithmus: Überprüfung ob Zustand sicher ist
Die Überprüfung simuliert die Darlehensvergabe der Kunden. Wenn
alle Kunden dabei befriedigt werden können, ist der Zustand sicher und
der aktuelle Darlehensantrag wird gewährt.
• Zunächst wird geprüft, ob noch ausreichende Mittel für einige
Kunden zur Verfügung stehen.
• Dann wählt er den Kunden, bei dem der Kreditrahmen am
weitesten ausgeschöpft ist und simuliert dessen Zusage.
• Dann wird der nächste Kunde simuliert.
• Wenn letztlich alle Darlehen zurückgezahlt werden können, war der
Zustand sicher.
37 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Bankier-Algorithmus für mehrere Betriebsmittelklassen
Bankier-Algorithmus für mehrere Betriebsmittelklassen
Der Bankier-Algorithmus kann auf mehrere Betriebsmittelklassen
erweitert werden.
Verwendet wird die Belegungsmatrix B, die Anforderungsmatrix A, der
Restevektor R.
Die Prüfung, ob ein Zustand sicher ist:
1
Suche eine Zeile (Prozess) i in A, für die gilt Ai ≤ R.
Falls es keine solche Zeile gibt, wird das System einen
Deadlock-Zustand erreichen, da kein Prozess seine Berechnungen
vollständig ausführen kann.
38 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Bankier-Algorithmus für mehrere Betriebsmittelklassen
Bankier-Algorithmus für mehrere Betriebsmittelklassen
Der Bankier-Algorithmus kann auf mehrere Betriebsmittelklassen
erweitert werden.
Verwendet wird die Belegungsmatrix B, die Anforderungsmatrix A, der
Restevektor R.
Die Prüfung, ob ein Zustand sicher ist:
1
2
Suche eine Zeile (Prozess) i in A, für die gilt Ai ≤ R.
Falls es keine solche Zeile gibt, wird das System einen
Deadlock-Zustand erreichen, da kein Prozess seine Berechnungen
vollständig ausführen kann.
Es wird angenommen, Prozess i wird beendet. Markiere i als
terminiert und füge seine freigegebenen Mittel zu R hinzu, also
R = R + Bi
38 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Bankier-Algorithmus für mehrere Betriebsmittelklassen
Bankier-Algorithmus für mehrere Betriebsmittelklassen
Der Bankier-Algorithmus kann auf mehrere Betriebsmittelklassen
erweitert werden.
Verwendet wird die Belegungsmatrix B, die Anforderungsmatrix A, der
Restevektor R.
Die Prüfung, ob ein Zustand sicher ist:
1
2
3
Suche eine Zeile (Prozess) i in A, für die gilt Ai ≤ R.
Falls es keine solche Zeile gibt, wird das System einen
Deadlock-Zustand erreichen, da kein Prozess seine Berechnungen
vollständig ausführen kann.
Es wird angenommen, Prozess i wird beendet. Markiere i als
terminiert und füge seine freigegebenen Mittel zu R hinzu, also
R = R + Bi
Wiederhole 1) und 2) solange, bis entweder alle Prozesse als
terminiert markiert sind, und der Anfangszustand sicher ist, oder bis
ein Deadlockzustand auftritt und damit der Anfangszustand unsicher
ist.
38 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Bankier-Algorithmus für mehrere Betriebsmittelklassen
Bankier-Algorithmus für mehrere Betriebsmittelklassen
Der Bankier-Algorithmus kann auf mehrere Betriebsmittelklassen
erweitert werden.
Verwendet wird die Belegungsmatrix B, die Anforderungsmatrix A, der
Restevektor R.
Die Prüfung, ob ein Zustand sicher ist:
1
2
3
Suche eine Zeile (Prozess) i in A, für die gilt Ai ≤ R.
Falls es keine solche Zeile gibt, wird das System einen
Deadlock-Zustand erreichen, da kein Prozess seine Berechnungen
vollständig ausführen kann.
Es wird angenommen, Prozess i wird beendet. Markiere i als
terminiert und füge seine freigegebenen Mittel zu R hinzu, also
R = R + Bi
Wiederhole 1) und 2) solange, bis entweder alle Prozesse als
terminiert markiert sind, und der Anfangszustand sicher ist, oder bis
ein Deadlockzustand auftritt und damit der Anfangszustand unsicher
ist.
38 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Bankier-Algorithmus für mehrere Betriebsmittelklassen
Bankier-Algorithmus: Zustand sicher prüfen
Prozess mit erfüllbaren
Anforderungen suchen
Prozess gefunden
angeforderte
Betriebsmittel
zuteilen
Prozess markieren
Prozess kann
terminieren, gibt
Betriebsmittel frei
noch unmarkierte
Prozesse
alle Prozesse markiert: Zustand ist sicher
39 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Bankier-Algorithmus für mehrere Betriebsmittelklassen
Beurteilung Bankier-Algorithmus
• Der Bankier-Algorithmus ist sehr gut untersucht.
• Die Voraussetzung für die Simulation (jeder Prozess kann alle seine
Betriebsmittel-Anforderungen beim Start bekannt machen), sind in
der Praxis nicht gegeben.
wieso eigentlich nicht ?
• Die Betriebsmittel können dynamisch in ihrer Anzahl variieren (ein
Drucker fällt aus).
Insgesamt wird der Algorithmus (und die Verhinderung insgesamt) in
aktuellen Betriebssystemen nicht eingesetzt.
40 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Verhinderung
Bankier-Algorithmus für mehrere Betriebsmittelklassen
Beurteilung Bankier-Algorithmus
• Der Bankier-Algorithmus ist sehr gut untersucht.
• Die Voraussetzung für die Simulation (jeder Prozess kann alle seine
Betriebsmittel-Anforderungen beim Start bekannt machen), sind in
der Praxis nicht gegeben.
wieso eigentlich nicht ?
• Die Betriebsmittel können dynamisch in ihrer Anzahl variieren (ein
Drucker fällt aus).
Insgesamt wird der Algorithmus (und die Verhinderung insgesamt) in
aktuellen Betriebssystemen nicht eingesetzt.
40 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Vermeidung
Deadlock-Vermeidung
Wenn sichergestellt werden könnten, dass nicht alle vier u.a.
Bedingungen gleichzeitig eintreten könnten, wäre Deadlocks nicht
möglich (strukturelle Vermeidung).
1
Wechselseitiger Ausschluss
41 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Vermeidung
Deadlock-Vermeidung
Wenn sichergestellt werden könnten, dass nicht alle vier u.a.
Bedingungen gleichzeitig eintreten könnten, wäre Deadlocks nicht
möglich (strukturelle Vermeidung).
1
Wechselseitiger Ausschluss
2
Anforderung weitere Betriebsmittel
41 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Vermeidung
Deadlock-Vermeidung
Wenn sichergestellt werden könnten, dass nicht alle vier u.a.
Bedingungen gleichzeitig eintreten könnten, wäre Deadlocks nicht
möglich (strukturelle Vermeidung).
1
Wechselseitiger Ausschluss
2
Anforderung weitere Betriebsmittel
Ununterbrechbarkeit
3
41 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Vermeidung
Deadlock-Vermeidung
Wenn sichergestellt werden könnten, dass nicht alle vier u.a.
Bedingungen gleichzeitig eintreten könnten, wäre Deadlocks nicht
möglich (strukturelle Vermeidung).
1
Wechselseitiger Ausschluss
2
3
Anforderung weitere Betriebsmittel
Ununterbrechbarkeit
4
Zyklische Wartebedingung
Dies ist aber in der Praxis nicht möglich, also ist dies kein gangbarer Weg.
41 / 41
Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65)
ARSnova 19226584
Deadlock-Vermeidung
Deadlock-Vermeidung
Wenn sichergestellt werden könnten, dass nicht alle vier u.a.
Bedingungen gleichzeitig eintreten könnten, wäre Deadlocks nicht
möglich (strukturelle Vermeidung).
1
Wechselseitiger Ausschluss
2
3
Anforderung weitere Betriebsmittel
Ununterbrechbarkeit
4
Zyklische Wartebedingung
Dies ist aber in der Praxis nicht möglich, also ist dies kein gangbarer Weg.
41 / 41