銀行家のアルゴリズム
さらに、プロセス3が資源Cを2単位要求するとする。
資源Cは要求を許可するに十分な量がない
要求は拒絶される
一方、プロセス3が資源Cを1単位要求するとする。
資源Cは要求を許可するに十分な量がある
要求が許可されると仮定すると、 新しいシステムの状態は:
新しい状態が安全かどうかを判断する P1はAを2、Bを1、Dを1獲得して終了することが可能 次にP2 はBを2、Dを1獲得して終了することが可能 最後に、P3 は Cを3獲得して終了することが可能 したがって、新しい状態は安全である
新しい状態が安全であるので、要求を許可する
最後に、プロセス2が資源Bを1要求するとすると、
十分な資源が存在
要求を許可したとすると、新しい状態は:
この状態は安全であるか? P1、P2、P3 が資源 B、Cをさらに要求したとする P1 は資源 B を獲得できない P2 は資源 B を獲得できない P3 は資源 C を獲得できない どのプロセスも終了するために十分な資源を獲得できず、この状態は安全ではない
状態が安全ではないので、要求を拒絶する
この例では、どのプロセスも終了できない。いくつかのプロセスが終了できる場合もあるが、全てではなく、したがって安全な状態ではない
銀行家のアルゴリズム(英: Banker's algorithm)とは、計算機科学における資源の割り当ておよびデッドロック回避のアルゴリズムで、エドガー・ダイクストラによって開発された。銀行家のアルゴリズムでは、あらかじめ決定された最大量の計算資源の割り当てをシミュレートすることで安全性をテストし、資源の割り当て継続するかどうかを決定する前に、遅延されたデッドロックが発生する条件に対する「安全状態」のチェックを行う。
このアルゴリズムは、THE オペレーティングシステムを設計する過程で考案された。もともとは(オランダ語で) EWD108 に記述されていたもので、この名前は銀行家が流動性の制約を説明する方法から取られている。