オペレーティングシステム:銀行家アルゴリズムの分析とコード実装(c++言語)

銀行家アルゴリズム(Banker's Algorithm)はデッドロック(Deadlock)を避ける有名なアルゴリズムで、1965年にエズグ・ディジェストラがT.H.Eシステムのために設計したデッドロックの発生を避けるアルゴリズムである.銀行ローンシステムの分配戦略に基づいて、システムの安全運行を判断し、保証します.
デッドロック回避方法では、プロセスがリソースを動的に申請することができますが、システムはリソースの割り当てを行う前に、今回の割り当てリソースのセキュリティを計算する必要があります.割り当てがシステムを不安全な状態にしない場合は、割り当て、そうでない場合は待機します.銀行家アルゴリズムを実現するために、システムはいくつかのデータ構造を設定しなければならない.
1)種々のリソース総数ベクトルresourceは、m個の要素を含む配列であり、各要素は、システムが提供できるリソースの総数を表す.resource[j]=Kの場合、システムに既存のRjクラスリソースK個が存在することを示す.2)最大需要行列Claimこれはn×システム内のnプロセスの各プロセスのmクラスリソースに対する最大の需要を定義するmのマトリクス.Claim[i,j]=Kの場合、プロセスiがRjクラスリソースを必要とする最大数はKであることを示す.3)分配行列allocationこれもn×mのマトリクスは、システム内の各クラスのリソースが現在各プロセスに割り当てられているリソースの数を定義します.allocation[i,j]=Kの場合、プロセスiが現在Rjクラスリソースに割り当てられている数がKであることを示す.4)使用可能なリソース数availableベクトルm個の要素を含む配列であり、各要素は1種類のリソースが使用可能な数を表す.アルゴリズムの実行フローは簡単である:(1)まずresource[i]-sum[i](各プロセスがあるリソースを占有する総数)でavailable[i]配列を求め(2)n*mの行列を遍歴し、1つのプロセスが各リソースに対する需要がavailable配列よりも小さい限り、それを安全と見なし、終了後に占有するリソースを解放する.すなわちavailable[j]+=alloc[i][j];
(3)逆に,前のステップでは,このようなシーケンスが見つからない場合は,セキュリティシーケンスではなく,割当てが許されず,プログラムが終了すると考える.

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
using namespace std;
#define M 4
#define N 3
int resource[M];
int available[M];
int claim[N][M];
int alloc[N][M];
int vis[N];
vector<int> ans;
int main()
{
	cout<<"                "<<endl;
	for(int i=0;i<N;i++)
		for(int j=0;j<M;j++)
			cin>>claim[i][j];
	cout<<"                "<<endl;
	for(int i=0;i<N;i++)
		for(int j=0;j<M;j++)
			cin>>alloc[i][j];
	cout<<"          "<<endl;
	for(int i=0;i<M;i++)
		cin>>resource[i];

	int sum[M];
	memset(sum,0,sizeof(sum)); 
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<M;j++)
			sum[j]+=alloc[i][j];
	}
	for(int i=0;i<M;i++)
	available[i]=resource[i]-sum[i];
	
	memset(vis,0,sizeof(vis));
	ans.clear();
	int is_ok=0;
	while(1)
	{
		if(ans.size()==N)
		{
			is_ok=1;
			break;
		}

		int index;
		int flag=0;
		for(int i=0;i<N;i++)
		{
			int judge=1;
			if(!vis[i])
			{
			  for(int j=0;j<M;j++)
			  {
				 if(available[j]<claim[i][j]-alloc[i][j])
				 {
					 judge=0;
					 break;
				 }
			 }
			}
			else
				continue;

			if(judge)
			{
				index=i;
				flag=1;
				break;

			}

		}
		   if(flag)
          {
		       vis[index]=1;
	           ans.push_back(index);
		       for(int k=0;k<M;k++)
		       available[k]+=alloc[index][k];
		  }
   	      else
		  {
				cout<<"    ，    !"<<endl;
				return 0;
		  }

	}
	if(is_ok)
	{
		cout<<"      ，     ："<<endl;
		for(int i=0;i<ans.size();i++)
			cout<<ans[i]<<"  ";
		cout<<endl;
	}
	return 0;
}