C语言银行家算法

全栈程序员-站长 • 2022年6月14日上午10:36 • 未分类 • 阅读 23

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();
                }
            }
        }
    }
}

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/130473.html原文链接：https://javaforall.net

全栈程序员-站长

0 0

C++学习——类和对象

C++学习——类和对象一、类和对象基本知识：1、类的访问控制有哪些？公有成员：以关键字public指明。私有成员：以关键字private指明。保护成员：以关键字protected指明。2、拷贝构造函数的作用是什么？用一个已经存在的对象初始化本类的新对象。3、友元函数和友元类的作用是什么？友元提供了不同类或对象的成员函数之间、类的成员函数与一般函数之间进行数据共享的机制。对于一个类，可以利用关键字fri…

全栈程序员-站长
2022年8月18日
3
Ubuntu 18.04换国内源中科大源阿里源 163源清华源

Ubuntu 18.04换国内源中科大源阿里源 163源清华源国内有很多Ubuntu的镜像源，包括阿里的、网易的，还有很多教育网的源，比如：清华源、中科大源。我们这里以中科大的源为例讲解如何修改Ubuntu18.04里面默认的源。编辑/etc/apt/sources.list文件,在文件最前面添加以下条目(操作前请做好相应备份)：##中科大源debhttps://mirrors.ustc.edu.cn/ubuntu/bionic…

全栈程序员-站长
2022年5月15日
54
555施密特触发器电路图_555定时器构成的施密特触发器

555施密特触发器电路图_555定时器构成的施密特触发器目录方法作用内部电路分析555内部电路图分析仿真电路图仿真结果总结将555的6脚和2脚连接在一起，并在5脚接上0.01uF的电容用于滤波，这就构成了施密特触发器。施密特触发器可作为波形整形电路，能将模拟信号波形整形为数字电路能够处理的方波波形，而且由于施密特触发器具有滞回特性，所以可用于抗干扰，其应用包括在开回路配置中用于抗扰，以及在闭回路正回授/负回授配置中用于实现多谐振荡器。百度百科：https://baike.baidu.com/item/%E6%96%

全栈程序员-站长
2022年10月26日
0
tortoisegit使用教程_git小乌龟拉取代码

tortoisegit使用教程_git小乌龟拉取代码一、下载之前需要下载三个安装包，分别是git、小乌龟客户端、小乌龟中文语言包：二、下载与配置：1.下载Git并且暗转，下载地址：https://git-for-windows.github.io/2.下载TortoiseGit客户端以及中文语言包地址：https://tortoisegit.org/download/此处省略一万个next3.配置TortoiseGit小乌龟首先选择自己需要进行管理的文件夹作为本地Git的仓库，我设置的是D:\A_Projects\OMS1.0然后在文

全栈程序员-站长
2022年9月16日
0
python能开发arm_获得通用技能的方法

python能开发arm_获得通用技能的方法看了很多资料介绍如何将python移植到嵌入式设备当中，但总感觉杂乱五章，还移植不成功，但是经过我的多方摸索，成功的探索出了一条阳光大道，供各位网友借鉴参考。我采用的方法可以成功移植python2.7以后的所有版本。第一步：从官网下载源码.并把解压放在/opt第二步：在/Python-3.4.5目录下新建一键移植脚本，并执行内容如下：（执行完会报错某某模块内没安装，这个不耽误，…

全栈程序员-站长
2022年10月10日
0
ffmpeg的安装和使用教程_Anaconda安装ffmpeg

ffmpeg的安装和使用教程_Anaconda安装ffmpeg一、ffmpeg的简介FFmpeg是一个自由软件，可以运行音频和视频多种格式的录影、转换、流功能，包含了libavcodec——这是一个用于多个项目中音频和视频的解码器库，以及libavformat——一个音频与视频格式转换库。主要参数-i——设置输入档名。-f——设置输出格式。-y——若输出文件已存在时则覆盖文件。-fs——超过指定的文件大小时则结束转换。-t——指定…

全栈程序员-站长
2022年9月12日
0

C语言银行家算法

相关推荐

C++学习——类和对象

Ubuntu 18.04换国内源 中科大源 阿里源 163源 清华源

555施密特触发器电路图_555定时器构成的施密特触发器

tortoisegit使用教程_git小乌龟拉取代码

python能开发arm_获得通用技能的方法

ffmpeg的安装和使用教程_Anaconda安装ffmpeg

发表回复

Ubuntu 18.04换国内源中科大源阿里源 163源清华源