Loading AI tools
Zustand, bei dem eine zyklische Wartesituation zwischen mehreren Prozessen auftritt Aus Wikipedia, der freien Enzyklopädie
Deadlock oder Verklemmung bezeichnet in der Informatik einen Zustand, bei dem eine zyklische Wartesituation zwischen mehreren Prozessen auftritt, wobei jeder beteiligte Prozess auf die Freigabe von mindestens einem Betriebsmittel (einer Ressource) wartet, das ein anderer beteiligter Prozess bereits exklusiv belegt hat. Eine andere Form der Blockierung von Prozessen ist der Livelock.
Der Zustand eines Deadlocks kann als eine Menge von Prozessen definiert werden, in dem sich ein Deadlock befindet, sofern jeder dieser Prozesse auf ein Ereignis wartet, das nur ein anderer Prozess aus dieser Menge verursachen kann.[1]
Beispielsweise kann einem Prozess π1 der Bildschirm zugeteilt worden sein. Gleichzeitig benötigt π1 allerdings den Drucker. Auf der anderen Seite ist der Drucker dem Prozess π2 zugeteilt, der wiederum den Bildschirm fordert. Ein Beispiel für eine Verklemmung aus dem realen Leben ist eine Straßenkreuzung, an der von allen vier Seiten Autos gekommen sind und nun (die Regel rechts vor links vorausgesetzt) darauf warten, dass das jeweils rechts wartende Auto zuerst fährt. Ein weiteres Beispiel ist das Philosophenproblem.
Nach Coffman et al.[2] sind die folgenden vier Bedingungen hinreichend für die Möglichkeit einer Verklemmung:
Verklemmungen können bei Systemen eintreten, die fähig sind, mehrere Prozesse parallel ablaufen zu lassen (Multitasksysteme) und bei denen die Reihenfolge der Betriebsmittelvergabe nicht festgelegt ist. Liegen die Ausführungszeiten der zirkulär abhängigen Prozesse weit genug auseinander, kommt es nicht zum Deadlock. Besteht aber die Möglichkeit einer Verklemmung und will man über den Vogel-Strauß-Algorithmus hinausgehen, so muss man sie verhindern oder vermeiden, ggf. beseitigen.
Die Definitionen von Verklemmungsverhinderung und Verklemmungsvermeidung werden auch öfter vertauscht in der Literatur gefunden.
Grundsätzlich gilt: Existiert nur ein Prozess in einem geschlossenen System, so kann dieser niemals verklemmen. Ebenso kann ein Prozess, der nur ein Betriebsmittel benötigt, nicht verklemmen.
Treten Verklemmungen ein, so können diese in der Regel nicht normal beseitigt werden. Stattdessen sollte die Betriebsmittelverwaltung versuchen, präventive Maßnahmen anzuwenden, um eine geeignete Sequentialisierung zu erreichen. Man spricht von einer Verhinderung, wenn mindestens eine der vier Bedingungen für eine Verklemmung nicht erfüllt wird.
Zusätzlich kann man versuchen, die Verklemmung zu vermeiden (stellenweise auch Verklemmungsverhütung genannt). Dadurch sind Verklemmungen zwar theoretisch möglich; das System versucht jedoch die Prozesse so zu überwachen, dass diese nicht verklemmen. Dieses Vorgehen basiert auf der Methode des sicheren Zustands. Ein Zustand gilt dann als sicher, wenn mindestens eine Scheduling-Reihenfolge existiert, in welcher alle vorhandenen Prozesse beendet werden können, selbst wenn diese noch ihre maximalen Ressourcenanforderungen stellen sollten.
Bei einer Vermeidung müssen alle möglichen folgenden Vorgänge bekannt sein. Hierbei wird häufig der Bankieralgorithmus angewandt, bei dem die Betriebsmittel nur dann einem Prozess zugeteilt werden, wenn sie vollständig zurückgegeben werden. Beispielsweise hat ein Prozess π1 insgesamt fünf Betriebsmittel und er benötigt noch drei weitere Betriebsmittel zur vollständigen Ausführung. Das Betriebssystem stellt noch drei weitere Betriebsmittel zur Verfügung. Ein Prozess π2 besitzt zwei Betriebsmittel und fordert noch acht Betriebsmittel. Demzufolge erhält Prozess π1 die drei Betriebsmittel. Damit besitzt er alle Ressourcen, um vollständig verarbeitet zu werden, worauf dem Betriebssystem nach der Verarbeitung acht Betriebsmittel frei zur Verfügung stehen, die nun Prozess π2 zugeteilt werden können. Eine Vermeidung ist oft sehr schwierig, da man schlecht abschätzen kann, welcher Prozess genügend Betriebsmittel wieder freigibt.
Zwei einfache Verfahren zur Vermeidung stellen wait/die und wound/wait dar. Hierbei werden zyklische Abhängigkeiten vermieden, indem es feste Regeln gibt, wer ein Mittel behalten darf und welchen es entzogen werden kann. Dieses Verfahren wird vor allem in Datenbanksystemen in Bezug auf Schreib- und Lesesperren genutzt, daher wird im Folgenden auch der Terminus Transaktionen und nicht Prozesse verwendet:
Bei beiden Verfahren wird jeder Transaktion ein Zeitstempel bei seiner Instanziierung zugewiesen.
wait/die:
wound/wait:
Die Terminologie ist wie folgt zu verstehen. wait/die bzw. wound/wait geben an, wie sich die anfordernde Transaktion verhält, wenn ein Sperrkonflikt auftritt. Der erste Terminus gibt jeweils an, was passiert, wenn die anfordernde Transaktion die ältere ist, der zweite Terminus gibt an, was passiert, wenn die anfordernde Transaktion die jüngere ist. „Wait“ bedeutet jeweils: die anfordernde Transaktion wartet auf die Freigabe der Sperre; englisch die ‚stirbt‘ bedeutet die anfordernde Transaktion wird zurückgesetzt; „wound“ (verwundet) bedeutet die anfordernde Transaktion „verwundet“ den Sperrbesitzer, d. h. die anfordernde Transaktion versucht den Sperrbesitzer zurückzusetzen. Um unnötige Rücksetzungen zu vermeiden, kann beim „wound“ auf die Rücksetzung dann verzichtet werden, wenn sich der Sperrbesitzer bereits in der Freigabe befindet. In diesem Fall wartet die anfordernde Transaktion entgegen der Regel, weil sichergestellt ist, dass der Sperrbesitzer an keinem Deadlock beteiligt ist.
Eine andere Form der Blockierung von Prozessen, die wie ein Deadlock die weitere Ausführung des Programms verhindert, ist der Livelock. Er bezeichnet eine Form der Blockierung zweier oder mehrerer Prozesse, die im Unterschied zum Deadlock nicht in einem Zustand verharren, sondern ständig zwischen mehreren Zuständen wechseln, aus denen sie nicht mehr entkommen können. Jeder einzelne Prozess verharrt also nicht für immer im Wartezustand, sondern ist weiterhin aktiv, kann aber auch nicht seine Aufgabe abarbeiten.[3]
Anschaulich kann man sich zum Livelock zwei Personen vorstellen, die sich in einem Gang entgegenkommen und fortwährend versuchen, einander in der gleichen (Absolut-)Richtung auszuweichen, und sich gerade dadurch immer gegenseitig blockieren. Beim Deadlock würden sich – in dieser Veranschaulichung bleibend – die zwei Personen nur gegenüberstehen und jeweils darauf warten, dass die andere beiseite geht, was nicht geschieht.
Im Bahnbetrieb bezeichnet Deadlock eine Betriebssituation, in der zwei oder mehrere Züge sich gegenseitig so blockieren, dass die Sicherungstechnik keine regulären Zugfahrten mehr zulässt.[4] Hier besteht eine Analogie zur Informatik: Jeder Zug blockiert einen Zugfolgeabschnitt und wartet darauf, in den nächsten Abschnitt einfahren zu können. Ein Deadlock lässt sich in Algorithmen zur Steuerung von Stellwerken dadurch erkennen, dass durch das Stellen einer Fahrstraße ein Zirkelbezug auftritt.[5][6]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
