銀行家のアルゴリズム計算（安全な順序とデッドロック検出）

銀行家のアルゴリズムは、複数の種類のリソースを持つシステムが安全な状態にあるかどうか（すべてのプロセスが、これから必要になり得るものを得て終了できる順序があるか）と、新しい要求を、安全性を失わずに許可できるかどうかを判定します。この計算ツールは、Need行列を作成し、Workベクトルを使う安全性アルゴリズムをステップごとに実行し、リソース要求を確認し、Request行列に対する関連のデッドロック検出アルゴリズムも実行します。

使い方

1. Allocation行列を、1行に1プロセスずつ入力します（P0: 0 1 0）。
2. Max行列（デッドロック検出の場合はRequest行列）を同じ順序で入力します。
3. Availableベクトル、または各リソースの全インスタンス数を入力します。
4. 必要なら、P1 1 0 2のような要求を入力し、許可されるかを確認します。

計算式

Need = Max − Allocation · Work = Available；繰り返し：Need ≤ WorkのPᵢを探してWork = Work + Allocationᵢ · すべてのプロセスが終了すれば安全

Pᵢからの要求は、Needを超えればエラー、Availableを超えれば待機となり、それ以外は、割り当てたと仮定した後の状態がなお安全な場合にのみ許可されます。デッドロック検出ではNeedの代わりに現在のRequestを使い、何も保持していないプロセスは最初から終了済みとして扱い、終了できないプロセスがデッドロックです。安全系列は複数あることがあり、探索順のオプションで、よく使われる2通りの追い方を再現できます。

計算例

サンプルは、Silberschatzの『Operating System Concepts』の教科書の例です。プロセス5個、リソースA・B・C、Available (3, 3, 2)。NeedはP0 (7,4,3)、P1 (1,2,2)、P2 (6,0,0)、P3 (0,1,1)、P4 (4,3,1)です。まずP1が終了でき（Workは5 3 2）、続いてP3 (7 4 3)、P4 (7 4 5)、P0 (7 5 5)、P2 (10 5 7)が終了できるので、状態は安全で、系列は<P1, P3, P4, P0, P2>です。P1の要求 (1, 0, 2)は許可されます。