操作系统：银行家算法（避免死锁）

算法介绍：

程序实现：

/*****************************************************

			程序：银行家算法实现
			作者：小单
			时间: 2013年11月5日

******************************************************/
#include <iostream>
#include <string>
using namespace std;

#define MAXPROCESS  50  //所能执行的进程最大数
#define MAXRESOURCE 50  //资源最大数

//银行家算法中的数据结构
int Available[MAXRESOURCE];  //可用资源向量
int Max[MAXPROCESS][MAXRESOURCE];   //最大需求矩阵
int Allocation[MAXPROCESS][MAXRESOURCE];  //分配矩阵
int Need[MAXPROCESS][MAXRESOURCE];   //需求矩阵
int Request[MAXPROCESS][MAXRESOURCE];  //请求向量

//安全性算法中的数据结构
int Work[MAXRESOURCE];    //工作向量
bool Finish[MAXPROCESS];    //表示是否有足够的资源分配给进程
int SafeSeries[MAXPROCESS];  //安全序列

////////////////////////////////////////////////////
int n;  //当前系统中的进程数
int m;   //当前系统中的资源数



//////////////////////////////////////////////////////////
//算法初始化
void InitAlgorithm()
{
	cout << "请输入系统所要运行的进程总数:";
	cin >> n;
	cout << "请输入系统中分配的资源种类数：";
	cin >> m;
	int i,j;

	//可利用资源向量的初始化
	cout << "请分别输入" << m << "类资源的当前可利用资源数目:";
	for( i = 0; i < m; ++i )
	{
		cin >> Available[i];
	}

	//最大需求矩阵的初始化
	cout << "请输入各进程对各资源的最大需求矩阵(按"
		<< n << "*" << m << "矩阵格式输入):" << endl;
	for( i = 0; i < n; ++i )
	{
		for( j = 0; j < m; ++j )
		{
			cin >> Max[i][j];
		}
	}

	//分配矩阵的初始化
	cout << "请输入分配矩阵(按"
		<< n << "*" << m << "矩阵格式输入):" << endl;
	for( i = 0; i < n; ++i )
	{
		for( j = 0; j < m; ++j )
		{
			cin >> Allocation[i][j];
		}
	}

	//需求矩阵的初始化
	cout << "请输入此刻的需求矩阵(按"
	<< n << "*" << m << "矩阵格式输入):" << endl;
	for( i = 0; i < n; ++i )
	{
		for( j = 0; j < m; ++j )
		{
			cin >> Need[i][j];
		}
	}

}

//输出资源分配情况
void PrintSrcAlloc()
{
	int i,j;
	for( i = 0; i < n; ++i )
	{
		cout << "进程P" << i << "的总体分配情况:" << endl;
		cout << "\tMax: ";
		for( j = 0; j < m; ++j )
		{
			cout << Max[i][j] << " ";
		}
		cout << endl;

		cout << "\tAllocation：";
		for( j = 0; j < m; ++j )
		{
			cout << Allocation[i][j] << " ";
		}
		cout << endl;

		cout << "\tNeed：";
		for( j = 0; j < m; ++j )
		{
			cout << Need[i][j] << " ";
		}
		cout << endl;
		cout << endl;
	}

	cout << "可利用资源情况：";
	for( i = 0; i < m; ++i )
	{
		cout << Available[i] << " ";
	}
	cout << endl;
	cout << endl;

}

//输出此时进程iProcess利用安全性算法的分析情况
void PrintSafeSeries( int iProcess )
{
	int j;
	cout << "进程P" << iProcess << "的安全性分析情况:" << endl;
	cout << "\tWork: ";
	for( j = 0; j < m; ++j )
	{
		cout << Work[j] << " ";
	}
	cout << endl;
	
	cout << "\tNeed：";
	for( j = 0; j < m; ++j )
	{
		cout << Need[iProcess][j] << " ";
	}
	cout << endl;
	
	cout << "\tAllocation：";
	for( j = 0; j < m; ++j )
	{
		cout << Allocation[iProcess][j] << " ";
	}
	cout << endl;
	
	cout << "\tWork + Allocation：";
	for( j = 0; j < m; ++j )
	{
		cout << Work[j] + Allocation[iProcess][j] << " ";
	}
	cout << endl;

	cout << "Finish[" << iProcess << "] = " << Finish[iProcess] << endl;
	cout << endl;


}

//判断是否存在安全序列
bool IsSafe()
{
	int i;
	for( i = 0; i < n; ++i )
	{
		if( !Finish[i] )
			return false;  //不存在安全序列
	}
	return true;//存在安全序列
}

//界面
void Menu()
{
	cout << "\t\t ==========================================="  << endl;
	cout << "\t\t|                                           |" << endl;
	cout << "\t\t|         程序：银行家算法的模拟实现        |" << endl;
	cout << "\t\t|         作者：小单                        |" << endl;
	cout << "\t\t|         时间：2013.11.5                   |" << endl;
	cout << "\t\t|                                           |" << endl;
	cout << "\t\t ==========================================="  << endl;
}


//选出满足条件的进程
//函数返回进程编号
//若不存在满足条件的，则返回false,否则返回true
bool SelectProcess( int &iProcNum )
{
	iProcNum = -1;
	int i, j;
	for( i = 0; i < n; ++i )
	{
  		if ( Finish[i] )  //Finish[i] != false
		{
			continue;
		}
		for ( j = 0; j < m; ++j )
		{
			if ( Need[i][j] > Work[j] )
			{
				break;
			}
		}
		if ( j == m )  //满足条件
		{
			iProcNum = i;
			return true;  
		}
	}
	return false;
}

//安全性算法
bool SafeAlgorithm()
{
	int i,j;

	//初始化Finish向量
	for( i = 0; i < n; ++i )
	{
		Finish[i] = false;
	}

	//初始化工作向量
	for ( j = 0; j < m; ++j )
	{
		Work[j] = Available[j];
	}

	int iProcNum;
	//选择满足条件的进程
	i = 0;
	while( SelectProcess( iProcNum) )
	{
		Finish[iProcNum] = true;
		PrintSafeSeries( iProcNum );  //输出此时利用安全性算法的分析情况
		int k;
		for ( k = 0; k < m; ++k )
		{
			Work[k] += Allocation[iProcNum][k];
		}
		SafeSeries[i++] = iProcNum;  //进程号加入安全序列数组

		
	}

	if( IsSafe() )
	{
		return true;  //存在一个安全序列
	}

	return false;  //不存在一个安全序列

}


//银行家算法
void BankAlgorithm()
{
	int i,j;
	cout << "请输入请求分配的进程号(0 - " << n-1 << "): ";
	cin >> i;
	cout << "请依次输入进程P" << i << "对" << m << "类资源的请求分配量: ";
	for( j = 0; j < m; ++j )
	{
		cin >> Request[i][j];
	}

	//步骤一
	for( j = 0; j < m; ++j )
	{
		if( Request[i][j] > Need[i][j] )
		{
			cout << "请求的资源已超过该资源宣布的最大值，请求资源失败!!" << endl;
			return;
		}
	}

	//步骤二
	for( j = 0; j < m; ++j )
	{
		if( Request[i][j] > Available[j] )
		{
			cout << "没有足够的资源，请求资源失败!!" << endl;
			return;
		}
	}

	//步骤三
	//系统试探着把资源分配给进程Pi，并修改相应的数值
	for ( j = 0; j < m; ++j )
	{
		Available[j] -= Request[i][j];
		Allocation[i][j] += Request[i][j];
		Need[i][j] -= Request[i][j];
	}

	//步骤四
	//系统执行安全性算法
	if ( !SafeAlgorithm() ) //检测到不安全，则恢复原来的状态
	{
		for ( j = 0; j < m; ++j )
		{
			Available[j] += Request[i][j];
			Allocation[i][j] -= Request[i][j];
			Need[i][j] += Request[i][j];
		}	
	}

}



int main()
{
	Menu();
	InitAlgorithm();
	PrintSrcAlloc();  //打印当前资源情况
	system("pause");
	SafeAlgorithm();
	while(1)
	{
		string flag;
		if( IsSafe() )
		{
			//存在安全序列
			cout << "恭喜！！资源分配成功!!" << endl;
			int i;
			cout << "此时刻存在的一个安全序列为：";
			for ( i = 0; i < n - 1; ++i )
			{
				cout << "P" << SafeSeries[i] << "-->";
			}
			cout << "P" << SafeSeries[i] << endl;
			cout << "继续操作吗？[Y/N]:";
			cin >> flag;
		}
		else
		{
			cout << "资源分配失败!!" << endl;
			cout << "继续操作吗？[Y/N]:";
			cin >> flag;
		}

		if ( flag == "Y" || flag == "y" )
		{
			;
		}
		else
		{
			break;
		}
		BankAlgorithm(); //执行银行家算法

	}


	return 0;

}