Deadlocks

Andrew S. Tanenbaum Moderne Betriebssysteme 2. überarbeitete Auflage übersetzt von Prof. Dr. Uwe Baumgarten Technische Universität München ein Imprint der Pearson Education Deutschland GmbH KAPITEL 3 Deadlocks Computersysteme enthalten zahlreiche Ressourcen, die nur ein Prozess zur gleichen Zeit benutzen kann. Typische Beispiele sind Drucker, Bandlaufwerke oder Einträge in Systemtabellen. Wenn zwei Prozesse gleichzeitig denselben Drucker benutzen, wird er wahrscheinlich nur Unbrauchbares drucken. Wenn zwei Prozesse gleichzeitig in densel- ben Eintrag einer Dateizuordnungstabelle schreiben, wird das Dateisystem inkonsistent. Folglich müssen alle Betriebssysteme die Fähigkeit haben, Ressourcen (zeitweise) einem einzigen Prozess zuzuordnen. Viele Anwendungen verlangen nicht nur auf eine Ressource den alleinigen Zugriff, sondern gleich auf mehrere. Nehmen wir zum Beispiel an, zwei Prozesse wollen beide ein Dokument einscannen und es dann auf eine CD brennen. Prozess A reserviert sich zunächst den Scanner. Prozess B läuft etwas anders ab und verlangt zunächst den CD- Brenner. Als Nächstes versucht A, sich den CD-Brenner zu reservieren, was aber fehl- schlägt, weil B ihn noch nicht freigegeben hat. Dummerweise verlangt B nun den Scan- ner, statt den CD-Brenner freizugeben. Zu diesem Zeitpunkt sind beide Prozesse blockiert und daran wird sich auch so schnell nichts ändern. Eine solche Situation wird Deadlock genannt. Deadlocks können auch über mehrere Rechner verteilt sein, beispielsweise im lokalen Netz einer Firma, in dem Geräte wie Drucker und Scanner von jedem Benutzer an jedem Rechner benutzt werden können. Wenn diese Ressourcen von entfernten Rechnern (also von einem beliebigen Arbeitsplatz aus) reserviert werden können, kann dies zu derselben Art von Deadlocks führen, wie sie eben beschrieben wurden. In komplizierteren Situationen können sich Deadlocks ergeben, an denen drei, vier oder noch mehr Geräte und Benutzer beteiligt sind. Deadlocks können nicht nur durch die Reservierung von E/A-Geräten1 , sondern auch in vielen anderen Situationen entstehen. In einer Datenbankanwendung könnte ein Pro- gramm zum Beispiel die Datensätze, an denen es arbeitet, sperren, um Überschneidungen bei zeitkritischen Abläufen zu vermeiden. Wenn Prozess A den Datensatz R1 und Pro- zess B den Datensatz R2 sperrt und anschließend jeder Prozess versucht, den Datensatz des anderen zu sperren, entsteht ebenfalls ein Deadlock. Deadlocks können also sowohl durch Hardware- als auch durch Softwareressourcen entstehen. In diesem Kapitel werden wir das Thema Deadlocks genauer untersuchen. Wir werden sehen, wie sie entstehen, und einige Möglichkeiten untersuchen, sie zu vermeiden oder zu verhindern. Obwohl wir uns hier auf Deadlocks im Umfeld von Betriebssystemen konzentrieren, kommen Deadlocks auch in Datenbanksystemen und in vielen anderen Gebieten der Informatik vor. Der Stoff in diesem Kapitel lässt sich also auf ein weites Feld von Mehrprozesssystemen anwenden. 1 E/A wird zwecks Erleichterung des Leseflusses im folgenden als Abkürzung für Ein-/Ausgabe be- nutzt. Im englischen wird dazu auch I/O für In-/Output gebraucht. 178 Kapitel 3 – Deadlocks Über Deadlocks existiert bereits eine Menge Literatur. Einen Überblick geben zwei Bibliographien, die in der Operating Systems Review erschienen sind (Newton, 1979 und Zobel, 1983). Diese Artikel sind zwar alt, aber immer noch nützlich, da die meiste Forschung über Deadlocks vor 1980 unternommen wurde. 3.1 Ressourcen Deadlocks entstehen, wenn Prozessen das alleinige Zugriffsrecht auf Geräte, Dateien oder Ähnliches erteilt wird. Um Deadlocks so allgemein wie möglich zu behandeln, nennen wir die reservierten Objekte Ressourcen. Eine Ressource kann ein physisches Gerät sein (z. B. ein Laufwerk), aber auch eine Informationseinheit (z. B. ein gesperrter Datensatz). Normalerweise hat ein Computer viele verschiedene Ressourcen, die reserviert werden können. Von einigen Ressourcen können mehrere identische Instanzen existieren, z. B. drei Diskettenlaufwerke. Wenn mehrere Kopien einer Ressource zur Verfügung stehen, kann jede von ihnen benutzt werden, um eine Anfrage nach dieser Ressource zu erfüllen. Kurz gesagt ist eine Ressource etwas, das nur von genau einem Prozess gleichzeitig benutzt werden kann. 3.1.1 Unterbrechbare und ununterbrechbare Ressourcen Es gibt zwei Arten von Ressourcen: unterbrechbare und ununterbrechbare. Eine unter- brechbare Ressource2 kann dem Prozess, der sie besitzt, ohne unerfreuliche Neben- wirkungen entzogen werden. Ein Beispiel hierfür ist Arbeitsspeicher. Stellen wir uns ein System vor, das über 32 MB Speicher und einen Drucker verfügt. Auf dem System laufen zwei 32 MB große Prozesse, die beide etwas ausdrucken wollen. Prozess A reserviert sich den Drucker und beginnt mit der Berechnung der Daten, die ausgedruckt werden sollen. Bevor er damit fertig ist, überschreitet er sein Rechenzeitquantum und wird ausgelagert. Jetzt wird Prozess B ausgeführt und versucht ohne Erfolg, den Drucker zu reservieren. Wir befinden uns nun in einer möglichen Deadlock-Situation, da A den Drucker und B den Speicher besitzt. Keiner der beiden kann ohne die Ressource des anderen wei- termachen. Zum Glück ist es möglich, B den Speicher zu entziehen (präemptiv), indem man B auslagert und A einlagert. Jetzt kann A seine Berechnung beenden, die Daten ausdrucken und dann den Drucker freigeben. So entsteht kein Deadlock. Im Gegensatz dazu kann eine ununterbrechbare Ressource3 ihrem gegenwärti- gen Besitzer nicht entzogen werden, ohne dass dessen Ausführung fehlschlägt. Einem Prozess einen CD-Brenner während des Schreibvorgangs zu entziehen, führt zu einer zerstörten CD. CD-Brenner sind also ununterbrechbare Ressourcen, d.h., sie können ei- nem Prozess nicht jederzeit entzogen werden. Generell haben Deadlocks immer mit ununterbrechbaren Ressourcen zu tun. Mögliche Deadlocks, an denen unterbrechbare Ressourcen beteiligt sind, können normalerweise aufgelöst werden, indem man unterbrechbare Ressourcen neu zuteilt, also werden wir uns hier auf die ununterbrechbaren Ressourcen konzentrieren. 2 engl.: preemptable resource 3 engl.: nonpreemptable resource 3.1 Ressourcen 179 Die Benutzung einer Ressource besteht aus den folgenden abstrakten Teilschritten: 1. Die Ressource anfordern. 2. Die Ressource benutzen. 3. Die Ressource freigeben. Wenn eine Ressource gerade besetzt ist, muss der Prozess, der sie anfordert, warten. Einige Betriebssysteme blockieren einen Prozess automatisch, wenn eine Ressourcen- Anforderung fehlschlägt, und wecken ihn wieder auf, sobald sie frei wird. Andere geben einen Fehlercode zurück und der Prozess muss von sich aus kurz warten und es dann nochmal versuchen. Ein Prozess, dem eine Ressource verweigert wurde, sitzt normalerweise in einer engen Schleife, die die Ressource anfordert, kurz wartet und sie dann erneut anfordert. Obwohl dieser Prozess technisch gesehen nicht blockiert ist, kann man ihn mit gutem Gewissen als blockiert ansehen, da er keine sinnvolle Arbeit leisten kann. Im Folgenden werden wir annehmen, dass ein Prozess blockiert wird, wenn ihm eine Ressource verweigert wird. Wie eine Ressource genau angefordert wird, hängt stark vom jeweiligen System ab. Einige Systeme stellen einen request-Systemaufruf zur Verfügung, mit dem Prozesse ausdrücklich Ressourcen anfordern können. In anderen Systemen stellt das Betriebssys- tem spezielle Dateien zur Verfügung, die nur ein Prozess gleichzeitig öffnen kann. Der Zugriff funktioniert dann einfach mit dem üblichen open-Systemaufruf. Wenn die Datei schon von einem anderen Prozess geöffnet wurde, wird der aufrufende Prozess blockiert, bis der Besitzer sie schließt. 3.1.2 Ressourcenanforderung Bei manchen Arten von Ressourcen, wie etwa den Datensätzen einer Datenbank, müssen sich die Prozesse selbst um die Zuteilung der Ressourcen kümmern. Eine Möglichkeit der Ressourcenverwaltung durch die Benutzer ist, jeder Ressource ein Semaphor zu- zuordnen. Die Semaphoren werden alle mit 1 initialisiert. Ein Mutex pro Ressource funktioniert genauso gut. Die vorher erwähnten drei Schritte werden dann folgenderma- ßen implementiert: Die Ressource wird durch eine Down-Operation auf dem Semaphor reserviert, anschließend benutzt und schließlich durch eine Up-Operation wieder freige- geben. Diese Schritte werden in Abbildung 3.1(a) dargestellt. Es kann vorkommen, dass ein Prozess zwei oder mehrere Ressourcen gleichzeitig benötigt. Diese können dann wie in Abbildung 3.1(b) angefordert werden. Wenn der Prozess mehrere Ressourcen benötigt, fordert er sie einfach eine nach der anderen an. So weit, so gut. Solange nur ein Prozess beteiligt ist, funktioniert alles hervorragend. Natürlich gibt es eigentlich auch gar keinen Grund, Ressourcen formell anzufordern, wenn die Konkurrenz fehlt. Nehmen wir also an, es gibt zwei Prozesse A und B und zwei Ressourcen. Abbildung 3.2 zeigt zwei mögliche Szenarien. In Abbildung 3.2(a) fordern beide Prozesse die Res- sourcen in derselben Reihenfolge an, in Abbildung 3.2(b) ist die Reihenfolge verschieden. Der Unterschied scheint vernachlässigbar, ist es aber nicht. Einer der Prozesse in 3.2(a) wird die erste Ressource anfordern, bevor es der andere Prozess tut. Dieser Prozess wird dann auch die zweite Ressource bekommen und kann 180 Kapitel 3 – Deadlocks Abbildung 3.1 Jede Ressource wird durch ein Semaphor geschützt. (a) Eine Ressource.