|
|
| Zeile 71: |
Zeile 71: |
| # ''No preemption condition''<br />Zugewiesene Ressourcen können einem Prozess nicht gewaltsam wieder entrissen werden. | | # ''No preemption condition''<br />Zugewiesene Ressourcen können einem Prozess nicht gewaltsam wieder entrissen werden. |
| # ''Circular wait condition''<br />Es gibt eine zyklische Kette von Prozessen, die bereits eine oder mehrere Ressourcen zugewiesen bekommen haben, und die gleichzeitig auf weitere Ressourcen warten, welche bereits dem jeweils nächsten Prozess in der Kette zugesprochen wurden. | | # ''Circular wait condition''<br />Es gibt eine zyklische Kette von Prozessen, die bereits eine oder mehrere Ressourcen zugewiesen bekommen haben, und die gleichzeitig auf weitere Ressourcen warten, welche bereits dem jeweils nächsten Prozess in der Kette zugesprochen wurden. |
| </p>
| |
|
| |
| <br />
| |
|
| |
| == Deadlocks erkennen ==
| |
| <p>
| |
| Die vierte der gerade beschriebenen Bedingungen liefert eine Möglichkeit, nach der ein bereits eingetretener Deadlock-Zustand auf einem System entdeckt werden kann. Man realisiert dies durch die Konstruktion eines speziellen Graphen, der anschließend untersucht wird. Die folgenden Aufgaben beschäftigen sich damit.
| |
| </p>
| |
|
| |
| <br />
| |
|
| |
| == Aufgabe 2 ==
| |
| <p>
| |
| <loop_index>Betriebsmittelgraph|Belegungs-Anforderungs-Graph|Zyklus im Betriebsmittelgraph|Konstruktion Betriebsmittelgraph</loop_index>
| |
| <loop_area type="task">
| |
| <loop_task title="Deadlocks erkennen mit Hilfe eines Betriebsmittelgraphen">
| |
| <p>
| |
| Die Universität Oldenburg stellt ein [http://olli.informatik.uni-oldenburg.de/Deadlock/Start.html Tutorial Deadlock-Algorithmen] bereit, bei dem u.a. auf die Erkennung eines Deadlock-Zustands eingegangen wird. Insbesondere kann die Erkennung mit Hilfe zweier Schritte erfolgen:
| |
| * Schritt 1: [http://olli.informatik.uni-oldenburg.de/Deadlock/Html/Erkennung1_Aufbau.html Konstruktion eines Betriebsmittelgraphen]
| |
| * Schritt 2: [http://olli.informatik.uni-oldenburg.de/Deadlock/Html/Erkennung1_Zyklus.html Überprüfung eines Betriebsmittelgraphen auf Zyklen]
| |
| </p>
| |
| <p>
| |
| Mache dich mit diesem Tutorial und insbesondere mit den beiden Schritten vertraut!
| |
| </p>
| |
| </loop_task>
| |
| </loop_area>
| |
| </p>
| |
|
| |
| <br />
| |
| <p>
| |
| Ein ''Betriebsmittelgraph'' wird in gängiger Literatur alternativ auch ''Belegungs-Anforderungs-Graph'' genannt.
| |
| </p>
| |
|
| |
| <br />
| |
|
| |
| == Aufgabe 3 ==
| |
| <p>
| |
| <loop_area type="task">
| |
| <loop_task title="Zeichne den Betriebsmittelgraph und erkenne den Deadlock!">
| |
| <p>
| |
| Gegeben seien die Prozesse ''P1'' bis ''P5'' und die Ressourcen ''Drucker'', ''Plotter'', ''Modem'', ''Magnetbandlaufwerk'' sowie ''Diskettenlaufwerk'' und ''CD-ROM-Laufwerk''. Jede Ressource sei genau einmal vorhanden.
| |
| </p>
| |
| <p>
| |
| Aktuell besteht folgende Ressourcenzuteilung und -anforderung:
| |
| * ''P1'' belegt ''Plotter'' und fordert ''Diskettenlaufwerk'' an.
| |
| * ''P2'' belegt ''Magnetbandlaufwerk'' und fordert ''Plotter'' und ''Modem'' an.
| |
| * ''P3'' belegt ''Modem'' und fordert ''Drucker'' an.
| |
| * ''P4'' belegt ''Drucker'' und fordert ''CD-ROM-Laufwerk'' an.
| |
| * ''P5'' belegt ''Diskettenlaufwerk'' und fordert ''Magnetbandlaufwerk'' an.
| |
| </p>
| |
| <p>
| |
| Zeichne den Betriebsmittelgraph! Achte dabei auf die Pfeilrichtungen!
| |
| </p>
| |
| <p>
| |
| Offensichtlich liegt hier ein Deadlock vor.
| |
| * Woran ist dies im Betriebsmittelgraphen erkennbar?
| |
| * Welche Prozesse sind daran beteiligt?
| |
| </p>
| |
| </loop_task>
| |
| </loop_area>
| |
| </p>
| |
|
| |
| <br />
| |
| <p>
| |
| Wie man sieht, hilft der Betriebsmittelgraph tatsächlich bei der Erkennung eines Deadlocks. Aber:
| |
| </p>
| |
| <p>
| |
| <loop_area type="notice">
| |
| <p>
| |
| Wenn du die letzte Aufgabe zum Betriebsmittelgraphen durchgeführt hast, dann hast du ('''ein Mensch!''') den Deadlock erkannt.
| |
| </p>
| |
| <p>
| |
| Eigentlich ist es aber die Aufgabe '''des Betriebssystems''' einen Deadlock zu erkennen!
| |
| </p>
| |
| </loop_area>
| |
| </p>
| |
|
| |
| <p>
| |
| Die Frage ist also:
| |
| </p>
| |
|
| |
| <p>
| |
| <loop_area type="question">
| |
| <p>
| |
| Kann '''ein Betriebssystem''' auch einen Betriebsmittelgraphen konstruieren und einen Zyklus darin erkennen?
| |
| </p>
| |
| </loop_area>
| |
| </p>
| |
|
| |
| <p>
| |
| Die Antwort ist: Ja, das geht!
| |
| </p>
| |
| <p>
| |
| Prof. Dr. [http://www2.informatik.hu-berlin.de/~hs/ Holger Schlingloff] vom Institut für Informatik der Humboldt-Universität zu Berlin geht darauf in seinem Aufsatz [http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo35.php Zyklensuche] <small>(hier auch als [http://www-i1.informatik.rwth-aachen.de/~algorithmus/Algorithmen/algo35/algo35.pdf PDF])</small> ein.
| |
| </p>
| |
| <p>
| |
| <loop_area type="notice">
| |
| <p>
| |
| Es wird an dieser Stelle nicht näher erläutert, wie die Graphenkonstruktion (bzw. -repräsentation) im Rechner, sowie die anschließende Zyklensuche abläuft.
| |
| </p>
| |
| <p>
| |
| Es sei aber darauf verwiesen, dass diese Tätigkeit eine Reihe anderer Dinge benutzt, die für Studierende an Hochschulen üblicherweise in Vorlesungen zur ''Mathematik'' oder zu ''Algorithmen und Datenstrukturen'' behandelt werden.
| |
| </p>
| |
| <p>
| |
| Falls du diese Vorlesungen bereits gehört hast, kommen dir diese Stichwörter vielleicht bekannt vor: Adjazenzmatrix, Nachbarschaftsliste, Rekursion, Tiefensuche, Breitensuche.
| |
| </p>
| |
| </loop_area>
| |
| </p>
| |
|
| |
| <br />
| |
| <p>
| |
| Es ist jetzt also klar, dass ein Betriebssystem die folgenden beiden Dinge tun muss, um einen gegebenenfalls vorhandenen Deadlock-Zustand zu erkennen:
| |
| # Konstruiere den aktuellen Betriebsmittelgraphen, d.h. repräsentiere ihn als interne Datenstruktur.
| |
| # Überprüfe den Graphen auf einen Zyklus, d.h. überprüfe die interne Datenstruktur entsprechend.
| |
| </p>
| |
|
| |
| <p>
| |
| Falls ein Zyklus erkannt wird, so liegt ein Deadlock vor, und es können auch die beteiligten Prozesse und Ressourcen identifiziert werden.
| |
| </p>
| |
| <p>
| |
| Falls kein Zyklus erkannt wird, so besteht die Gewissheit, dass "alles in Ordnung" ist, d.h. es liegt kein Deadlock vor.
| |
| </p>
| |
|
| |
| <br />
| |
| == Aufgabe 4 ==
| |
| <p>
| |
| <loop_area type="task">
| |
| <loop_task title="Was tun bei erkanntem Deadlock?">
| |
| <p>
| |
| Was sollte das Betriebssystem tun, wenn es einen Deadlock erkannt und die zugehörigen Prozesse und Betriebsmittel identifiziert hat?
| |
| </p>
| |
| <p>
| |
| Überlege, recherchiere und diskutiere in deiner Lerngruppe! Schätze für jeden Vorschlag auch die möglichen Folgen ab.
| |
| </p>
| |
| </loop_task>
| |
| </loop_area>
| |
| </p>
| |
|
| |
| <br />
| |
| == Aufgabe 5 ==
| |
| <p>
| |
| <loop_area type="task">
| |
| <loop_task title="Wie oft nach einem Deadlock suchen?">
| |
| <p>
| |
| Wie oft sollte ein Betriebssystem die Suche nach einem eventuell existenten Deadlock durchführen?
| |
| * Einmal pro Sekunde?
| |
| * Einmal pro Minute?
| |
| * Einmal pro Stunde?
| |
| * Einmal am Tag?
| |
| * etc.
| |
| </p>
| |
| <p>
| |
| Die pragmatischte Antwort lautet immer: "Es kommt darauf an!"
| |
| </p>
| |
| <p>
| |
| Dann erläutere doch mal: Worauf kommt es an?
| |
| * Welche Situationen oder Einsatzzwecke für Betriebssysteme sind vorstellbar, bei denen eine Suche nach Deadlocks in kürzeren oder längeren Zeitabständen durchgeführt werden sollte?
| |
| * Welche Vor- oder Nachteile hat eine (zu) häufige oder (zu) seltene Suche?
| |
| </p>
| |
| </loop_task>
| |
| </loop_area>
| |
| </p>
| |
|
| |
| <br />
| |
| <p>
| |
| Vielleicht liefert die Antwort auf die letzte Aufgabe ja auch Gründe für das nächste Thema:
| |
| </p>
| |
|
| |
| <br />
| |
|
| |
| == Deadlocks ignorieren ==
| |
| <p>
| |
| Eine durchaus gängige Methode im Umgang mit Deadlocks ist das Ignorieren:
| |
| </p>
| |
| <p>
| |
| <loop_area type="practice">
| |
| <p>
| |
| "Es gibt keine Deadlocks, weil ich daran glaube, dass es keine Deadlocks gibt!", sagt das Betriebssystem.
| |
| </p>
| |
| </loop_area>
| |
| </p>
| |
|
| |
| <p>
| |
| Rechtfertigen kann man diese Haltung, wenn die Wahrscheinlichkeit des Auftretens eines Deadlocks gering ist, und gleichzeitig die Folgen eines aufgetretenen Deadlocks "nicht dramatisch" sind <small>(wie immer man "dramatisch" dann auch definieren möchte)</small>.
| |
| </p>
| |
|
| |
| <p>
| |
| Zum Ignorieren von Deadlocks kommt in Betriebssystemen üblicherweise der [http://de.wikipedia.org/wiki/Vogel-Strau%C3%9F-Algorithmus Vogel-Strauß-Algorithmus] zum Einsatz.
| |
| </p>
| |
|
| |
| <br />
| |
|
| |
| == Aufgabe 6 ==
| |
| <p>
| |
| <loop_area type="task">
| |
| <loop_task title="Implementiere!">
| |
| <p>
| |
| Implementiere den Vogel-Strauß-Algorithmus in einer beliebigen Hochsprache! Welcher Quellcode fehlt zwischen den geschweiften Klammern?
| |
| </p>
| |
| <span style="font-family:Courier">
| |
| void Vogel-Strauss-Algorithmus() {<br />
| |
| // ? ? ?<br />
| |
| }<br />
| |
| </span>
| |
| </loop_task>
| |
| </loop_area>
| |
| </p>
| |
|
| |
| <br />
| |
|
| |
| == Vermeiden von Deadlocks ==
| |
| <p>
| |
| Wenn es um die Erkennung von Deadlocks geht, dann impliziert dies immer, dass der Deadlock-Zustand bereits eingetreten ist. Irgendeine Art von negativen Folgen wird sich daraus zwangsläufig ergeben.
| |
| </p>
| |
|
| |
| <p>
| |
| Eine andere Strategie ist die Vermeidung von Deadlocks. Ein Betriebssystem könnte von vorneherein so konstruiert werden, dass Deadlocks gar nicht möglich sind.
| |
| </p>
| |
|
| |
| <br />
| |
| <p>
| |
| <loop_area type="important">
| |
| <p>
| |
| Wenn man ein Betriebssystem entwickelt, welches mindestens eine der [[Deadlocks#Vier_Bedingungen_f.C3.BCr_einen_Deadlock|vier Bedingungen für Deadlocks]] '''unerfüllbar''' macht, dann können Deadlocks überhaupt nicht auftreten!
| |
| </p>
| |
| </loop_area>
| |
| </p>
| |
|
| |
| <br />
| |
| <p>
| |
| Man betrachte also einzelne Möglichkeiten in dieser Richtung. Die folgenden Aufgaben beschäftigen sich damit.
| |
| </p>
| |
|
| |
| <br />
| |
| == Aufgabe 7 ==
| |
| <p>
| |
| <loop_area type="task">
| |
| <loop_task title="Spooling">
| |
| <p>
| |
| Recherchiere und erläutere:<br />
| |
| Was versteht man unter Spooling? (Zum Beispiel bei einem Drucker-Spooler.)
| |
| </p>
| |
| <p>
| |
| Spooling ist prinzipiell geeignet, um Deadlocks zu vermeiden. Welche der [[Deadlocks#Vier_Bedingungen_f.C3.BCr_einen_Deadlock|vier Bedingungen]] macht Spooling unerfüllbar?
| |
| </p>
| |
| </loop_task>
| |
| </loop_area>
| |
| </p>
| |
|
| |
| <br />
| |
| == Aufgabe 8 ==
| |
| <p>
| |
| <loop_area type="task">
| |
| <loop_task title="Überweis' mal was">
| |
| <p>
| |
| Denke dir folgende Situation in einer Bank:
| |
| </p>
| |
| <p>
| |
| Es werden von einem Großrechner der Bank viele Überweisungen durchgeführt. Der Einfachheit halber (für diese Aufgabe) nur innerhalb derselben Bank.
| |
| </p>
| |
| <p>
| |
| Zu einer Überweisung gehören drei Dinge:
| |
| # Der Überweisungsbetrag.
| |
| # Die Nummer des Kontos, von dem der Betrag abgebucht wird (Konto A).
| |
| # Die Nummer des Kontos, dem der Betrag gutgeschrieben wird (Konto B).
| |
| </p>
| |
| <p>
| |
| Für jede Überweisung startet das Betriebssystem des Großrechners einen separaten Prozess. Dieser ''Prozess zur Durchführung einer einzelnen Überweisung'' geht nun wie folgt vor:
| |
| * Reserviere Konto A.
| |
| * Reserviere Konto B.
| |
| * Führe aus: A minus Überweisungsbetrag ("abbuchen").
| |
| * Führe aus: B plus Überweisungsbetrag ("gutschreiben").
| |
| * Gib Konto B frei.
| |
| * Gib Konto A frei.
| |
| </p>
| |
| <p>
| |
| Die beiden Konten A und B sind damit die vom Überweisungsprozess benötigten Betriebsmittel.
| |
| </p>
| |
| <p>
| |
| Erläutere eine Situation, bei der es durch die zu erledigenden Überweisungen zu einem Deadlock kommt! Zeichne dazu den Betriebsmittelgraphen.
| |
| </p>
| |
| </loop_task>
| |
| </loop_area>
| |
| </p>
| |
|
| |
| <br />
| |
|
| |
| == Aufgabe 9 ==
| |
| <p>
| |
| <loop_area type="task">
| |
| <loop_task title="Überweisen ohne Deadlock?">
| |
| <p>
| |
| Es geht wieder um Überweisungen in einer Bank, gemäß der vorangegangenen Aufgabe. Der Prozess zur Durchführung einer einzelnen Überweisung geht diesmal nach einem besonderen Muster vor.
| |
| </p>
| |
| <p>
| |
| Für jede Überweisung:
| |
| * Reserviere zunächst das Konto mit der '''kleineren''' Kontonummer.
| |
| * Reserviere anschließend das Konto mit der '''größeren''' Kontonummer.
| |
| * Führe aus: A minus Überweisungsbetrag ("abbuchen").
| |
| * Führe aus: B plus Überweisungsbetrag ("gutschreiben").
| |
| * Gebe das Konto mit der '''größeren''' Kontonummer wieder frei.
| |
| * Gebe das Konto mit der '''kleineren''' Kontonummer wieder frei.
| |
| </p>
| |
| <p>
| |
| Kann bei dieser Vorgehensweise noch ein Deadlock auftreten?
| |
| * Falls ja: Erläutere eine Beispielsituation mit dem Deadlock und zeichne den zugehörigen Betriebsmittelgraphen.
| |
| * Falls nein: Welche der [[Deadlocks#Vier_Bedingungen_f.C3.BCr_einen_Deadlock|vier Bedingungen]] ist nicht erfüllt?
| |
| </p>
| |
| </loop_task>
| |
| </loop_area>
| |
| </p>
| |
|
| |
| <br />
| |
| == Verhinderung von Deadlocks ==
| |
| <p>
| |
| Bei der [[Deadlocks#Vermeiden_von_Deadlocks|Vermeidung von Deadlocks]] sollte eine Umgebung geschaffen werden, in der Deadlocks gar nicht erst auftreten können. In der Praxis ist das - wenn überhaupt - nur in Einzelfällen (d.h. für bestimmte, aber nicht für alle Betriebsmittel) möglich.
| |
| </p>
| |
|
| |
| <br />
| |
| <p>
| |
| <loop_area type="notice">
| |
| <p>
| |
| Betriebsmittel werden i.d.R. '''nach und nach''' von Prozessen '''angefordert'''. Sie werden deshalb auch '''nicht alle auf einmal''' dem betreffenden Prozess zugeteilt!
| |
| </p>
| |
| </loop_area>
| |
| </p>
| |
|
| |
| <br />
| |
| <p>
| |
| Angenommen einem Prozess sind bereits eine beliebige Anzahl an Betriebsmitteln zugewiesen worden. Dann geht es bei der ''Verhinderung von Deadlocks'' darum, dem Prozess nur dann eine weitere Ressource zuzusprechen, wenn sichergestellt ist, dass dadurch '''in der Zukunft''' kein Deadlock entstehen kann.
| |
| </p>
| |
|
| |
| <p>
| |
| Bei der Anforderung eines Betriebsmittels muss vom Betriebssystem also eine Entscheidung getroffen werden. <cite>Tanenbaum+2009</cite> bringt es auf den Punkt:
| |
| </p>
| |
| <p>
| |
| <loop_area type="question">
| |
| <p>
| |
| Es stellt sich also die Frage, ob ein Algorithmus existiert, der Deadlocks zuverlässig verhindern kann, indem er immer die richtige Entscheidung trifft.
| |
| </p>
| |
| </loop_area>
| |
| </p>
| |
| <p>
| |
| Eine Antwort erläutert <cite>Tanenbaum+2009</cite> dazu auch: "ja, aber", wobei das "aber" zu der Erkenntnis führt, dass in der Praxis immer Situationen zu befürchten sind, die nicht von dem betreffenden Algorithmus abgedeckt werden können.
| |
| </p>
| |
| <p>
| |
| Weitere Details zur Deadlock-Verhinderung können - je nach Verfügbarkeit der Quellen - nachgelesen werden bei:
| |
| * <cite>Glatz+2010</cite>, Kapitel 4.6.3
| |
| * <cite>Strelen+2012</cite>, Kapitel 5.1.3
| |
| * <cite>Tanenbaum+2009</cite>, Kapitel 6.5
| |
| </p>
| |
|
| |
| <br />
| |
|
| |
| == Deadlock-Fazit==
| |
| <p>
| |
| <loop_area type="summary">
| |
| <p>
| |
| Allgemein ist davon auszugehen, dass die Erkennung, Vermeidung oder Verhinderung von Deadlocks sehr aufwendig ist. Eine ausnahmlose Abdeckung aller denkbarer Fälle scheint nahezu unmöglich.
| |
| </p>
| |
| </loop_area>
| |
| </p>
| |
|
| |
| <p>
| |
| Wenn dann die Wahrscheinlichkeit für das Auftreten eines Deadlocks noch als sehr gering eingeschätzt werden kann, ist schon verständlich, dass Betriebssystem-Hersteller gerne die Strategie des "ignorierens" anwenden. Aber falls der unwahrscheinliche Fall dann doch einmal eintritt, trägt der Anwender die Folgen.
| |
| </p> | | </p> |
|
| |
|