Deadlock

📎 Bankers Algorithm Beispiele

📎 Deadlock Detection Algorithm - Beispiel

Definition

Permanentes Blockieren von Prozessen die miteinander um Ressourcen konkurrieren.

Ressourcen können erneubar / wiederherstellbar oder konsumierbar sein.

Erneubar Lassen sich nicht verbrauchen, zB Prozessorleistung, Peripherals, Speicher

Konsumierbar Lassen sich zerstören, zB Interrupts, Messages und Informationen in IO Buffern

Prozessfortschrittsdiagramm für Mutual Exclusion Beispiel

$n$ Prozesse brauchen ein $n$ -Dimensionales Diagramm

4 Deadlock Bedingungen

Mutual Exclusion Exklusiver Zugang eines jeweils einzigen Prozesses zu einer Ressource

Hold and wait Prozess kann beim warten Ressource halten und für andere blockieren

No Preemption Ressourcen können Prozessen nicht wieder weggenommen werden

Circular Wait Zyklischer Ressourcenkonflikt zwischen ≥ 2 Prozessen
Es gibt eine geschlossene Kette von Prozessen, sodass jeder zumindest
eine Ressource hält die der nächste benötigt.

1-3 sind Systembedingungen, 4 ist eine besondere Ereignisfolge.

Ein Deadlock tritt genau dann auf, wenn das Circular Wait nicht aufgelöst werden kann.

Circular Wait kann nicht aufgelöst werden, wenn Bedingungen 1 bis 3 gelten.

Deadlock genau dann, wenn alle 4 Bedingungen erfüllt sind.

Deadlock Beispiele

Einfache Deadlock Beispiele
Beispiel: Kreisverkehr
Prozesse: Autos
Ressourcen: Fahrbahnstücke (wiederherstellbare Ressourcen)
Deadlock: jedes Auto blockiert ein Fahrbahnstück und möchte auf das Fahrbahnstück des vorderen Autos (dieses wiederum wartet aber auf das Fahrbahnstück des vorderen Autos)
Beispiel: Nachrichten
Nachrichten sind konsumierbare Ressourcen (wenn sie gelesen werden verschwinden sie von der queue).
```
...
receive(MQ1, msg); //waits for msg
...
send(MQ2, msg);
...
```
```
...
receive(MQ2, msg); //waits for msg
...
send(MQ1, msg);
...
```
Beispiel: Mutual Exclusion
```
Get B
...
Get A <--
...
Release B
...
Release A
```
```
Get A <--
...
Get B
...
Release B
...
Release A
```
```
Get A <--
...
Release A
...
Get B
...
Release B
```

1) Deadlock verhindern - Davor

Deadlock prevention

Eine Art der Deadlockbehandlung: OS design versucht die Deadlock Bedingungen zu unterbinden

Indirect Deadlock Prevention - Bedingungen 1-3

Mutual Exclusion

Kann man nicht verbieten

Hold and Wait

Alles oder Nichts:

Alle angeforderten Ressourcen müssen aufeinmal ankommen - bis dahin Prozess blockieren.

Beispiel
Atomare Operation für mehrere Semaphore
mWait(S1...SN) blockiert wenn irgendeines ≤0 ist, verringert sonst alle gleichzeitig
mSignal(S1...SN) erhöht alle gleichzeitig um 1
(Bei mSignal ist es eigentlich egal ob sie alle gleichzeitig erhöht werden, es geht nur um die Lesbarkeit.)

Problem:

Wir müssen alle erforderlichen Ressourcen eines Prozesses im Vorhinein kennen.

Dadurch lange Verzögerungen bis ein Prozess alle Ressourcen bei Ankunft verarbeitet.

Parallelität wird nicht ausgenützt.

No Preemption

Prozessen Ressourcen wegnehmen:

Entweder der blockierte Prozess gibt seine (nicht seinen Anforderungen entsprechenden) Ressourcen frei und fordert sie später wieder,

Oder erzwingt andere Prozesse ihre Ressourcen frei zu geben.

Danach wird ein Zustand des Prozesses und der Ressource selbst wiederhergestellt in der die Prozesse (denen man die Ressource weggenommen hat) die Ressource noch nicht hatten.

Anwendbar für Ressourcen, deren Zustand leicht gespeichert und später wieder hergestellt werden kann - zB Prozessor, durch Processor State Information

Direct Deadlock Prevention - Bedingung 4

Circular Wait

Verhinderung mit einem Protokoll:

Ressourcen-Nummerierung, dann wird Reihenfolge mit der auf sie zugegriffen wird festgelegt.

Beispiel: strikte lineare Ordnung, Ressourcen-Index mit $O(R_i)$ abfragbar.

Prozess fordert gleichzeitig in einem Schritt eine beliebige Anzahl einer Ressource der Art $R_i$ an.

Der nächste Prozess erhält nur Ressourcen mit $O(R_k) > O(R_i)$

Ineffizient: Dadurch wird aber die Parallelität eingeschränkt und Ressourcen können nicht angenommen werden, wenn die Ordnung nicht stimmt.

____________

2) Deadlock vermeiden - Währenddessen

Deadlock avoidance

Die Bedingungen 1-3 sind erlaubt aber die Ressourcenvergabe ist selektiv,

Insgesamt höhere Parallelität als bei Deadlock Prevention.

Ressourcenbedarf der Prozesse muss im Vorhinein bekannt sein.

Notation

$n$ Prozesse

$m$ Ressourcenarten (als Vektor)

Ressourcen-Vektoren

$\textsf{Resource} = (R_1, R_2, \dots, R_m)$ - Anzahl möglicher Stücke aller Ressoucen

$\textsf{Available} = (V_1, V_2, \dots, V_m)$ - Anzahl der verfügbaren Stücke aller Ressourcen

Anforderungsmatrix (statisch)

Wie viel kann ich höchstens jemals brauchen?

Wie viele Stücke von jeder Ressourcen-Kategorie kann ein Prozess höchstens jemals benötigen?

In Matrizen stehen Zeilen für Prozesse, Spalten für Ressourcen

$\textsf{Claim}=\begin{pmatrix} C_{11}, & C_{12}, & ..., & C_{1m}\\ ~&~&\dots\\ C_{n1}, & C_{n2}, & ..., & C_{nm} \end{pmatrix}$

Zuweisungsmatrix (dynamisch)

Wie viel habe ich gerade?

Ressourcenbelegung: Wie viel Stück von jeder Ressourcen-Kategorie hat ein Prozess aktuell?

$\textsf{Allocation}=\begin{pmatrix} A_{11}, & A_{12}, & ..., & A_{1m}\\ ~&~&\dots\\ A_{n1}, & A_{n2}, & ..., & A_{nm} \end{pmatrix}$

Need-Matrix (dynamisch)

Wie viel fehlt mir zu dem was ich höchstens brauchen könnte?

Wie viele Stück jeder Ressourcen-Kategorie werden von jedem Prozess bis zur maximalen Gebrauchsallokation gebraucht?

$\textsf{Required / Needed}=\begin{pmatrix} N_{11}, & N_{12}, & ..., & N_{1m}\\ ~&~&\dots\\ N_{n1}, & N_{n2}, & ..., & N_{nm} \end{pmatrix}$ wobei $N_{ki} = C_{ki} - A_{ki}$

Process Initiation Denial

Prozess wird nicht gestartet, wenn seine Anforderungen zu einenm Deadlock führen könnten.

Ein weiterer Prozess $P_{n+1}$ (zu den $n$ bestehenden Prozessen) wird nur dann gestartet wenn seine Ressourcenanforderungen keinen deadlock auslösen können:

∀i:Riundefinedtotalavailable≥C(n+1)iundefinednewprocess+∑k=1nCkiundefinedoldprocesses\forall i:\underbrace{R_i}_{\textsf{total available}} \geq \underbrace{C_{(n+1)i}}_{\textsf{new process}} + \underbrace{\sum^n_{k=1} C_{ki}}_{\textsf{old processes}}∀i:total availableRi≥new processC(n+1)i+old processesk=1∑nCki

Geht vom worst-case aus:

Geht davon aus, dass in jedem Moment alle Prozesse gleichzeitig die maximale Stückanzahl erfordern werden.

Einschränkung der Parallelität.

Resource Allocation Denial → Banker's Algorithm

Feinere Granularität als bei Process Initiation denial.

Eine Ressourcenanforderung wird abgelehnt wenn dadurch ein Deadlock entstehen könnte.

State Beliebige Ressourcenbelegung der Prozesse

Safe State $\exists$ Exekutionsfolge mit der alle Prozesse zu einem finished state kommen können

Unsafe State $\not \exists$ solche Exekutionsfolge - daher Deadlock möglich.

Anwendung des Banker's Algorithm

Prozess $P_k$ fordert $Q_{ki}$ -Stück von der Ressourcenart $i$ an.

Plausibilitäts-Check: $\forall i: Q_{ki} \leq N_{ki}$
Falls false, dann Anforderung an sich oder unsere Claim-Matrix falsch.

Kapazitäts-Check: $\forall i: Q_{ki} \leq V_i$
Falls false, dann Ressourcen für diese Anforderung nicht verfügbar.

Provisorisches Erlauben der Anforderung und Untersuchung der Safe State.
Wir definieren unsere Variablen für alle Ressourcen $i$ die angefordert wurden neu:
$\forall i: V_i := V_i - Q_{ki}$ Weniger insgesamt verfügbar
$\forall i: A_{ki} := A_{ki} + Q_{ki}$ Mehr von $P_k$ beansprucht
$\forall i: N_{ki} := N_{ki}- Q_{ki}$ Weniger Bedarf von $P_k$
Danach nutzen wir den Banker's Algorithm.
Falls der vorliegende state ein safe-safe ist, dann werden Ressourcen $Q_{ki}$ an $P_k$ zugewiesen, ansonsten nicht.

Bankers Algorithm

Iterativer Algorithmus, der Prozesse markiert und testet ob ein state safe oder unsafe ist.

Initialisierung

Markiere alle Prozesse $P_i$ als unfinished

Initialisiere Work Vector für alle $i$ mit $W_i := V_i$ - copy that we will change

Algorithmus

Suche unfinished $P_k$ und $\forall i: N_{ki} \leq W_i$ - potentially needed by $P_k$ ≤ total currently available

Falls kein Prozess gefunden $\rarr$ gehe zum Ende

Ansonsten markiere $P_k$ als finished und gib seine Ressourcen frei:

$\forall i: W_i = W_i + A_{ki}$ - increase currently available by what $P_k$ used

Ende

Wenn alle $P_i$ finished sind, retourniere safe state , sonst unsafe state

Erklärung + Beispiele

💡

\forall i: W_i = W_i + A_{ki}

ist deshalb sinnvoll, da

P_k

irgendwann terminieren wird und seine Ressourcen freigeben wird, und wir danach diese Ressourcen zur Verfügung haben werden.

📎 Bankers Algorithm Beispiele

Keine False Negatives, aber False Positives möglich

Safe state $\rarr$ definitiv kein Deadlock

Unsafe state $\rarr$ möglicherweise Deadlock

Prozesse benötigen Ressourcen nicht durchgehend.

Maximalanforderungen in der Prozesse treten nicht alle gemeinsam auf - aber wir nehmen Prozess-Unabhängigkeit an (keine Bedingungssynchronisation zwischen Prozessen).

Insgesamt ist die Überprüfung bei jeder Ressourcenanforderung sehr CPU intensiv.

____________

3) Deadlock auflösen - Danach

Deadlock detection and recovery

Ressourcenanforderungen immer erlaubt, falls Ressource vorhanden.

Periodisches Überprüfen, ob ein Deadlock vorliegt und falls notwendig Recovery.

Deadlock Detection

Algorithmus in OS, um Deadlock zu erkennen.

Deadlock detection algorithm

Markiert deadlock-freie Prozesse.

Initialisierung

setze alle Prozesse auf unmarkiert

markiere alle Prozesse $P_k$ mit $\forall i: A_{ki} = 0$ - this line is the only difference to the banker's algo.

Initialisiere Work Vector für alle $i$ mit $W_i := V_i$ - copy that we will change

Algorithmus

Suche unmarkierten $P_k$ mit $\forall i: Q_{ki} \leq W_i$ - requested by $P_k$ ≤ total currently available

Falls dieser existiert:

markiere $P_k$

$\forall i: W_i = W_i + A_{ki}$ - increase currently available by what $P_k$ used

Ansonsten: exit loop

Ende

unmarkierte Prozesse befinden sich in einem deadlock

Beispiel

📎 Deadlock Detection Algorithm - Beispiel

Bemerkung

Optimistische Annahme, dass Prozesse für Fertigstellung keine zusätzlichen Ressourcen brauchen.

Falls diese Annahme nicht stimmt, wird dieser Deadlock wird beim darauf folgenden Aufruf des Deadlock Detection Algorithmus erkannt.

Deadlock Recovery

Strategien zur Deadlockbehebung

Alle auf einmal

Alle betroffenen Prozesse abbrechen und Rollback to recovery-point (ab der aber möglicherweise ein Deadlock wieder auftreten kann) .

Iterativ - bis der detection algorithm kein deadlock mehr aufzeigt

Von betroffenen Prozessen, einzeln welche wählen, abbrechen, ihnen Ressourcen entziehen und anderen Prozessen zuordnen und diese mit rollback zurücksetzten.

Kombination

Kombination der oben gennanten Möglichkeiten:

Ressourcen-Gruppen bilden
Nicht alle Ressourcen sind gleich einfach / schnell zu freizugeben und zu recovern.
zB die CPU kann man besonders leicht freigeben und recovern.
Swappable Space (Sekundärspeicher)
Prozess-Ressourcen (I/O-Geräte, Files, etc.)
Hauptspeicher

Zwischen Gruppen: Circular Wait Prevention

Innerhalb der Gruppen: Best-geeignete Strategie
zB für Hauptspeicher - Prevention, Preemption
zB für Processressourcen - Avoidance

Auswahl des zu unterbrechenden Prozesses zB durch

wenigste bisher verbrauchte CPU-Zeit

geringste Anzahl an bisher belegten Ressourcen

geringster Fortschritt