Livelock

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]

Allgemeines

Beispielsweise kann einem Prozess π₁ der Bildschirm zugeteilt worden sein. Gleichzeitig benötigt π₁ allerdings den Drucker. Auf der anderen Seite ist der Drucker dem Prozess π₂ 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 π₁ 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 π₂ besitzt zwei Betriebsmittel und fordert noch acht Betriebsmittel. Dem zu Folge erhält Prozess π₁ 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 π₂ 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

• Lock
• Petri-Netz

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

• Lernprogramm Deadlock-Algorithmen
• Deadlock-Erkennung