操作系统课设银行家算法实现

admin 管理员组

文章数量: 887021

创作不易，请勿直接抄袭！

源代码在文章最后面

一、实验题目：银行家算法

二、实验目的

(1) 进一步了解进程的并发执行。

(2) 加强对进程死锁的理解，理解安全状态与不安全状态的概念。

(3) 掌握使用银行家算法避免死锁问题。

三、总体设计

背景知识：银行家算法是避免死锁的一种算法，死锁就是两个或以上的进程互等资源而都阻塞的一种情况，在写银行家算法之前，要先明白安全序列和安全状态不安全状态的概念。安全序列就是系统能按照某种顺序并发执行并且能满足所有进程所需要的最大资源的一个顺序序列，能找到安全序列就处于安全状态，否则为不安全状态，安全状态一定不会发生死锁。银行家算法就是用来判断是否存在安全序列的一种算法。

基本原理：首先会给出所有进程所需要的最大资源数要求，然后给出已经分配给进程的资源数，求出进程还需要的资源数，然后给出分配之后剩余的资源数，接下来就是根据这个剩余资源数来判断是否能够找到安全序列。如果有一个进程不能够分配，则阻塞该进程，找其他进程，如果遍历完所有进程之后仍然有进程不能够满足分配，则该序列为不安全序列。

设计步骤：

1.给定进程数和资源数。

2.实现进程最大需求资源数的输入和已分配给进程的资源数的输入，根据这两个输入数据算出进程还需要的资源数。

3.给定剩余可用资源数。

4.根据剩余可用资源数来判断初始状态是否安全，如果不安全直接拒绝任何进程申请分配，如果存在一个安全序列则可以进行下一步：进程的资源申请分配。

四、详细设计

1. 主要的数据结构：主要用到的数组。(以下N为进程数，M为资源种类数)

Max[N][M]:最大声明进程资源矩阵。

Allocation[N][M]:进程已经分配资源矩阵。

Need[N][M]:进程还需要的资源数矩阵。该矩阵由以上两个矩阵求得。

Available[M]:目前还可用的资源数。

over[N]:用来记录某进程是否被放入安全序列当中。

list[N]:用来记录安全序列。

work[M]:用来实时记录剩余可用资源数的变化。

1. 各个函数的实现：

init()函数：用来初始化进程数，资源数和Max和Allocation矩阵。直接使用for循环实现二维数组的输入，init函数的关键代码如下：

cout<<"请输入各个进程所需的最大资源数:"<<endl;
	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++)
			cin>>Max[i][j];
	cout<<"请输入各个进程已经分配的资源数："<<endl;
	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++)
			cin>>Allocation[i][j];

show()函数：用来展示各个矩阵的实时变化，如果进程申请资源成功，则会输出三个矩阵的变化。

Safe()函数：用来判断初始给定的条件是否满足一个安全序列。首先需要将可用资源数赋值给一个中间变量数组work，然后循环每个进程，判断现有资源是否能满足进程所需要的资源，如果满足，将该进程的标志改为true，更新work数组，将该进程的分配资源数加到work里面，将循环变量i改为-1，然后重头便利每个进程，如果该进程的标志为true，则跳过，执行下一次循环，否则继续之前的判断操作。最后查看进程的标志数组over是否都为true，

如果有一个是false，则为不安全序列。否则为安全序列，输出即可。

关键代码：

for(int i=0; i<n; i++) {//判断是否存在安全序列
		int flag=1;
		if(over[i])
			continue;
		else {//判断当前可用资源数是否大于Need矩阵
			for(int j=0; j<m; j++) {
				if(Need[i][j]>work[j]) {
					flag=0;
					break;
				}
			}
		}
		if(flag==1) {//满足条件就更新work数组；并且重头开始遍历
			over[i]=true;
			for(int j=0; j<m; j++) {
				work[j]=work[j]+Allocation[i][j];
			}
			list[cnt++]=i;
			i=-1;
		}
	}
	int demo=1;
	for(int i=0; i<n; i++) {
		if(!over[i]) {
			cout<<"该序列不安全，应该禁止分配！"<<endl;
			demo=0;
			exit(0);
		}
	}

Process()函数：该函数只会在safe函数判断为初始状态为安全的情况下才会执行，目的是用来为进程申请资源分配。大体逻辑和safe函数的逻辑是一致的，但是增加了几个细节。首先要清空work数组，其次要判断该进程申请的资源数是否大于自己所需的资源数，如果大于禁止分配；接着判断该进程申请的资源数是否大于当前可用资源数，如果大于禁止分配；当以上两个条件都满足之后才会进行安全序列的判断，如果分配成功，要实时改变各个矩阵数据。关键代码如下：

for(int i=0; i<m; i++) {
		if(Request[i]>Need[id][i]) {
			flag=0;
			break;
		}
	}
	if(flag==0) {
		cout<<"请求资源数大于需求资源数，拒绝分配！"<<endl;
		continues();
	}
	for(int i=0; i<m; i++) {
		if(Request[i]>Available[i]) {
			flag2=0;
			break;
		}
	}
	if(flag2==0) {
		cout<<"请求的资源数大于剩余可用资源数，拒绝分配！"<<endl;
		continues();
	}
	if(flag==1&&flag2==1) { //满足基本请求条件
		for(int i=0; i<m; i++) {
			work[i]=Available[i];
			work[i]-=Request[i];
			Need[id][i]-=Request[i];
			Allocation[id][i]+=Request[i];
			Available[i]-=Request[i];
		}

五、实验结果与分析

运行结果如下：

分析：可以看到初始状态是满足安全序列的，则能够进行进程的资源申请分配，当为进程1申请1 0 2的资源数后，经判断也能够进行分配，则更改各个矩阵后输出安全序列，当为进程4申请3 3 0的资源数时，会因为当前申请资源数大于可用资源数而拒绝分配，满足银行家算法的要求，成功实现。

六、小结与心得体会

小结：通过编写银行家算法，让我对如何处理避免死锁问题有了更为深刻的认识和理解，也让我把书上的理论成功转化为实践，同时锻炼了我编写c++算法的能力，提高了我的思维能力和逻辑能力。在编写银行家算法时，我深刻地感受到了安全性和效率之间的平衡。一方面，为了保证系统的安全性，必须保证所有资源的分配都是安全的，即不存在任何进程陷入死锁的可能。另一方面，为了保证系统的效率，需要尽可能地满足进程的资源需求，避免资源的浪费，从而提高系统的整体运行效率。在使用银行家算法时，我还意识到了资源管理的重要性。进程之间的资源竞争往往是系统崩溃或死锁的主要原因之一。因此，在设计系统时，需要合理分配和管理资源，避免资源的浪费和滥用，从而提高系统的可靠性和稳定性。总之，银行家算法是一种非常重要的算法，它可以避免系统死锁的情况，提高系统的稳定性和可靠性。在编写这个算法时，我们需要权衡系统的安全性和效率，并合理分配和管理系统的资源，从而让整个系统更加健康和高效。

心得体会：在编写的过程之中，我也遇到过一些问题，比如在判断完安全序列之后没有重新将over数组更新为false，导致进程一直处于安全序列，最后调试之后解决了问题。总而言之，这次实际操作编写让我收获了很多，提高了我解决问题的积极性，提升了我的能力。
 

源代码如下：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=10,M=10;
int Need[N][M];//现在的需求矩阵 
int Allocation[N][M];//已分配资源矩阵 
int Max[N][M];//最大声明资源矩阵 
bool over[N];//用来记录某进程是否被放入安全序列 
int work[M];//用来实时记录剩余可用资源数的变化 
int Available[M];//初始给定剩余可用资源数 
int list[N];//用来记录安全序列 
int n,m;//n代表进程数，m代表资源个数
void continues();
void init() {//初始化数据 
	cout<<"请输入进程数和资源数:"<<endl;
	cin>>n>>m;
	cout<<"请输入各个进程所需的最大资源数:"<<endl;
	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++)
			cin>>Max[i][j];
	cout<<"请输入各个进程已经分配的资源数："<<endl;
	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++)
			cin>>Allocation[i][j];

	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++)
			Need[i][j]=Max[i][j]-Allocation[i][j];

	cout<<"请输入现有可用资源数："<<endl;
	for(int i=0; i<m; i++)
		cin>>Available[i];
}
void show() {//展示当前的各个矩阵的情况 
	cout<<"系统当前剩余可用资源如下："<<endl;
	for(int i=0; i<m; i++) {
		cout<<Available[i]<<" ";
	}
	cout<<endl;
	cout<<"系统当前资源分配如下："<<endl;
	cout<<"进程名\t"<<"Max\t"<<"Allocation\t"<<"Need"<<endl;
	for(int i=0; i<n; i++) {
		cout<<"P"<<i<<'\t';
		for(int j=0; j<m; j++)
			cout<<Max[i][j]<<" ";
		cout<<'\t'<<"  ";
		for(int j=0; j<m; j++)
			cout<<Allocation[i][j]<<" ";
		cout<<'\t'<<" ";
		for(int j=0; j<m; j++)
			cout<<Need[i][j]<<" ";
		cout<<endl;
	}
}
void safe() {//判断初始资源是否安全 
	int cnt=0;
	for(int i=0; i<m; i++)
		work[i]=Available[i];//将初始的资源数赋值给work

	for(int i=0; i<n; i++) {//判断是否存在安全序列
		int flag=1;
		if(over[i])
			continue;
		else {//判断当前可用资源数是否大于Need矩阵
			for(int j=0; j<m; j++) {
				if(Need[i][j]>work[j]) {
					flag=0;
					break;
				}
			}
		}
		if(flag==1) {//满足条件就更新work数组；并且重头开始遍历
			over[i]=true;
			for(int j=0; j<m; j++) {
				work[j]=work[j]+Allocation[i][j];
			}
			list[cnt++]=i;
			i=-1;
		}
	}
	int demo=1;
	for(int i=0; i<n; i++) {
		if(!over[i]) {
			cout<<"该序列不安全，应该禁止分配！"<<endl;
			demo=0;
			exit(0);
		}
	}
	if(demo==1) {
		cout<<"该状态安全，其中一个安全序列为：";
		for(int i=0; i<n; i++) {
			cout<<"P"<<list[i]<<" ";
		}
		cout<<endl;
	}
}

void process() {//判断某个进程是否可以请求资源分配 
	cout<<"请输入你想分配资源的进程号(0-n-1)："<<endl;
	int id;
	cin>>id;
	int Request[M];
	cout<<"请输入你想为该进程分配的资源数："<<endl;
	memset(work,0,sizeof work);
	for(int i=0; i<m; i++)
		cin>>Request[i];
	int flag=1,flag2=1;
	for(int i=0; i<m; i++) {
		if(Request[i]>Need[id][i]) {
			flag=0;
			break;
		}
	}
	if(flag==0) {
		cout<<"请求资源数大于需求资源数，拒绝分配！"<<endl;
		continues();
	}
	for(int i=0; i<m; i++) {
		if(Request[i]>Available[i]) {
			flag2=0;
			break;
		}
	}
	if(flag2==0) {
		cout<<"请求的资源数大于剩余可用资源数，拒绝分配！"<<endl;
		continues();
	}
	if(flag==1&&flag2==1) { //满足基本请求条件
		for(int i=0; i<m; i++) {
			work[i]=Available[i];
			work[i]-=Request[i];
			Need[id][i]-=Request[i];
			Allocation[id][i]+=Request[i];
			Available[i]-=Request[i];
		}

		memset(over,false,sizeof over);//初始化序列为未判断
		memset(list,0,sizeof list);//清空安全序列数组
		int cnt=0;
		for(int i=0; i<n; i++) {//判断是否存在安全序列
			int flag=1;
			if(over[i])
				continue;
			else {//判断当前可用资源数是否大于Need矩阵
				for(int j=0; j<m; j++) {
					if(Need[i][j]>work[j]) {
						flag=0;
						break;
					}
				}
			}
			if(flag==1) {//满足条件就更新work数组；并且重头开始遍历
				over[i]=true;
				for(int j=0; j<m; j++) {
					work[j]=work[j]+Allocation[i][j];
				}
				list[cnt++]=i;
				i=-1;
			}
		}
		int demo=1;
		for(int i=0; i<n; i++) {
			if(!over[i]) {
				show();
				cout<<"该序列不安全，应该禁止分配！"<<endl;
				demo=0;
				break;
			}
		}
		if(demo==0) {
			for(int i=0; i<m; i++) {
				Need[id][i]+=Request[i];
				Allocation[id][i]-=Request[i];
				Available[i]+=Request[i];
			}
			show();
			continues();
		}
		if(demo==1) {
			show();
			cout<<"该状态安全，其中一个安全序列为："<<endl;
			for(int i=0; i<n; i++) {
				cout<<"P"<<list[i]<<" ";
			}
			cout<<endl;
			continues();
		}

	}
}
void continues() {
	char s;
	cout<<"------------------"<<endl;
	cout<<"银行家算法功能判断"<<endl;
	cout<<"请选择你想要执行的操作Y(为进程请求分配)N（退出）"<<endl;
	cin>>s;
	if(s=='N') {
		return ;
	} else {
		process();
	}
}

int main() {

	init();
	show();
	safe();
	continues();
}

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