Deadlock (Informatik)

Ein Deadlock (auch Verklemmung genannt) ist in der Informatik ein Zustand von Prozessen, bei dem mindestens zwei Prozesse auf Betriebsmittel warten, die einem anderen beteiligten Prozess zugeteilt sind. Beispielsweise kann einem Prozess π₁ der Bildschirm zugeteilt worden sein. Gleichzeitig benötigt π1 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 Auto rechts von ihm fährt.
Ein weiteres Beispiel ist das Philosophenproblem.

Nach Coffman et al. (1971) müssen vier notwendige Kriterien für einen Deadlock zutreffen:

Die Betriebsmittel werden ausschließlich durch die Prozesse freigegeben (No Preemption).
Die Prozesse fordern Betriebsmittel an, besitzen aber zugleich den Zugriff auf andere (Hold and Wait).
Der Zugriff auf die Betriebsmittel ist exklusiv (Mutual Exclusion).
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.

Die Definitionen von Deadlock-Verhinderung und Deadlock-Vermeidung werden auch öfters vertauscht in der Literatur gefunden.

Deadlock-Verhinderung

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.

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

Deadlock-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 mindestens eine Scheduling - Reihenfolge existiert, in welcher alle vorhandenen Prozesse beendet werde können, selbst wenn diese noch ihre maximalen Ressourcenanforderungen stellen sollten.

Bei einer Vermeidung müssen alle folgenden Vorgänge bekannt sein. Hierbei wird häufig der Banker's Algorithmus angewandt, bei dem die Betriebsmittel nur dann einem Prozess zugeteilt werden, wenn sie vollständig zurückgegeben werden. Z. B. hat ein Prozess π₁ 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 π₂ besitzt 2 Betriebsmittel und fordert noch 8 Betriebsmittel. Dem zu Folge erhält Prozess π₁ 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 π₂ zugeteilt werden können.

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

Deadlock-Beseitigung

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

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

Deadlock in der Politik

In der Verfassung der Vereinigten Staaten von Amerika ist ein Deadlock der Zustand, wenn die verfassungsrechtlichen Institutionen auf verschiedene Parteien verteilt sind. Einen Deadlock gibt es, wenn beispielsweise die Republikaner das Weiße Haus kontrollieren, also wenn der Präsident ein Republikaner ist, und die Opposition, also die Demokraten, den Kongress (Senat und Repräsentantenhaus) kontrollieren. Somit ist die Macht streng nach den Lehren aus der Gewaltenteilung verteilt. Das gegeneinander Arbeiten von Kongress (Legislative) und Präsident (Exekutive) war von den Gründungsvätern, die stark von der Aufklärung beeinflusst waren, beabsichtigt. Sie versuchten den Deadlock eintreten zu lassen, in dem sie Zwischenwahlen fest in die Verfassung verankerten. D.h., dass immer in der Mitte der Amtszeit des Präsidenten weite Teile des Kongresses (also das gesamte Repräsentantenhaus und ⅓ des Senates) neu gewählt werden. Nur zweimal trat nach zwei Jahren kein Deadlock ein. Das eine Mal 2002, als die Wahl noch von den Terroranschlägen am 11. September 2001 in den USA beeinflusst war. Deshalb kann George W. Bush momentan ohne einen Deadlock regieren.

Siehe auch

Speisende_Philosophen

Weblinks