C语言银行家算法
大家好，又见面了，我是你们的朋友全栈君。
算法简介 银行家算法（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-版权所有 转载请注明出处
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/130473.html原文链接：https://javaforall.cn
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
