操作系统之二———银行家算法

admin 管理员组

文章数量: 887017

参考资料：http://blog.csdn/yaopeng_2005/article/details/6935235

https://wwwblogs/chuxiuhong/p/6103928.html

      银行家算法： Dijkstra E.W 于1968年提出。该算法需要检查申请者对资源的最大需求量，如果系统现存的各类资源可以满足申请者的请求，就满足申请者的请求。这样申请者就可很快完成其计算，然后释放它占用的资源，从而保证了系统中的所有进程都能完成，从而避免死锁的发生。

     首先，要了解什么是死锁？在两个或多个并发进程中，如果每个进程持有某种资源而又都等待着别的进程释放它或它们现在保持着的资源，否则就不能向前推进。此时，我们就称这一组进程产生了死锁。

    如图所示：

       为了提高设备的利用率，应采用动态的设备分配方法，但应设法避免发生死锁，若存在发生死锁的可能性，则拒绝分配。从而产生了死锁避免，即在动态分配资源的策略下采用某种算法来避免可能发生的死锁，从而拒绝可能产生死锁的某个资源的请求。在这种情况下，提出了银行家算法。

     要想真切的理解银行家算法，还需要理解一个概念——安全状态。那么什么情况下我们可以说，一个系统处于安全状态呢？举个简单的例子，例子：假定系统有10个资源，目前资源分配的情况如下：

       此时，系统中只剩下2个资源，能满足Q最大要求， 于是将剩下的2个资源分配给Q，Q就能完成，然后释放所占用的4+2=6个资源。 6个资源可满足P，然后可满足R，这时不论分给谁都能保证完成。可利用的资源能依次满足进程Q,P,R的最大需求，此时系统处于安全状态中！  

       银行家算法正是利用保证进程始终处于安全状态的方法来避免死锁的。对于操作系统而言，我们可以来这样描述银行家算法：当某个进程提出资源请求时，假定先分配给它，然后：

1 查找请求矩阵R中的一行，检查其未满足的资源需求是否都小于或等于A1。如果有这样的行存在，则转2；

2 将资源分配给所选进程，该进程最终能运行完。标记这个进程为终止进程，并将它占有的全部资源归还给向量A1；

3 重复第一步和第2步，直到所有进程标记为终止进程，或直到一个死锁发生。

      若所有进程都标记为终止进程，则系统的初始状态是安全的，否则为不安全的。若安全，则正式将资源分配给它。否则，假定的分配作废，让其等待。

     那么经过前面一些知识储备，我们来研究一下银行家算法是如何实现的吧！

银行计算法

设进程cusneed 提出请求REQUEST [i] ，则银行家算法按如下规则进行判断。

(1) 如果REQUEST [cusneed] [i]<= NEED[cusneed][i] ，则转(2) ；否则，出错。

(2) 如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i] ，则转(3) ；否则，出错。

(3) 系统试探分配资源，修改相关数据：

         AVAILABLE[i]-=REQUEST[cusneed][i];

         ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];

         NEED[cusneed][i]-=REQUEST[cusneed][i];

(4) 系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复 原状，进程等待。

下面具体定义数据结构：

#define MAXRESOURCES 100 //定义最大资源数 
#define MAXPROCESS    50  //定义最大进程数

Avaliable[MAXRESOURCES]; //定义可用资源数组
Max[MAXPROCESS][MAXRESOURCES];//定义最大需求矩阵
Allocation[MAXPROCESS][MAXRESOURCES];//当前分配给各个进程的各资源数量
Need[MAXPROCESS][MAXRESOURCES];//当前各个进程还需要分配的资源
Requests[MAXPROCESS][MAXRESOURCES];//当前进程请求的资源数
Finish[MAXPROCESS];//当前进 程是否结束

PR[MAXPROCESS];//存放记录序列

参照流程图（图片来自网络）

初始化

由用户输入数据，分别对上述定义的时数据结构，如可利用资源向量矩阵AVAILABLE 、 最大需求矩阵MAX 、分配矩阵ALLOCATION、 需求矩阵NEED 赋值。

安全性检测

如果所有进程i都是能完成的，即Finish[i]=ture则系统处于安全状态，否则系统处于不安全状态。

安全性检测的原则是：
1、 进程申请资源可分布申请，但总量不应超过其最大需求量；
2 、每次申请的资源量必须小于系统可供使用的资源量；

3、分配完成后，系统是安全的，即仍存在一个序列，可以运行完当前所有进程，这是关键。

参照流程图（图片来自网络）

测试及结果

在网上找了道银行家算法的题，在这里测试一下；在银行家算法中，若出现下述资源分配情况，试问：

1）该状态是否安全？
2）若进程P2提出请求Request（1,2,2,2）后，系统能否将资源分配？

按照题目，输入数据进行测试:

最终测试结果，该进程安全，0、3、4、1、2为该进程的安全序列，

 进而测试2号申请，最终结果，该申请不安全。

测试结束，成功！

 最后附代码源码如下：https://pan.baidu/s/1MJ8G9_PtkPHkEb-mLBjQgQ

#include<iostream>
using namespace std;
#define MAXRESOURCES    100    //定义最大资源数 
#define    MAXPROCESS        50    //定义最大进程数
int   Avaliable[MAXRESOURCES]; //定义可用资源数组
int    Max[MAXPROCESS][MAXRESOURCES];//定义最大需求矩阵
int Allocation[MAXPROCESS][MAXRESOURCES];//当前分配给各个进程的各种资源数量
int  Need[MAXPROCESS][MAXRESOURCES];//当前各个进程还需要分配的资源
int Requests[MAXPROCESS][MAXRESOURCES];//当前进程请求的资源数
bool  Finish[MAXPROCESS];//当前进 程是否结束
int PR[MAXPROCESS];//存放记录序列
int m, n;//定义m个进程，n个资源
void  Initial();//初始化
bool   IsSafe();//安全检测函数
void   BankAlgorithm();//银行家算法实现
void ShowData(int n, int m);//显示用户界面
int  main()
{
	Initial();
	IsSafe();
	BankAlgorithm();
}


/*初始化*/
void  Initial()
{
	int    i, j;
	cout << "请输入总进程数：" << endl;
	cin >> m;
	cout << "请输入总资源种类数：" << endl;
	cin >> n;
	cout << "请输入每个进程最多所需要的资源数，按照" << m << "*" << n << "的矩阵输入:" << endl;
	for (i = 0; i < m; i++)
		for (j = 0; j < n; j++)
			cin >> Max[i][j];
	cout << "请输入每个进程已经分配的资源数，按照" << m << "*" << n << "的矩阵输入:" << endl;
	for (i = 0; i < m; i++)
		for (j = 0; j < n; j++)
		{
			cin >> Allocation[i][j];
			Need[i][j] = Max[i][j] - Allocation[i][j];
			if (Need[i][j] < 0)
			{
				cout << "您输入的第" << i + 1 << "个进程拥有的第" << j + 1 << "个资源出现错误，请您重新输入：" << endl;
				j--;
				continue;
			}
		}
	cout << "请输入各个资源现有的数目;" << endl;
	for (i = 0; i < n; i++)
		cin >> Avaliable[i];
}

/*
安全检测函数
如果所有进程i都是能完成的，即Finish[i]=ture
则系统处于安全状态，否则系统处于不安全状态
*/

bool IsSafe()
{
	int i, j, k, l = 0;
	int Work[MAXRESOURCES];    //工作数组
	for (i = 0; i < n; i++)
		Work[i] = Avaliable[i];//	工作数组赋值，与AVAILABLE数组相同
	for (i = 0; i < m; i++)//FINISH数组赋值，初始为全部false
		Finish[i] = false;    //FINISH记录每个进程是否安全
  while(l< m)    //正常的话，共执行m次
	{
		int init_index = l;
		for (i = 0; i < m; i++)
		{
			if (Finish[i] == true)    //如果这个进程安全则继续下一个循环
				continue;
			for (j = 0; j < n; j++)
				if (Need[i][j] > Work[j])
					break;
		  if (j == n)
			{
				Finish[i] = true;
				for (k = 0; k < n; k++)
				Work[k] += Allocation[i][k];//把放出去的贷款也当做自己的资产
				PR[l++] = i;//记录下已经完成的进程号 
			}
			else    //如果超过继续循环下一个进程
				continue;
		}
		if (l == init_index)
		{
			cout << "系统是不安全的" << endl;
			return false;
		}
	}
	cout << "系统是安全的" << endl;
	cout << "安全序列:" << endl;
	for (i = 0; i < l; i++)
	{
		cout << PR[i];
		if (i != l - 1)
			cout << "-->";
	}
	cout << endl;
	return true;
}
	
/*银行家算法实现*/
void   BankAlgorithm()
{
	int Currentneed, i, flag = 0;
	char Judge;//判断命令字符
	while (1)
	{
		ShowData(n, m);
		cout << endl;
		while (true)
		{
			cout << "输入当前要申请资源的进程号：（从0开始）" << endl;
			cin >> Currentneed;
			if (Currentneed > m)
			{
				cout << "不存在该进程，请您重新输入：" << endl;
				continue;
			}
			cout << "请输入该进程所需要的各个资源数：" << endl;
			for (i = 0; i < n; i++)
				cin >> Requests[Currentneed][i];
			for (i = 0; i < n; i++)
			{
				//如果用户选择的线程的第i个资源请求数＞该线程该资源所需的数量
				if (Requests[Currentneed][i] > Need[Currentneed][i])
				{
					cout << "您输入的请求数超出进程的需求量，请您重新输入：" << endl;
					continue;
				}

				//如果用户选择的线程的第i个资源请求数＞系统现有的第i个资源的数量
				if (Requests[Currentneed][i] > Avaliable[i])
				{
					cout << "您输入的请求数超出系统现有资源数，请您重新输入：" << endl;
					continue;
				}
			}
			break;
		}
		/*如果请求合理，那么开始银行家算法计算*/
		/*先将申请的资源进行分配*/
		for (i = 0; i < n; i++)
		{
			Avaliable[i] -= Requests[Currentneed][i];//系统可用资源减去申请了的
			Allocation[Currentneed][i] += Requests[Currentneed][i];//当前分配给各个进程的各种资源数量增加
			Need[Currentneed][i] -= Requests[Currentneed][i];//当前该进程还需要分配的资源减少

		}

		/*资源一经分配就要进行判断，系统是否安全
		如果不安全，将已经分配的资源归还给系统*/
		if (IsSafe())
			cout << "同意分配请求!" << endl;
		else
		{
			cout << "您的请求被拒绝!" << endl;
			//资源还回系统
			for (i = 0; i < n; i++)
			{
				Avaliable[i] += Requests[Currentneed][i];
				Allocation[Currentneed][i] -= Requests[Currentneed][i];
				Need[Currentneed][i] += Requests[Currentneed][i];
			}
		}


		//对进程的需求资源进行判断,Need数组是否为0,是否还需要资源；
		for (i = 0; i < n; i++)
		{
			if (Need[Currentneed][i] <= 0)
				flag++;
			if (flag == n) //如果该进程各资源都已满足条件，则释放资源
			{
				for (i = 0; i < n; i++)
				{
					Avaliable[i] += Allocation[Currentneed][i];
					Allocation[Currentneed][i] = 0;
					Need[Currentneed][i] = 0;
				}
				cout << "线程" << Currentneed << "的资源已经被释放" << endl;
				flag = 0;
			}
			for (i = 0; i < n; i++)
				Finish[i] = false;
			//判断是否需要继续申请
			cout << "您是否需要继续申请资源分配？是，请选择Y/y,否，请选择其他任意键：" << endl;
			cin >> Judge;
			if (Judge == 'y' || Judge == 'Y')
				continue;
			break;
		}
	}
}

/*显示用户界面*/
	void ShowData(int n, int m)   
	{
		int i, j;
		cout << endl;
		cout << "***********************************" << endl;
		cout << "系统可用的资源数为:    ";
		for (j = 0; j<n; j++)
			cout << "    " << Avaliable[j];
		cout << endl;
		cout << "各进程还需要的资源量:" << endl;
		for (i = 0; i<m; i++)
		{
			cout << "    进程" << i << ":";

			for (j = 0; j<n; j++)
				cout << "     " << Need[i][j];
			cout << endl;
		}

		cout << endl;
		cout << "各进程已经得到的资源量:    " << endl << endl;

		for (i = 0; i<m; i++)
		{
			cout << "    进程" << i << ":";

			for (j = 0; j<n; j++)
				cout << "     " << Allocation[i][j];
			cout << endl;
		}
		cout << endl;
	}

本文标签： 银行家 之二 算法 操作系统