銀行家のアルゴリズム（英: Banker's algorithm）とは、計算機科学における資源の割り当ておよびデッドロック回避のアルゴリズムで、エドガー・ダイクストラによって開発された。銀行家のアルゴリズムでは、あらかじめ決定された最大量の計算資源の割り当てをシミュレートすることで安全性をテストし、資源の割り当て継続するかどうかを決定する前に、遅延されたデッドロックが発生する条件に対する「安全状態」のチェックを行う。
このアルゴリズムは、THE オペレーティングシステムを設計する過程で考案された。もともとは(オランダ語で) EWD108 [1]に記述されていたもので、この名前は銀行家が流動性の制約を説明する方法から取られている。
銀行家のアルゴリズムは、プロセスがオペレーティングシステムに資源を要求した際に実行される[2]。 このアルゴリズムでは、要求を受理するとシステムが安全でない（デッドロックを引き起こすような）状態になるような場合、要求を拒絶するか遅延させることによりデッドロックを防止する。
銀行家のアルゴリズムが動作するためには、3つの情報を得ておく必要がある。
実システムで資源として管理されるのは、記憶装置、セマフォ、インターフェイスへのアクセスなどがある。
システムがABCDの4種類の資源を識別できるとする。下記の例では、資源をどのように配布するかを示す。この例では資源に対する新しい要求が届く直前を示す。また、資源の種類と数量は抽象的なものにしているが、実システムではもっと多い資源を扱うだろう。
利用できる資源: A B C D 3 1 1 2
プロセス(および現在割り当て済みの資源): A B C D P1 1 2 2 1 P2 1 0 3 3 P3 1 1 1 0
プロセス (および最大資源): A B C D P1 3 3 2 2 P2 1 2 3 4 P3 1 1 5 0
上記の例において、全てのプロセスが実行を完了するのであれば現在の状態は安全と考えることができる。システムにはプロセスが完了するか、また完了までに要求する資源の量は未知なので、全てのプロセスが最終的には決められた最大の資源を要求して、その直後に終了すると考える。これはたいていの場合には理にかなった仮定で、（少なくともデッドロックを防ぐという観点からは）システムは各プロセスの実行する時間と関係がないためである。また、最大の資源を確保することなく終了した場合には問題が簡単になるのみである。
この仮定をもとに、アルゴリズムは状態が安全かどうかを判断するため、各プロセスが最大の資源を獲得し、終了する（そして資源を返却する）ことができるような仮想的なプロセスからの要求を作り出すことができるかを判定する。そのような状態がなければ、システムは危険な状態である。
P - プロセスの集合
Mp - プロセス p が要求する最大の資源
Cp - プロセス p への現在の資源の割り当て
A - 現在利用可能な資源
while (P != ∅) {
found = False
foreach (p ∈ P) {
if (Mp - Cp ≦ A) {
/* p はすべてのリソースを取得できる */
/* 取得、終了、解放を行うと仮定 */
A = A + Cp
P = P - {p}
found = True
}
}
if (!found) return UNSAFE
}
return SAFE
前の例で示した状態が安全であることを、各プロセスが最大の資源を確保し終了できることによって示す。
これらの資源獲得要求は「仮説的」、すなわちアルゴリズムがシステム状態の安全性を確認するために生成したもので、実際に資源が与えられたり、プロセスが終了するわけでない。また要求が生成される順序は、もし満たされるとしても、重要ではない。仮説的な要求によりプロセスが終了し、システムの利用可能な資源が増えるためである。
危険な状態の例として、例えばプロセス2が最初から資源Bを1つ多く保持していた場合が考えられる。
システムは資源の要求を受けると、銀行家のアルゴリズムを走らせ、要求を許可しても安全かどうかを判定する。この判定が済めば、その後のアルゴリズムは難しいものではない。
システムが実行不能ないし安全でない要求を拒絶・延期するかどうかはオペレーティングシステムに固有の判断である
さらに、プロセス3が資源Cを2単位要求するとする。
一方、プロセス3が資源Cを1単位要求するとする。
利用可能な資源
A B C D
空き 3 1 0 2
プロセス (割り当て済み資源):
A B C D
P1 1 2 2 1
P2 1 0 3 3
P3 1 1 2 0
プロセス (最大の資源):
A B C D
P1 3 3 2 2
P2 1 2 3 4
P3 1 1 5 0
最後に、プロセス2が資源Bを1要求するとすると、
利用可能な資源:
A B C D
空き 3 0 1 2
プロセス (割り当て済み資源):
A B C D
P1 1 2 2 1
P2 1 1 3 3
P3 1 1 1 0
プロセス (最大の資源):
A B C D
P1 3 3 2 2
P2 1 2 3 4
P3 1 1 5 0
この例では、どのプロセスも終了できない。いくつかのプロセスが終了できる場合もあるが、全てではなく、したがって安全な状態ではない
多くのアルゴリズムと同様、銀行家のアルゴリズムにはトレードオフがある。特に、プロセスが各リソースをどれほど使用する可能性があるかを知っておく必要があるが、大半のシステムではこうした情報は入手できず、銀行家のアルゴリズムは役に立たない。また、大半のシステムではプロセス数が動的に変化するため、プロセスの数が固定的であると仮定するのは非現実的である。
さらに、プロセスが終了時に全ての資源を解放する必要がある、という点はアルゴリズムの正しさという点では十分だが、実際のシステムでは十分であるとはいえない。資源の解放に数時間や数日かかることは通例許容されない。