操作系统实验二银行家算法

admin 管理员组

文章数量: 887019

一、实验目的
1、了解什么是操作系统安全状态和不安全状态；
2、了解如何避免系统死锁；
3、理解银行家算法是一种最有代表性的避免死锁的算法，掌握其实现原理及实现过程。
二、实验环境
虚拟机的Ubuntu 64位系统
三、实验内容
根据银行家算法的基本思想，编写和调试一个实现动态资源分配的模拟程序，并能够有效避免死锁的发生。
四、实验原理 实验中用到的系统调用函数（包括实验原理中介绍的和自己采用的），实验步骤，
进程申请资源时，系统通过一定的算法判断本次申请是否不可能产生死锁（处于安全状态）。若可能产生死锁（处于不安全状态），则暂不进行本次资源分配，以避免死锁。算法有著名的银行家算法。
1、什么是系统的安全状态和不安全状态？
所谓安全状态，是指如果系统中存在某种进程序列＜P1，P2，…，Pn＞，系统按该序列为每个进程分配其所需要的资源，直至最大需求，则最终能使每个进程都可顺利完成，称该进程序列＜P1，P2，…，Pn，＞为安全序列。
如果不存在这样的安全序列，则称系统处于不安全状态。
2、银行家算法
把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。
为保证资金的安全，银行家规定:
(1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客;
(2) 顾客可以分期贷款，但贷款的总数不能超过最大需求量;
(3) 当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款;
(4) 当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金。

操作系统按照银行家制定的规则设计的银行家算法为：
（1）进程首次申请资源的分配：如果系统现存资源可以满足该进程的最大需求量，则按当前的申请量分配资源，否则推迟分配。
（2）进程在执行中继续申请资源的分配：若该进程已占用的资源与本次申请的资源之和不超过对资源的最大需求量，且现存资源能满足该进程尚需的最大资源量，则按当前申请量分配资源，否则推迟分配。
（3）至少一个进程能完成：在任何时刻保证至少有一个进程能得到所需的全部资源而执行到结束。
银行家算法通过动态地检测系统中资源分配情况和进程对资源的需求情况来决定如何分配资源，并能在确保系统处于安全状态时才把资源分配给申请者，从而避免系统发生死锁
因为是模拟程序，可以不使用系统调用函数。

五、实验要求
1、画出银行家算法流程图；

2、对算法所用的数据结构进行说明；
#define process 5 //表示有5个进程
#define resources 3 //表示有3种资源
int Max[process][resources]; //最大资源需求量
int Allocation[process][resources]; //系统已分配资源量
int Need[process][resources]; //进程最多还需要资源量
int Available[resources]; //系统剩余资源量
int Request[process][resources]; //进程申请资源数
int flag = 0; //判断是否有可能发生死锁标志
int Judge[resources]; //判断所有进程是否运行完毕
int Remainder =process; //剩余的进程数
3、测试数据随机产生。不可手工输入；
4、 编写程序并调试；

// An highlighted block
#include<iostream>
#include<time.h>
using namespace std;
#define process 5					//表示有5个进程
#define resources 3					//表示有3种资源
int Max[process][resources];		//最大资源需求量
int Allocation[process][resources];	//系统已分配资源量
int	Need[process][resources];		//进程最多还需要资源量
int Available[resources];			//系统剩余资源量
int Request[process][resources];	//进程申请资源数
int flag = 0;						//判断是否有可能发生死锁标志
int Judge[resources];				//判断所有进程是否运行完毕
int Remainder =process;						//剩余的进程数
void initialization()//用随机数函数初始化各个矩阵
{
	srand((unsigned)time(NULL));
	for (int i = 0; i < process; i++)
	{
		for (int j = 0; j < resources; j++)
		{
				Max[i][j] = rand() % 9 + 1;
				Allocation[i][j] = rand() % 9 + 1;
				while (Allocation[i][j] > Max[i][j])
				{
					Allocation[i][j] = rand() % 9 + 1;
				}
				Need[i][j] = Max[i][j] - Allocation[i][j];		
		}
	}
}
void show()//打印矩阵
{
	for (int i = 0; i < process; i++)
	{
		cout
			<< "进程"<<i<<"\t\t" <<"("<< Max[i][0] <<"  "<< Max[i][1] << "  " << Max[i][2] <<")"<< "\t\t"
			<< "(" << Allocation[i][0] << "  " << Allocation[i][1] << "  " << Allocation[i][2] << ")" << "\t\t"
			<< "(" << Need[i][0] << "  " << Need[i][1] << "  " << Need[i][2] << ")" << endl;
	}		
}
void banker()//银行家算法
{
	for (int i = 0; i < resources; i++)//扫描随机生成出来的进程是否有已完成的
	{
		if (Need[i][0] == 0 && Need[i][1] == 0 && Need[i][2] == 0)
		{
			Remainder--;
			for (int j = 0; j < resources; j++)
			{
				Available[j] = Available[j] + Max[i][j];
			}
			cout << "进程" << i << "的最大需求已满足，运行完收回资源" << endl;
			cout << "系统剩余的资源为(" << Available[0] << "  " << Available[1]
				<< "  " << Available[2] << ")" << endl;
			cout << "-----------------------------------------------------------------------" << endl;
		}
	}
	while (Available[0]!=0|| Available[1] != 0||Available[2] != 0)
	{
		int temp = rand() % 5;
		while(Need[temp][0] == 0&& Need[temp][1] == 0&& Need[temp][2] == 0)//如果进程已运行结束
		{																//则该进程不会发出请求
			temp = rand() % 5;
		}
		do 
		{
			for (int i = 0; i < resources; i++)
			{
				Request[temp][i] = rand() % 10;		//模拟随机一个进程请求第(i+1)种资源
				while (Request[temp][i] > Need[temp][i])//使得模拟请求的资源数小于最多还需要资源数
				{
					Request[temp][i] = rand() % (Need[temp][i] + 1);
				}
			}
		} while (Request[temp][0] == 0 && Request[temp][1] == 0 && Request[temp][2] == 0);
		if (Request[temp][0] <= Available[0] && Request[temp][1] <= Available[1] 
			&& Request[temp][2] <= Available[2])//安全性算法
		{
			for (int i = 0; i < resources; i++)//系统尝试分配
			{
				Available[i] = Available[i] - Request[temp][i];
				Allocation[temp][i] = Allocation[temp][i] + Request[temp][i];
				Need[temp][i] = Need[temp][i] - Request[temp][i];
			}
			for (int n = 0; n < process; n++)
			{
				for (int m = 0; m < resources; m++)
				{
					if (Available[m] >= Need[n][m])
					{
						continue;
					}
					else
					{
						flag++;
						break;
					}
				}
			}
			if (flag == Remainder)
			{
				flag = 0;
				cout << "进程" << temp << "请求的资源数为(" << Request[temp][0] << "  "
					<< Request[temp][1] << "  " << Request[temp][2] << ")" << endl;
				cout << "系统分配后剩余的资源为(" << Available[0] << "  " << Available[1]
					<< "  " << Available[2] << ")" << endl;
				cout<<"虽然系统剩余的资源足够分配给进程"<< temp 
					<< ",但是进行分配有可能引起系统发生死锁，所以拒绝本次分配" << endl;
				cout << "-----------------------------------------------------------------------" << endl;
				for (int i = 0; i < resources; i++)//有可能引起死锁，所以拒绝分配，把之前分配的资源收回
				{
					Available[i] = Available[i] + Request[temp][i];
					Allocation[temp][i] = Allocation[temp][i] - Request[temp][i];
					Need[temp][i] = Need[temp][i] + Request[temp][i];
				}
			}
			else 
			{
				flag = 0;
				cout << "进程" << temp << "请求的资源数为(" << Request[temp][0] << "  "
					<< Request[temp][1] << "  " << Request[temp][2] << ")" << endl;
				cout<<"系统剩余的资源足够分配给进程"<< temp 
					<< ",并且不会引起死锁，同意本次分配" << endl;
				cout << "-----------------------------------------------------------------------" << endl;
				cout << "分配后系统当前进程资源使用情况" << endl;
				cout << "进程ID \t\t最大需求\t\t已分配\t\t\t最多还需要" << endl;
				show();
				cout << "系统分配后剩余的资源为(" << Available[0] << "  " << Available[1]
					<< "  " << Available[2] << ")" << endl;
				cout << "-----------------------------------------------------------------------" << endl;
			}
			if (Max[temp][0] == Allocation[temp][0]&& Max[temp][1] == Allocation[temp][1] 
				&& Max[temp][2] == Allocation[temp][2] )
			{
				Remainder--;
				for (int i = 0; i < resources; i++)
				{
					Available[i] = Available[i] + Max[temp][i];
				}	
				cout << "进程" << temp << "的最大需求已满足，运行完收回资源" << endl;
				cout << "系统剩余的资源为(" << Available[0] << "  " << Available[1]
					<< "  " << Available[2] << ")" << endl;
				cout << "-----------------------------------------------------------------------" << endl;
				if (Judge[0] == Available[0] && Judge[1] == Available[1] && Judge[2] == Available[2])
				{
					cout << "所有进程运行完毕" << endl;
					cout << "-----------------------------------------------------------------------" << endl;
					break;
				}
			}
		}
		else
		{
			cout << "进程" << temp << "请求的资源数为(" << Request[temp][0] << "  "
				<< Request[temp][1] << "  " << Request[temp][2] << ")" << endl;
			cout<<"系统剩余的资源为("<< Available[0] << "  " << Available[1] << "  " << Available[2] << "),系统剩余资源不足，进程" <<
				temp << "必须等待" << endl;
			cout << "-----------------------------------------------------------------------" << endl;
		}
	}
	if (Available[0] == 0 && Available[1] == 0 && Available[2] == 0)
	{
		cout << "系统已无资源分配" << endl;
	}
}
int main()
{
	cout << "系统当前进程资源使用情况" << endl;
	cout << "进程ID \t\t最大需求\t\t已分配\t\t\t最多还需要" << endl;
	initialization();
	show();
	for (int i = 0; i < resources; i++)
	{
		Available[i] = rand() % 15 + 1;	//随机生成系统剩余资源量
	}
	cout << "系统剩余资源为(" << Available[0] << "  " << Available[1] << "  " << Available[2] <<")"<< endl;
	cout << "-----------------------------------------------------------------------" << endl;
	for (int i = 0; i < resources; i++)
	{
		Judge[i] = Available[i];
	}
	for (int i = 0; i < process; i++)
	{
		for (int j = 0; j < resources; j++)
		{
			Judge[j] = Judge[j] + Allocation[i][j];
		}
	}
	banker();
}

5、 多次测试程序，截屏输出实验结果；
6、根据实验结果与理论课讲述的原理进行实验分析。
六、思考题
1、如何设计程序的输入模块才能满足实验要求，请举例说明；
输入模块中Max矩阵、Allocation矩阵都是由系统rand()函数随机生成的，其中Max矩阵生成的数我设置为0~9，这个可以自行设置，但是Allocation矩阵的随机输入必须低于Max矩阵中对应的数字，不然会导致安全性问题，Need矩阵=Max矩阵-Allocation矩阵
2、银行家算法在实现过程中必须注意哪些资源分配细节才能避免死锁？
当收到系统随机生成的请求后
1、判断是否低于该进程的最大还需资源量(即小于Need矩阵中对应的资源量)
2、判断系统的剩余资源量是否满足请求量
3、若满足以上两个条件，则系统尝试分配资源，然后进行安全性检查，如果存在发生死锁的可能，则回滚已分配的资源，该进程的资源请求必须阻塞等待
七、实验结果分析（截屏的实验结果，与实验结果对应的实验分析）

实验结果与分析均表现在运行截图上

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