31
07.01.16 1 Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks Betriebssysteme Teil 12: Deadlocks

Betriebssysteme Teil 12: Deadlocks - Wirtschaftsinformatikwi.f4.htw-berlin.de/users/messer/LV/AI-BS-WS15/Folien/BS-12/12-BS-Deadlocks-1.pdf · Betriebssysteme - WS 2015/16 - Teil

Embed Size (px)

Citation preview

07.01.16 1Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks

Betriebssysteme

Teil 12: Deadlocks

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 2

Literatur

[12-1] Coffman, E. C.; Elphick, Michael John; Shoshani,A.: System Deadlocks. In: Computing Surveys. 3, Nr. 2, 1971, S. 67–78.Einsehbar in http://de.wikipedia.org/wiki/Deadlock

[12-2] Lernprogramm: Deadlock-Algorithmenhttp://olli.informatik.uni-oldenburg.de/Deadlock/Start.html

[12-3] Andrew S. Tanenbaum: Moderne Betriebssysteme, 2. Auflage, Hanser, 1995

[12-4] R.G. Herrtwich, G.Hommel: Kooperation und Konkurrenz, Springer, 1989

[12-5] Silberschatz, A.; Galvin, P.G.; Gagne, G.: Operating System Concepts. 9. Auflage, Wiley, 2012

[12-6] Finkel, Raphael: An Operating Systems Vade Mecum.http://sistop.gwolf.org/biblio/An_operating_system_vade_mecum_-_Raphael_Finkel.pdf

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 3

Übersicht

• Definitionen – Philosophen - reloaded

• Vermeidung

• Bankier-Algorithmus

• Erkennung

• Behandlung

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 4

Definitionen - Wiederholung

• Deadlock = Warten auf ein Ereignis, das nicht eintreten kann, weil die für das Ereignis verantwortliche Aktivität entweder nicht existiert oder selbst das Ereignis nicht realisieren kann

• Starvation = Zu langes Warten auf ein mögliches, aber zur weiteren Arbeit notwendiges Ereignis

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 5

Das Problem der Philosophen I – Verfahren 1

Verfahren 1

PROC philosopher(int nr) REPEAT wait(fork-right) wait(fork-left) eat(); release(fork-left) release(fork-right) think(); FOREVER

Verfahren 1

PROC philosopher(int nr) REPEAT p(fork[nr]) p(fork[(nr+1)%N]) eat(); v(fork(nr+1)%N) v(fork[nr]) think(); FOREVER

Die Gabeln werden als Array von Semaphoren mit dem initialen Wert 1realisiert.N ist die Anzahl der Gabeln bzw. Philosophen.

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 6

Das Problem der Philosophen II – Verfahren 2

PROC philosopher(int nr) REPEAT REPEAT p(fork-right) IF would sleep(fork-left) THEN v(fork-right) ELSE p(fork-left) FI UNTIL both-forks eat(); release(fork-left) release(fork-right) think(); FOREVER

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 7

Das Problem der Philosophen III

• Beim Verfahren 1 besteht die Gefahr eines Deadlocks, nämlich, wenn alle Philosophen zuerst erfolgreich ihre rechte Gabel genommen haben und dann zugleich auf die linke warten.

• Beim Verfahren 2 besteht die Gefahr von Starvation, da alle Philosophen wie in einem Tanz jeweils synchron ihre rechte Gabel aufnehmen, um sie in einer Schleife gleich wieder wegzulegen.

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 8

Bedingungen eines Deadlocks

(a)Ausschließliche Benutzung (Mutual Exclusion)Ein Betriebsmittel kann nicht gleichzeitig von mehreren Tasks benutzt werden, sondern ausschließlich von einer Task.

(b)Sequentielle Anforderung (Hold and Wait)Verschiedene Betriebsmittel werden nach einander angefordert.

(c)Keine Möglichkeit des Entzugs (No Preemption)Ein einmal zugewiesenes Betriebsmittel kann nicht von außen entzogen werden.

(d)Zyklen beim Warten (Circular Wait)Das Warten auf Freigabe von Betriebsmitteln ergibt einen Zyklus.

Erst wenn alle vier Bedingungen erfüllt sind, entsteht ein Deadlock.

Die Verhinderung von Deadlocks besteht darin, dafür zu sorgen, dassmindestens eine dieser Bedingungen nicht erfüllt ist.

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 9

Vermeidung – Strategie 1

• Wenn mehrere Ressourcen benötigt werden, dann werden diese immer zugleich in einem Stück angefordert.Wenn bei einer Ressource gewartet werden muss, werden die anderen eventuell freien nicht belegt; also ganz oder gar nicht.

• Nachteil:Ressourcen werden zu früh angefordert (niedrige Effizienz)

PROC philosopher(int nr) REPEAT p(fork-right,fork-left) eat(); release(fork-left) release(fork-right) think(); FOREVER

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 10

Vermeidung – Strategie 2 I

• Alle Ressourcen erhalten eine Nummer.

• Eine Task darf immer nur Ressourcen einer höheren Nummer anfordern als er schon besitzt.

• Wenn Ressourcen dieselbe Nummer besitzen, werden sie zugleich angefordert.

Damit ist die Reihenfolge der Anforderungen für alle Tasks gleich.

• Nachteile– Ein vernünftige Vergabe der Nummern ist schwierig.

– Verletzungen dieser Regel sind aufwendig zu prüfen.

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 11

Vermeidung – Strategie 2 II

Schritt P0 P1 P2 P3

1 wait(f0) get(f1) get(f2) get(f0)

2 - wait(f2) get(f3) wait(f3)

3 - - eat -

4 - - put(f3) get(f3)

5 - get(f2) put(f2) eat

6 - eat think put(f3)

7 get(f0) put(f2) - put(f0)

8 get(f1) put(f1) - think

9 eat think - -

10 put(f1) - - -

11 put(f2) - - -

12 think - - -

P2 gewinnt

P3 gewinnt

Es werden immer die Gabeln mit der niedrigeren Nummer zuerst angefordert.

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 12

Vermeidung – Strategie 2 III - Erläuterungen

• Es bedeuten:– wait(fx) Philosoph forderte Gabel fx an und wurde schlafen gelegt

– get(fx) Philosoph erhält Gabel fx

– put(fx) Philosoph legt Gabel fx zurück

• Auf der vorherigen Folie ist ein Beispielablauf dargestellt, bei dem zwei Konflikte entstehen. In diesen gewinnt einer der Philosophen. Auch wenn der jeweils andere Philosoph gewinnen würde, würde es keinen Deadlock geben.

• Das Verfahren vermeidet die zyklische Bedingung, da einer der Philosophen zuerst nicht wie alle anderen seine linke sondern seine rechte Gabel anfordert und damit nicht sofort in Konflikt mit seinem Nachbarn gerät. Das führt dazu, dass immer ein Philosoph beide Gabeln bekommen kann.

• An der Darstellung ist gut erkennbar, dass Philosoph P0 verhungern könnte, denn er muss zwei Essenszeiten warten...

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 13

Vermeidung – Bankier-Algorithmus I

Used

R1 R2 R3

P1 1 2 0

P2 1 1 1

P3 0 0 0

R1 R2 R3

P1 2 3 0

P2 1 4 1

P3 1 0 2

Claim

Free 1 1 1

Avail 3 4 2

• Der Bankier-Algorithmus beruht darauf, dass alle Tasks zum Start die maximale Anzahl an benötigten Ressourcen angeben müssen; diese Zahl darf sich später nicht ändern.

• Es gibt in diesem Beispiel drei Klassen von Ressourcen R1 bis R3. Es gibt drei Tasks P1 bis P3, die schon in der Used-Tabelle einen Teil ihrer Ressourcen angefordert und bekommen haben.

• Die Claim-Tabelle gibt an, wie viele Ressourcen maximal die Tasks anfordern dürfen, d.h. ihr "Recht".

Der Algorithmuswird an einemBeispiel spätererläutert.

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 14

Vermeidung – Bankier-Algorithmus II

• Ein Zustand heißt sicher, wenn es eine Sequenz von Ressourcen-Zuteilungen gibt, bei der alle Tasks positiv terminieren.

• Sicher bedeutet, dass dann mindestens eine Task alle ihre ausstehenden Ressourcen erhalten und terminieren kann.

• Prüfung, ob ein Zustand sicher ist:1)Einer Task werden fiktiv seine noch ausstehenden Ressourcen

zugeordnet.

2)Damit kann er terminieren: alle seine Ressourcen werden freigegeben und er wird aus der Liste der Tasks entfernt.

3)Die nun fiktiv entstandene neue Situation wird geprüft, ob eine weitere Task terminieren kann (nun mit den vermehrten freien Ressourcen). Mit diesem wird genauso verfahren.

4)Wenn am Ende alle Tasks terminieren können, ist der Ausgangszustand sicher, ansonsten unsicher.

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 15

Vermeidung – Bankier-Algorithmus III

Used R1 R2 R3

P1 1 2 0

P2 1 1 1

P3 0 0 0

R1 R2 R3

P1 2 3 0

P2 1 4 1

P3 1 0 2

Claim

Free 1 1 1

Avail 3 4 2

P1 bekommt alles Nötige

Used R1 R2 R3

P1 2 3 0

P2 1 1 1

P3 0 0 0

Free 0 0 1

Avail 3 4 2 und kann terminieren

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 16

Vermeidung – Bankier-Algorithmus IV

Used R1 R2 R3

- 0 0 0

P2 1 1 1

P3 0 0 0

R1 R2 R3

P1 2 3 0

P2 1 4 1

P3 1 0 2

Claim

Free 2 3 1

Avail 3 4 2

P2 bekommt alles Nötige

Used R1 R2 R3

- 0 0 0

P2 1 4 1

P3 0 0 0

Free 2 0 1

Avail 3 4 2 und kann terminieren

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 17

Vermeidung – Bankier-Algorithmus V

Used R1 R2 R3

- 0 0 0

- 0 0 0

P3 0 0 0

R1 R2 R3

P1 2 3 0

P2 1 4 1

P3 1 0 2

Claim

Free 3 4 2

Avail 3 4 2

P3 bekommt als letzte Task alles Nötige und kann terminieren,daher war die Ausgangssituation sicher.

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 18

Vermeidung – Bankier-Algorithmus VI

Used R1 R2 R3

P1 1 2 0

P2 1 1 1

P3 1 0 0

R1 R2 R3

P1 2 3 0

P2 1 4 1

P3 1 0 2

Claim

Free 0 1 1

Avail 3 4 2

P3 fordert eine Ressource vom Typ R1 an und es entsteht die obigeSituation, die unsicher ist, denn keine andere Task kann terminieren.

Daher darf diese Ressourcen-Zuweisung nicht erfolgen.

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 19

Vermeidung – Bankier-Algorithmus VII

1) Bevor ein Task seine angeforderten Ressourcen bekommt, wird geprüft, ob dadurch ein unsicherer Zustand entsteht. Tut es das, dann muss die anfordernde Task warten, auch dann wenn die konkret angeforderten Ressourcen frei sind.

2) Entsteht dagegen ein sicherer Zustand, dann erhält die Task ihre angeforderten Ressourcen.

• Das bedeutet, dass sichere Zustände in jedem Falle Deadlocks vermeiden, aber unsichere Zustände zu Deadlocks führen können.

• Ein unsicherer Zustand ist also gekennzeichnet durch die Menge der Abläufe ohne Deadlocks vereinigt mit der Menge der Abläufe mit einem Deadlock.

Ein (zentraler) Ressource-Manager führt aus:

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 20

Vermeidung – Bankier-Algorithmus VIII

• Der Bankier-Algorithmus funktioniert sehr gut, wenn zum Zeitpunkt des Systemstarts die Anforderungen sowie Anzahl der Ressourcen und Tasks bekannt und konstant sind.

• Diese Bedingung ist eigentlich nur bei den Embedded-Systems, den in anderen Geräten verbauten Rechnern mit festen Aufgaben erfüllt; für Desktop- oder Server-Rechner gilt dies nicht.

• Der Algorithmus hat seinen Namen wegen der Analogie eines (guten) Bankiers, der immer soviel Geld (Ressourcen) in seinem Tresor (Freie Ressourcen) hat, damit er jederzeit den Kunden (Tasks) ihre Sparguthaben (Claim) auszahlen kann.

• Dieser Algorithmus wurde von Edsger W. Dijkstra 1965 entworfen, in einer Zeit, in der an das Gute im Bankier noch geglaubt wurde.

• Es gibt einen schnelleren Algorithmus von Nico Habermann.

Siehe: http://de.wikipedia.org/wiki/Bankieralgorithmus

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 21

Erkennung von Deadlocks I

• Das Verfahren ist dem Bankier-Algorithmus ähnlich, nur dass hier nicht von vornherein bekannt ist,

– wer maximal welche Ressourcen bekommen will.

– wie viele Tasks beteiligt sind.

• M.a.W. es werden richtige praktische Situationen betrachtet.

• Das nun an einem Beispiel skizzierte Verfahren wird von einer zentralen Überwachungs-Task durchgeführt, der dann Deadlocks feststellt.

• Die Zuweisung von Ressourcen erfolgt vollkommen unabhängig von dieser Überwachungs-Task.

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 22

Erkennung von Deadlocks II - Ausgangssituation

Used R1 R2 R3 R4

P1 0 1 0 1

P2 1 1 0 0

P3 0 0 0 0

P4 0 0 0 0

R1 R2 R3 R4

P1 1 0 1 0

P2 0 1 1 0

P3 0 0 0 1

P4 0 0 0 1

Wait

Free 1 1 1 2

Avail 2 3 1 3

Used: Matrix mit den benutzten RessourcenWait: Matrix mit den zu erlangenden Ressourcen

P3 bekommt R4 und terminiert.

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 23

Erkennung von Deadlocks III

Used R1 R2 R3 R4

P1 0 1 0 1

P2 1 1 0 0

- 0 0 0 0

P4 0 0 0 0

R1 R2 R3 R4

P1 1 0 1 0

P2 0 1 1 0

- 0 0 0 0

P4 0 0 0 1

Wait

Free 1 1 1 2

Avail 2 3 1 3

P4 bekommt R4 und terminiert.

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 24

Erkennung von Deadlocks IV

Used R1 R2 R3 R4

P1 0 1 0 1

P2 1 1 0 0

- 0 0 0 0

- 0 0 0 0

R1 R2 R3 R4

P1 1 0 1 0

P2 0 1 1 0

- 0 0 0 0

- 0 0 0 0

Wait

Free 1 1 1 2

Avail 2 3 1 3

P1 bekommt R1 und R3 und terminiert.

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 25

Erkennung von Deadlocks V

Used R1 R2 R3 R4

P1 0 0 0 0

P2 1 1 0 0

- 0 0 0 0

- 0 0 0 0

R1 R2 R3 R4

P1 0 0 0 0

P2 0 1 1 0

- 0 0 0 0

- 0 0 0 0

Wait

Free 1 2 1 3

Avail 2 3 1 3

P2 bekommt R2 und R3 und terminiert. --> Kein Deadlock!

Denn es gibt beginnend von der Ausgangssituation eine Sequenz, diezum Terminieren aller beteiligten Tasks führt.

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 26

Erkennung von Deadlocks VI - Ausgangssituation

Used R1 R2 R3 R4

P1 0 1 0 1

P2 2 1 0 0

P3 0 0 0 0

P4 0 0 0 0

R1 R2 R3 R4

P1 1 2 1 0

P2 0 2 1 0

P3 0 0 0 1

P4 0 0 0 1

Wait

Free 0 1 1 2

Avail 2 3 1 3

Nun wird variiert: P2 besitzt schon zwei Ressourcen R1, so dass keinevon der Sorte R1 mehr frei sind. P1 und P2 wollen beide zwei Stück vonR2 bekommen...

P3 und P4 bekommen jeweils einmal R4 und können terminieren.

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 27

Erkennung von Deadlocks VII

Used R1 R2 R3 R4

P1 0 1 0 1

P2 2 1 0 0

- 0 0 0 0

- 0 0 0 0

R1 R2 R3 R4

P1 1 2 1 0

P2 0 2 1 0

- 0 0 0 0

- 0 0 0 0

Wait

Free 0 1 1 2

Avail 2 3 1 3

P1 kann nicht terminieren, denn R1 ist vergeben.P2 kann nicht terminieren, denn dafür ist ein R2 zu wenig frei.

Also liegt ein Deadlock vor, denn es gibt keine Sequenz der Ressourcen-Zuordnung, die zum Terminieren aller Tasks führt.

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 28

Behandlung von Deadlocks

• Feststellen, wer mit welchen Ressourcen im Deadlock liegtReaktionen:– Bestimmte Ressourcen wegnehmen

– Bestimmte Tasks von außen abbrechen

• Kriterien für destruktive Maßnahmen– Wichtigkeit/Priorität

– Dauer der bisherigen Verarbeitung

– Fähigkeit zum WiederanlaufIntern werden z.B. Transaktionen benutzt

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 29

Zeitpunkte der Prüfungen auf Deadlocks

• Regelmäßig, z.B. alle paar Minuten

• Wenn eine Task seine Reaktionszeit nicht einhält

• Wenn die CPU-Belastung unter einen Normalwert fällt

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 30

Und die Praxis?

• In (fast) allen Betriebssystemen der Unix- und Windows-Familie wird weder Deadlock-Vermeidung noch Deadlock-Erkennung durchgeführt.

• Stattdessen wird dafür gesorgt, dass genügend Ressourcen verfügbar sind, so dass keine Konflikte entstehen.

• Diese Verfahren werden nur bei Embedded-Systems benutzt, da in diesem Bereich nur wenige Ressourcen und wenige Tasks möglich sind.

Betriebssysteme - WS 2015/16 - Teil 12/Deadlocks 31

Nach dieser Anstrengung etwas Entspannung....

Das mit den Deadlocks ist etwas steinig...