Dead Lock

Dead Lock
Beispiel für einen Deadlock

Deadlock oder Verklemmung bezeichnet in der Informatik einen Zustand, bei dem ein oder mehrere Prozesse auf Betriebsmittel warten, die dem Prozess selbst oder einem anderen beteiligten Prozess zugeteilt sind. Eine Abart der Verklemmung ist der Livelock.

Der Zustand eines Deadlocks kann folgendermaßen definiert werden: Eine Menge von Prozessen befindet sich in einem Deadlock, wenn jeder dieser Prozesse auf ein Ereignis wartet, das nur ein anderer Prozess aus dieser Menge verursachen kann.[1]


Inhaltsverzeichnis

Allgemeines

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] müssen vier notwendige Kriterien für eine Verklemmung zutreffen:

  1. Die Betriebsmittel werden ausschließlich durch die Prozesse freigegeben (Da Ressourcenzugriff eines Prozesses nicht unterbrochen werden kann. No Preemption).
  2. Die Prozesse fordern Betriebsmittel an, behalten aber zugleich den Zugriff auf andere (Hold and Wait).
  3. Der Zugriff auf die Betriebsmittel ist exklusiv (Mutual Exclusion).
  4. Mindestens zwei Prozesse besitzen bezüglich der Betriebsmittel eine zirkuläre Abhängigkeit (Circular Wait).

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. Will man über den Vogel-Strauß-Algorithmus hinausgehen und die Möglichkeit einer Verklemmung einräumen, so muss man sie verhindern oder vermeiden, ggf. beseitigen.

Die Definitionen von Verklemmungsverhinderung und Verklemmungsvermeidung werden auch öfter vertauscht in der Literatur gefunden.

Verklemmungsverhinderung (deadlock prevention)

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.

Preemption durchführen
Einem Prozess werden Betriebsmittel entzogen, um sie einem anderen zuzuteilen.
Hold and Wait verhindern
Jeder Prozess gibt zu Beginn an, welche Betriebsmittel er benötigt. Falls alle benötigten Betriebsmittel gleichzeitig frei sind, bekommt sie ein Prozess auf einmal zugeteilt.
Mutual Exclusion beseitigen
Die benötigten Betriebsmittel für alle Prozesse zugänglich zu machen, indem man den exklusiven Zugriff auflöst. Alternativ Spooling (Beispiel: Drucker) oder Virtualisierung von Betriebsmitteln (Beispiel: CPU).
Circular Wait ausschließen
Betriebsmittel werden durchnummeriert und in aufsteigender Reihenfolge vergeben.

Verklemmungsvermeidung (deadlock avoidance)

Zusätzlich kann man versuchen, die Verklemmung zu vermeiden. 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. Z. B. 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 zu Verfügung. Ein Prozess π2 besitzt zwei Betriebsmittel und fordert noch acht Betriebsmittel. Dem zu Folge 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 zu Verfügung stehen, die nun Prozess π2 zugeteilt werden können.

Ein weiteres Verfahren zur Vermeidung stellt 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 Instanzierung zugewiesen.

wait/die:

  • Fordert eine Transaktion eine Sperre an, die von einer jüngeren gehalten wird, so wartet die ältere bis die Sperre von der jüngeren freigegeben wird.
  • Fordert eine Transaktion eine Sperre an, die von einer älteren gehalten wird, so bricht sie sich selber ab (genauer: sie startet neu, allerdings behält sie ihren alten Zeitstempel bei, um so „älter“ zu wirken und ihre Chancen zu erhöhen, diesmal komplett durchlaufen zu können)

wound/wait:

  • Fordert eine Transaktion eine Sperre an, die von einer jüngeren gehalten wird, so wird die jüngere abgebrochen (genauer: neu gestartet) und die ältere bekommt die Sperre zugewiesen.
  • Fordert eine Transaktion eine Sperre an, die von einer älteren gehalten wird, so wartet sie bis die Sperre von der älteren wieder freigegeben wird.

(Dieses Verfahren wird „wound“ und nicht „die“ genannt, da eine jüngere Transaktion, sofern sie im Verlauf des Zwei-Phasen-Sperrprotokolls (Wie es vorrangig in verteilten Datenbanken eingesetzt wird. Siehe 2PL in: Scheduler (Datenbank)) bereits ein "READY" gesendet hat, nicht abgebrochen wird. In diesem Fall wartet die ältere Transaktion bis zur Freigabe der Sperre.)

Eine Vermeidung ist oft sehr schwierig, da man schlecht abschätzen kann, welcher Prozess genügend Betriebsmittel wieder freigibt.

Verklemmungsbeseitigung (recovery from deadlocks)

Beseitigung durch Prozessabbruch

Die einfachste Art eine Verklemmung zu beseitigen ist das gezielte Abbrechen von Prozessen. Hierbei sollte nach Möglichkeit ein Prozess gewählt werden der die Verklemmung sicher löst, ansonsten muss das Verfahren wiederholt werden bis alle Konflikte beseitigt wurden. Der meist unvermeidliche Datenverlust kann bei geschickter Prozessauswahl minimiert werden, wodurch dieses Verfahren nur sehr schlecht automatisiert werden kann.

Beseitigung durch Preemption

Eine etwas elegantere Lösung um Verklemmungen zu beseitigen, ist einen Prozess der eine Ressource belegt zu suspendieren und erst zu einem späteren Zeitpunkt dessen Ausführung fortzusetzen. In der Zwischenzeit können die blockierten Prozesse ihre Aufgabe vollenden wodurch die Verklemmung beseitigt wird. Allerdings ist es für diese Vorgehensweise entscheidend, genau über die Tätigkeit des zu unterbrechenden Prozesses Bescheid zu wissen, um Fehler ausschließen zu können. Es ist meist praktisch nicht möglich Deadlocks durch dieses Verfahren automatisch zu beseitigen.

Beseitigung durch Rollback

Eine weitere Möglichkeit ist das Ausführen eines Rollback auf einem ausgewählten Prozess, der für die Verklemmung verantwortlich gemacht werden kann. Hierzu werden von jedem Prozess in vorher festgelegten zeitlichen Abständen Sicherungen angelegt zu denen bei Bedarf zurückgesprungen werden kann. Tritt eine Verklemmung auf, wird ein Prozess ausgewählt, auf den zuletzt gesicherten Zustand zurückgesetzt und suspendiert, um die Verklemmung zu beseitigen. Nicht alle Arten von Prozessen können Problemlos auf diese Weise zurückgesetzt werden. Beispielsweise eignet sich ein Festplatten-Schreibvorgang in den meisten Fällen besser als ein CD-Brennvorgang. Der unterbrochene Prozess wird seine Ausführung erst fortsetzen, wenn die benötigten Betriebsmittel bereit stehen, wodurch dieser in ungünstigen Fällen verhungern kann.

Varianten

Es gibt auch noch andere Formen der Verklemmung von Prozessen, die wie ein Deadlock die weitere Ausführung des Programms verhindern.

Livelock

Live bezeichnet eine Art des Deadlocks von zwei oder mehr Prozessen, 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 wait-Zustand, sondern ist weiterhin aktiv, kann aber auch nicht seine Aufgabe abarbeiten.

Anschaulich kann man sich dazu zwei Personen vorstellen, die sich in einem Gang entgegenkommen und bis in die Unendlichkeit versuchen, einander in der gleichen Richtung auszuweichen, und sich dabei trotzdem immer gegenseitig blockieren.

Siehe auch

Quellenangaben

  1. Tanenbaum, Andrew S.: Modern Operating Systems 2nd Edition
  2. Coffman, E.C., Elphick, M.J., and Shoshani, A.: “System Deadlocks,” Computing Surveys, vol. 3, pp. 67-78, June 1971.

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • dead|lock — «DEHD LOK», noun, verb. –n. 1. a condition or situation in which activity between two opposing sides stops because they are equally strong and neither one will give in; complete standstill: »Employers and strikers had reached a deadlock in their… …   Useful english dictionary

  • dead-lock — deadˈ bolt or deadˈ lock noun One moved by turning the key or knob without intervention of a spring • • • Main Entry: ↑dead …   Useful english dictionary

  • dead lock — impasse; deadlock; standstill; dead end …   English contemporary dictionary

  • dead-lock — n. Complete standstill, utter misunderstanding, insoluble difference …   New dictionary of synonyms

  • dead lock — …   Useful english dictionary

  • dead-bolt — deadˈ bolt or deadˈ lock noun One moved by turning the key or knob without intervention of a spring • • • Main Entry: ↑dead …   Useful english dictionary

  • Dead bolt — For other uses, see deadbolt (disambiguation). Door with two locks, one in the doorknob and a separate deadbolt. A dead bolt or dead lock (also deadbolt), is a locking mechanism distinct from a spring bolt lock because a deadbolt cannot be moved… …   Wikipedia

  • Dead Set (TV series) — Dead Set redirects here. For the album by The Grateful Dead, see Dead Set (album). Dead Set Format Horror, Thriller, Drama, Satire …   Wikipedia

  • Dead to Rights: Retribution — Developer(s) Volatile Games Publisher(s) Namco Bandai Games …   Wikipedia

  • Lock Up (U.S. band) — Lock Up is a rock band that featured Tom Morello on guitar before Rage Against the Machine was formed.The band was founded by the original guitar player Mike Livingston (formerly of The Mau Mau s) and Kevin Wood on bass. They had previously… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”