Deadlock

Ein Deadlock (auch Verklemmung genannt) ist in der Informatik ein Zustand von Prozessen, bei dem mindestens zwei Prozesse untereinander auf Betriebsmittel warten, die dem jeweils anderen Prozess zugeteilt sind. Z.B. Kann einem Prozess π1 der Bildschirm zugeteilt worden sein. Gleichzeitig benötigt π1 allerdings den Drucker. Auf der Gegenseite ist der Drucker dem Prozess π2 zugeteilt, der wiederum den Bildschirm fordert.

Ein solcher Zustand kann nur unter bestimmten Voraussetzungen zu Stande kommen:

1. Die Betriebsmittel werden ausschließlich durch die Prozesse freigegeben (No Preemption).
2. Die Prozesse fordern zwar Betriebsmittel, geben aber keine ab (Hold and Wait).
3. Der Zugriff auf die Betriebsmittel ist exklusiv (Mutal Exclusion).
4. Nicht weniger als zwei Prozesse warten in einem geschlossenen System (Circular Wait).

Deadlocks 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.

Table of contents

1 Verhindern einer Verklemmung 2 Vermeidung 3 Beseitigung

Verhindern einer Verklemmung

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, ebenfalls nicht verklemmen.

Treten Verklemmungen ein, so können diese in der Regel nicht normal beseitigt werden. Statt dessen sollte die Betriebsmittelverwaltung versuchen, präventive Maßnahmen anzuwenden. Man spricht von einer Verhinderung, wenn mindestens eine der vier Bedingungen für einen Deadlock nicht erfüllt werden. So könnten z.B. Betriebsmittel einem Prozess entzogen, und gezielt einem anderen Prozess zugeteilt werden (betrifft Non Preemption).

Weitere Möglichkeiten:

• Mutal Exclusion: Die benötigten Betriebsmittel für alle Prozesse zugänglich zu machen, in dem man den exklusiven Zugriff auflöst.
• Hold and Wait: Ein Prozess gibt alle Betriebsmittel frei und kann erst danach auf andere benötigte Betriebsmittel zugreifen.
• Circular Wait: Betriebsmittel werden durchnummeriert und in aufsteigender Reihenfolge vergeben.

Vermeidung

Zusätzlich kann man versuchen den Deadlock 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 alle Prozesse ohne Deadlock zu einem Ende gebracht werden.

Bei einer Vermeidung müssen alle folgenden Vorgänge bekannt sein. Hierbei wird häufig der Bankiersalgorithmus 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 5 Betriebsmittel und er benötigt noch 3 weitere Betriebsmittel zur vollständigen Ausführung. Das Betriebssystem stellt noch 3 weitere Betriebsmittel zu Verfügung. Ein Prozess π2 besitzt 2 Betriebsmittel und fordert noch 8 Betriebsmittel. Dem zu Folge erhält Prozess π1 die 3 Betriebsmittel. Damit besitzt er alle Ressourcen um vollständig verarbeitet zu werden, worauf dem Betriebssystem nach der Verarbeitung 8 Betriebsmittel frei zu 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.

Beseitigung

Die einfachste Art eine Verklemmung zu beseitigen, besteht im Neustart des Systems. Besser ist es jedoch, wenn man nur einzelne Prozesse vernichtet. Dabei kann das System jedoch instabil werden.

Ebenfalls kann man einen oder mehrere Prozesse auf frühere Zustände zurücksetzten (Rollback). Wenn er ständig zurückgestellt wird und somit nie die benötigten Betriebsmittel erhält, kann der Prozess jedoch verhungern.