操作系统实习-银行家算法（C语言）-USB迷|专注于互联网分享

文章目录

- 设计目的
- 设计内容
- 设计思路
- 算法流程图
- 测试数据
- 程序结构
- 数据结构
- 实现代码
- 测试结果

设计目的

了解死锁产生的条件和原因，并采用银行家算法有效地避免死锁的发生，进一步理解银行家算法。

设计内容

完成银行家算法的模拟实现：设计有m个进程共享n个系统资源的系统，进程可动态的申请和释放资源。系统按各进程的申请动态的分配资源时，采用银行家算法有效地避免死锁的发生。

设计思路

对进程的资源请求进行合法性检查；若请求合法，则进行试分配。试分配后，调用安全性检查算法进行安全性检查。若安全，则满足该进程请求，分配资源；若不安全，则拒绝该进程申请，不分配资源，并恢复系统试分配前的资源状态。

算法流程图

测试数据

系统有5个进程（P0,P1,P2,P3,P4）和4类资源（A，B，C，D），在T0时刻的资源分配情况如下表所示：

Process	Max	Allocation	Need	Available
P0	0 0 4 4	0 0 3 2	0 0 1 2	1 6 2 2
P1	2 7 5 0	1 0 0 0	1 7 5 0	上面为系统总的可用资源
P2	3 6 10 10	1 3 5 4	2 3 5 6
P3	0 9 8 4	0 3 3 2	0 6 5 2
P4	0 6 6 10	0 0 1 4	0 6 5 6

试问：

该状态是否安全？
如果进程P2提出请求Request2（1，2，2，2）后，系统能否将资源分配给它？

程序结构

（1）最大需求量Max()
输入各进程对各类资源的最大需求量
（2）资源需求量Need()
输入各进程运行完成仍需要的各类资源量
（3）资源分配Allocation()
根据各进程对资源的最大需求量以及资源需求量自动计算已分配的资源量
（4）系统可用资源数Available()
输入系统的可用资源数
（5）安全性检查算法Safe()
① 设置两个向量：
工作向量Work：表示系统可提供给进程继续运行所需的各类资源数目，在执行安全性算法开始时，令Work= Available。
结束向量Finish：表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]=false；当有足够的资源分配给进程时，再令Finish[i]=TRUE。
② 在进程集合中查找符合以下条件的进程：
条件1：Finish[i]=FALSE
条件2：Need[i][j]<=Work[j]
若找到，则执行步骤③；否则，执行步骤④
③ 当进程获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Work[j]=Work[j]+ Allocation[i][j]
Finish[i]=true
跳至 ②
④若所有进程的Finish[i]=true都满足，则表示已找到安全序列，系统处于安全状态，试分配成功；否则，系统处于不安全状态，不予分配。
（6）资源请求量Requst()
输入进程i在某一时刻对系统发出资源的请求量
（7）银行家算法Bank()
进程i发出请求申请k个j资源，Request[i][j]=k
① 检查申请量是否小于等于需求量：
Request[i][j]<=Need[i][j],若条件不符重新输入，不允许申请大于需求量。
②检查申请量是否小于等于系统中的可利用资源量：
Request[i][j]<=Available[j]，若条件不符就申请失败，阻塞该进程，用goto语句跳转至重新申请资源。
③若以上两个条件都满足，则系统试探着将资源分配给申请的进程，并修改下面数据结构中的数值：
Available[j]=Available[j]- Request[i][j]；
Allocation[i][j]= Allocation[i][j]+Request[i][j]；
Need[i][j]= Need[i][j]- Request [i][j]；
④试分配后，执行安全性检查，调用Safe()函数检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程；否则本次试探分配作废，恢复原来的资源分配状态，让该进程等待。
⑤ 用while循环实现输入字符Y/y判断是否继续请求资源分配。

数据结构

int *Available;		//可利用资源向量
int **Max;			//最大需求矩阵
int **Allocation;	//分配矩阵
int **Need;			//需求矩阵
int **Requst;		//申请各类资源数量
int *Work;			//工作向量
int *Finish;		//结束向量

实现代码

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
int i,j,k,l;
int flag;
char c;
typedef struct Banker{
	int *Available;		//可利用资源向量
	int **Max;			//最大需求矩阵
	int **Allocation;	//分配矩阵
	int **Need;			//需求矩阵
	int **Requst;		//申请各类资源数量
	int *Work;			//工作向量
	int *Finish;		//结束向量
}Process;
int Bank(Process *process,int m,int n);
int Safe(Process *process,int m,int n);
void Max(Process *process,int m,int n);
void Need(Process *process,int m,int n);
void Allocation(Process *process,int m,int n);
void Available(Process *process,int n);
int Requst(Process *process,int m,int n);

int Bank(Process *process,int m,int n)
{
	do	//资源请求失败或者系统不安全时flag=0,并重新输入。
	{
		if((flag=Requst(process,m,n))==1)
		{
			printf("请求并试分配成功。\n");
			for(j=0;j<n;j++)
			{
				(process->Available)[j]-=(process->Requst)[l][j];
				(process->Allocation)[l][j]+=(process->Requst)[l][j];
				(process->Need)[l][j]-=(process->Requst)[l][j];
			}
		}
		if(flag==1&&(flag=Safe(process,m,n))==0)//系统不安全，撤销资源试分配
		{
			printf("撤销资源试分配。\n");
			for(j=0;j<n;j++)
				{
					(process->Available)[j]+=(process->Requst)[l][j];
					(process->Allocation)[l][j]-=(process->Requst)[l][j];
					(process->Need)[l][j]+=(process->Requst)[l][j];	
				}
		}
	}while(flag==0);
	if(flag==1) 
	{
		printf("分配成功。\n");
		printf("是否继续请求资源分配？输入Y继续，输入y结束：\n");
		getchar();
		c=getchar();
		if(c=='Y')return 1;
		if(c=='y')return 0;
	}
}
int Safe(Process *process,int m,int n)
{
	(process->Work)=(int *)malloc(sizeof(int)*n);
	for(j=0;j<n;j++)
		(process->Work)[j]=(process->Available)[j];//系统可提供给进程继续运行所需的各类资源数目
	
	(process->Finish)=(int *)malloc(sizeof(int)*m);
	for(i=0;i<m;i++)
		(process->Finish)[i]=FALSE;
	k=m;
	int flag1;				//当有不符合条件的资源时标记为0
	int flag2;				//当所有进程不都分配成功时标记为0
	int *s=(int *)malloc(sizeof(int)*m);//记录安全序列
	do
	{
		for(i=0;i<m;i++)		//一轮分配
			if((process->Finish)[i]==FALSE)
			{
				flag1=1;
				for(j=0;j<n;j++)
					if((process->Need)[i][j]>(process->Work)[j])
						flag1=0;//有不符合条件的资源
				if(flag1==1)
				{
					for(j=0;j<n;j++)
						*((process->Work)+j)+=*((process->Allocation)[i]+j);
					(process->Finish)[i]=TRUE;
					*s=i;
					s++;
				}
			}
		k--;//每完成一次进程分配时k减1,以便跳出循环和防止死循环
	}while(k>0);
	flag2=1;
	for(i=0;i<m;i++)	//判断是否所有进程都完成
	{
		if((process->Finish)[i]==FALSE)
		{
			flag2=0;
			break;
		}
	}
	if(flag2==0)
	{
		printf("当前状态不安全！\n");
		return 0;
	}
	else
	{
		printf("当前状态安全！\n");
		for(i=0;i<m;i++)s--;
		printf("安全序列为：");
		for(i=0;i<m;i++)
			printf("P%d ",s[i]);
		printf("\n");
		free(s);
		return 1;
	}
}
void Max(Process *process,int m,int n)
{
	process->Max=(int **)malloc(sizeof(int *)*m);//分配m个指针，用来指向数组的首地址
	for(i=0;i<m;i++)
		(process->Max)[i]=(int *)malloc(sizeof(int)*n);//为每个数组分配n个指针元素
	printf("输入各进程对各类资源的最大需求量：\n");
	for(i=0;i<m;i++)
	{
		printf("P%d:\n",i);
		for(j=0;j<n;j++)
		{
			scanf("%d",((process->Max)[i]+j));
		}
	}
}
void Need(Process *process,int m,int n)
{
	process->Need=(int **)malloc(sizeof(int *)*m);
	for(i=0;i<m;i++)
		(process->Need)[i]=(int *)malloc(sizeof(int)*n);
	printf("输入各进程对各类资源的需求量：\n");
	for(i=0;i<m;i++)
	{
		printf("P%d:\n",i);
		for(j=0;j<n;j++)
		{
			scanf("%d",((process->Need)[i]+j));
		}
	}
}
void Allocation(Process *process,int m,int n)
{
	process->Allocation=(int **)malloc(sizeof(int *)*m);
	for(i=0;i<m;i++)
		(process->Allocation)[i]=(int *)malloc(sizeof(int)*n);
	for(i=0;i<m;i++)
		for(j=0;j<n;j++)
			*((process->Allocation)[i]+j)=(*((process->Max)[i]+j))-(*((process->Need)[i]+j));
}
void Available(Process *process,int n)
{
	process->Available=(int *)malloc(sizeof(int)*n);
	printf("输入系统可用资源数：\n");
	for(i=0;i<n;i++)
		scanf("%d",&(process->Available)[i]);
}
int Requst(Process *process,int m,int n)
{
	process->Requst=(int **)malloc(sizeof(int *)*m);
	for(i=0;i<m;i++)
		(process->Requst)[i]=(int *)malloc(sizeof(int)*n);
	printf("输入进程名及其资源请求量：\n");
	scanf("%d",&i);
	l=i;
	for(j=0;j<n;j++)
		scanf("%d",(process->Requst)[i]+j);
	int flag1=1;//申请量大于需求量时标记为0
	int flag2=1;//申请量大于可利用资源量时标记为0
	for(j=0;j<n;j++)//检查申请量是否小于等于需求量
		if((process->Requst)[i][j]>(process->Need)[i][j])
			flag1=0;
	if(flag1==0)
	{
		printf("不允许申请量大于需求量!请重新输入。\n");
		return 0;
	}
	if(flag1==1)
	{
		for(j=0;j<n;j++)//检查申请量是否小于等于系统中的可利用资源量
			if((process->Requst)[i][j]>(process->Available)[j])
				flag2=0;
		if(flag2==0)
		{
			printf("不允许申请量大于可利用资源量!请重新输入。\n");
			return 0;
		}
		else return 1;
	}
}
int main()
{	
	Process process;
	int m,n;
	printf("请输入进程数：");
	scanf("%d",&m);
	printf("请输入资源种类数：");
	scanf("%d",&n);
	Max(&process,m,n);
	Need(&process,m,n);
	Allocation(&process,m,n);
	Available(&process,n);
	Safe(&process,m,n);
	while(Bank(&process,m,n));
	return 0;
}

测试结果

参考文献

[1]姜学锋.C程序设计[M].北京：清华大学出版社，2012.3
[2]胡元义.操作系统原理[M].北京：电子工业出版社，2018.8

文章目录

- 设计目的
- 设计内容
- 设计思路
- 算法流程图
- 测试数据
- 程序结构
- 数据结构
- 实现代码
- 测试结果

设计目的

了解死锁产生的条件和原因，并采用银行家算法有效地避免死锁的发生，进一步理解银行家算法。

设计内容

完成银行家算法的模拟实现：设计有m个进程共享n个系统资源的系统，进程可动态的申请和释放资源。系统按各进程的申请动态的分配资源时，采用银行家算法有效地避免死锁的发生。

设计思路

对进程的资源请求进行合法性检查；若请求合法，则进行试分配。试分配后，调用安全性检查算法进行安全性检查。若安全，则满足该进程请求，分配资源；若不安全，则拒绝该进程申请，不分配资源，并恢复系统试分配前的资源状态。

算法流程图

测试数据

系统有5个进程（P0,P1,P2,P3,P4）和4类资源（A，B，C，D），在T0时刻的资源分配情况如下表所示：

Process	Max	Allocation	Need	Available
P0	0 0 4 4	0 0 3 2	0 0 1 2	1 6 2 2
P1	2 7 5 0	1 0 0 0	1 7 5 0	上面为系统总的可用资源
P2	3 6 10 10	1 3 5 4	2 3 5 6
P3	0 9 8 4	0 3 3 2	0 6 5 2
P4	0 6 6 10	0 0 1 4	0 6 5 6

试问：

该状态是否安全？
如果进程P2提出请求Request2（1，2，2，2）后，系统能否将资源分配给它？

程序结构

（1）最大需求量Max()
输入各进程对各类资源的最大需求量
（2）资源需求量Need()
输入各进程运行完成仍需要的各类资源量
（3）资源分配Allocation()
根据各进程对资源的最大需求量以及资源需求量自动计算已分配的资源量
（4）系统可用资源数Available()
输入系统的可用资源数
（5）安全性检查算法Safe()
① 设置两个向量：
工作向量Work：表示系统可提供给进程继续运行所需的各类资源数目，在执行安全性算法开始时，令Work= Available。
结束向量Finish：表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]=false；当有足够的资源分配给进程时，再令Finish[i]=TRUE。
② 在进程集合中查找符合以下条件的进程：
条件1：Finish[i]=FALSE
条件2：Need[i][j]<=Work[j]
若找到，则执行步骤③；否则，执行步骤④
③ 当进程获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Work[j]=Work[j]+ Allocation[i][j]
Finish[i]=true
跳至 ②
④若所有进程的Finish[i]=true都满足，则表示已找到安全序列，系统处于安全状态，试分配成功；否则，系统处于不安全状态，不予分配。
（6）资源请求量Requst()
输入进程i在某一时刻对系统发出资源的请求量
（7）银行家算法Bank()
进程i发出请求申请k个j资源，Request[i][j]=k
① 检查申请量是否小于等于需求量：
Request[i][j]<=Need[i][j],若条件不符重新输入，不允许申请大于需求量。
②检查申请量是否小于等于系统中的可利用资源量：
Request[i][j]<=Available[j]，若条件不符就申请失败，阻塞该进程，用goto语句跳转至重新申请资源。
③若以上两个条件都满足，则系统试探着将资源分配给申请的进程，并修改下面数据结构中的数值：
Available[j]=Available[j]- Request[i][j]；
Allocation[i][j]= Allocation[i][j]+Request[i][j]；
Need[i][j]= Need[i][j]- Request [i][j]；
④试分配后，执行安全性检查，调用Safe()函数检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程；否则本次试探分配作废，恢复原来的资源分配状态，让该进程等待。
⑤ 用while循环实现输入字符Y/y判断是否继续请求资源分配。

数据结构

int *Available;		//可利用资源向量
int **Max;			//最大需求矩阵
int **Allocation;	//分配矩阵
int **Need;			//需求矩阵
int **Requst;		//申请各类资源数量
int *Work;			//工作向量
int *Finish;		//结束向量

实现代码

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
int i,j,k,l;
int flag;
char c;
typedef struct Banker{
	int *Available;		//可利用资源向量
	int **Max;			//最大需求矩阵
	int **Allocation;	//分配矩阵
	int **Need;			//需求矩阵
	int **Requst;		//申请各类资源数量
	int *Work;			//工作向量
	int *Finish;		//结束向量
}Process;
int Bank(Process *process,int m,int n);
int Safe(Process *process,int m,int n);
void Max(Process *process,int m,int n);
void Need(Process *process,int m,int n);
void Allocation(Process *process,int m,int n);
void Available(Process *process,int n);
int Requst(Process *process,int m,int n);

int Bank(Process *process,int m,int n)
{
	do	//资源请求失败或者系统不安全时flag=0,并重新输入。
	{
		if((flag=Requst(process,m,n))==1)
		{
			printf("请求并试分配成功。\n");
			for(j=0;j<n;j++)
			{
				(process->Available)[j]-=(process->Requst)[l][j];
				(process->Allocation)[l][j]+=(process->Requst)[l][j];
				(process->Need)[l][j]-=(process->Requst)[l][j];
			}
		}
		if(flag==1&&(flag=Safe(process,m,n))==0)//系统不安全，撤销资源试分配
		{
			printf("撤销资源试分配。\n");
			for(j=0;j<n;j++)
				{
					(process->Available)[j]+=(process->Requst)[l][j];
					(process->Allocation)[l][j]-=(process->Requst)[l][j];
					(process->Need)[l][j]+=(process->Requst)[l][j];	
				}
		}
	}while(flag==0);
	if(flag==1) 
	{
		printf("分配成功。\n");
		printf("是否继续请求资源分配？输入Y继续，输入y结束：\n");
		getchar();
		c=getchar();
		if(c=='Y')return 1;
		if(c=='y')return 0;
	}
}
int Safe(Process *process,int m,int n)
{
	(process->Work)=(int *)malloc(sizeof(int)*n);
	for(j=0;j<n;j++)
		(process->Work)[j]=(process->Available)[j];//系统可提供给进程继续运行所需的各类资源数目
	
	(process->Finish)=(int *)malloc(sizeof(int)*m);
	for(i=0;i<m;i++)
		(process->Finish)[i]=FALSE;
	k=m;
	int flag1;				//当有不符合条件的资源时标记为0
	int flag2;				//当所有进程不都分配成功时标记为0
	int *s=(int *)malloc(sizeof(int)*m);//记录安全序列
	do
	{
		for(i=0;i<m;i++)		//一轮分配
			if((process->Finish)[i]==FALSE)
			{
				flag1=1;
				for(j=0;j<n;j++)
					if((process->Need)[i][j]>(process->Work)[j])
						flag1=0;//有不符合条件的资源
				if(flag1==1)
				{
					for(j=0;j<n;j++)
						*((process->Work)+j)+=*((process->Allocation)[i]+j);
					(process->Finish)[i]=TRUE;
					*s=i;
					s++;
				}
			}
		k--;//每完成一次进程分配时k减1,以便跳出循环和防止死循环
	}while(k>0);
	flag2=1;
	for(i=0;i<m;i++)	//判断是否所有进程都完成
	{
		if((process->Finish)[i]==FALSE)
		{
			flag2=0;
			break;
		}
	}
	if(flag2==0)
	{
		printf("当前状态不安全！\n");
		return 0;
	}
	else
	{
		printf("当前状态安全！\n");
		for(i=0;i<m;i++)s--;
		printf("安全序列为：");
		for(i=0;i<m;i++)
			printf("P%d ",s[i]);
		printf("\n");
		free(s);
		return 1;
	}
}
void Max(Process *process,int m,int n)
{
	process->Max=(int **)malloc(sizeof(int *)*m);//分配m个指针，用来指向数组的首地址
	for(i=0;i<m;i++)
		(process->Max)[i]=(int *)malloc(sizeof(int)*n);//为每个数组分配n个指针元素
	printf("输入各进程对各类资源的最大需求量：\n");
	for(i=0;i<m;i++)
	{
		printf("P%d:\n",i);
		for(j=0;j<n;j++)
		{
			scanf("%d",((process->Max)[i]+j));
		}
	}
}
void Need(Process *process,int m,int n)
{
	process->Need=(int **)malloc(sizeof(int *)*m);
	for(i=0;i<m;i++)
		(process->Need)[i]=(int *)malloc(sizeof(int)*n);
	printf("输入各进程对各类资源的需求量：\n");
	for(i=0;i<m;i++)
	{
		printf("P%d:\n",i);
		for(j=0;j<n;j++)
		{
			scanf("%d",((process->Need)[i]+j));
		}
	}
}
void Allocation(Process *process,int m,int n)
{
	process->Allocation=(int **)malloc(sizeof(int *)*m);
	for(i=0;i<m;i++)
		(process->Allocation)[i]=(int *)malloc(sizeof(int)*n);
	for(i=0;i<m;i++)
		for(j=0;j<n;j++)
			*((process->Allocation)[i]+j)=(*((process->Max)[i]+j))-(*((process->Need)[i]+j));
}
void Available(Process *process,int n)
{
	process->Available=(int *)malloc(sizeof(int)*n);
	printf("输入系统可用资源数：\n");
	for(i=0;i<n;i++)
		scanf("%d",&(process->Available)[i]);
}
int Requst(Process *process,int m,int n)
{
	process->Requst=(int **)malloc(sizeof(int *)*m);
	for(i=0;i<m;i++)
		(process->Requst)[i]=(int *)malloc(sizeof(int)*n);
	printf("输入进程名及其资源请求量：\n");
	scanf("%d",&i);
	l=i;
	for(j=0;j<n;j++)
		scanf("%d",(process->Requst)[i]+j);
	int flag1=1;//申请量大于需求量时标记为0
	int flag2=1;//申请量大于可利用资源量时标记为0
	for(j=0;j<n;j++)//检查申请量是否小于等于需求量
		if((process->Requst)[i][j]>(process->Need)[i][j])
			flag1=0;
	if(flag1==0)
	{
		printf("不允许申请量大于需求量!请重新输入。\n");
		return 0;
	}
	if(flag1==1)
	{
		for(j=0;j<n;j++)//检查申请量是否小于等于系统中的可利用资源量
			if((process->Requst)[i][j]>(process->Available)[j])
				flag2=0;
		if(flag2==0)
		{
			printf("不允许申请量大于可利用资源量!请重新输入。\n");
			return 0;
		}
		else return 1;
	}
}
int main()
{	
	Process process;
	int m,n;
	printf("请输入进程数：");
	scanf("%d",&m);
	printf("请输入资源种类数：");
	scanf("%d",&n);
	Max(&process,m,n);
	Need(&process,m,n);
	Allocation(&process,m,n);
	Available(&process,n);
	Safe(&process,m,n);
	while(Bank(&process,m,n));
	return 0;
}

测试结果

参考文献

[1]姜学锋.C程序设计[M].北京：清华大学出版社，2012.3
[2]胡元义.操作系统原理[M].北京：电子工业出版社，2018.8

USB迷 | 专注于互联网分享

操作系统实习-银行家算法（C语言）

文章目录

设计目的

设计内容

设计思路

算法流程图

测试数据

程序结构

数据结构

实现代码

测试结果

文章目录

设计目的

设计内容

设计思路

算法流程图

测试数据

程序结构

数据结构

实现代码

测试结果

与本文相关的文章

评论列表 (0)