Bankers Algorithm Beispiele

Beispiel 1

$4$ Prozesse

$3$ Ressourcen-Arten

$R=\left(\begin{array}{lll} 9 & 3 & 6 \end{array}\right)$ - Anzahl möglicher Stücke aller Ressoucen

$V=\left(\begin{array}{lll}1 & 1 & 2\end{array}\right)$ - Anzahl der verfügbaren Stücke aller Ressourcen

Claim Matrix (Maximalbedarf)

$C=\left(\begin{array}{lll} 3 & 2 & 2 \\ 6 & 1 & 3 \\ 3 & 1 & 4 \\ 4 & 2 & 2 \end{array}\right)$

Allocation Matrix (Aktuell beansprucht)

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

Need Matrix (Maximal beanspruchbar)

$N=\left(\begin{array}{lll}2 & 2 & 2 \\1 & 0 & 2 \\1 & 0 & 3 \\4 & 2 & 0\end{array}\right)$

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

Anforderung von $P_2$ : $Q_{2}=\left(\begin{array}{lll}1 & 0 & 1\end{array}\right)$

Provisorisches Erlauben - Wir setzen unsere Variablen und starten den Algorithmus:

$\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$

Daher setzen wir den state zu:

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

$C=\left(\begin{array}{lll} 3 & 2 & 2 \\ 6 & 1 & 3 \\ 3 & 1 & 4 \\ 4 & 2 & 2 \end{array}\right)$

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

$N=\left(\begin{array}{lll}2 & 2 & 2 \\ \textcolor{orange} 0 & \textcolor{orange} 0 & \textcolor{orange} 1 \\1 & 0 & 3 \\4 & 2 & 0\end{array}\right)$

Wir benutzen danach den Bankers algorithm um zu untersuchen ob unser state ein safe state ist:

Wir finden heraus dass es eine Abarbeitungsreihenfolge gibt $( P_2, P_1, P_3, P_4)$ mit der alle Prozesse fertiggestellt werden können.

Deshalb wählen wir unsere unfinished processes nach dieser Reihenfolge in diesem Beispiel.

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

$C=\left(\begin{array}{lll} 3 & 2 & 2 \\ 6 & 1 & 3 \\ 3 & 1 & 4 \\ 4 & 2 & 2 \end{array}\right)$

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

$N=\left(\begin{array}{lll}2 & 2 & 2 \\ \textcolor{orange} 0 & \textcolor{orange} 0 & \textcolor{orange} 1 \\1 & 0 & 3 \\4 & 2 & 0\end{array}\right)$

Wir wählen $P_2$ und prüfen ob $N_{ki} \leq W_i$ also $\left(\begin{array}{lll}0 & 0 & 1\end{array}\right) \leq \left(\begin{array}{lll}0 & 1 & 1\end{array}\right)$ .

Das trifft zu - deshalb:

setzen wir $P_2$ auf finished

updaten $W$ mit $W=\left(\begin{array}{lll} 6 & 2 & 3 \end{array}\right) \textcolor{grey}{= \left(\begin{array}{lll} 0 & 1 & 1 \end{array}\right) + \left(\begin{array}{lll} 6 & 1 & 2 \end{array}\right)}$

und setzen mit $P_1$ fort.

$W=\left(\begin{array}{lll} 6 & 2 & 3 \end{array}\right)$

$C=\left(\begin{array}{lll} 3 & 2 & 2 \\ 6 & 1 & 3 \\ 3 & 1 & 4 \\ 4 & 2 & 2 \end{array}\right)$

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

$N=\left(\begin{array}{lll} \textcolor{orange} 2 & \textcolor{orange} 2 & \textcolor{orange} 2 \\0 & 0 & 0 \\1 & 0 & 3 \\4 & 2 & 0\end{array}\right)$

Wir wählen $P_1$ und prüfen ob $N_{ki} \leq W_i$ also $\left(\begin{array}{lll}2 & 2 &2\end{array}\right) \leq \left(\begin{array}{lll}6 & 2 &3\end{array}\right)$ .

Das trifft zu - deshalb:

setzen wir $P_1$ auf finished

updaten $W$ mit $W=\left( \begin{array}{lll}7 & 2 & 3\end{array}\right) \textcolor{grey}{= \left(\begin{array}{lll} 6 & 2 & 3 \end{array}\right) + \left(\begin{array}{lll} 1 & 0 & 1 \end{array}\right)}$

und setzen mit $P_3$ fort.

$W=\left( \begin{array}{lll}7 & 2 & 3\end{array}\right)$

$C=\left(\begin{array}{lll} 3 & 2 & 2 \\ 6 & 1 & 3 \\ 3 & 1 & 4 \\ 4 & 2 & 2 \end{array}\right)$

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

$N=\left(\begin{array}{lll}0 & 0 & 0 \\0 & 0 & 0 \\ \textcolor{orange} 1 & \textcolor{orange} 0 & \textcolor{orange} 3 \\4 & 2 & 0\end{array}\right)$

Wir wählen $P_3$ und prüfen ob $N_{ki} \leq W_i$ also $\left(\begin{array}{lll}1 & 0 &3\end{array}\right) \leq \left(\begin{array}{lll}7 & 2 &3\end{array}\right)$ .

Das trifft zu - deshalb:

setzen wir $P_3$ auf finished

updaten $W$ mit $W=\left( \begin{array}{lll}9 & 3 & 4\end{array}\right) \textcolor{grey}{= \left(\begin{array}{lll} 7 & 2 & 3 \end{array}\right) + \left(\begin{array}{lll} 2 & 1 & 1 \end{array}\right)}$

und setzen mit $P_4$ fort.

$W=\left( \begin{array}{lll}9 & 3 & 4\end{array}\right)$

$C=\left(\begin{array}{lll} 3 & 2 & 2 \\ 6 & 1 & 3 \\ 3 & 1 & 4 \\ 4 & 2 & 2 \end{array}\right)$

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

$N=\left(\begin{array}{lll}0 & 0 & 0 \\0 & 0 & 0 \\ 0 & 0 & 0 \\ \textcolor{orange} 4 & \textcolor{orange} 2 & \textcolor{orange} 0\end{array}\right)$

Wir wählen $P_3$ und prüfen ob $N_{ki} \leq W_i$ also $\left(\begin{array}{lll} 4 & 2 &0\end{array}\right) \leq \left(\begin{array}{lll}9 & 3 &4\end{array}\right)$ .

Das trifft zu - deshalb:

setzen wir $P_4$ auf finished

updaten $W$ mit $W=\left( \begin{array}{lll}9 & 3 & 6\end{array}\right) \textcolor{grey}{= \left(\begin{array}{lll} 9 & 3 & 4 \end{array}\right) + \left(\begin{array}{lll} 0 & 0 & 2 \end{array}\right)}$

$W=\left( \begin{array}{lll}9 & 3 & 6\end{array}\right)$

$C=\left(\begin{array}{lll} 3 & 2 & 2 \\ 6 & 1 & 3 \\ 3 & 1 & 4 \\ 4 & 2 & 2 \end{array}\right)$

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

$N=\left(\begin{array}{lll}0 & 0 & 0 \\0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}\right)$

Da es keine unfinished processes mehr gibt, und alle finished sind, wissen wir, dass dieser state safe war.

________

Beispiel 2

$4$ Prozesse

$3$ Ressourcen-Arten

$R=\left(\begin{array}{lll} 9 & 3 & 6 \end{array}\right)$ - Anzahl möglicher Stücke aller Ressoucen

$V=\left(\begin{array}{lll}1 & 1 & 2\end{array}\right)$ - Anzahl der verfügbaren Stücke aller Ressourcen

Claim Matrix (Maximalbedarf)

$C=\left(\begin{array}{lll} 3 & 2 & 2 \\ 6 & 1 & 3 \\ 3 & 1 & 4 \\ 4 & 2 & 2 \end{array}\right)$

Allocation Matrix (Aktuell beansprucht)

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

Need Matrix (Maximal beanspruchbar)

$N=\left(\begin{array}{lll}2 & 2 & 2 \\1 & 0 & 2 \\1 & 0 & 3 \\4 & 2 & 0\end{array}\right)$

Anforderung von $P_1$ : $Q_{1}=\left(\begin{array}{lll}1 & 0 & 1\end{array}\right)$

Provisorisches Erlauben - Wir setzen unsere Variablen und starten den Algorithmus:

$\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$

Daher setzen wir den state zu:

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

$C=\left(\begin{array}{lll} 3 & 2 & 2 \\ 6 & 1 & 3 \\ 3 & 1 & 4 \\ 4 & 2 & 2 \end{array}\right)$

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

$N=\left(\begin{array}{lll} \textcolor{orange}1 & \textcolor{orange}2 & \textcolor{orange}1 \\1 & 0 & 2 \\1 & 0 & 3 \\4 & 2 & 0\end{array}\right)$

Wir benutzen danach den Bankers algorithm um zu untersuchen ob unser state ein safe state ist:

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

$C=\left(\begin{array}{lll} 3 & 2 & 2 \\ 6 & 1 & 3 \\ 3 & 1 & 4 \\ 4 & 2 & 2 \end{array}\right)$

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

$N=\left(\begin{array}{lll} \textcolor{orange}1 & \textcolor{orange}2 & \textcolor{orange}1 \\1 & 0 & 2 \\1 & 0 & 3 \\4 & 2 & 0\end{array}\right)$

Wir wählen $P_1$ und prüfen ob $N_{ki} \leq W_i$ also $\left(\begin{array}{lll}1 & 2 & 1\end{array}\right) \leq \left(\begin{array}{lll}0 & 1 & 1\end{array}\right)$ .

Das trifft nicht zu - wir beenden den Algorithmus, und da nicht alle states finished sind, ist das ein unsafe state.