Deadlock Detection Algorithm - Beispiel

Algorithmus

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

$V=\left(\begin{array}{lllll}0 & 0 & 0 & 0 & 1\end{array}\right)$

Anforderungs Matrix

(Ressourcen-Anforderungen)

$Q=\left(\begin{array}{lllll}0 & 1 & 0 & 0 & 1 \\0 & 0 & 1 & 0 & 1 \\0 & 0 & 0 & 0 & 1 \\1 & 0 & 1 & 0 & 1\end{array}\right)$

Allocation Matrix (Aktuell beansprucht)

$A=\left(\begin{array}{lllll}1 & 0 & 1 & 1 & 0 \\1 & 1 & 0 & 0 & 0 \\0 & 0 & 0 & 1 & 0 \\0 & 0 & 0 & 0 & 0\end{array}\right)$

Initialisierung

Alle Prozesse sind unmarkiert.

Wir markieren $P_4$ .

$W:=\left(\begin{array}{lllll}0 & 0 & 0 & 0 & 1\end{array}\right)$

Algorithmus

Wir suchen unmarkierten Prozess von der Menge $\{P_1, P_2, P_3\}$ mit der Eigenschaft

$\forall i: Q_{3i} \leq W_i$ und finden nur $P_3$ .

Da $\left(\begin{array}{lllll} 0 & 0 & 0 & 0 & 1\end{array}\right) \leq \left(\begin{array}{lllll} 0 & 0 & 0 & 0 & 1\end{array}\right)$ , markieren wir $P_3$ .

Wir setzen

$W=\left(\begin{array}{lllll}0 & 0 & 0 & 0 & 1\end{array}\right) + \left(\begin{array}{lllll}0 & 0 & 0 & 1 & 0\end{array}\right) = \left(\begin{array}{lllll}0 & 0 & 0 & 1 & 1\end{array}\right)$

Wir suchen unmarkierten Prozess von der Menge $\{P_1, P_2\}$ mit der Eigenschaft

$\forall i: Q_{3i} \leq W_i$ und finden nichts.

Ende

Es sind nicht alle Prozesse markiert, der Algorithmus liefert Deadlock von $\{P_1, P_2\}$ .

Circular Wait / Hold and Wait von $P_1, P_2$ lässt sich auch in der Matrix beobachten:

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

$Q=\left(\begin{array}{lllll} 0 & \textcolor{orange}1 & \textcolor{orange}0 & 0 & 1 \\ 0 & \textcolor{orange}0 & \textcolor{orange}1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1\end{array}\right)$

$A=\left(\begin{array}{lllll}1 & \textcolor{orange}0 & \textcolor{orange}1 & 1 & 0 \\1 & \textcolor{orange}1 & \textcolor{orange}0 & 0 & 0 \\0 & 0 & 0 & 1 & 0 \\0 & 0 & 0 & 0 & 0\end{array}\right)$