Banker’s_algorithm
バンカーアルゴリズムと呼ばれることもある、検出アルゴリズムは、あるリソース割り当てとデッドロック回避アルゴリズムによって開発Edsgerダイクストラ全ての所定の最大可能量の配分シミュレーションによる安全性のためにテストすることを資源をその後、および「S状態」を作ります割り当ての続行を許可するかどうかを決定する前に、他のすべての保留中のアクティビティで発生する可能性のあるデッドロック状態をテストするために確認して
このアルゴリズムは、THE オペレーティングシステムの設計プロセスで開発され、元々はEWD108で（オランダ語で）記述されていました。新しいプロセスがシステムに入るとき、それが主張する可能性のある各リソースタイプのインスタンスの最大数を宣言する必要が明らかに、その数はシステム内のリソースの総数を超えてはなりません。また、プロセスが要求されたすべてのリソースを取得すると、有限の時間内にそれらを返す必要が
コンテンツ
1 資力
1.1 例 1.2 安全な状態と安全でない状態 1.3 リクエスト
1.3.1 例
2 制限事項
3 参考文献
4 参考文献
資力
銀行家のアルゴリズムが機能するには、次の3つのことを知っている必要が
各プロセスが要求できる可能性のある各リソースの量
各プロセスが現在保持している各リソースの量
システムが現在利用可能な各リソースの量
要求されたリソースの量が使用可能な量以下の場合にのみ、リソースをプロセスに割り当てることができます。それ以外の場合、プロセスはリソースが使用可能になるまで待機します。
実際のシステムで追跡されるリソースには、メモリ、セマフォ、インターフェイスアクセスなどが
銀行家のアルゴリズムの名前は、このアルゴリズムを銀行システムで使用して、銀行がリソースを使い果たしないようにすることができるという事実に由来しています。すべての顧客のニーズ。銀行家のアルゴリズムを使用することにより、銀行は、顧客がお金を要求したときに銀行が安全な状態を決して離れないことを保証します。顧客の要求によって銀行が安全な状態を離れない場合、現金が割り当てられます。それ以外の場合、顧客は他の顧客が十分に預金するまで待つ必要が
銀行家のアルゴリズムを実装するために維持される基本的なデータ構造：
させて {n}
システム内のプロセスの数であり、 {m}
リソースタイプの数です。次に、次のデータ構造が必要です。
使用可能：長さmのベクトルは、各タイプの使用可能なリソースの数を示します。Available = kの場合、利用可能なリソースタイプRjのインスタンスがk個
マックス： {n}
×× {m}
マトリックスは、各プロセスの最大需要を定義します。もしマックス = K、次いで、P iはリソースタイプRの大部分のk個のインスタンスに要求してもよいJ。
割り当て： {n}
×× {m}
マトリックスは、各プロセスに現在割り当てられている各タイプのリソースの数を定義します。Allocation = kの場合、プロセスP iには、現在、リソースタイプRjのk個のインスタンスが割り当てられています。
必要性： {n}
×× {m}
マトリックスは、各プロセスの残りのリソースの必要性を示します。Need = kの場合、P iは、タスクを完了するために、リソースタイプRjのインスタンスをさらにk個必要とする場合が
注：Need = Max -割り当て。n = ma。
例
システムリソースの合計は次のとおりです。あいうえお6 5 7 6
利用可能なシステムリソースは次のとおりです。あいうえお3 1 1 2
プロセス（現在割り当てられているリソース）： あいうえおP1 1 2 2 1P2 1 0 3 3P3 1 2 1 0
プロセス（最大リソース）： あいうえおP1 3 3 2 2P2 1 2 3 4P3 1 3 5 0
必要=最大リソース-現在割り当てられているリソースプロセス（おそらく必要なリソース）： あいうえおP1 2 1 0 1P2 0 2 0 1P3 0 1 4 0
安全な状態と安全でない状態
すべてのプロセスが実行を終了（終了）できる場合、状態（上記の例のように）は安全であると見なされます。システムは、プロセスがいつ終了するか、またはそれまでに要求されたリソースの数を知ることができないため、すべてのプロセスが最終的に指定された最大リソースを取得しようとし、その後すぐに終了すると想定します。システムは各プロセスの実行時間に特に関係がないため（少なくともデッドロック回避の観点からは）、これはほとんどの場合合理的な仮定です。また、プロセスが最大のリソースを取得せずに終了した場合、それはシステム上でそれを容易にするだけです。安全な状態は、準備完了キューを処理する場合の意思決定者と見なされます。
その仮定を前提として、アルゴリズムは、プロセスが最大のリソースを取得して終了する（システムにリソースを返す）ことを可能にする仮想のリクエストセットを見つけようとすることで、状態が安全かどうかを判断します。そのようなセットが存在しない状態は、安全でない状態です。
前の例で示した状態は、各プロセスが最大のリソースを取得して終了できることを示すことで、安全な状態であることを示すことができます。
P1は、最大値を達成するために、さらに2 A、1 B、および1Dのリソースを必要とします。
[利用可能なリソース：– = ]
システムには、まだ1 A、Bなし、1 C、および1Dのリソースが
P1が終了し、3 A、3 B、2 C、および2Dのリソースがシステムに返されます。
[利用可能なリソース： + = ]
システムには、4 A、3 B、3 C、および3Dのリソースが利用可能になりました。
P2は2Bと1Dの追加リソースを取得してから終了し、すべてのリソースを返します
[利用可能なリソース：– + = ]
システムには、5 A、3 B、6 C、および6Dのリソースが
P3は1Bおよび4Cリソースを取得し、終了します。
[利用可能なリソース：– + = ]
これで、システムにすべてのリソースがあります：6 A、5 B、7 C、および6 D
すべてのプロセスを終了できたため、この状態は安全です
安全でない状態の例として、プロセス2が最初に2ユニットのリソースBを保持していた場合にどうなるかを考えてみます。
リクエスト
システムはリソースの要求を受信すると、銀行家のアルゴリズムを実行して、要求を許可しても安全かどうかを判断します。安全な状態と安全でない状態の区別が理解されれば、アルゴリズムはかなり簡単です。
リクエストを許可できますか？
そうでない場合、リクエストは不可能であり、拒否するか、順番待ちリストに入れる必要があります
リクエストが許可されたと仮定します
新しい状態は安全ですか？
もしそうなら、リクエストを許可します
そうでない場合は、リクエストを拒否するか、順番待ちリストに入れます
システムが不可能または安全でない要求を拒否するか延期するかは、オペレーティングシステムに固有の決定です。
例
前の例で開始したのと同じ状態で開始し、プロセス1が2ユニットのリソースCを要求するとします。
リクエストを許可するために利用できるリソースCが十分ではありません
リクエストは拒否されました
一方、プロセス3が1ユニットのリソースCを要求するとします。
リクエストを許可するのに十分なリソースがあります
リクエストが許可されたと仮定します
システムの新しい状態は次のようになります。
利用可能なシステムリソース あいうえお無料31 02 プロセス（現在割り当てられているリソース）： あいうえおP1 1 2 2 1P2 1 0 3 3P3 1 2 2 0 プロセス（最大リソース）： あいうえおP1 3 3 2 2P2 1 2 3 4P3 1 3 5 0
この新しい状態が安全かどうかを判断します
P1は、2 A、1 B、および1Dのリソースを取得して終了できます。
次に、P2は2つのBおよび1Dのリソースを取得して終了できます。
最後に、P3は1Bおよび3Cリソースを取得して終了できます
したがって、この新しい状態は安全です
新しい状態は安全なので、リクエストを許可します
最後の例：開始した状態から、プロセス2が1ユニットのリソースBを要求するとします。
十分なリソースがあります
リクエストが許可されたとすると、新しい状態は次のようになります。
利用可能なシステムリソース： あいうえお無料30 1 2 プロセス（現在割り当てられているリソース）： あいうえおP1 1 2 5 1P2 1 1 3 3P3 1 2 1 0 プロセス（最大リソース）： あいうえおP1 3 3 2 2P2 1 2 3 4P3 1 3 5 0
この状態は安全ですか？P1、P2、およびP3がリソースBおよびCをさらに要求するとします。
P1は十分なBリソースを取得できません
P2は十分なBリソースを取得できません
P3は十分なBリソースを取得できません
プロセスが終了するのに十分なリソースを取得できないため、この状態は安全ではありません
状態が安全ではないため、リクエストを拒否します
numpy を npとしてインポートn_processes = int （input （’プロセス数？’ ））n_resources = int （input （’リソース数？’ ））available_resources = [ int （x ） for x in input （’クレームベクトル？’ ）。分割（” ）]currently_allocated = NP 。array （[[ int （x ） for x in input （’現在プロセスに割り当てられている’ + str （i + 1 ） + ‘？’ ）。split （” ）] for i in range （n_processes ）]）max_demand = np 。array （[[ int （x ） for x in input （’プロセスからの最大需要’ + str （i + 1 ） + ‘？’ ）。split （” ）] for i in range （n_processes ）]）total_available = available_resources – np 。合計（currently_allocated 、 axis = 0 ）running = np 。ones （n_processes ） ＃プロセスがまだ実行されていないかどうかを示すn_processes1の配列 npながら。count_nonzero （実行） > 0 ： at_least_one_allocated = Falseの ための P における 範囲（n_processesの）
場合に 実行されている：
場合 、すべての（I > = 0 のための I における total_available – （max_demand – currently_allocated ））：
at_least_one_allocated = 真
印刷（STR （P ） + ‘実行されている’ ）
実行 = 0
total_available + = currently_allocated 場合 ではない at_least_one_allocated ：
プリント（’安全でない’ ）
出口（）
印刷（’安全’ ）
制限事項
他のアルゴリズムと同様に、バンカーのアルゴリズムには、実装時にいくつかの制限が具体的には、プロセスが要求する可能性のある各リソースの量を知る必要がほとんどのシステムでは、この情報は利用できないため、銀行家のアルゴリズムを実装することは不可能です。また、ほとんどのシステムではプロセスの数が動的に変化するため、プロセスの数が静的であると想定するのは非現実的です。さらに、プロセスが最終的にすべてのリソースを解放するという要件（プロセスが終了したとき）は、アルゴリズムの正確さには十分ですが、実際のシステムには十分ではありません。通常、リソースが解放されるまで数時間（または数日）待つことは受け入れられません。
参考文献
^ Dijkstra、Edsger W.Eenアルゴリズムtervoorkoming van de dodelijke omarming（EWD-108） （PDF）。EWダイクストラアーカイブ。テキサス大学オースティン校アメリカ史センター。（転写）（オランダ語;致命的な抱擁を防ぐためのアルゴリズム）
^ Silberschatz、Galvin、およびGagne（2013）。オペレーティングシステムの概念、第9版。ワイリー。NS。330. ISBN 978-1-118-06333-0。
参考文献
Silberschatz、Galvin、およびGagneによる「オペレーティングシステムの概念」（第7版の259〜261ページ）
Silberschatz、Galvin、およびGagneによる「オペレーティングシステムの概念」（第8版の298〜300ページ）
Dijkstra、Edsger W. 銀行家のアルゴリズムの背後にある数学（EWD-623） （PDF）。EWダイクストラアーカイブ。テキサス大学オースティン校アメリカ史センター。（転写）（1977）、エドガー・ダイクストラのページ308〜312として公開、コンピューティング上の著作を選択：Aカメラマンの視点、シュプリンガー・フェアラーク、1982年
ISBN 0-387-90652-5 “