close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Betriebssysteme - Deadlocks

EinbettenHerunterladen
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Betriebssysteme - Deadlocks
→ alois.schuette@h-da.de
Version: WS2014(967c57d)
Alois Sch¨
utte
21. Oktober 2014
1 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Inhaltsverzeichnis
Dieser Teil er¨
ortert 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 k¨
onnen.
¨
1 Uberblick
2 Ignorieren des Problems
3 Deadlock-Erkennung und -Behebung
Ein Betriebsmittel je Klasse
Mehrere Betriebsmittel je Klasse
4 Deadlock-Verhinderung
Betriebsmittelflugbahnen
Sichere und unsichere Zust¨ande
Bankier-Algorithmus f¨
ur eine Betriebsmittelklasse
Bankier-Algorithmus f¨
ur mehrere Betriebsmittelklassen
5 Deadlock-Vermeidung
2 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
¨
Uberblick
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 ausgel¨ost werden kann.
Da alle am Deadlock beteiligten Prozesse warten, kann keiner ein Ereignis
ausl¨
osen, so dass ein anderer geweckt wird. Also warten alle beteiligten
Prozesse ewig.
3 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
¨
Uberblick
Beispiel aus der realen Welt
Abbildung: 4 Autos an Kreuzung ohne Verkehrsschilder
Welche Beispiele f¨
ur Deadlocks kennen Sie?
4 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
¨
Uberblick
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 : m¨
o chte noch Hannah " );
synchronized ( resource2 ) {
System . out . println ( " as : habe Hannah " );
}
17
18
19
20
21
}
22
}
23
24
};
5 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
¨
Uberblick
// 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 : m¨
o 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 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
¨
Uberblick
Bedingungen f¨ur Deadlocks
Damit ein Deadlock entsteht, m¨
ussen alle vier folgenden Bedingungen
erf¨
ullt sein:
1
Wechselseitiger Ausschluss:
Jedes Betriebsmittel wird entweder von genau einem Prozess belegt
oder es ist verf¨
ugbar.
7 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
¨
Uberblick
Bedingungen f¨ur Deadlocks
Damit ein Deadlock entsteht, m¨
ussen alle vier folgenden Bedingungen
erf¨
ullt sein:
1
Wechselseitiger Ausschluss:
Jedes Betriebsmittel wird entweder von genau einem Prozess belegt
oder es ist verf¨
ugbar.
2
Anforderung weitere Betriebsmittel:
Ein Prozess, der bereits Betriebsmittel belegt hat, kann weitere
Betriebsmittel anfordern.
7 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
¨
Uberblick
Bedingungen f¨ur Deadlocks
Damit ein Deadlock entsteht, m¨
ussen alle vier folgenden Bedingungen
erf¨
ullt sein:
1
Wechselseitiger Ausschluss:
Jedes Betriebsmittel wird entweder von genau einem Prozess belegt
oder es ist verf¨
ugbar.
2
Anforderung weitere Betriebsmittel:
Ein Prozess, der bereits Betriebsmittel belegt hat, kann weitere
Betriebsmittel anfordern.
3
Ununterbrechbarkeit:
Die von einem Prozess belegten Betriebsmittel k¨
onnen nicht von
außen entzogen werden; der Prozess selbst muss sie explizit
freigeben.
7 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
¨
Uberblick
Bedingungen f¨ur Deadlocks
Damit ein Deadlock entsteht, m¨
ussen alle vier folgenden Bedingungen
erf¨
ullt sein:
1
Wechselseitiger Ausschluss:
Jedes Betriebsmittel wird entweder von genau einem Prozess belegt
oder es ist verf¨
ugbar.
2
Anforderung weitere Betriebsmittel:
Ein Prozess, der bereits Betriebsmittel belegt hat, kann weitere
Betriebsmittel anfordern.
3
Ununterbrechbarkeit:
Die von einem Prozess belegten Betriebsmittel k¨
onnen 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 n¨achsten Prozess der
Kette belegt ist.
7 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
¨
Uberblick
Bedingungen f¨ur Deadlocks
Damit ein Deadlock entsteht, m¨
ussen alle vier folgenden Bedingungen
erf¨
ullt sein:
1
Wechselseitiger Ausschluss:
Jedes Betriebsmittel wird entweder von genau einem Prozess belegt
oder es ist verf¨
ugbar.
2
Anforderung weitere Betriebsmittel:
Ein Prozess, der bereits Betriebsmittel belegt hat, kann weitere
Betriebsmittel anfordern.
3
Ununterbrechbarkeit:
Die von einem Prozess belegten Betriebsmittel k¨
onnen 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 n¨achsten Prozess der
Kette belegt ist.
7 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
¨
Uberblick
Betriebsmittel-Graphen
Man kann die Beziehung von Betriebsmitteln und Prozessen durch
bipartite gerichtete Graphen darstellen
• Die Knoten des Graphen sind unterteilt in:
8 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
¨
Uberblick
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 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
¨
Uberblick
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 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
¨
Uberblick
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 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
¨
Uberblick
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 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
¨
Uberblick
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 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
¨
Uberblick
Beispiel f¨ur 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 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
¨
Uberblick
Betriebsmittel-Graphen sind Hilfsmittel f¨
ur das Betriebssystem, um
Abfolgen von Anforderungen und Freigaben von Betriebsmitteln durch
Prozesse verwalten zu k¨
onnen, 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 ben¨
otigt B1 und B2
• P2 ben¨
otigt B2 und B3
• P3 ben¨
otigt B3 und B1
Welche Situationen (Reihenfolge der Betriebsmittelzuteilung) f¨
uhren zu
Deadlocks?
10 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
¨
Uberblick
Keine Nebenl¨
aufigkeit, d.h. Betriebssystem w¨ahlt zuerst P1, dann P2
und am Schluss P3, wobei jeder Prozess vollst¨andig abgearbeitet wird:
P1 fordert B1 an
P1 fordert B2 an
P1 gibt B1 und B2 frei
P2 fordert B2 an
P2 fordert B3 an
P2 gibt B2 und B3 frei
P3 fordert B1 an
P3 forbert B3 an
P3 gibt B1 und B3 frei
P1
P2
P3
B2
B1
B3
P1
P2
P3
B2
B1
B3
P1
P2
P3
B2
B1
B3
kein Deadlock
11 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
¨
Uberblick
Nebenl¨aufigkeit 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
12 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
¨
Uberblick
Nebenl¨aufigkeit 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
13 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
¨
Uberblick
Strategien der Deadlock-Behandlung
Durch geschickte Auswahl der Prozesse k¨
onnen also
Deadlock-Situationen behandelt werden. Man kann grunds¨atzlich vier
Strategien unterscheiden:
1
Ignorieren des Problems (Strategie von Unix Systemen)
2
3
Erkennen und Beheben von Deadlocks
dynamische Verhinderung durch vorsichtige
Betriebsmittelzuteilung
4
Vermeidung durch Verbieten einer der 4 notwendigen Bedingungen
Im Folgenden werden diese Arten des Umgangs mit Deadlocks
verdeutlicht.
14 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Ignorieren des Problems
Vogel Strauß Algorithmus
Der Vogel-Strauß Algorithmus“ (Stecke Kopf in den Sand und verhalte
”
dich so, als g¨abe es kein Problem) geht davon aus, dass
• Deadlocks eher selten auftreten,
• Systeme h¨
aufiger 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 ge¨
offnete Datei oder nur ein Prozess je
Programm erlaubt)
In Unix ist diese Strategie gew¨ahlt.
15 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
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 verf¨
ugbar sind.
16 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
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?
17 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Erkennung und -Behebung
Ein Betriebsmittel je Klasse
L¨osung
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
18 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
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 f¨
ur Auswahlkandidaten
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 ();
// n¨
a 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) {
// f¨
u 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 );
// n¨
a 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
19 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
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 gepr¨
uft, sondern etwa nur:
• alle k Minuten oder
• wenn die Prozessorlast unter festgesetzte Schwelle f¨
allt.
20 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
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 gepr¨
uft, sondern etwa nur:
• alle k Minuten oder
• wenn die Prozessorlast unter festgesetzte Schwelle f¨
allt.
20 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Mehrere Betriebsmittel je Klasse
Wenn mehrere Instanzen einer Betriebsmittelklasse existieren, kann
folgender Matrix-basierter Ansatz gew¨ahlt 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.
21 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Mehrere Betriebsmittel je Klasse
Wenn mehrere Instanzen einer Betriebsmittelklasse existieren, kann
folgender Matrix-basierter Ansatz gew¨ahlt 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.
21 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Mehrere Betriebsmittel je Klasse
Wenn mehrere Instanzen einer Betriebsmittelklasse existieren, kann
folgender Matrix-basierter Ansatz gew¨ahlt 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 verf¨
ugbar ist, gilt:
n
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 verf¨
ugbaren Mittel
der Klasse j.
21 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Mehrere Betriebsmittel je Klasse
Wenn mehrere Instanzen einer Betriebsmittelklasse existieren, kann
folgender Matrix-basierter Ansatz gew¨ahlt 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 verf¨
ugbar ist, gilt:
n
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 verf¨
ugbaren Mittel
der Klasse j.
21 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Betriebsmittelvektor V = ( 4 2 3
Betriebsmittelrestevektor R = ( 2 1 3



0 0 1 0
2 0 0 1
B =  2 0 0 1 A =  1 0 1 0
0 1 2 0
2 1 0 0
CD-ROM
Drucker
Plotter
Bandger¨at
Beispiel
1 )
0 )


Also belegt der Prozess 2 z.B. 2 Bandger¨
ate und ein CD-Rom Laufwerk und
m¨
ochte weiterhin ein weiteres Bandger¨
at und einen Drucker haben.
Der Deadlockerkennungsalgorithmus basiert auf dem Vergleich von
Vektoren. Die Relation ≤ f¨
ur 2 Vektoren A und B sei definiert als:
A ≤ B gdw. f¨
ur alle 0 ≤ i ≤ m gilt: Ai ≤ Bi
Also m¨
ussen alle Elemente von A kleiner oder gleich dem korrespondierenden
Element von B sein.
22 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Betriebsmittelvektor V = ( 4 2 3
Betriebsmittelrestevektor R = ( 2 1 3



0 0 1 0
2 0 0 1
B =  2 0 0 1 A =  1 0 1 0
0 1 2 0
2 1 0 0
CD-ROM
Drucker
Plotter
Bandger¨at
Beispiel
1 )
0 )


Also belegt der Prozess 2 z.B. 2 Bandger¨
ate und ein CD-Rom Laufwerk und
m¨
ochte weiterhin ein weiteres Bandger¨
at und einen Drucker haben.
Der Deadlockerkennungsalgorithmus basiert auf dem Vergleich von
Vektoren. Die Relation ≤ f¨
ur 2 Vektoren A und B sei definiert als:
A ≤ B gdw. f¨
ur alle 0 ≤ i ≤ m gilt: Ai ≤ Bi
Also m¨
ussen alle Elemente von A kleiner oder gleich dem korrespondierenden
Element von B sein.
22 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
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 Ausf¨
uhrung beenden kann.
1
Anf¨anglich ist kein Prozess markiert.
23 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
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 Ausf¨
uhrung beenden kann.
1
Anf¨anglich ist kein Prozess markiert.
2
W¨ahle einen beliebigen unmarkierten Prozess Pi aus, f¨
ur den gilt
Ai ≤ R
(also alle Anforderungen von Pi k¨
onnen befriedigt werden)
23 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
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 Ausf¨
uhrung beenden kann.
1
Anf¨anglich ist kein Prozess markiert.
2
W¨ahle einen beliebigen unmarkierten Prozess Pi aus, f¨
ur den gilt
Ai ≤ R
(also alle Anforderungen von Pi k¨
onnen befriedigt werden)
23 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
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 Ausf¨
uhrung beenden kann.
1
Anf¨anglich ist kein Prozess markiert.
2
W¨ahle einen beliebigen unmarkierten Prozess Pi aus, f¨
ur den gilt
Ai ≤ R
(also alle Anforderungen von Pi k¨
onnen 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
23 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
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 Ausf¨
uhrung beenden kann.
1
Anf¨anglich ist kein Prozess markiert.
2
W¨ahle einen beliebigen unmarkierten Prozess Pi aus, f¨
ur den gilt
Ai ≤ R
(also alle Anforderungen von Pi k¨
onnen 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
23 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
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 Ausf¨
uhrung beenden kann.
1
Anf¨anglich ist kein Prozess markiert.
2
W¨ahle einen beliebigen unmarkierten Prozess Pi aus, f¨
ur den gilt
Ai ≤ R
(also alle Anforderungen von Pi k¨
onnen 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.
23 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
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 Ausf¨
uhrung beenden kann.
1
Anf¨anglich ist kein Prozess markiert.
2
W¨ahle einen beliebigen unmarkierten Prozess Pi aus, f¨
ur den gilt
Ai ≤ R
(also alle Anforderungen von Pi k¨
onnen 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.
23 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
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 Ausf¨
uhrung beenden kann.
1
Anf¨anglich ist kein Prozess markiert.
2
W¨ahle einen beliebigen unmarkierten Prozess Pi aus, f¨
ur den gilt
Ai ≤ R
(also alle Anforderungen von Pi k¨
onnen 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.
23 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
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 Ausf¨
uhrung beenden kann.
1
Anf¨anglich ist kein Prozess markiert.
2
W¨ahle einen beliebigen unmarkierten Prozess Pi aus, f¨
ur den gilt
Ai ≤ R
(also alle Anforderungen von Pi k¨
onnen 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.
23 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Beispiel

0
B =  2
0
0
0
1
1
0
2
Plotter
Drucker
CD-ROM
Betriebsmittelvektor V = (
Betriebsmittelrestevektor R = (
Algorithmus
Bandger¨
at
Ausgangssituation
4
2
2
1
3
0
1
0


0
2
1 A =  1
0
2
0
0
1
0
1
0
1
Anf¨
anglich ist kein Prozess markiert.
2
W¨
ahle einen beliebigen unmarkierten Prozess Pi aus, f¨
ur
den gilt Ai ≤ R
(also alle Anforderungen von Pi k¨
onnen befriedigt werden)
)
)

1
0 
0
24 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
Beispiel

0
B =  2
0
0
0
1
1
0
2
Plotter
Drucker
CD-ROM
Betriebsmittelvektor V = (
Betriebsmittelrestevektor R = (
Algorithmus
Bandger¨
at
Ausgangssituation
4
2
2
1
3
0
1
0


0
2
1 A =  1
0
2
0
0
1
0
1
0
)
)
1
Anf¨
anglich ist kein Prozess markiert.
2
W¨
ahle einen beliebigen unmarkierten Prozess Pi aus, f¨
ur
den gilt Ai ≤ R
(also alle Anforderungen von Pi k¨
onnen 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

1
0 
0
24 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
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
Bandger¨
at
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
Anf¨
anglich ist kein Prozess markiert.
2
W¨
ahle einen beliebigen unmarkierten Prozess Pi aus, f¨
ur
den gilt Ai ≤ R
(also alle Anforderungen von Pi k¨
onnen 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: {}
24 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
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
Bandger¨
at
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
Anf¨
anglich ist kein Prozess markiert.
2
W¨
ahle einen beliebigen unmarkierten Prozess Pi aus, f¨
ur
den gilt Ai ≤ R
(also alle Anforderungen von Pi k¨
onnen 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: {}
24 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
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
Bandger¨
at
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
Anf¨
anglich ist kein Prozess markiert.
2
W¨
ahle einen beliebigen unmarkierten Prozess Pi aus, f¨
ur
den gilt Ai ≤ R
(also alle Anforderungen von Pi k¨
onnen 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 gew¨
ahlt werden, denn A1 ≤ R nicht erf¨
ullt erf¨
ullt (CD Rom
fehlt), A2 ≤ R auch nicht erf¨
ullt
24 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
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
Bandger¨
at
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
Anf¨
anglich ist kein Prozess markiert.
2
W¨
ahle einen beliebigen unmarkierten Prozess Pi aus, f¨
ur
den gilt Ai ≤ R
(also alle Anforderungen von Pi k¨
onnen 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 gew¨
ahlt werden, denn A1 ≤ R nicht erf¨
ullt erf¨
ullt (CD Rom
fehlt), A2 ≤ R auch nicht erf¨
ullt
24 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
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
Bandger¨
at
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
Anf¨
anglich ist kein Prozess markiert.
2
W¨
ahle einen beliebigen unmarkierten Prozess Pi aus, f¨
ur
den gilt Ai ≤ R
(also alle Anforderungen von Pi k¨
onnen 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 gew¨
ahlt werden, denn A1 ≤ R nicht erf¨
ullt erf¨
ullt (CD Rom
fehlt), A2 ≤ R auch nicht erf¨
ullt
P3 arbeitet, d.h. R = (0000) markierte Prozesse: {P3}, P3 terminiert, d.h.
alle Ressourcen von P3 werden freigegeben, damit ist R = (2220)
24 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
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
Bandger¨
at
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
Anf¨
anglich ist kein Prozess markiert.
2
W¨
ahle einen beliebigen unmarkierten Prozess Pi aus, f¨
ur
den gilt Ai ≤ R
(also alle Anforderungen von Pi k¨
onnen 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 gew¨
ahlt werden, denn A1 ≤ R nicht erf¨
ullt erf¨
ullt (CD Rom
fehlt), A2 ≤ R auch nicht erf¨
ullt
P3 arbeitet, d.h. R = (0000) markierte Prozesse: {P3}, P3 terminiert, d.h.
alle Ressourcen von P3 werden freigegeben, damit ist R = (2220)
24 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
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
Bandger¨
at
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
Anf¨
anglich ist kein Prozess markiert.
2
W¨
ahle einen beliebigen unmarkierten Prozess Pi aus, f¨
ur
den gilt Ai ≤ R
(also alle Anforderungen von Pi k¨
onnen 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 gew¨
ahlt werden, denn A1 ≤ R nicht erf¨
ullt erf¨
ullt (CD Rom
fehlt), A2 ≤ R auch nicht erf¨
ullt
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 ausgef¨
uhrt, danach ist R = (4221) und P1 kann arbeiten,
markierte Prozesse: {P1, P2, P3} also kein Deadlock.
24 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
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
Bandger¨
at
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
Anf¨
anglich ist kein Prozess markiert.
2
W¨
ahle einen beliebigen unmarkierten Prozess Pi aus, f¨
ur
den gilt Ai ≤ R
(also alle Anforderungen von Pi k¨
onnen 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 gew¨
ahlt werden, denn A1 ≤ R nicht erf¨
ullt erf¨
ullt (CD Rom
fehlt), A2 ≤ R auch nicht erf¨
ullt
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 ausgef¨
uhrt, danach ist R = (4221) und P1 kann arbeiten,
markierte Prozesse: {P1, P2, P3} also kein Deadlock.
24 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Erkennung und -Behebung
Mehrere Betriebsmittel je Klasse
H¨orsaal¨ubung
Was passiert in der u.a. Situation?
(Prozess 3 fordert zus¨atzlich 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
Bandger¨
at
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
Anf¨
anglich ist kein Prozess markiert.
2
W¨
ahle einen beliebigen unmarkierten Prozess Pi aus, f¨
ur
den gilt Ai ≤ R
(also alle Anforderungen von Pi k¨
onnen 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
25 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
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 Betreibsmittel-Zuteilung sicher ist oder nicht
2
und nur im sicheren Fall die Zuteilung erlauben.
Deadlock-Verhinderungsalgorithmen basieren auf dem Konzept der
sicheren Zust¨ande.
26 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Betriebsmittelflugbahnen
Betriebsmittelflugbahnen
2 Prozesse A und B, die je einen Drucker und einen Plotter ben¨otigen.
• Jeder Punkt repr¨
asentiert einen
gemeinsamen Zustand von A und B.
• Bevor A und B starten, sind wir im
Punkt p.
27 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Betriebsmittelflugbahnen
Betriebsmittelflugbahnen
2 Prozesse A und B, die je einen Drucker und einen Plotter ben¨otigen.
• Jeder Punkt repr¨
asentiert einen
gemeinsamen Zustand von A und B.
• Bevor A und B starten, sind wir im
Punkt p.
• Der Scheduler w¨
ahlt A, wir gelangen
zu Punkt q; der Scheduler w¨ahlt B
und wir sind in r.
27 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Betriebsmittelflugbahnen
Betriebsmittelflugbahnen
2 Prozesse A und B, die je einen Drucker und einen Plotter ben¨otigen.
• Jeder Punkt repr¨
asentiert einen
gemeinsamen Zustand von A und B.
• Bevor A und B starten, sind wir im
Punkt p.
• Der Scheduler w¨
ahlt A, wir gelangen
zu Punkt q; der Scheduler w¨ahlt 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).
27 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Betriebsmittelflugbahnen
Betriebsmittelflugbahnen
2 Prozesse A und B, die je einen Drucker und einen Plotter ben¨otigen.
• Jeder Punkt repr¨
asentiert 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 w¨
ahlt A, wir gelangen
zu Punkt q; der Scheduler w¨ahlt 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.
27 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Betriebsmittelflugbahnen
Betriebsmittelflugbahnen
2 Prozesse A und B, die je einen Drucker und einen Plotter ben¨otigen.
• Jeder Punkt repr¨
asentiert 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 w¨
ahlt A, wir gelangen
zu Punkt q; der Scheduler w¨ahlt 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.
27 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Sichere und unsichere Zust¨
ande
Sichere und unsichere Zust¨ande
Der Deadlock-Verhinderungsalgorithmus verwendet die bekannten
Betriebsmittelvektoren, um sichere Zust¨ande zu erkennen.
Def: sicherer Zustand
Ein Zustand ist sicher, wenn er kein Deadlockzustand ist und es
ein M¨oglichkeit gibt, alle Anforderungen zu erf¨
ullen, indem eine
geschickte Reihenfolge der Prozesse gew¨ahlt wird.
28 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Sichere und unsichere Zust¨
ande
Sichere und unsichere Zust¨ande
Beispiel mit einer Betriebsmittelklasse
(10 Einheiten insgesamt verf¨
ugbar):
• Prozess A hat aktuell 3 Einheiten, er
ben¨
otigt insgesamt 9.
• Prozess B hat aktuell 2 Einheiten, er
ben¨
otigt insgesamt 4.
• Ist dies ein sicherer Zustand ?
A
B
C
akt max
3
9
2
4
2
7
frei: 3
29 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Sichere und unsichere Zust¨
ande
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 gew¨ahlt
30 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Sichere und unsichere Zust¨
ande
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 gew¨ahlt
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
30 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Sichere und unsichere Zust¨
ande
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 gew¨ahlt
3
B ist beendet, gibt Mittel frei
4
Scheduler w¨ahlt 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
30 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Sichere und unsichere Zust¨
ande
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 gew¨ahlt
3
B ist beendet, gibt Mittel frei
1
4
Scheduler w¨ahlt 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
30 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Sichere und unsichere Zust¨
ande
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 gew¨ahlt
3
B ist beendet, gibt Mittel frei
1
A
B
C
4
Scheduler w¨ahlt 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 !
30 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Sichere und unsichere Zust¨
ande
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 gew¨ahlt
3
B ist beendet, gibt Mittel frei
1
A
B
C
4
Scheduler w¨ahlt 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 !
30 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Sichere und unsichere Zust¨
ande
Beispiel f¨ur 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 ausgew¨ahlt.
Gibt es jetzt noch eine Folge ?
3
Versuchen wir B: B erh¨alt 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 ben¨
otigen 5 !
Der Schritt 1, (A eine Einheit geben war falsch!)
31 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Bankier-Algorithmus f¨
ur eine Betriebsmittelklasse
Bankier-Algorithmus f¨ur eine Betriebsmittelklasse
Dijkstra hat 1965 den Bankier-Algorithmus vorgestellt.
• Der Bankier betreut Kunden (Prozesse), die jeweils einen
Kreditrahmen (maximale Betriebsmittel-Anforderung) einger¨aumt
bekommen.
32 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Bankier-Algorithmus f¨
ur eine Betriebsmittelklasse
Bankier-Algorithmus f¨ur eine Betriebsmittelklasse
Dijkstra hat 1965 den Bankier-Algorithmus vorgestellt.
• Der Bankier betreut Kunden (Prozesse), die jeweils einen
Kreditrahmen (maximale Betriebsmittel-Anforderung) einger¨aumt
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.
32 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Bankier-Algorithmus f¨
ur eine Betriebsmittelklasse
Bankier-Algorithmus f¨ur eine Betriebsmittelklasse
Dijkstra hat 1965 den Bankier-Algorithmus vorgestellt.
• Der Bankier betreut Kunden (Prozesse), die jeweils einen
Kreditrahmen (maximale Betriebsmittel-Anforderung) einger¨aumt
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 f¨
ur
weitere Kunden hat, die es den Kunden erm¨
oglichen, ihre bereits
erhaltenen Kredite zur¨
uckzahlen zu k¨
onnen.
32 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Bankier-Algorithmus f¨
ur eine Betriebsmittelklasse
Bankier-Algorithmus f¨ur eine Betriebsmittelklasse
Dijkstra hat 1965 den Bankier-Algorithmus vorgestellt.
• Der Bankier betreut Kunden (Prozesse), die jeweils einen
Kreditrahmen (maximale Betriebsmittel-Anforderung) einger¨aumt
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 f¨
ur
weitere Kunden hat, die es den Kunden erm¨
oglichen, ihre bereits
erhaltenen Kredite zur¨
uckzahlen zu k¨
onnen.
• Der Bankier pr¨
uft bei einem Darlehensantrag, ob die Zuteilung zu
einem sicheren Zustand f¨
uhrt. Ist das nicht der Fall, wird die
Zuteilung aufgeschoben, ansonsten gezahlt.
32 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Bankier-Algorithmus f¨
ur eine Betriebsmittelklasse
Bankier-Algorithmus f¨ur eine Betriebsmittelklasse
Dijkstra hat 1965 den Bankier-Algorithmus vorgestellt.
• Der Bankier betreut Kunden (Prozesse), die jeweils einen
Kreditrahmen (maximale Betriebsmittel-Anforderung) einger¨aumt
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 f¨
ur
weitere Kunden hat, die es den Kunden erm¨
oglichen, ihre bereits
erhaltenen Kredite zur¨
uckzahlen zu k¨
onnen.
• Der Bankier pr¨
uft bei einem Darlehensantrag, ob die Zuteilung zu
einem sicheren Zustand f¨
uhrt. Ist das nicht der Fall, wird die
Zuteilung aufgeschoben, ansonsten gezahlt.
32 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Bankier-Algorithmus f¨
ur eine Betriebsmittelklasse
¨
Bankier-Algorithmus: Uberpr¨
ufung ob Zustand sicher ist
¨
Die Uberpr¨
ufung simuliert die Darlehensvergabe der Kunden. Wenn
alle Kunden dabei befriedigt werden k¨
onnen, ist der Zustand sicher und
der aktuelle Darlehensantrag wird gew¨ahrt.
• Zun¨
achst wird gepr¨
uft, ob noch ausreichende Mittel f¨
ur einige
Kunden zur Verf¨
ugung stehen.
33 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Bankier-Algorithmus f¨
ur eine Betriebsmittelklasse
¨
Bankier-Algorithmus: Uberpr¨
ufung ob Zustand sicher ist
¨
Die Uberpr¨
ufung simuliert die Darlehensvergabe der Kunden. Wenn
alle Kunden dabei befriedigt werden k¨
onnen, ist der Zustand sicher und
der aktuelle Darlehensantrag wird gew¨ahrt.
• Zun¨
achst wird gepr¨
uft, ob noch ausreichende Mittel f¨
ur einige
Kunden zur Verf¨
ugung stehen.
• Dann w¨
ahlt er den Kunden, bei dem der Kreditrahmen am weitesten
ausgesch¨
opft ist und simuliert dessen Zusage.
33 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Bankier-Algorithmus f¨
ur eine Betriebsmittelklasse
¨
Bankier-Algorithmus: Uberpr¨
ufung ob Zustand sicher ist
¨
Die Uberpr¨
ufung simuliert die Darlehensvergabe der Kunden. Wenn
alle Kunden dabei befriedigt werden k¨
onnen, ist der Zustand sicher und
der aktuelle Darlehensantrag wird gew¨ahrt.
• Zun¨
achst wird gepr¨
uft, ob noch ausreichende Mittel f¨
ur einige
Kunden zur Verf¨
ugung stehen.
• Dann w¨
ahlt er den Kunden, bei dem der Kreditrahmen am weitesten
ausgesch¨
opft ist und simuliert dessen Zusage.
• Dann wird der n¨
achste Kunde simuliert.
33 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Bankier-Algorithmus f¨
ur eine Betriebsmittelklasse
¨
Bankier-Algorithmus: Uberpr¨
ufung ob Zustand sicher ist
¨
Die Uberpr¨
ufung simuliert die Darlehensvergabe der Kunden. Wenn
alle Kunden dabei befriedigt werden k¨
onnen, ist der Zustand sicher und
der aktuelle Darlehensantrag wird gew¨ahrt.
• Zun¨
achst wird gepr¨
uft, ob noch ausreichende Mittel f¨
ur einige
Kunden zur Verf¨
ugung stehen.
• Dann w¨
ahlt er den Kunden, bei dem der Kreditrahmen am weitesten
ausgesch¨
opft ist und simuliert dessen Zusage.
• Dann wird der n¨
achste Kunde simuliert.
• Wenn letztlich alle Darlehen zur¨
uckgezahlt werden k¨onnen, war der
Zustand sicher.
33 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Bankier-Algorithmus f¨
ur eine Betriebsmittelklasse
¨
Bankier-Algorithmus: Uberpr¨
ufung ob Zustand sicher ist
¨
Die Uberpr¨
ufung simuliert die Darlehensvergabe der Kunden. Wenn
alle Kunden dabei befriedigt werden k¨
onnen, ist der Zustand sicher und
der aktuelle Darlehensantrag wird gew¨ahrt.
• Zun¨
achst wird gepr¨
uft, ob noch ausreichende Mittel f¨
ur einige
Kunden zur Verf¨
ugung stehen.
• Dann w¨
ahlt er den Kunden, bei dem der Kreditrahmen am weitesten
ausgesch¨
opft ist und simuliert dessen Zusage.
• Dann wird der n¨
achste Kunde simuliert.
• Wenn letztlich alle Darlehen zur¨
uckgezahlt werden k¨onnen, war der
Zustand sicher.
33 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Bankier-Algorithmus f¨
ur mehrere Betriebsmittelklassen
Bankier-Algorithmus f¨ur mehrere Betriebsmittelklassen
Der Bankier-Algorithmus kann auf mehrere Betriebsmittelklassen
erweitert werden.
Verwendet wird die Belegungsmatrix B, die Anforderungsmatrix A, der
Restevektor R.
Die Pr¨
ufung, ob ein Zustand sicher ist:
1
Suche eine Zeile (Prozess) i in A, f¨
ur die gilt Ai ≤ R.
Falls es keine solche Zeile gibt, wird das System einen
Deadlock-Zustand erreichen, da kein Prozess seine Berechnungen
vollst¨andig ausf¨
uhren kann.
34 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Bankier-Algorithmus f¨
ur mehrere Betriebsmittelklassen
Bankier-Algorithmus f¨ur mehrere Betriebsmittelklassen
Der Bankier-Algorithmus kann auf mehrere Betriebsmittelklassen
erweitert werden.
Verwendet wird die Belegungsmatrix B, die Anforderungsmatrix A, der
Restevektor R.
Die Pr¨
ufung, ob ein Zustand sicher ist:
1
2
Suche eine Zeile (Prozess) i in A, f¨
ur die gilt Ai ≤ R.
Falls es keine solche Zeile gibt, wird das System einen
Deadlock-Zustand erreichen, da kein Prozess seine Berechnungen
vollst¨andig ausf¨
uhren kann.
Es wird angenommen, Prozess i wird beendet. Markiere i als
terminiert und f¨
uge seine freigegebenen Mittel zu R hinzu, also
R = R + Bi
34 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Bankier-Algorithmus f¨
ur mehrere Betriebsmittelklassen
Bankier-Algorithmus f¨ur mehrere Betriebsmittelklassen
Der Bankier-Algorithmus kann auf mehrere Betriebsmittelklassen
erweitert werden.
Verwendet wird die Belegungsmatrix B, die Anforderungsmatrix A, der
Restevektor R.
Die Pr¨
ufung, ob ein Zustand sicher ist:
1
2
3
Suche eine Zeile (Prozess) i in A, f¨
ur die gilt Ai ≤ R.
Falls es keine solche Zeile gibt, wird das System einen
Deadlock-Zustand erreichen, da kein Prozess seine Berechnungen
vollst¨andig ausf¨
uhren kann.
Es wird angenommen, Prozess i wird beendet. Markiere i als
terminiert und f¨
uge 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.
34 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Bankier-Algorithmus f¨
ur mehrere Betriebsmittelklassen
Bankier-Algorithmus f¨ur mehrere Betriebsmittelklassen
Der Bankier-Algorithmus kann auf mehrere Betriebsmittelklassen
erweitert werden.
Verwendet wird die Belegungsmatrix B, die Anforderungsmatrix A, der
Restevektor R.
Die Pr¨
ufung, ob ein Zustand sicher ist:
1
2
3
Suche eine Zeile (Prozess) i in A, f¨
ur die gilt Ai ≤ R.
Falls es keine solche Zeile gibt, wird das System einen
Deadlock-Zustand erreichen, da kein Prozess seine Berechnungen
vollst¨andig ausf¨
uhren kann.
Es wird angenommen, Prozess i wird beendet. Markiere i als
terminiert und f¨
uge 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.
34 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Bankier-Algorithmus f¨
ur mehrere Betriebsmittelklassen
Bankier-Algorithmus: Zustand sicher pr¨ufen
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
35 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Verhinderung
Bankier-Algorithmus f¨
ur mehrere Betriebsmittelklassen
Beurteilung Bankier-Algorithmus
• Der Bankier-Algorithmus ist sehr gut untersucht.
• Die Voraussetzung f¨
ur die Simulation (jeder Prozess kann alle seine
Betriebsmittel-Anforderungen beim Start bekannt machen), sind in
der Praxis nicht gegeben.
wieso eigentlich nicht ?
• Die Betriebsmittel k¨
onnen dynamisch in ihrer Anzahl variieren (ein
Drucker f¨allt aus).
Insgesamt wird der Algorithmus (und die Verhinderung insgesamt) in
aktuellen Betriebssystemen nicht eingesetzt.
36 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Vermeidung
Deadlock-Vermeidung
Wenn sichergestellt werden k¨
onnten, dass nicht alle vier u.a.
Bedingungen gleichzeitig eintreten k¨
onnten, w¨are Deadlocks nicht
m¨oglich (strukturelle Vermeidung).
1
Wechselseitiger Ausschluss
37 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Vermeidung
Deadlock-Vermeidung
Wenn sichergestellt werden k¨
onnten, dass nicht alle vier u.a.
Bedingungen gleichzeitig eintreten k¨
onnten, w¨are Deadlocks nicht
m¨oglich (strukturelle Vermeidung).
1
Wechselseitiger Ausschluss
2
Anforderung weitere Betriebsmittel
37 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Vermeidung
Deadlock-Vermeidung
Wenn sichergestellt werden k¨
onnten, dass nicht alle vier u.a.
Bedingungen gleichzeitig eintreten k¨
onnten, w¨are Deadlocks nicht
m¨oglich (strukturelle Vermeidung).
1
Wechselseitiger Ausschluss
2
Anforderung weitere Betriebsmittel
Ununterbrechbarkeit
3
37 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Vermeidung
Deadlock-Vermeidung
Wenn sichergestellt werden k¨
onnten, dass nicht alle vier u.a.
Bedingungen gleichzeitig eintreten k¨
onnten, w¨are Deadlocks nicht
m¨oglich (strukturelle Vermeidung).
1
Wechselseitiger Ausschluss
2
3
Anforderung weitere Betriebsmittel
Ununterbrechbarkeit
4
Zyklische Wartebedingung
Dies ist aber in der Praxis nicht m¨
oglich, also ist dies kein gangbarer Weg.
37 / 37
Betriebssysteme - Deadlocks → alois.schuette@h-da.de Version: WS2014(967c57d)
Deadlock-Vermeidung
Deadlock-Vermeidung
Wenn sichergestellt werden k¨
onnten, dass nicht alle vier u.a.
Bedingungen gleichzeitig eintreten k¨
onnten, w¨are Deadlocks nicht
m¨oglich (strukturelle Vermeidung).
1
Wechselseitiger Ausschluss
2
3
Anforderung weitere Betriebsmittel
Ununterbrechbarkeit
4
Zyklische Wartebedingung
Dies ist aber in der Praxis nicht m¨
oglich, also ist dies kein gangbarer Weg.
37 / 37
Document
Kategorie
Bildung
Seitenansichten
11
Dateigröße
368 KB
Tags
1/--Seiten
melden