| [gesichtete Version] | [gesichtete Version] |
Keine Bearbeitungszusammenfassung |
|||
| Zeile 389: | Zeile 389: | ||
</p> | </p> | ||
<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 | 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> | ||
<p> | <p> | ||
| Zeile 399: | Zeile 399: | ||
<br /> | <br /> | ||
==== Deadlock-Fazit==== | ==== Deadlock-Fazit==== | ||
<p> | <p> | ||
{{#index:Deadlock|Verklemmung|Deadlock-Zustand|Zustand, Deadlock}} Deadlocks sind eine unangenehme Sache, sie sollten besser nicht auftreten. Zunächst die Definition:
Eine Menge von Prozessen befindet sich nach Tanenbaum 2009 in einem Deadlock-Zustand, wenn jeder Prozess aus der Menge auf ein Ereignis wartet, das nur ein anderer Prozess aus der Menge auslösen kann.
Wenn sich mehrere Prozesse in einem Deadlock-Zustand befinden, so sagt man auch vereinfachend: Es ist ein Deadlock aufgetreten.
Der englische Betriff Deadlock wird auf deutsch gerne mit Verklemmung übersetzt.
In der realen Welt gibt es eine schöne Analogie zum Deadlock-Zustand von Prozessen:
Wenn du dir vorstellen kannst, dass ein Auto im Strassenverkehr einen Prozess repräsentiert, dann zeigt dieses Bild einen Deadlock-Zustand einer Menge von Autos. (Hier gibt es eine kleine Sammlung mit ähnlichen Fotos.)
In Anbetracht dieser Bilder kannst du überlegen, ob die Menge der Prozesszustände noch um einen ergänzt werden sollte. Welcher Zustand ist damit gemeint?
Mandl 2013 geht am Ende von Kapitel 6.2.2 auf das Philosophenproblem und eine dabei bestehende Deadlock-Gefahr ein.
Erläutere:
Eine grundlegende Arbeit über System Deadlocks veröffentlichten E.G. Coffman, Jr.; M.J. Elphick und A. Shoshani im Jahre 1971 in der Zeitschrift Computing Surveys, Vol. 3, No. 2; (hier ist ein alternativer Link zu diesem Dokument).
Sie beschreiben darin vier Bedingungen, welche allesamt eingetreten sein müssen, und damit einen Deadlock-Zustand verursacht haben:
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.
{{#index:Betriebsmittelgraph|Belegungs-Anforderungs-Graph|Zyklus im Betriebsmittelgraph|Konstruktion Betriebsmittelgraph}}
Die Universität Oldenburg stellt ein 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:
Mache dich mit diesem Tutorial und insbesondere mit den beiden Schritten vertraut!
Ein Betriebsmittelgraph wird in gängiger Literatur alternativ auch Belegungs-Anforderungs-Graph genannt.
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.
Aktuell besteht folgende Ressourcenzuteilung und -anforderung:
Zeichne den Betriebsmittelgraph! Achte dabei auf die Pfeilrichtungen!
Offensichtlich liegt hier ein Deadlock vor.
Wie man sieht, hilft der Betriebsmittelgraph tatsächlich bei der Erkennung eines Deadlocks. Aber:
Wenn du die letzte Aufgabe zum Betriebsmittelgraphen durchgeführt hast, dann hast du (ein Mensch!) den Deadlock erkannt.
Eigentlich ist es aber die Aufgabe des Betriebssystems einen Deadlock zu erkennen!
Die Frage ist also:
Kann ein Betriebssystem auch einen Betriebsmittelgraphen konstruieren und einen Zyklus darin erkennen?
Die Antwort ist: Ja, das geht!
Prof. Dr. Holger Schlingloff vom Institut für Informatik der Humboldt-Universität zu Berlin geht darauf in seinem Aufsatz Zyklensuche (hier auch als PDF) ein.
Es wird an dieser Stelle nicht näher darauf eingegangen, wie die Graphenkonstruktion (bzw. -repräsentation) im Rechner, sowie die anschließende Zyklensuche abläuft.
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.
Falls du diese Vorlesungen bereits gehört hast, kommen dir diese Stichwörter vielleicht bekannt vor: Adjazenzmatrix, Nachbarschaftsliste, Rekursion, Tiefensuche, Breitensuche.
Es ist jetzt also klar, dass ein Betriebssystem die folgenden beiden Dinge tun muss, um einen gegebenenfalls vorhandenen Deadlock-Zustand zu erkennen:
Falls ein Zyklus erkannt wird, so liegt ein Deadlock vor, und es können auch die beteiligten Prozesse und Ressourcen identifiziert werden.
Falls kein Zyklus erkannt wird, so besteht die Gewissheit, dass "alles in Ordnung" ist, d.h. es liegt kein Deadlock vor.
Was sollte das Betriebssystem tun, wenn es einen Deadlock erkannt und die zugehörigen Prozesse und Betriebsmittel identifiziert hat?
Überlege, recherchiere und diskutiere in deiner Lerngruppe! Schätze für jeden Vorschlag auch die möglichen Folgen ab.
Wie oft sollte ein Betriebssystem die Suche nach einem Deadlock durchführen?
Die pragmatischte Antwort lautet immer: "Es kommt drauf an!"
Dann erläutere doch mal: Worauf kommt es an?
Vielleicht liefert die Antwort auf die letzte Aufgabe ja auch Gründe für das nächste Thema:
Eine durchaus gängige Methode im Umgang mit Deadlocks ist das Ignorieren:
"Es gibt keine Deadlocks, weil ich daran glaube, dass es keine Deadlocks gibt!", sagt das Betriebssystem.
Rechtfertigen kann man diese Haltung, wenn die Wahrscheinlichkeit des Auftretens eines Deadlocks gering ist, und gleichzeitig die Folgen eines aufgetretenen Deadlocks "nicht dramatisch" sind (wie immer man "dramatisch" dann auch definieren möchte).
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.
Eine andere Strategie ist die Vermeidung von Deadlocks. Ein Betriebssystem könnte von vorneherein so konstruiert werden, dass Deadlocks gar nicht möglich sind.
Wenn man ein Betriebssystem entwickelt, welches mindestens eine der vier Bedingungen für Deadlocks unerfüllbar macht, dann können Deadlocks überhaupt nicht auftreten!
Man betrachte also einzelne Möglichkeiten in dieser Richtung. Die folgenden Aufgaben beschäftigen sich damit.
Recherchiere und erläutere:
Was versteht man unter Spooling? (Zum Beispiel bei einem Drucker-Spooler.)
Spooling ist prinzipiell geeignet, um Deadlocks zu vermeiden. Welche der vier Bedingungen macht Spooling unerfüllbar?
Denke dir folgende Situation in einer Bank:
Es werden von einem Großrechner der Bank viele Überweisungen durchgeführt. Der Einfachheit halber (für diese Aufgabe) nur innerhalb derselben Bank.
Zu einer Überweisung gehören drei Dinge:
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:
Die beiden Konten A und B sind damit die vom Überweisungsprozess benötigten Betriebsmittel.
Erläutere eine Situation, bei der es durch die zu erledigenden Überweisungen zu einem Deadlock kommt! Zeichne dazu den Betriebsmittelgraphen.
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.
Für jede Überweisung:
Kann bei dieser Vorgehensweise noch ein Deadlock auftreten?
Bei der 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.
Betriebsmittel werden i.d.R. nach und nach von Prozessen angefordert. Sie werden deshalb auch nicht alle auf einmal dem betreffenden Prozess zugeteilt!
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.
Tanenbaum 2009 bringt es auf den Punkt:
Es stellt sich also die Frage, ob ein Algorithmus existiert, der Deadlocks zuverlässig verhindern kann, indem er immer die richtige Entscheidung trifft.
Eine Antwort erläutert Tanenbaum 2009 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.
Weitere Details zur Deadlock-Verhinderung können nachgelesen werden bei:
Allgemein ist davon auszugehen, dass die Erkennung, Vermeidung oder Verhinderung von Deadlocks sehr aufwendig ist. Ein ausnahmlose Abdeckung aller denkbarer Fälle scheint nahezu unmöglich.
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.
Diese Seite steht unter der Creative Commons Namensnennung 3.0 Unported Lizenz http://i.creativecommons.org/l/by/3.0/80x15.png