オペレーティング システムのバンカー アルゴリズム [例]

バンカーズアルゴリズムとは何ですか?

バンカーのアルゴリズム 主に銀行システムで使用され、デプロイを回避します。adlock。 融資が受けられるかどうかを判断するのに役立ちます。

このアルゴリズムは、すべてのリソースで利用可能な最大量を決定するための割り当てを安全にシミュレートするためのテストに使用されます。 また、割り当てを継続するかどうかを決定する前に、考えられるすべてのアクティビティをチェックします。

たとえば、特定の銀行の口座名義人が X 人いて、その口座の合計金額が G であるとします。

銀行が車のローンを処理するとき、ソフトウェア システムは、銀行が保有する合計金額 (G+ 定期預金 + 月収制度 + ゴールドなど) から車の購入に許可されたローンの金額を差し引きます。

また、差額が G 以上であるかどうかもチェックします。すべての口座所有者が同時にお金を引き出した場合でも、銀行に十分な資金がある場合にのみ自動車ローンを処理します。neo普通に。

バンカーズアルゴリズムの表記法

バンカーのアルゴリズムで使用される重要な表記法を次に示します。

  • X:システムの総プロセス数を示します。
  • Y: システム内に存在するリソースの総数を示します。

利用できます

[I: Y] は、どのリソースが利用可能であるかを示します。

最大値

[l:X,l:Y]: タイプ j またはプロセス i のリソースの最大数の式

割り当て

[l:X、l:Y]。 タイプ j のリソースを受け取ったプロセスを示します

必要

将来的にさらにどれだけのリソースを割り当てることができるかを表現する

バンカーアルゴリズムの例

次のようなものがあると仮定しますwing リソース:

  • 5 ペンドライブ
  • 2 プリンター
  • 4 スキャナー
  • 3 ハードディスク

ここでは、総リソースを表すベクトル、利用可能 = (5, 2, 4, 3) を作成しました。

プロセスが XNUMX つあると仮定します。 利用可能なリソースは、以下のマトリックス テーブルに従ってすでに割り当てられています。

プロセス名 ペンドライブ プリンタ スキャナー ハードディスク
P 2 0 1 1
Q 0 1 0 0
R 1 0 1 1
S 1 1 0 1
トータル 4 2 2 3

ここで、割り当てられたリソースは次の列の合計です。

割り当て済み = (4, 2, 2, 3)。

また、すべてのプロセスに必要な各リソースの数を表示するマトリックスも作成します。 この行列は次のように呼ばれます 必要=(3,0,2,2)

プロセス名 ペンドライブ プリンタ スキャナー ハードディスク
P 1 1 0 0
Q 0 1 1 2
R 2 1 0 0
S 0 0 1 0

利用可能なベクトルは次のとおりです。

利用可能=利用可能 - 割り当て済み

= (5, 2, 4, 3) -(4, 2, 2, 3)

=(1, 0, 2, 0)

リソース要求アルゴリズム

リソース要求アルゴリズムを使用すると、特定のプロセスがリソース要求を行ったときのシステムの動作を表現できます。

これを次のように理解しましょうwing 手順:

ステップ1) すべてのリソースの要求されたインスタンスの合計がプロセスより小さい場合は、ステップ 2 に進みます。

ステップ2) それぞれのリソース タイプの要求されたインスタンスが、各タイプの利用可能なリソースと比較して少ない場合、次のステップに処理されます。他のwise、十分なリソースが利用できないため、プロセスは待機する必要があります。

ステップ3) リソースは、以下の擬似コードのように割り当てられます。

Available = Available – Request (y)
Allocation(x) = Allocation(x) + Request(x)
Need(x) = Need(x) - Request(x)

この最後のステップは、システムがリソースが割り当てられていると想定する必要があるために実行されます。 そのため、割り当て後に利用できるリソースは少なくなるはずです。

バンカーズアルゴリズムの特徴

バンカーのアルゴリズムの重要な特徴は次のとおりです。

  • 少なくとも XNUMX つのクライアントの要件を満たす多くのリソースを保持します
  • プロセスはすべてのリソースを取得するたびに、制限された期間内にそれらを返す必要があります。
  • プロセスがリソースを要求すると、待機する必要があります
  • システムのリソース数には限りがあります
  • リソースを最大限に割り当てるための高度な機能

バンカーアルゴリズムの欠点

バンカーアルゴリズムを使用することの短所/欠点は次のとおりです

  • 処理中にプロセスが最大ニーズを変更することを許可しません
  • すべてのリクエストを制限時間内に許可することができますが、その期間は XNUMX 年間と定められています。
  • すべてのプロセスは、リソースの最大ニーズを事前に認識し、明示する必要があります。

まとめ

  • バンカーのアルゴリズムは主に銀行システムで使用されており、 deadlock。 融資が受けられるかどうかを判断するのに役立ちます。
  • バンカーのアルゴリズムで使用される表記は、1) 利用可能、2) 最大、3) 割り当て、4) 必要です。
  • リソース要求アルゴリズムを使用すると、特定のプロセスがリソース要求を行ったときのシステムの動作を表現できます。
  • バンカーのアルゴリズムは、少なくとも XNUMX つのクライアントの要件を満たす多くのリソースを保持します
  • バンカーのアルゴリズムの最大の欠点は、プロセスが処理中に最大ニーズを変更できないことです。