Kapitel 8 - Deadlocks
|
Inhalt
|
- 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
|
|
|
|
|
|
|
Home 
