银行家算法实验报告

一、 实验名称：银行家算法

二、 实验目的：银行家算法是避免死锁的一种重要方法，通过编写

一个简单的银行家算法程序，加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。 三、 问题分析与设计：

1、算法思路：先对用户提出的请求进行合法性检查，即检查请求是否大于需要的，是否大于可利用的。若请求合法，则进行预分配，对分配后的状态调用安全性算法进行检查。若安全，则分配；若不安全，则拒绝申请，恢复到原来的状态，拒绝申请。

2、银行家算法步骤：（1）如果Requesti＜or =Need,则转向步骤(2)；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。

（2）如果Request＜or=Available,则转向步骤（3）；否则，表示系统中尚无足够的资源，进程必须等待。

（3）系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值：

Available=Available-Request[i]; Allocation=Allocation+Request;

Need=Need-Request;

(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。

3、安全性算法步骤：

（1）设置两个向量

①工作向量Work。它表示系统可提供进程继续运行所需要的各类资源数目，执行安全算法开始时，Work=Allocation;

②布尔向量Finish。它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finish[i]=false，当有足够资源分配给进程时，令Finish[i]=true。

（2）从进程集合中找到一个能满足下述条件的进程：

①Finish[i]=false ②Need如找到，执行步骤（3）；否则，执行步骤（4）。

（3）当进程P获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

Work=Work+Allocation; Finish[i]=true; 转向步骤（2）。

（4）如果所有进程的Finish[i]=true,则表示系统处于安全状态；否则，系统处于不安全状态。

4、流程图： 系统主要过程流程图

银行家算法流程图

安全性算法流程图

四、 实验代码：

//#define M 5 //#define N 3

#include //本实验中使用到的库函数 #include #include

int max[5][1]; //开始定义银行家算法中需要用到的数据 int allocation[5][1]; int need[5][1]; int available[1]; int request[5][1]; char *finish[5]; int safe[5]; int n,i,m; int k=0; int j=0; int work[1]; int works[5][1];

void line() //美化程序，使程序运行时更加明朗美观 {

printf(\"------------------------------------------------\\n\"); }

void start() //表示银行家算法开始 {

line();

printf(\" 银行家算法开始\\n\");

printf(\" -- 死锁避免方法 line(); }

void end() //表示银行家算法结束 {

line();

printf(\" 银行家算法结束，谢谢使用\\n\"); line(); }

void input() //输入银行家算法起始各项数据 { for (n=0;n<5;n++) { printf(\"请输入进程P%d的相关信息：\\n\ printf(\"Max:\"); for (m=0;m<1;m++)

scanf(\"%d\

printf(\"Allocation:\"); for (m=0;m<1;m++)

scanf(\"%d\

\\n\");

}

for (m=0;m<1;m++)

need[n][m]=max[n][m]-allocation[n][m];

printf(\"请输入系统可利用资源数Available:\"); for (m=0;m<1;m++) }

void output() //输出系统现有资源情况 {

line();

printf(\"资源情况 Max Allocation Need Available\\n\"); printf(\"进程 A A A A \\n\"); line();

for(n=0;n<5;n++) {

printf(\"P%d%3d%3d%3d\ } line(); }

void change() //当Request[i,j]<=Available[j]时，系统把资源分配给进程P[i]，Available[j]和Need[i,j]发生改变

{

for (m=0;m<1;m++) {

if (n==0) else

printf(\"\\n\");

printf(\"%3d%3d\\n\

scanf(\"%d\

} }

available[m]-=request[i][m]; allocation[i][m]+=request[i][m]; need[i][m]-=request[i][m];

void outputsafe() //输出安全序列的资源分配表 {

printf(\"该安全序列的资源分配图如下：\\n\"); line();

printf(\"资源情况 Work Need Allocation Work+Allocation Finish\\n\");

printf(\"进程 A A A A \\n\"); line();

for(n=0;n<5;n++)

printf(\"P%d%9d%3d%3d%5d%12s\\n\e[n]][0],allocation[safe[n]][0],works[safe[n]][0]+allocation[safe[n]][0],finish[n]);

line(); }

int check() //安全性算法 {

printf(\"开始执行安全性算法……\\n\");

for (m=0;m<1;m++) //数组work和finish初始化

work[m]=available[m];

for (n=0;n<5;n++) { }

finish[n]=\"false\"; safe[n]=0;

k=0;

for (m=0;m<5;m++)

for (n=0;n<5;n++)

if(strcmp(finish[n],\"false\")==0 &&

need[n][0]<=work[0] ) //查找可以分配资源但尚未分配到资源的进程

{

safe[k]=n; //以数组safe[k]记下各个进程得到

分配的资源的顺序

works[safe[k]][0]=work[0];

放出分配给它的资源

work[0]+=allocation[n][0]; //进程执行后释

finish[n]=\"ture\"; //finish[n]变为1以示该进

程完成本次分

}

k++;

for (m=0;m<5;m++) //判断是否所有进程分配资源完成 { 0

素都为ture

} else

if (m==4) //此处m=4表示所有数组finish的所有元

if (strcmp(finish[m],\"false\")==0) {

printf(\"找不到安全序列，系统处于不安全状态。\\n\"); return 0; //找不到安全序列，结束check函数，返回

{

printf(\"找到安全序列P%d->P%d->P%d->P%d->P%d，系统是安全的\\n\

} return 1; }

void main() //主程序开始 {

start();

for (;j==0;) //确认输入数据的正确性，若输入错误，重新输入 { 入：\");

}

printf(\"数据确认无误，算法继续。\\n\");

if (check()==0) //若check函数返回值为0，表示输入的初始数据找不到安全序列，无法进行下一步，程序结束

{ }

for(;j==1;) //当有多个进程请求资源时，循环开始 {

printf(\"请输入请求资源的进程i(0、1、2、3、4)：\"); //输入发出请求向量的进程及请求向量

end(); exit(0); input();

printf(\"以下为进程资源情况，请确认其是否正确：\\n\"); output();

printf(\"数据是否无误：\\n正确：输入1\\n错误：输入0\\n请输

}

j=1;

outputsafe(); //输出安全序列的资源分配表

scanf(\"%d\

scanf(\"%d\

printf(\"请输入进程P%d的请求向量Request%d：\for(n=0;n<1;n++)

scanf(\"%d\

for (;request[i][0]>need[i][0];) //若请求向量大于需求资源，则认为是输入错误，要求重新输入

{

printf(\"数据输入有误，请重试！\\n请输入进程P%d的请求向量Request%d：\

提供分配

\\n\

}

if(request[i][0]<=available[0]) //判断系统是否有足够资源

for(n=0;n<1;n++)

scanf(\"%d\

{ } else

printf(\"系统没有足够的资源，进程P%d需要等待。printf(\"系统正在为进程P%d分配资源……\\n\change(); //分配资源 j=0;

if (j==0) //j=0表示系统有足够资源分配的情况 {

printf(\"当前系统资源情况如下：\\n\"); //输出分配资源后的系统资源分配情况

分配无效

output();

if(check()==0) //若找不到安全系列，则之前的资源

{

printf(\"本次资源分配作废，恢复原来的资源分配

状态。\\n\");

资源状态

输入：\");

for (m=0;m<1;m++) //恢复分配资源前的系统

}

}

{ }

output(); //输出系统资源状态

available[m]+=request[i][m]; allocation[i][m]-=request[i][m]; need[i][m]+=request[i][m];

printf(\"是否还有进程请求资源？\\n是：输入1\\n否：输入0\\n请

scanf(\"%d\若还有进程请求资源，j=1，之前的for循环条件满足

} end(); }

五、 程序执行结果：

六、实验总结

多个进程同时运行时，系统根据各类系统资源的最大需求和各类系统的剩余资源为进程安排安全序列，使得系统能快速且安全地运行进程，不至发生死锁。银行家算法是避免死锁的主要方法，其思路在很多方面都非常值得我们来学习借鉴。