C语言银行家算法

C语言银行家算法算法简介银行家算法(Banker’sAlgorithm)是一个避免死锁(Deadlock)的著名算法,是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础,判断并保证系统的安全运行。算法目的为了了解系统的资源分配情况,假定系统的任何一种资源在任意时刻只能被一个进程使用,任何进程已经占用的资源只能由进程自己释放,而不能由其他进…

大家好,又见面了,我是你们的朋友全栈君。

算法简介
银行家算法(Banker’s Algorithm)是一个避免死锁(Deadlock)的著名算法,是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础,判断并保证系统的安全运行。

算法目的
为了了解系统的资源分配情况,假定系统的任何一种资源在任意时刻只能被一个进程使用,任何进程已经占用的资源只能由进程自己释放,而不能由其他进程抢占,当进程申请的资源不能满足时,必须等待。因此只要资源分配算法能保证进程的资源请求,且不出现循环等待,则系统不会出现死锁。

算法原理
在避免死锁的方法中,所施加的限制条件较弱,有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态,只要能使系统始终都处于安全状态,便可以避免发生死锁。

银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。

设进程cusneed提出请求REQUEST [i],则银行家算法按如下规则进行判断。

(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i],则转(2);否则,出错。
(2)如果REQUEST [cusneed] [i]<= AVAILABLE[i],则转(3);否则,等待。
(3)系统试探分配资源,修改相关数据:
AVAILABLE[i]-=REQUEST[cusneed][i];

ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];

NEED[cusneed][i]-=REQUEST[cusneed][i];

(4)系统执行安全性检查,如安全,则分配成立;否则试探险性分配作废,系统恢复原状,进程等待。
安全性检查算法

(1)设置两个工作向量Work=AVAILABLE;FINISH
(2)从进程集合中找到一个满足下述条件的进程,
FINISH==false;

NEED<=Work;

如找到,执行(3);否则,执行(4)

(3)设进程获得资源,可顺利执行,直至完成,从而释放资源。
Work=Work+ALLOCATION;

Finish=true;

GOTO 2
这里写图片描述
原始代码:

#include<stdio.h>
#define true 1
#define false 0
#define processNum 5
#define resourceNum 3
#define MAXINT 9999
typedef int bool;
int available[resourceNum]={ 
3,3,2};
int maxRequest[processNum][resourceNum]={ 
7,5,3,3,2,2,9,0,2,2,2,2,4,3,3};
int allocation[processNum][resourceNum]={ 
0,1,0,2,0,0,3,0,2,2,1,1,0,0,2};
int need[processNum][resourceNum]={ 
7,4,3,1,2,2,6,0,0,0,1,1,4,3,1};
bool Finish[processNum];
int safeSeries[processNum]={ 
MAXINT, MAXINT , MAXINT , MAXINT , MAXINT};
int request[resourceNum];
void Init()
{ 

int i, j;
printf("输入进程数量、资源数量\n");
//scanf("%d %d",&processNum,&resourceNum);
printf("输入当前资源可用数目\n");
for(i = 0; i < resourceNum; i++){ 

scanf("%d",&available[i]);
}
printf("输入最大需求矩阵\n");
for(i = 0; i < processNum; i++){ 

for(j = 0; j < resourceNum; j++){ 

scanf("%d",&maxRequest[i][j]);
}
}
printf("输入分配矩阵\n");
for(i = 0; i < processNum; i++){ 

for(j = 0; j < resourceNum; j++){ 

scanf("%d",&allocation[i][j]);
}
}
printf("输入当前需求矩阵\n");
for(i = 0; i < processNum; i++){ 

for(j = 0; j < resourceNum; j++){ 

scanf("%d",&need[i][j]);
}
}
}
void showInfo()
{ 

int i,j;
printf("当前资源剩余:");
for(j = 0; j < resourceNum; j++){ 

printf("%d ",available[j]);
}
printf("\n");
printf(" PID\t Max\t\tAllocation\tNeed\n");
for(i = 0; i < processNum; i++){ 

printf(" P%d\t",i);
for(j = 0; j < resourceNum; j++){ 

printf("%d ",maxRequest[i][j]);
}
printf("\t\t");
for(j = 0; j < resourceNum; j++){ 

printf("%d ",allocation[i][j]);
}
printf("\t\t");
for(j = 0; j < resourceNum; j++){ 

printf("%d ",need[i][j]);
}
printf("\n");
}
}
bool isSafe()
{ 

int i,j,k;
int trueFinished = 0;
int work[resourceNum];
for(i = 0; i < resourceNum; i++){ 

work[i]=available[i];
}
for(i = 0; i < processNum; i++){ 

Finish[i]=false;
}
i = 0;
int temp = 0;
while(trueFinished != processNum){ 

int j =0;
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];
}
int k2;
safeSeries[trueFinished++] = i;
}
i++;
if(i >= processNum)
{ 

i = i % processNum;
if(temp == trueFinished)
break;
}
temp = trueFinished;
}
if(trueFinished == processNum){ 

printf("\n系统安全!\n\n安全序列为:");
for(i = 0; i < processNum; i++){ 

printf("%d ",safeSeries[i]);
}
return true;
}
printf("******系统不安全!******\n");
return false;
}
void SafeInfo(int *work, int i)
{ 

int j;
printf(" P%d\t",i);
for(j = 0; j < resourceNum; j++){ 

printf("%d ",work[j]);
}
printf("\t\t");
for(j = 0; j < resourceNum; j++){ 

printf("%d ",need[i][j]);
}
printf("\t ");
for(j = 0; j < resourceNum; j++){ 

printf("%d ",allocation[i][j]);
}
printf("\t\t");
for(j = 0; j < resourceNum; j++){ 

printf("%d ",allocation[i][j]+work[j]);
}
printf("\n");
}
int main()
{ 

int i,j,curProcess;
int wheInit = 0;
printf("是否使用内置数据?0是,1否:");
scanf("%d",&wheInit);
if(wheInit)
Init();  //可以不使用,选用内置的数据进行测试
printf("---------------------------------------------------------\n");
showInfo();
printf("\n系统安全情况分析\n");
printf(" PID\t Work\t\tNeed\tAllocation\tWork+Allocation\n");
isSafe();
while(true){ 

printf("\n---------------------------------------------------------\n");
printf("\n输入要分配的进程:");
scanf("%d",&curProcess);
printf("\n输入要分配给进程P%d的资源:",curProcess);
for(j = 0; j < resourceNum; j++){ 

scanf("%d", &request[j]);
}
for(j = 0; j < resourceNum; j++){ 

if(request[j] <= need[curProcess][j])continue;
else{ 
printf("ERROR!\n");break;}
}
if(j == resourceNum){ 

for(j = 0; j < resourceNum; j++){ 

if(request[j] <= need[curProcess][j])continue;
else{ 
printf("资源不足,等待中!\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];
}
printf("\n系统安全情况分析\n");
printf(" PID\t Work\t\tNeed\tAllocation\tWork+Allocation\n");
if(isSafe()){ 

printf("分配成功!\n");
showInfo();
}else{ 

for(j = 0; j < resourceNum; j++){ 

available[j] += request[j];
allocation[curProcess][j] -= request[j];
need[curProcess][j] += request[j];
}
printf("分配失败!\n");
showInfo();
}
}
}
}
}

这里写图片描述
修正后的代码:参考评论Sean0977

#include<stdio.h>
#define true 1
#define false 0
#define processNum 5
#define resourceNum 3
#define MAXINT 9999
typedef int bool;
int available[resourceNum]={ 
3,3,2};
int maxRequest[processNum][resourceNum]={ 
7,5,3,3,2,2,9,0,2,2,2,2,4,3,3};
int allocation[processNum][resourceNum]={ 
0,1,0,2,0,0,3,0,2,2,1,1,0,0,2};
int need[processNum][resourceNum]={ 
7,4,3,1,2,2,6,0,0,0,1,1,4,3,1};
bool Finish[processNum];
int safeSeries[processNum]={ 
MAXINT, MAXINT , MAXINT , MAXINT , MAXINT};
int request[resourceNum];
void Init()
{ 

int i, j;
printf("输入进程数量、资源数量\n");
//scanf("%d %d",&processNum,&resourceNum);
printf("输入当前资源可用数目\n");
for(i = 0; i < resourceNum; i++){ 

scanf("%d",&available[i]);
}
printf("输入最大需求矩阵\n");
for(i = 0; i < processNum; i++){ 

for(j = 0; j < resourceNum; j++){ 

scanf("%d",&maxRequest[i][j]);
}
}
printf("输入分配矩阵\n");
for(i = 0; i < processNum; i++){ 

for(j = 0; j < resourceNum; j++){ 

scanf("%d",&allocation[i][j]);
}
}
printf("输入当前需求矩阵\n");
for(i = 0; i < processNum; i++){ 

for(j = 0; j < resourceNum; j++){ 

scanf("%d",&need[i][j]);
}
}
}
void showInfo()
{ 

int i,j;
printf("当前资源剩余:");
for(j = 0; j < resourceNum; j++){ 

printf("%d ",available[j]);
}
printf("\n");
printf(" PID\t Max\t\tAllocation\tNeed\n");
for(i = 0; i < processNum; i++){ 

printf(" P%d\t",i);
for(j = 0; j < resourceNum; j++){ 

printf("%d ",maxRequest[i][j]);
}
printf("\t\t");
for(j = 0; j < resourceNum; j++){ 

printf("%d ",allocation[i][j]);
}
printf("\t\t");
for(j = 0; j < resourceNum; j++){ 

printf("%d ",need[i][j]);
}
printf("\n");
}
}
bool isSafe()
{ 

int i,j,k;
int trueFinished = 0;
int work[resourceNum];
for(i = 0; i < resourceNum; i++){ 

work[i]=available[i];
}
for(i = 0; i < processNum; i++){ 

Finish[i]=false;
}
i = 0;
int temp = 0;
while(trueFinished != processNum){ 

int j =0;
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];
}
int k2;
safeSeries[trueFinished++] = i;
}
i++;
if(i >= processNum)
{ 

if(flag==0)
{ 

temp=trueFinished;
temp0=trueFinished;        		
}
i = i % processNum;         
if(flag==1){ 

temp=trueFinished;
if(temp == temp0)
break;
else
temp0=temp;
}        
flag=1;
}
temp = trueFinished;
}
if(trueFinished == processNum){ 

printf("\n系统安全!\n\n安全序列为:");
for(i = 0; i < processNum; i++){ 

printf("%d ",safeSeries[i]);
}
return true;
}
printf("******系统不安全!******\n");
return false;
}
void SafeInfo(int *work, int i)
{ 

int j;
printf(" P%d\t",i);
for(j = 0; j < resourceNum; j++){ 

printf("%d ",work[j]);
}
printf("\t\t");
for(j = 0; j < resourceNum; j++){ 

printf("%d ",need[i][j]);
}
printf("\t ");
for(j = 0; j < resourceNum; j++){ 

printf("%d ",allocation[i][j]);
}
printf("\t\t");
for(j = 0; j < resourceNum; j++){ 

printf("%d ",allocation[i][j]+work[j]);
}
printf("\n");
}
int main()
{ 

int i,j,curProcess;
int wheInit = 0;
printf("是否使用内置数据?0是,1否:");
scanf("%d",&wheInit);
if(wheInit)
Init();  //可以不使用,选用内置的数据进行测试
printf("---------------------------------------------------------\n");
showInfo();
printf("\n系统安全情况分析\n");
printf(" PID\t Work\t\tNeed\tAllocation\tWork+Allocation\n");
isSafe();
while(true){ 

printf("\n---------------------------------------------------------\n");
printf("\n输入要分配的进程:");
scanf("%d",&curProcess);
printf("\n输入要分配给进程P%d的资源:",curProcess);
for(j = 0; j < resourceNum; j++){ 

scanf("%d", &request[j]);
}
for(j = 0; j < resourceNum; j++){ 

if(request[j] <= need[curProcess][j])continue;
else{ 
printf("ERROR!\n");break;}
}
if(j == resourceNum){ 

for(j = 0; j < resourceNum; j++){ 

if(request[j] <= need[curProcess][j])continue;
else{ 
printf("资源不足,等待中!\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];
}
printf("\n系统安全情况分析\n");
printf(" PID\t Work\t\tNeed\tAllocation\tWork+Allocation\n");
if(isSafe()){ 

printf("分配成功!\n");
showInfo();
}else{ 

for(j = 0; j < resourceNum; j++){ 

available[j] += request[j];
allocation[curProcess][j] -= request[j];
need[curProcess][j] += request[j];
}
printf("分配失败!\n");
showInfo();
}
}
}
}
}

更多内容访问omegaxyz.com
网站所有代码采用Apache 2.0授权
网站文章采用知识共享许可协议BY-NC-SA4.0授权
© 2018 • OmegaXYZ-版权所有 转载请注明出处

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/130473.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • Java面试题总结(附答案)「建议收藏」

    Java面试题总结(附答案)「建议收藏」2012年毕业,2016年转行,没有一个体面的工作,机缘巧合之下,来到了大连,Java培训,一个全新的领域,迷茫、困惑、漫无目的的努力,转行真的被歧视,真的不行吗?我命由我不由天,我觉得我行!相信我,只要你足够努力,总有成为架构师,独挡一面的一天。最近参加了一些面试,效果不是很理想,项目介绍只有大框,没有突出重点,没有项目中的具体细节,因为都是看的B站视频,实际工作中都是在做重复的CRUD工作,愁人啊。618买的新书塑料还没拆!视频计划已经执行到第二篇了!熬夜学习,是刻苦奋斗还是自欺欺人?面试

  • 示例的意思_实例

    示例的意思_实例JBoss 系列三十八:jBPM5示例之 Reusable Sub-Process

  • ucos创建任务流程图_createthread函数的参数

    ucos创建任务流程图_createthread函数的参数uC/OS-III任务创建函数OSTaskCreate()1.OSTaskCreate()函数原型voidTaskCreate(OS_TCB*p_tcb,//任务控制OS_TCB的地址CPU_CHAR*p_name,//任务的名字OS_TASK_PTRp_task,//任务代码的起始地址void*p_arg,//任务第一次运行时接收到

  • vggnet pytorch_Javaweb项目

    vggnet pytorch_Javaweb项目VGG网络是在2014年由牛津大学著名研究组VGG(VisualGeometryGroup)提出。

    2022年10月25日
  • java c socket通信 中文乱码解决「建议收藏」

    java c socket通信 中文乱码解决「建议收藏」前言(扯淡)作为一个一直从事Java的人来说,突然做C++很多地方都是乱撞墙,就发送的这个乱码就让人感到十分头秃,昨天跟老板对话,老板说不行咱就花钱找别人做。。。能力别质疑的感觉真是让人糟心啊–不扯太多,程序员节快乐,大家一起头秃吧。。虽然我并不想秃。问题言归正传,c++接收信息是gb2312,Java发数据是UTF-8,我Java接收数据没有问题,但是发给C++就遇到乱码问题…

  • jetbrains 激活码[在线序列号]

    jetbrains 激活码[在线序列号],https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号