4.3 Verklemmungen
... drohen überall, wo synchronisiert wird
Def. 1 (1.3):
Beim Ablauf eines nichtsequentiellen Programms
liegt eine Verklemmung (deadlock) vor,
wenn es Prozesse im Wartezustand gibt,
die durch keine mögliche Fortsetzung des
Programms daraus erlöst werden können.
Def. 2: Eine Verklemmung heißt deterministisch,
wenn sie bei jedem möglichen Ablauf – mit gleichen
Eingabedaten – eintritt (andernfalls nichtdeterminstisch).
Def. 3: Eine Verklemmung heißt total oder partiell,
je nachdem, ob alle oder nicht alle Prozesse
verklemmt sind.
3 Alternativen für den Umgang mit Verklemmungen:
 Erkennung (detection) + Auflösung
 Umgehung/Vermeidung (avoidance)
 Ausschluß (prevention)
Wichtigstes Anwendungsgebiet:
Verklemmungen beim Sperren von Ressourcen (nichtdeterm.)
 Datenbanksysteme (DB):
2-Phasen-Sperren
 Betriebssysteme (BS):
Betriebsmittelverwaltung
Anzahl Exemplare
Anzahl Typen
1
1
mehrere
mehrere
1/N (BS)
N/1 (DB,BS)
N/M (BS)
4.3.1 Erkennung
am Beispiel N/1
Def.: Anforderungsgraph ist markierter gerichteter Graph,
der den Systemzustand modelliert:
 Ecke bedeutet Prozeß, ist markiert mit Menge
der Ressourcen, die in seinem Besitz sind

Kante PQ, markiert mit r, bedeutet:
P wartet auf Ressource r, die im Besitz von Q ist.
Beachte: Jede Ecke hat höchstens eine konvergierende Kante.
Beispiel mit 4 Prozessen A,B,C,D und 3 Ressourcen r,s,t:
Zeit
0
A
B
C
D
lock(r)
lock(s)
lock(t)
s
B
D
rA
C
t
Beispiel mit 4 Prozessen A,B,C,D und 3 Ressourcen r,s,t:
Zeit
0
1
A
B
C
lock(r)
lock(s)
lock(s)
lock(t)
s
D
s
B
D
rA
C
t
Beispiel mit 4 Prozessen A,B,C,D und 3 Ressourcen r,s,t:
Zeit
0
1
2
A
B
C
D
lock(r)
lock(s)
lock(s)
lock(t)
lock(s)
s
s
B
s
D
rA
C
t
Beispiel mit 4 Prozessen A,B,C,D und 3 Ressourcen r,s,t:
Zeit
0
1
2
3
A
B
C
D
lock(r)
lock(s)
lock(s)
lock(t)
lock(s)
lock(t)
s
rA
s
B
s
t
C
t
D
Beispiel mit 4 Prozessen A,B,C,D und 3 Ressourcen r,s,t:
Zeit
0
1
2
3
4
A
B
C
D
lock(r)
lock(s)
lock(s)
lock(t)
lock(s)
lock(t)
lock(r)
s
s
B
s
t
rA
r
C
t
D
Eine Verklemmung liegt genau dann vor, wenn der
Anforderungsgraph einen Zyklus enthält.
Verklemmungs-Erkennung:
Ständige Überwachung des Anforderungsgraphen:
bei jedem Hinzufügen einer Kante PQ prüfen,
ob damit ein Zyklus geschlossen wird,
d.h. ob es einen Weg von Q nach P gibt.
( ! Ohne Backtracking,
weil jede Ecke höchstens eine divergierende Kante hat ! )
Repräsentation des Anforderungsgraphen:
Prozesse durchnumeriert mit
Ressourcen durchnumeriert mit
Ferner:
1,...,processCount
1,...,resourceCount
me() liefert die Nummer des laufendes Prozesses
int[] owner = new int[resourceCount+1];
// owner[i]: process that owns resource i
// - if any, else 0
int[] requested = new int[processCount+1];
// requested[i]: resource requested by
// process i - if any, else 0
Verklemmungs-Erkennung: bei jeder Anforderung einer
im Augenblick nicht verfügbaren Ressource res
wird mit deadlock(int res) geprüft,
ob ein Zyklus entsteht:
boolean deadlock(int res) {
int p;
// 1..processCount
int r = res;
// 0..resourceCount
do { p = owner[r];
// != 0
r = requested[p]; }
while(r!=0);
return p==me();
}
Verklemmungs-Auflösung
durch Wahl eines Opfers, dem gewaltsam
die Ressource entzogen wird – mit der Konsequenz

(Datenbank:) Transaktion abbrechen
und neu starten

(Checkpointing:) Prozeß zurücksetzen
zum letzten Checkpoint

(sonst:) Prozeß abbrechen
4.3.2 Vermeidung
am Beispiel 1/N
Beispiel:
2 Prozesse P,Q
mit n = 4 Exemplaren eines Ressourcen-Typs
Vor.: Maximalbedarf jedes Prozesses ist bekannt
und ist  n.
P:
0
1
Q:
0
1
2
1
2
2
3
2
1
3
2
1
0
0
Beobachtungen:
Wie ein Prozeß sich in der Zukunft verhalten wird,
ist unbekannt (abgesehen vom Maximalbedarf);
man muß daher stets mit dem Schlimmsten rechnen,
d.h. daß er seinen Maximalbedarf fordert;
wenn man die Ressourcen-Vergabe so steuert,
daß jederzeit für mindestens einen Prozeß die
Maximalforderung befriedigt werden kann,
kann dieser garantiert zu Ende gebracht werden
- womit eine Verklemmung vermieden wird.
Def.: Ein Zustand in einem Ablauf heißt sicher (safe),
wenn in ihm für mindestens einen Prozeß der
Maximalbedarf befriedigt werden kann.
Feststellung 1:
Ein direkter Übergang von einem sicheren
Zustand in einen Verklemmungszustand
ist nicht möglich.
Feststellung 2:
Verklemmungen werden vermieden,
wenn das System stets in einem sicheren
Zustand gehalten wird.
Feststellung 3:
Die Sicherheit beizubehalten ist möglich:
 der Anfangszustand ist sicher;
 in einem sicheren Zustand wird der Anforderung
eines Prozesses nur dann stattgegeben, wenn
der Folgezustand ebenfalls sicher ist (selbst wenn
genügend freie Ressourcen vorhanden sein sollten!).
Die eventuelle Blockierung des anfordernden
Prozesses kann keine Verklemmung verursachen
da der Ausgangszustand sicher ist.
Feststellung 4:
Die Orientierung an der Sicherheit ist eine
konservative Strategie: Sicherheit ist
hinreichend, aber nicht notwendig
für Verklemmungsfreiheit.
Maximalforderung
von P : 3
von Q : 3
sicher sicher sicher
P:
0
1
Q:
0
1
2
1
Verklemmung
2
2
3
3
2
2
1
0
1
0
unsicher unsicher
Bereits dieser Zustand würde nicht
zugelassen werden, d.h. der Anforderung
von Q (1  2) würde nicht stattgegeben werden
Bankiers-Algorithmus (banker‘s algorithm) [Dijkstra 65]
beantwortet die Frage nach der Sicherheit für
beliebig viele Prozesse:
Ein Zustand heißt sicher, wenn in ihm mindestens
ein Prozeß unter Gewährung seines Maximalbedarfs
zum Abschluß gebracht werden kann
und mit den damit freiwerdenden Ressourcen ein
weiterer Prozeß zum Abschluß gebracht werden kann
und mit den damit freiwerdenden .....
usw.
Präzisierung:
Setze B auf Anzahl der Betriebsmittel;
setze F auf Anzahl der freien Betriebsmittel;
setze P auf Menge der Prozesse.
Wiederhole: suche Prozeß pP,
dessen Maximalbedarf befriedigt werden kann;
wenn nicht vorhanden, Unsicher;
erhöhe F um aktuellen Betriebsmittelbesitz von p;
wenn F = B, Sicher;
streiche p aus P.
Dieser Algorithmus wird entweder mit der Meldung
Unsicher oder mit der Meldung Sicher beendet.
Weitere Präzisierung:
int resCount
int available
int procCount
int[] maxclaim
int[] allocated
Anzahl der Betriebsmittel
freie Betriebsmittel
Anzahl der Prozesse
Maximalforderungen der Prozesse
vergebene Betriebsmittel
boolean safe() {
boolean[] terminated = new boolean[procCount];
int avail = available;
int p = 0;
while(p < procCount) {
if(terminated[p] ||
maxclaim[p] – allocated[p] > avail)
p++;
else {terminated[p] = true;
avail += allocated[p];
p = 0; } }
return avail == total; }
Bemerkungen:
Effizienzverbesserungen möglich, z.B. Prozesse in der
Reihenfolge abfallender maximaler Zusatzforderung
betrachten.
Gegebenenfalls Maßnahmen für die Gewährleistung
von Fairness treffen.
Der Bankiers-Algorithmus kann für den Fall N/M
verallgemeinert werden („mehrere Währungen“)
– was aber eher von akademischem Interesse ist
4.3.3 Ausschluß
am Beispiel N/1
Zur Erinnerung: Anforderungsgraph (4.3.1)
Behauptung:
Die Betriebsmittel seien linear geordnet,
und die Prozesse tätigen ihre Anforderungen
nur in der Reihenfolge dieser Ordnung
(Prozeß im Besitz von r fordert s nur dann, wenn s>r).
Dann bleibt der Anforderungsgraph zyklenfrei.
Beweis (indirekt):
Es liege ein Zyklus vor. Dann gibt es n Prozesse Pi,
n2, i[0,n–1], und n Betriebsmittel ri derart, daß
Pi besitzt ri und wartet auf ri1 .
Nach Voraussetzung gilt ri < ri1 für alle i, also
r0 < r1 < r2 < . . . . rn-1 < r0 ,
was zum ungültigen r0 < r0
und damit zum Widerspruch führt.
Beispiel:
0
Die Philosophen bei Tisch
(Dining Philosophers, Dijkstra 71)
0
5 Teller –
aber auch nur 5 Gabeln !
1
4
1
Zum Essen braucht man 2 Gabeln
Spaghetti
4
2
3
2
3
2 benachbarte Philosophen
können nicht gleichzeitig essen
Jeder Philosoph lebt wie folgt:
Wiederhole: denken;
linke und rechte Gabel greifen;
essen;
linke und rechte Gabel ablegen.

N/1 Problem mit 5 Ressourcen und 5 Prozessen
void philosopher(int i) { // i=0,1,2,3,4
while(true){ think();
getForks(i);
eat();
putForks(i); }
}
getForks/putForks
z.B. als Semaphor-Operationen präzisieren (3.3.1):
getForks(i) =
P(fork[i],fork[i1]);
putForks(i) =
V(fork[i],fork[i1]);
Verklemmungen? Keine Gefahr.
Fairness?
Nicht gegeben !
Z.B. 1 und 3 können sich verabreden,
2 auszuhungern (starvation)
Daher Alternative:
getForks(i) =
fork[i].P(); fork[i1].P();
putForks(i) =
fork[i].V(); fork[i1].V();
Fairness?
Ja, wenn P/V fair.
! Verklemmung
tritt ein, wenn alle gleichzeitig
ihre erste Gabel greifen.
Daher Alternative:
Gabeln zwar einzeln greifen,
aber nur in der Reihenfolge ihrer Ordnung:
 4 muß sich anders verhalten:
getForks(4) =

fork[0].P(); fork[4].P();
Verklemmungsfreiheit und Fairneß
Übung: getFork/putForks als Operationen eines Monitors
4.3.4 Verklemmungsbehandlung in Java
gibt es nicht !
... sofern man sie nicht selbst programmiert.
Manche Systeme praktizieren wenigstens Erkennung:
wenn z.B. alle Prozesse blockiert sind
– aber keiner wegen Wartens auf Eingabe –,
kann dies als Verklemmung gemeldet werden.
Verklemmungen in Java:
Programm terminiert nicht, reagiert nicht
auf Eingabe und verbraucht keine Rechenzeit:

Totale Verklemmung
Programm terminiert nicht, verbraucht
Rechenzeit, erbringt aber nur Teilleistung:

Partielle Verklemmung
oder nicht abbrechende Schleife(n)
Beachte:
Ein System.exit();
– unabhängig vom ausführenden Thread –
beendet stets das Programm.
4.3.5 Livelocks
(Kunstwort, aus deadlock abgeleitet, schwer übersetzbar)
... ähneln Deadlocks, daher der Name, sind aber keine!
... treten typischerweise bei elementaren Versuchen
zur Realisierung von Sperrsynchronisation auf –
Beispiel:
volatile boolean lock1 = false;
volatile boolean lock2 = false;
Prozeß 1
do {lock1 = true;
lock1 = !lock2
while(!lock1);
kritischer Abschnitt
lock1 = false;
Prozeß 2
do {lock2 = true;
lock2 = !lock1;
while(!lock2);
kritischer Abschnitt
lock2 = false;
„busy waiting“ (normalerweise verpönt)
Ausschluß garantiert?
Ja !
Verklemmungsfreiheit?
Ja !
Aber bei zufällig streng synchronem Ablauf
Livelock,
d.h. beide Prozesse sagen gleichzeitig
„bitte nach Ihnen“
und wiederholen das unbeschränkt lange.
Lösung: Asynchronie einbauen.

nsp4.3