銀行家のアルゴリズム

銀行家のアルゴリズム（英: 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

安全な状態、危険な状態

上記の例において、全てのプロセスが実行を完了するのであれば現在の状態は安全と考えることができる。システムにはプロセスが完了するか、また完了までに要求する資源の量は未知なので、全てのプロセスが最終的には決められた最大の資源を要求して、その直後に終了すると考える。これはたいていの場合には理にかなった仮定で、（少なくともデッドロックを防ぐという観点からは）システムは各プロセスの実行する時間と関係がないためである。また、最大の資源を確保することなく終了した場合には問題が簡単になるのみである。

この仮定をもとに、アルゴリズムは状態が安全かどうかを判断するため、各プロセスが最大の資源を獲得し、終了する（そして資源を返却する）ことができるような仮想的なプロセスからの要求を作り出すことができるかを判定する。そのような状態がなければ、システムは危険な状態である。

擬似コード^[3]

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

例

前の例で示した状態が安全であることを、各プロセスが最大の資源を確保し終了できることによって示す。

P1 がさらに Aを2、Bを1、Dを1 の資源を獲得し、最大値に到達する
- システムは A1、B0、C1、D1の資源を利用可能である
P1 終了し、Aを3 Bを3, Cを2、Dを2返却する
- システムはこの時点でA4、B3、C3、D3の資源を利用できる
P2 がさらにBを2、D1を確保し、終了、全ての資源を返却する
- システムはこの時点でA5、B3、C6、D6の資源を利用できる
P3 がCを4獲得し、終了する
- システムはこの時点で全ての資源A6、B4、C7、D6を利用できる
全てのプロセスが完了できたので、現在の状態は安全である

これらの資源獲得要求は「仮説的」、すなわちアルゴリズムがシステム状態の安全性を確認するために生成したもので、実際に資源が与えられたり、プロセスが終了するわけでない。また要求が生成される順序は、もし満たされるとしても、重要ではない。仮説的な要求によりプロセスが終了し、システムの利用可能な資源が増えるためである。

危険な状態の例として、例えばプロセス2が最初から資源Bを1つ多く保持していた場合が考えられる。

要求

システムは資源の要求を受けると、銀行家のアルゴリズムを走らせ、要求を許可しても安全かどうかを判定する。この判定が済めば、その後のアルゴリズムは難しいものではない。

要求に許可を与えられるか？
- 与えられない場合、要求は実行不可能で、拒絶されるか待ちリストに入れられる
要求が許可された場合を仮定する
新しい状態は安全か?
- 安全であれば許可する
- そうでなければ拒絶する待ちリストに入れる

システムが実行不能ないし安全でない要求を拒絶・延期するかどうかはオペレーティングシステムに固有の判断である

例

さらに、プロセス3が資源Cを2単位要求するとする。

資源Cは要求を許可するに十分な量がない
要求は拒絶される

一方、プロセス3が資源Cを1単位要求するとする。

資源Cは要求を許可するに十分な量がある
要求が許可されると仮定すると、
- 新しいシステムの状態は:

    利用可能な資源
     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

新しい状態が安全かどうかを判断する
1. P1はAを2、Bを1、Dを1獲得して終了することが可能
2. 次にP2 はBを2、Dを1獲得して終了することが可能
3. 最後に、P3 は Cを3獲得して終了することが可能
4. したがって、新しい状態は安全である
新しい状態が安全であるので、要求を許可する

最後に、プロセス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

この状態は安全であるか? P1、P2、P3 が資源 B、Cをさらに要求したとする
- P1 は資源 B を獲得できない
- P2 は資源 B を獲得できない
- P3 は資源 C を獲得できない
- どのプロセスも終了するために十分な資源を獲得できず、この状態は安全ではない
状態が安全ではないので、要求を拒絶する

この例では、どのプロセスも終了できない。いくつかのプロセスが終了できる場合もあるが、全てではなく、したがって安全な状態ではない

トレードオフ

多くのアルゴリズムと同様、銀行家のアルゴリズムにはトレードオフがある。特に、プロセスが各リソースをどれほど使用する可能性があるかを知っておく必要があるが、大半のシステムではこうした情報は入手できず、銀行家のアルゴリズムは役に立たない。また、大半のシステムではプロセス数が動的に変化するため、プロセスの数が固定的であると仮定するのは非現実的である。

さらに、プロセスが終了時に全ての資源を解放する必要がある、という点はアルゴリズムの正しさという点では十分だが、実際のシステムでは十分であるとはいえない。資源の解放に数時間や数日かかることは通例許容されない。

参考文献

^ E. W. Dijkstra "EWD108: Een algorithme ter voorkoming van de dodelijke omarming" (in Dutch; An algorithm for the prevention of the deadly embrace)
^ Lubomir, F. Bic; Alan C. Shaw (2003). Operating System Principles. Prentice Hall. ISBN 0-13-026611-6
^ Concurrency

参考書籍

"Operating System Concepts" by Silberschatz, Galvin, and Gagne (pages 259-261 of the 7th edition)
"EWD623: The mathematics behind the Banker’s Algorithm" (1977) by E. W. Dijkstra, published as pages 308?312 of Edsger W. Dijkstra, Selected Writings on Computing: A Personal Perspective, Springer-Verlag, 1982. ISBN 0-387-90652-5

外部リンク

銀行家のアルゴリズム

[1] E. W. Dijkstra "EWD108: Een algorithme ter voorkoming van de dodelijke omarming" (in Dutch; An algorithm for the prevention of the deadly embrace)

[2] Lubomir, F. Bic; Alan C. Shaw (2003). Operating System Principles. Prentice Hall. ISBN 0-13-026611-6

[3] Concurrency

[1]

[2]

[3]