Betriebssysteme

Transcript

Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 Alois Sch¨ utte 23. M¨arz 2016 1 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ¨ Uberblick ARSnova 19226584 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. Kennen Sie Beispiele ? 3 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ¨ Uberblick ARSnova 19226584 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. Kennen Sie Beispiele ? 3 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ¨ Uberblick ARSnova 19226584 Beispiel aus der realen Welt Abbildung: 4 Autos an Kreuzung ohne Verkehrsschilder Welche Beispiele f¨ ur Deadlocks kennen Sie? 4 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ¨ Uberblick ARSnova 19226584 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 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ¨ Uberblick ARSnova 19226584 // 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 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ¨ Uberblick ARSnova 19226584 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 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ¨ Uberblick ARSnova 19226584 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 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ¨ Uberblick ARSnova 19226584 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 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ¨ Uberblick ARSnova 19226584 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 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ¨ Uberblick ARSnova 19226584 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 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ¨ Uberblick ARSnova 19226584 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) ¨ Uberblick ARSnova 19226584 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) ¨ Uberblick ARSnova 19226584 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) ¨ Uberblick ARSnova 19226584 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) ¨ Uberblick ARSnova 19226584 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) ¨ Uberblick ARSnova 19226584 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) ¨ Uberblick ARSnova 19226584 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 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ¨ Uberblick ARSnova 19226584 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 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ¨ Uberblick ARSnova 19226584 Keine Nebenl¨ aufigkeit, d.h. Betriebssystem w¨ahlt zuerst P1, dann P2 und am Schluss P3, wobei jeder Prozess vollst¨andig abgearbeitet wird: 11 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ¨ Uberblick ARSnova 19226584 Keine Nebenl¨ aufigkeit, d.h. Betriebssystem w¨ahlt zuerst P1, dann P2 und am Schluss P3, wobei jeder Prozess vollst¨andig abgearbeitet wird: 12 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ¨ Uberblick ARSnova 19226584 Keine Nebenl¨ aufigkeit, d.h. Betriebssystem w¨ahlt zuerst P1, dann P2 und am Schluss P3, wobei jeder Prozess vollst¨andig abgearbeitet wird: 13 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ¨ Uberblick ARSnova 19226584 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 14 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ¨ Uberblick ARSnova 19226584 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 15 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ¨ Uberblick ARSnova 19226584 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 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) ¨ Uberblick ARSnova 19226584 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 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 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. 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 verf¨ ugbar 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 verf¨ ugbar 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 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 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 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 21 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 Deadlock-Erkennung und -Behebung Ein Betriebsmittel je Klasse H¨orsaal¨ubung 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 gepr¨ uft, sondern etwa nur: • alle k Minuten oder • wenn die Prozessorlast unter festgesetzte Schwelle f¨ allt. 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 gepr¨ uft, sondern etwa nur: • alle k Minuten oder • wenn die Prozessorlast unter festgesetzte Schwelle f¨ allt. 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 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. 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 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. 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 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 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 verf¨ ugbaren 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 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 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 verf¨ ugbaren 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 = ( Bandger¨at 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 Bandger¨ ate und ein CD-Rom Laufwerk und m¨ ochte weiterhin ein weiteres Bandger¨ at 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 ≤ 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. 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 Ausf¨ uhrung beenden kann. 1 Anf¨anglich 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 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) 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 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) 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 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 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 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 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 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. 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 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. 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 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. 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 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. 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 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: {} 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 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 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 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 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 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) 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 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) 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 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. 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 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. 28 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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 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 Zust¨ande. 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 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. 31 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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. 32 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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 33 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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 34 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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 34 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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 34 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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 34 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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 ! 34 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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 ! 34 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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!) 35 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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. 36 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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. 36 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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. 36 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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. 36 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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. 36 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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. 37 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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. 37 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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. 37 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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. 37 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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. 37 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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. 38 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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 38 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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. 38 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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. 38 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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 39 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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. 40 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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. 40 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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 41 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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 41 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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 41 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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. 41 / 41 Betriebssysteme - Deadlocks → [email protected] Version: (8c45d65) ARSnova 19226584 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. 41 / 41