Coffman-Bedingungen: Deadlocks sicher erkennen

Ein Betriebsmittel (auch Ressource) ist ein Systemelement, das ein Prozess zur korrekten Ausführung braucht, zum Beispiel Festplatte, Arbeitsspeicher oder Drucker. Das Betriebssystem regelt den Zugriff darauf. Ein Deadlock (Verklemmung) ist eine zyklische Wartesituation zwischen mehreren Prozessen: Jeder beteiligte Prozess wartet auf mindestens ein Betriebsmittel, das ein anderer beteiligter Prozess bereits exklusiv belegt hat.

Nach Coffman et al. sind die folgenden vier Bedingungen hinreichend für die Möglichkeit einer Verklemmung.

Mutual Exclusion (gegenseitiger Ausschluss): Der Zugriff auf ein Betriebsmittel ist exklusiv. Nur einem einzigen Prozess wird der Zugriff gestattet. Eine Datei, auf die schreibend zugegriffen wird, kann zum Beispiel nur exklusiv von einem Prozess genutzt werden. Gelesen werden kann eine Datei dagegen von mehreren Prozessen gleichzeitig.

Hold and Wait: Die Prozesse fordern Betriebsmittel an, behalten aber zugleich den Zugriff auf andere.

No Preemption: Die Betriebsmittel werden ausschließlich durch die Prozesse freigegeben, weil der Ressourcenzugriff eines Prozesses nicht unterbrochen werden kann. Ein Drucker ist ein nicht-entziehbares Betriebsmittel: Er muss bis zur Beendigung der Tätigkeit beim Prozess bleiben. Speicher dagegen ist entziehbar.

Circular Wait (zirkuläres Warten): Mindestens zwei Prozesse besitzen bezüglich der Betriebsmittel eine zirkuläre Abhängigkeit.

Einen festen Ablauf schreibt dir die Theorie hier nicht vor. Ein sinnvoller Vorschlag zum Üben: Du fragst die vier Bedingungen nacheinander ab und belegst jede am Fall.

Zuerst klärst du, ob überhaupt eine Verklemmung in Frage kommt. Existiert nur ein Prozess in einem geschlossenen System, so kann er niemals verklemmen. Ebenso kann ein Prozess, der nur ein Betriebsmittel benötigt, nicht verklemmen. Verklemmungen können bei Systemen eintreten, die mehrere Prozesse parallel ablaufen 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.

Dann fragst du der Reihe nach: Ist der Zugriff exklusiv (Mutual Exclusion)? Kann man das Betriebsmittel dem Prozess nicht entziehen (No Preemption)? Hält ein Prozess etwas und fordert zugleich mehr an (Hold and Wait)? Bilden mindestens zwei Prozesse einen Kreis aus Abhängigkeiten (Circular Wait)? Sind alle vier erfüllt, ist eine Verklemmung möglich. Fehlt eine, sind nicht alle vier erfüllt.

Ein zweiter Fall: Zwei Jobs Jₕ und Jₙ und zwei Ressourcen R₁ und R₂. Jₙ beginnt und greift R₁. Jₕ verdrängt Jₙ und greift erst R₂ und dann R₁. Dabei geht die Zeitscheibe von Jₕ auf Jₙ über. Jₙ greift R₂, bevor er R₁ freigibt. Es tritt eine Verklemmung auf: Keiner der beiden Jobs kann gerechnet werden, weil jeder eine Ressource hält, die der andere benötigt. Man sagt, sie hängen zyklisch voneinander ab.

Treten Verklemmungen ein, können sie in der Regel nicht normal beseitigt werden. Stattdessen sollte die Betriebsmittelverwaltung präventive Maßnahmen anwenden, um eine geeignete Sequentialisierung zu erreichen. Man spricht von einer Verhinderung, wenn mindestens eine der vier Bedingungen nicht erfüllt wird. Die Idee: Du suchst eine Bedingung, die du am Fall abschalten kannst.

Zu den Bedingungen gibt es diese Maßnahmen. Gegen No Preemption: Preemption durchführen. Einem Prozess werden Betriebsmittel entzogen, um sie einem anderen zuzuteilen. Gegen Hold and Wait: Jeder Prozess gibt zu Beginn an, welche Betriebsmittel er benötigt. Falls alle benötigten Betriebsmittel gleichzeitig frei sind, bekommt er sie auf einmal zugeteilt. Gegen Mutual Exclusion: Man macht die Betriebsmittel für alle Prozesse zugänglich, indem man den exklusiven Zugriff auflöst. Alternativ gibt es Spooling (Beispiel: Drucker) oder die Virtualisierung von Betriebsmitteln (Beispiel: CPU). Gegen Circular Wait: Die Betriebsmittel werden linear geordnet und nur in dieser definierten Reihenfolge angefordert oder zugeteilt.

Begründen heißt also: Du nennst die Bedingung, die wegfällt, und sagst, wie die Maßnahme das erreicht.

Verwechsle Verhinderung nicht mit Vermeidung. Bei der Vermeidung sind Verklemmungen theoretisch möglich, das System überwacht die Prozesse aber so, dass sie nicht verklemmen. Das beruht auf der Methode des sicheren Zustands. In der Literatur werden beide Begriffe auch öfter vertauscht.