银行家算法C语言实现(大三操作系统实验)

为实现银行家算法，每个新进程在进入系统时它必须申明在运行过程中，可能需要的每种资源类型的最大单元数目，其数目不应超过系统所拥有的资源总量。当某一进程请求时，系统会自动判断请求量是否小于进程最大所需，同时判断请求量是否小于当前系统资源剩余量。若两项均满足，则系统试分配资源并执行安全性检查算法

YSRM

9119人浏览 · 2022-11-24 11:13:42

YSRM · 2022-11-24 11:13:42 发布

实验原理：

1.银行家算法

银行家算法最初级为银行系统设计，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。在OS设计中，用它来避免死锁。

为实现银行家算法，每个新进程在进入系统时它必须申明在运行过程中，可能需要的每种资源类型的最大单元数目，其数目不应超过系统所拥有的资源总量。当某一进程请求时，系统会自动判断请求量是否小于进程最大所需，同时判断请求量是否小于当前系统资源剩余量。若两项均满足，则系统试分配资源并执行安全性检查算法。

2.安全性检查算法

安全性检查算法用于检查系统进行资源分配后是否安全，若安全系统才可以执行此次分配；若不安全，则系统不执行此次分配。

安全性检查算法原理为：在系统试分配资源后，算法从现有进程列表寻找出一个可执行的进程进行执行，执行完成后回收进程占用资源；进而寻找下一个可执行进程。当进程需求量大于系统可分配量时，进程无法执行。当所有进程均可执行，则产生一个安全执行序列，系统资源分配成功。若进程无法全部执行，即无法找到一条安全序列，则说明系统在分配资源后会不安全，所以此次分配失败。

实验内容：

1.银行家算法

算法流程图

a.定义进程块JOBS

struct job
{
	int max[10];//进程所需最大资源
	int allocation[10];//进程已分配资源
	int need[10];//进程还需要分配的资源 
	int request[10];//进程请求资源 
	string name;//进程名 
};

max:定义了系统中该进程对各种资源的最大需求

allocation:定义了系统各类资源已分配给该进程的资源数

need:表示该进程尚需的各类资源数

request:表面该进程对各类资源的请求向量

name:各个进程的名字

b.进程以及资源的输入

	struct job jobs[50];
	int num,count,n,flag=0;//num为资源总类，count为进程总数，flag判断请求向量是否符合算法 
	int available[10],request[10];
	string rname;//请求进程名字 
	char source[10];//资源名称 
	cout<<"请输入总资源种类:";
	cin>>num;
	cout<<"请输入每种资源的名称:";
	for(int i=0;i<num;i++){
		cin>>source[i];
	}
	cout<<"请输入系统所拥有的资源总量:";
	for(int i=0;i<num;i++){
		cin>>available[i];
	}
	cout<<"请输入进程数:";
	cin>>count;
	cout<<"请输入每个进程的进程名:";
	for(int i=0;i<count;i++){
		cin>>jobs[i].name;
	}
	cout<<"请输入每个进程的最大需求量:";
	for(int i=0;i<count;i++){
		for(int j=0;j<num;j++){
			cin>>jobs[i].max[j];
		}
	}
	cout<<"请输入每个进程的已分配资源量:";
	for(int i=0;i<count;i++){
		for(int j=0;j<num;j++){
			cin>>jobs[i].allocation[j];
		}
	}
	//求每个进程的剩余需求量 
	for(int i=0;i<count;i++){
		for(int j=0;j<num;j++){
			jobs[i].need[j]=jobs[i].max[j]-jobs[i].allocation[j];
		}
	}
	cout<<"请输入需要请求资源的进程名:";
	cin>>rname;
	for(int i=0;i<count;i++){
		if(jobs[i].name==rname){
			n=i;
			break;
		}
	}
	cout<<n<<endl;
	cout<<"请输入需要请求资源的资源量:";
	for(int i=0;i<num;i++){
		cin>>jobs[n].request[i];
	}

运行起来是这样的：

c.银行家算法的构造

void yhj(struct job jobs[50],int n,int num,int available[10],int flag,int count,char source[10]){
	for(int i=0;i<num;i++){
		if((jobs[n].request[i]<=available[i]) && (jobs[n].request[i]<=jobs[n].need[i])){//如果请求向量既小于等于可利用资源，也小于等于该进程的需求量 
			flag=1;
		}
		else{
			flag=0;
			break;
		}
	}
	if(flag==1){//符合要求，允许分配 
		cout<<"可以尝试分配"<<endl;
		for(int i=0;i<num;i++){//相关数据进行更新 
			available[i]=available[i]-jobs[n].request[i];
			jobs[n].allocation[i]=jobs[n].allocation[i]+jobs[n].request[i];
			jobs[n].need[i]=jobs[n].need[i]-jobs[n].request[i];
		}	
		print(jobs,num,count,source,available);
	}
	else{
		cout<<"不可以分配"<<endl;
	}
}

第一个for循环是为了测试需要请求资源的进程是否满足每一个资源都小于等于它的对应资源的需求量以及系统可利用资源量。

如果都符合则flag=1，否则只要有一个资源不符合就会使得flag=0，并跳出for循环。

for循环结束后，如果flag=1，说明请求向量符合要求，则可以尝试分配，系统试探着把资源分配给进程jobs(n)，并修改对应的数据结构中的数值，并将资源分配表输出。

系统由于分配了资源，则它的可利用资源要减少

由于进程得到了资源，则对应已分配资源会增加

由于进程得到了资源，则对应的需求资源会减少

如果flag=0，则说明请求资源向量不满足，则不给予分配，相关数据结构不需要更新。

d.输出格式的实现

void print(struct job jobs[50],int num,int count,char source[10],int available[10]){
	cout<<"资源情况 Max            Allocation     Need           Available"<<endl;
	cout<<"进程名   ";
	for(int j=0;j<4;j++){
		for(int i=0;i<num;i++){
			cout << setiosflags(ios::left);//向左对齐 
			cout<<setw(5)<<source[i];//向左对齐5个空格 
		}
	}
	cout<<endl;
	for(int i=0;i<count;i++){
		cout << setiosflags(ios::left);
		cout<<setw(9)<<jobs[i].name;
		for(int j=0;j<num;j++){
			cout << setiosflags(ios::left);
			cout<<setw(5)<<jobs[i].max[j];
		}
		for(int j=0;j<num;j++){
			cout << setiosflags(ios::left);
			cout<<setw(5)<<jobs[i].allocation[j];
		}
		for(int j=0;j<num;j++){
			cout << setiosflags(ios::left);
			cout<<setw(5)<<jobs[i].need[j];
		}
		if(i==0){
			for(int j=0;j<num;j++){
				cout << setiosflags(ios::left);
				cout<<setw(5)<<available[j];
			}
		}
		cout<<endl;
	}
}

并没有什么难度，主要是输出后的结构是否美观，也就是数据对齐的问题。

setiosflags(ios::left)控制输出左对齐，setiosflags(ios::right)控制输出右对齐

setw(n)表示向左对齐，不足n个单位用空格填充直到n个单位，setr(n)表示向右对齐，使用方法类似setr(n)。

e.总代码

#include<stdio.h>
#include<iostream>
#include<iomanip>
#include<string.h>
using namespace std;
struct job
{
	int max[10];//进程所需最大资源
	int allocation[10];//进程已分配资源
	int need[10];//进程还需要分配的资源 
	int request[10];//进程请求资源 
	string name;//进程名 
};
void print(struct job jobs[50],int num,int count,char source[10],int available[10]){
	cout<<"资源情况 Max            Allocation     Need           Available"<<endl;
	cout<<"进程名   ";
	for(int j=0;j<4;j++){
		for(int i=0;i<num;i++){
			cout << setiosflags(ios::left);//向左对齐 
			cout<<setw(5)<<source[i];//向左对齐5个空格 
		}
	}
	cout<<endl;
	for(int i=0;i<count;i++){
		cout << setiosflags(ios::left);
		cout<<setw(9)<<jobs[i].name;
		for(int j=0;j<num;j++){
			cout << setiosflags(ios::left);
			cout<<setw(5)<<jobs[i].max[j];
		}
		for(int j=0;j<num;j++){
			cout << setiosflags(ios::left);
			cout<<setw(5)<<jobs[i].allocation[j];
		}
		for(int j=0;j<num;j++){
			cout << setiosflags(ios::left);
			cout<<setw(5)<<jobs[i].need[j];
		}
		if(i==0){
			for(int j=0;j<num;j++){
				cout << setiosflags(ios::left);
				cout<<setw(5)<<available[j];
			}
		}
		cout<<endl;
	}
}
void yhj(struct job jobs[50],int n,int num,int available[10],int flag,int count,char source[10]){
	for(int i=0;i<num;i++){
		if((jobs[n].request[i]<=available[i]) && (jobs[n].request[i]<=jobs[n].need[i])){//如果请求向量既小于等于可利用资源，也小于等于该进程的需求量 
			flag=1;
		}
		else{
			flag=0;
			break;
		}
	}
	if(flag==1){//符合要求，允许分配 
		cout<<"可以尝试分配"<<endl;
		for(int i=0;i<num;i++){//相关数据进行更新 
			available[i]=available[i]-jobs[n].request[i];
			jobs[n].allocation[i]=jobs[n].allocation[i]+jobs[n].request[i];
			jobs[n].need[i]=jobs[n].need[i]-jobs[n].request[i];
		}	
		print(jobs,num,count,source,available);
	}
	else{
		cout<<"不可以分配"<<endl;
	}
}

int main(){
	struct job jobs[50];
	int num,count,n,flag=0;//num为资源总类，count为进程总数，flag判断请求向量是否符合算法 
	int available[10],request[10];
	string rname;//请求进程名字 
	char source[10];//资源名称 
	cout<<"请输入总资源种类:";
	cin>>num;
	cout<<"请输入每种资源的名称:";
	for(int i=0;i<num;i++){
		cin>>source[i];
	}
	cout<<"请输入系统所拥有的资源总量:";
	for(int i=0;i<num;i++){
		cin>>available[i];
	}
	cout<<"请输入进程数:";
	cin>>count;
	cout<<"请输入每个进程的进程名:";
	for(int i=0;i<count;i++){
		cin>>jobs[i].name;
	}
	cout<<"请输入每个进程的最大需求量:";
	for(int i=0;i<count;i++){
		for(int j=0;j<num;j++){
			cin>>jobs[i].max[j];
		}
	}
	cout<<"请输入每个进程的已分配资源量:";
	for(int i=0;i<count;i++){
		for(int j=0;j<num;j++){
			cin>>jobs[i].allocation[j];
		}
	}
	//求每个进程的剩余需求量 
	for(int i=0;i<count;i++){
		for(int j=0;j<num;j++){
			jobs[i].need[j]=jobs[i].max[j]-jobs[i].allocation[j];
		}
	}
	cout<<"请输入需要请求资源的进程名:";
	cin>>rname;
	for(int i=0;i<count;i++){
		if(jobs[i].name==rname){
			n=i;
			break;
		}
	}
	cout<<n<<endl;
	cout<<"请输入需要请求资源的资源量:";
	for(int i=0;i<num;i++){
		cin>>jobs[n].request[i];
	} 
	cout<<"分配前的表"<<endl;
	print(jobs,num,count,source,available);
	yhj(jobs,n,num,available,flag,count,source);
	return 0;
}

f.运行结果

此时银行家算法已经结束？不不不，上面说了只是尝试分配，并不是真的会给它分配，能不能真正分配得看尝试分配后的资源是否安全，这就需要安全性算法。

2.安全性算法

安全性算法是对上面银行家算法的延申。

a.定义进程块

struct job
{
	int max[10];//进程所需最大资源
	int allocation[10];//进程已分配资源
	int need[10];//进程还需要分配的资源 
	int request[10];//进程请求资源 
	string name;//进程名
	int finish=0;//完成状态 
	int allocation1[10]={0};//work+allocation
	int work[10]={0};//工作向量 
};

比银行家算法的数据结构多了finish，allocation1,work.

finish:等于0时，表示系统没有足够的资源分配给进程，等于1，表明有，初始值全为0

work:表示系统可提供给进程继续运行所需的歌类资源数目

allocation1:work的更新，work+allocation

b.银行家算法的修改

void yhj(struct job jobs[50],int n,int num,int available[10],int flag,int count,char source[10],string xulie[10]){
	for(int i=0;i<num;i++){
		if((jobs[n].request[i]<=available[i]) && (jobs[n].request[i]<=jobs[n].need[i])){//如果请求向量既小于等于可利用资源，也小于等于该进程的需求量 
			flag=1;
		}
		else{
			flag=0;
			break;
		}
	}
	if(flag==1){//符合要求，允许分配 
		cout<<"可以尝试分配"<<endl;
		for(int i=0;i<num;i++){//相关数据进行更新 
			available[i]=available[i]-jobs[n].request[i];
			jobs[n].allocation[i]=jobs[n].allocation[i]+jobs[n].request[i];
			jobs[n].need[i]=jobs[n].need[i]-jobs[n].request[i];
			jobs[n].work[i]=available[i];
		}	
		print(jobs,num,count,source,available);
		safe(jobs,n,num,available,flag,count,source,xulie);
	}
	else{
		cout<<"不可以分配"<<endl;
	}
}

修改了两处地方，第一处是对jobs[n]的work量进行了修改，即工作向量等于可利用资源向量

第二处是使用safe函数，即安全性算法

c.安全性算法

void safe(struct job jobs[50],int n,int num,int available[10],int flag,int count ,char source[10],string xulie[10]){
	int flag1=0;//等于1时表明该进程可以分配资源，安全
	int index=0;//可分配资源进程的索引值，也表明可分配资源进程的数目
	for(int i=0;i<num;i++){
		jobs[n].allocation1[i]=jobs[n].allocation[i]+ jobs[n].work[i];
	}
	xulie[index]=jobs[n].name;
	jobs[n].finish=1;
	int a=n;
	for(int i=0;i<count;i++){
		if(jobs[i].finish!=1){
			flag1=0;
			for(int j=0;j<num;j++){
				if(jobs[i].need[j]<=jobs[a].allocation1[j]){
					flag1=1;
				}
				else{
					flag1=0;
					break;
				}
			}
			if(flag1==1){
				index++;
				xulie[index]=jobs[i].name;
				for(int k=0;k<num;k++){
					jobs[i].work[k]=jobs[a].allocation1[k];
					jobs[i].finish=1;
					jobs[i].allocation1[k]=jobs[i].work[k]+jobs[i].allocation[k];
				}
				a=i;
				i=-1;
			}
		}
	}
	if((count-index)!=1){
		cout<<"不安全"<<endl; 
	}
	else{
		cout<<"安全序列为:";
		for(int i=0;i<count;i++){
			cout<<xulie[i]<<" ";
		}
		cout<<endl;
		print1(jobs,num,count,source,available);
	}
}

采用顺序索引的方式，当找到没有被分配资源的进程时，判断其是否符合work>need，如果符合，则更新其数据结构，a置为i，表明下一个需要比较的a的allocation1，并将其i置为-1，表明循环重新开始。如果for循环结束，要么是因为所有进程资源都被分配，要么是因为剩下未被分配的进程都不能被分配。

如果剩下未被分配的进程都不能被分配，则进入if语句，输出"不安全"，否则表明这个是安全的，输出安全序列，并输出安全性检查表。

d.另一种输出函数

void print1(struct job jobs[50],int num,int count,char source[10],int available[10]){
	cout<<"资源情况 Work           Need           Allocation     Work+Available Finish"<<endl;
	cout<<"进程名   ";
	for(int j=0;j<4;j++){
		for(int i=0;i<num;i++){
			cout << setiosflags(ios::left);//向左对齐 
			cout<<setw(5)<<source[i];//向左对齐5个空格 
		}
	}
	cout<<endl;
	for(int i=0;i<count;i++){
		cout << setiosflags(ios::left);
		cout<<setw(9)<<jobs[i].name;
		for(int j=0;j<num;j++){
			cout << setiosflags(ios::left);
			cout<<setw(5)<<jobs[i].work[j];
		}
		for(int j=0;j<num;j++){
			cout << setiosflags(ios::left);
			cout<<setw(5)<<jobs[i].need[j];
		}
		for(int j=0;j<num;j++){
			cout << setiosflags(ios::left);
			cout<<setw(5)<<jobs[i].allocation[j];
		}
		for(int j=0;j<num;j++){
			cout << setiosflags(ios::left);
			cout<<setw(5)<<jobs[i].allocation1[j];
		}
		cout << setiosflags(ios::left);
		cout<<setw(5)<<"true";
		cout<<endl;
	}
}

e.总代码

#include<stdio.h>
#include<iostream>
#include<iomanip>
#include<string.h>
using namespace std;
struct job
{
	int max[10];//进程所需最大资源
	int allocation[10];//进程已分配资源
	int need[10];//进程还需要分配的资源 
	int request[10];//进程请求资源 
	string name;//进程名
	int finish=0;//完成状态 
	int allocation1[10]={0};//work+allocation
	int work[10]={0};//工作向量 
};
void print(struct job jobs[50],int num,int count,char source[10],int available[10]){
	cout<<"资源情况 Max            Allocation     Need           Available"<<endl;
	cout<<"进程名   ";
	for(int j=0;j<4;j++){
		for(int i=0;i<num;i++){
			cout << setiosflags(ios::left);//向左对齐 
			cout<<setw(5)<<source[i];//向左对齐5个空格 
		}
	}
	cout<<endl;
	for(int i=0;i<count;i++){
		cout << setiosflags(ios::left);
		cout<<setw(9)<<jobs[i].name;
		for(int j=0;j<num;j++){
			cout << setiosflags(ios::left);
			cout<<setw(5)<<jobs[i].max[j];
		}
		for(int j=0;j<num;j++){
			cout << setiosflags(ios::left);
			cout<<setw(5)<<jobs[i].allocation[j];
		}
		for(int j=0;j<num;j++){
			cout << setiosflags(ios::left);
			cout<<setw(5)<<jobs[i].need[j];
		}
		if(i==0){
			for(int j=0;j<num;j++){
				cout << setiosflags(ios::left);
				cout<<setw(5)<<available[j];
			}
		}
		cout<<endl;
	}
}
void print1(struct job jobs[50],int num,int count,char source[10],int available[10]){
	cout<<"资源情况 Work           Need           Allocation     Work+Available Finish"<<endl;
	cout<<"进程名   ";
	for(int j=0;j<4;j++){
		for(int i=0;i<num;i++){
			cout << setiosflags(ios::left);//向左对齐 
			cout<<setw(5)<<source[i];//向左对齐5个空格 
		}
	}
	cout<<endl;
	for(int i=0;i<count;i++){
		cout << setiosflags(ios::left);
		cout<<setw(9)<<jobs[i].name;
		for(int j=0;j<num;j++){
			cout << setiosflags(ios::left);
			cout<<setw(5)<<jobs[i].work[j];
		}
		for(int j=0;j<num;j++){
			cout << setiosflags(ios::left);
			cout<<setw(5)<<jobs[i].need[j];
		}
		for(int j=0;j<num;j++){
			cout << setiosflags(ios::left);
			cout<<setw(5)<<jobs[i].allocation[j];
		}
		for(int j=0;j<num;j++){
			cout << setiosflags(ios::left);
			cout<<setw(5)<<jobs[i].allocation1[j];
		}
		cout << setiosflags(ios::left);
		cout<<setw(5)<<"true";
		cout<<endl;
	}
}
void safe(struct job jobs[50],int n,int num,int available[10],int flag,int count ,char source[10],string xulie[10]){
	int flag1=0;
	int index=0;
	for(int i=0;i<num;i++){
		jobs[n].allocation1[i]=jobs[n].allocation[i]+ jobs[n].work[i];
	}
	xulie[index]=jobs[n].name;
	jobs[n].finish=1;
	int a=n;
	for(int i=0;i<count;i++){
		if(jobs[i].finish!=1){
			flag1=0;
			for(int j=0;j<num;j++){
				if(jobs[i].need[j]<=jobs[a].allocation1[j]){
					flag1=1;
				}
				else{
					flag1=0;
					break;
				}
			}
			if(flag1==1){
				index++;
				xulie[index]=jobs[i].name;
				for(int k=0;k<num;k++){
					jobs[i].work[k]=jobs[a].allocation1[k];
					jobs[i].finish=1;
					jobs[i].allocation1[k]=jobs[i].work[k]+jobs[i].allocation[k];
				}
				a=i;
				i=-1;
			}
		}
	}
	if((count-index)!=1){
		cout<<"不安全"<<endl; 
	}
	else{
		cout<<"安全序列为:";
		for(int i=0;i<count;i++){
			cout<<xulie[i]<<" ";
		}
		cout<<endl;
		print1(jobs,num,count,source,available);
	}
}
 
void yhj(struct job jobs[50],int n,int num,int available[10],int flag,int count,char source[10],string xulie[10]){
	for(int i=0;i<num;i++){
		if((jobs[n].request[i]<=available[i]) && (jobs[n].request[i]<=jobs[n].need[i])){//如果请求向量既小于等于可利用资源，也小于等于该进程的需求量 
			flag=1;
		}
		else{
			flag=0;
			break;
		}
	}
	if(flag==1){//符合要求，允许分配 
		cout<<"可以尝试分配"<<endl;
		for(int i=0;i<num;i++){//相关数据进行更新 
			available[i]=available[i]-jobs[n].request[i];
			jobs[n].allocation[i]=jobs[n].allocation[i]+jobs[n].request[i];
			jobs[n].need[i]=jobs[n].need[i]-jobs[n].request[i];
			jobs[n].work[i]=available[i];
		}	
		print(jobs,num,count,source,available);
		safe(jobs,n,num,available,flag,count,source,xulie);
	}
	else{
		cout<<"不可以分配"<<endl;
	}
}

int main(){
	struct job jobs[50];
	string xulie[10];
	int num,count,n,flag=0;//num为资源总类，count为进程总数，flag判断请求向量是否符合算法 
	int available[10],request[10];
	string rname;//请求进程名字 
	char source[10];//资源名称 
	cout<<"请输入总资源种类:";
	cin>>num;
	cout<<"请输入每种资源的名称:";
	for(int i=0;i<num;i++){
		cin>>source[i];
	}
	cout<<"请输入系统所拥有的资源总量:";
	for(int i=0;i<num;i++){
		cin>>available[i];
	}
	cout<<"请输入进程数:";
	cin>>count;
	cout<<"请输入每个进程的进程名:";
	for(int i=0;i<count;i++){
		cin>>jobs[i].name;
	}
	cout<<"请输入每个进程的最大需求量:";
	for(int i=0;i<count;i++){
		for(int j=0;j<num;j++){
			cin>>jobs[i].max[j];
		}
	}
	cout<<"请输入每个进程的已分配资源量:";
	for(int i=0;i<count;i++){
		for(int j=0;j<num;j++){
			cin>>jobs[i].allocation[j];
		}
	}
	//求每个进程的剩余需求量 
	for(int i=0;i<count;i++){
		for(int j=0;j<num;j++){
			jobs[i].need[j]=jobs[i].max[j]-jobs[i].allocation[j];
		}
	}
	cout<<"请输入需要请求资源的进程名:";
	cin>>rname;
	for(int i=0;i<count;i++){
		if(jobs[i].name==rname){
			n=i;
			break;
		}
	}
	cout<<n<<endl;
	cout<<"请输入需要请求资源的资源量:";
	for(int i=0;i<num;i++){
		cin>>jobs[n].request[i];
	} 
	cout<<"分配前的表"<<endl;
	print(jobs,num,count,source,available);
	yhj(jobs,n,num,available,flag,count,source,xulie);
	return 0;
}

f.运行结果