操作系统实验三——银行家算法

admin管理员组

文章数量:1531793

银行家算法

银行家算法概述

我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源。
当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源 的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。

安全状态

安全状态：如果存在一个由系统中所有进程构成的 安全序列P1，…，Pn，则系统处于安全状态。安全状态 一定是没有死锁发生。
不安全状态：不存在一个安全序列。不安全状态不一定导致死锁。
安全序列：一个进程序列{P1，…，Pn}是安全的， 如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资 源量不超过系统当前剩余资源量与所有进程Pj (j < i ) 当前占有资源量之和。

请求算法

设request­­i为进程p[i]的请求向量，如果 requesti[j]=K，表示进程p[i]需要K个Rj资源。当系统发出请求后，系统按下述步骤开始检查：
① 如果requesti[j]<=need[i][j]，转向步骤②；否则报告出错，申请的资源已经大于它需要的最大值。
② 如果requesti[j]<=available[j]，转向步骤③；否则报告出错，尚无足够的资源。
③ 系统试探着把资源分配给p[i]，并修改下列数据结构中的值：
available[j]=available[j]­request[j]
allocation[i][j]=allocation[i][j]+request[j]
need[i][j]=need[i][j]­request[j]
④ 系统进行安全性算法，检查此次分配后，系统是否还处于安全状态，若安全，把资源分配给进程p[i]；否则，恢复原来的资源分配状态，让进程p[j]等待。

安全性算法

安全性算法：
int work[RESOURCE_NUMBER]；
bool finish[PROCESS_NUMBER]；
① Work=Available;
Finish=false;
② 寻找满足条件的 i：
A、Finish[i]=false;
B、 Need[i]≤Work;
如果不存在，则转④
③ Work:=Work+Allocation[i]；Finish[i]:=true；转②
④ 若对所有 i,，Finish[i]=true，则系统处于安全状态，否则处于不安全状态

银行家算法的程序流程图

代码实现

#include <bits/stdc++.h>

using namespace std;

int processNum;				//进程数
int resourceNum;			//资源数
int available[1000];		//可用资源
int maxRequest[1000][1000]; //最大所需资源
int allocation[1000][1000]; //已经分配资源
int need[1000][1000];		//需要的资源
bool Finish[1000];			//进程是否完成
int work[1000];				//工作时可分配资源
int safeSeries[1000];		//安全序列
int request[1000];			//请求资源
void SafeInfo(int *work, int i);

//初始化
void Init()
{
	int i, j;
	cout << "输入进程数量、资源数量\n";
	cin >> processNum >> resourceNum;
	cout << "输入当前资源可用数目\n";
	for (i = 0; i < resourceNum; i++)
	{
		cin >> available[i];
	}
	cout << "输入最大需求矩阵\n";
	for (i = 0; i < processNum; i++)
	{
		for (j = 0; j < resourceNum; j++)
		{
			cin >> maxRequest[i][j];
		}
	}
	cout << "输入分配矩阵\n";
	for (i = 0; i < processNum; i++)
	{
		for (j = 0; j < resourceNum; j++)
		{
			cin >> allocation[i][j];
		}
	}
	cout << "输入当前需求矩阵\n";
	for (i = 0; i < processNum; i++)
	{
		for (j = 0; j < resourceNum; j++)
		{
			cin >> need[i][j];
		}
	}
}
//显示当前所有进程分配状态
void showInfo()
{
	int i, j;
	cout << "当前资源剩余：";
	for (j = 0; j < resourceNum; j++)
	{
		cout << available[j] << " ";
	}
	cout << "\n";
	cout << " PID\t Max\t\tAllocation\tNeed\n";
	for (i = 0; i < processNum; i++)
	{
		cout << "P" << i << "\t";
		for (j = 0; j < resourceNum; j++)
		{
			cout << maxRequest[i][j] << " ";
		}
		cout << "\t\t";
		for (j = 0; j < resourceNum; j++)
		{
			cout << allocation[i][j] << " ";
		}
		cout << "\t\t";
		for (j = 0; j < resourceNum; j++)
		{
			cout << need[i][j] << " ";
		}
		cout << "\n";
	}
}
//安全性检查
bool isSafe()
{
	int i, j, k;
	int lunci = 0;
	int Finishednum = 0;
	int work[resourceNum];
	//work初始化
	for (i = 0; i < resourceNum; i++)
	{
		work[i] = available[i];
	}
	//Finish初始化
	for (i = 0; i < processNum; i++)
	{
		Finish[i] = false;
	}
	i = 0;
	int temp = 0;

	while (Finishednum != processNum)
	{
		int j = 0;
		//当前进程i是否满足finish==false并且need<work
		if (Finish[i] != true)
		{
			for (j = 0; j < resourceNum; j++)
			{
				if (need[i][j] > work[j])
				{
					break;
				}
			}
		}
		//上面的条件满足则进行第三步，分配并释放资源并完成进程，安全序列加一
		if (j == resourceNum)
		{
			Finish[i] = true;
			SafeInfo(work, i);
			for (k = 0; k < resourceNum; k++)
			{
				work[k] += allocation[i][k];
			}
			safeSeries[Finishednum++] = i;
		}
		i++;
		if (i >= processNum)
		{
			i = i % processNum;
			lunci++;
			if (temp == Finishednum && lunci > 0) //再次循环一遍之后没有任何变化，可以认为当前序列中已经没有可以继续执行的进程了
				break;
			temp = Finishednum; //记录本轮的Finishednum 一共有多少
		}
	}

	if (Finishednum == processNum)
	{
		cout << "\n系统安全！\n\n安全序列为：";
		for (i = 0; i < processNum; i++)
		{
			cout << "P" << safeSeries[i] << " ";
		}
		return true;
	}
	else
	{
		cout << "******系统不安全！******\n";
		return false;
	}
}
//显示给定进程当前的状态
void SafeInfo(int *work, int i)
{
	int j;
	cout << "P" << i << "\t";
	for (j = 0; j < resourceNum; j++)
	{
		cout << work[j] << " ";
	}
	cout << "\t\t";
	for (j = 0; j < resourceNum; j++)
	{
		cout << need[i][j] << " ";
	}
	cout << "\t ";
	for (j = 0; j < resourceNum; j++)
	{
		cout << allocation[i][j] << " ";
	}
	cout << "\t\t";
	for (j = 0; j < resourceNum; j++)
	{
		cout << allocation[i][j] + work[j] << " ";
	}
	cout << "\n";
}
//主函数
int main()
{
	int i, j, curProcess;
	Init();
	showInfo();
	cout << "\n系统安全情况分析\n";
	cout << " PID\t Work\t\tNeed\tAllocation\tWork+Allocation\n";
	isSafe();
	while (true)
	{
		cout << "\n---------------------------------------------------------\n";
		cout << "\n输入要分配的进程：";
		cin >> curProcess;
		cout << "\n输入要分配给进程P" << curProcess << "的资源：";
		for (j = 0; j < resourceNum; j++)
		{
			cin >> request[j];
		}
		for (j = 0; j < resourceNum; j++)
		{
			if (request[j] <= need[curProcess][j])
				continue;
			else
			{
				cout << "ERROR！\n";
				break;
			}
		}
		if (j == resourceNum)
		{
			for (j = 0; j < resourceNum; j++)
			{
				if (request[j] <= available[j])
					continue;
				else
				{
					cout << "资源不足，等待中！\n";
					break;
				}
			}
			if (j == resourceNum)
			{
				for (j = 0; j < resourceNum; j++)
				{
					available[j] -= request[j];
					allocation[curProcess][j] += request[j];
					need[curProcess][j] -= request[j];
				}
				cout << "\n系统安全情况分析\n";
				cout << " PID\t Work\t\tNeed\tAllocation\tWork+Allocation\n";
				if (isSafe())
				{
					cout << "分配成功！\n";
					showInfo();
				}
				else
				{
					for (j = 0; j < resourceNum; j++)
					{
						available[j] += request[j];
						allocation[curProcess][j] -= request[j];
						need[curProcess][j] += request[j];
					}
					cout << "分配失败！\n";
					showInfo();
				}
			}
		}
	}
}

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