Kapitel 8 - Deadlocks
- notwendige und hinreichende Bedingung
- Deadlock-Erkennung und Vermeidung
- Bankieralgorithmus
|
Was sind die notwendigen Bedingungen für Deadlocks?
-
Mutual Exclusion (z.B. via Druckerspooler über Ersatz-BM
Buffer aufgelöst)
-
Belegungs- und Wartebedingung (Prozess kann weitere BM
anfordern)
-
Unterbrechbarkeitsbedingung (BM können nicht entzogen werden)
-
zyklische Wartebedingung (Zyklus im Betriebsmittelgraph)
Was sind die hinreichende Bedingungen für Deadlocks?
Es darf keine externe Betriebsmittelinstanz bestehen.
Was ist ein Livelock?
Es wurde ein Betriebsmittel vergeben, es besteht aber keine Verhinderung. Das
BM könnte irgendwann wieder freigegeben werden, aber der Zeitpunkt unbekannt.
Z.B. Priotitätsscheduling (langwierige Prozesse verhungern da
benachteiligt)
Wie kann man Deadlocks auflösen oder umgehen?
- Vogel-Strauß Algorithmus (einfach Ignorieren)
- Versuchen zu Erkennen und zu beheben (Topologische Sortierung des BM-Graphs
oder Vektoren-Matrix Variante)
- dynamisches Verhindern (vor Zuteilung auf Deadlock prüfen)
- konzeptionelles Vermeiden (eine der notwendigen Bedingungen eliminieren)
Welche Prozesse sind an einem Deadlock beteiligt?
Prozesse die mehrere Betriebsmittel mit jeweils exklusiven
Zugriff benötigen.
Wie kann man Deadlocks (im Voraus) erkennen?
Die zur Ausführung eines Prozesses notwendigen Betriebsmittel müssten vor
Ausführung bekannt sein. Das ist aber in einem offenen System nicht möglich. Das
Prinzip ist das gleiche wie das Preclaiming im DBMS. Erst wenn
alle angeforderten Betriebsmittel verfügbar sind, führt der Prozess den nächsten
Schritt aus. Algorithmisch wäre dies durch zyklische Prüfung (für jeden Prozeß) auf
Vorhandensein der erforderlichen Betriebsmittel erreichbar.
Wie werden Deadlocks beseitigt?
Durch Abbruch der beteiligten Prozesse und Freigabe der
belegten Betriebsmittel. Siehe optimistische Sperrverfahren bei
DBMS.
Wie können Deadlocks vermieden werden?
Möglichkeit 1
Es müsste bei jeder Betriebsmittelanforderung geprüft werden, ob diese zu einem
Deadlock führen würde. Da dies sehr aufwendig ist, wird so nicht verfahren.
Möglichkeit 2:
Bei Anforderung zusätzlicher Betriebsmittel werden alle bisher reservierten
Betriebsmittel freigegeben und dann zusammen mit den zusätzlichen Betriebsmitteln
erneut angefordert (Form von Preclaiming).
Möglichkeit 3
Betriebsmitteltypen werden linear nach Priorität angefordert . Falls schon
Betriebsmittel reserviert sind, können keine Betriebsmittel, die wichtiger sind als
die schon reservierten, angefordert werden. Damit wird zyklisches Warten unmöglich
(ähnelt dem 2-Phasen-Sperrprotokoll). Problem ist aber die Vergabe geeigneter
Nummerierungen, da reale und abstrakte Betriebsmittel (z.B. Spoolbereiche auf
Festplatten) sich nur schwer Ordnen lassen.
Möglichkeit 4 Der Banker Algorithmus als Verfahren zur Erkennung sicherer
Systemzustände bei der Verteilung von Ressourcen.
Wie arbeitet der Bankieralgorithmus?
Ein Banker hat einen bestimmte Menge einer Ressource. Jeder Kunde hat ein
Limit, bis zu dem er Ressourcen vom Banker erhalten kann. Der Banker hat aber so
viele Ressourcen, daß er das größte vorhandene Limit gerade noch bedienen kann. Der
Kunde bekommt die Ressource, falls der Banker danach noch genügend Ressourcen hat,
um mindestens einem der Kunden sein komplettes Limit zuteilen zu können.
Beispiel Bankieralgorithmus
Der Banker habe 10 Einheiten eines Betriebsmittels verfügbar.
- Das Limit von Kunde A betrage 8 Einheiten.
- Das Limit von Kunde B ist 7 Einheiten.
- A hat zur Zeit 5 Einheiten belegt
- und B hat 2 Einheiten reserviert
Falls B nun eine weitere Einheit anfordert, so muss dies verweigert werden, da
dann der Banker nur noch 2 Einheiten übrig hätte, diese aber nicht zur Befriedigung
einer kompletten Reservierung von A oder B ausreichen würde und zu einem Deadlock
führen würde. Solch ein Zustand heißt unsicherer Zustand. Der Problem ist nun, daß
jeder Prozeß muß im Voraus wissen muss, wieviele Einheiten eines Betriebsmittels er
maximal während seiner Abarbeitung benötigen wird.
Warum funktioniert die Deadlock-Vermeidung bei linearer Ordnung der
Betriebsmittel?
Prozesse können zwar alle Betriebsmittel anfordern, aber alle Anforderungen
müssen gemäß der Nummerierungsreihenfolge geschehen. Somit ist es von vornherein
ausgeschlossen, daß ein Prozeß der ein Betriebsmittel höherer Ordnung besitzt, ein
Betriebsmittel niedrigerer Ordnung, das von einem anderen Prozeß belegt ist,
anfordern kann. Also werden Schlingen im Wartegraph und damit Deadlocks vermieden,
da nun eine notwendige Voraussetzung für Deadlocks eliminiert wurde. Umgesetzt kann
das Ganze durch eine Nummerierung der Betriebsmittel werden. Das Prinzip ähnelt dem
Zeitstempelverfahren bei DBMS.
|
|
|
|
|
|
Kapitel 1
|
Einleitung
|
|
Ebenen- oder Schichtenmodell, Aufgaben...
|
|
Kapitel 2
|
Modelle
|
|
Schichtenmodell, Betriebsmittel, Instanzen...
|
|
Kapitel 3
|
Aktivitäten
|
|
Token, Multitasking, Prozesse,Timesharing...
|
|
Kapitel 4
|
Kritischer Abschnitt
|
|
Gegenseitiger Ausschluss,Peterson,Semaphore...
|
|
Kapitel 5
|
Scheduling
|
|
Prozessorzuteilung, Prioritätsscheduling, RR...
|
|
Kapitel 6
|
Speichermanagment
|
|
Freispeicherverwaltung, Segmentierung, Paging...
|
|
Kapitel 7
|
Seitenersetzung
|
|
NRU, FiFo, Second Chance, LRU, NFU, Aging...
|
|
Kapitel 8
|
Deadlocks
|
|
Bedingungen, Erkennung und Auflösung...
|
|
Kapitel 9
|
Dateisysteme
|
|
Freispeicherverwaltung, Festplattenscheduling...
|
|
|
|
|
|
|
|
Quellen:
|
Andrew S. Tanenbaum
Computerarchitektur
|
Andrew S. Tanenbaum
Moderne Betriebssysteme
|
Petterson
Computer Architectur & Design
|
Christian Märtin
Rechnerarchitekturen
|
Kalfa
Skript und Vorlesung
|
Word Wide Web
Verschiedenste Seiten
|
|
|
|
|
