操作系统——“银行家算法”实验报告

操作系统实验报告

——银行家算法 班级：xxxxxx

学号：xxxxxx 姓名：xxxxxx

实验目的：

银行家算法是避免死锁的一种重要方法，通过编写一个简单的银行家算法

程序，加深了解有关资源申请，避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。

算法思想：

操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。

实验步骤：

银行家算法

进程i发出请求资源申请，

(1)如果Request [j]<=need[i,j],转向步骤(2),否则认为出错，因为他所需要的资源数已经超过它所宣布的最大值。

(2)如果：Request i[j]<=available[i,j]，转向步骤(3)，否则表示尚无足够资源，进程i需等待。

(3)若以上两个条件都满足，则系统试探着将资源分配给申请的进程，并修改下面数据结构中的数值：

Available[i,j]= Available[i,j]- Request [j]； Allocation[i][j]= Allocation[i][j]+ Request [j]； need[i][j]= need[i][j]- Request [j]；

(4)试分配后，执行安全性检查，调用check()函数检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程；否则本次试探分配作废，恢复原来的资源分配状态，让该进程等待。

(5)用do{…}while 循环语句实现输入字符y/n判断是否继续进行资源申请。

安全性检查算法 (1)设置两个向量：

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

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

(2)在进程中查找符合以下条件的进程： 条件1：Finish[i]=false； 条件2：need[i][j]<=Work[j]

若找到，则执行步骤(3)否则，执行步骤(4)

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

Work[j]= Work[j]+ Allocation[i][j]； Finish[i]=true； goto step (2)；

(4)如果所有的Finish[i]=true都满足，则表示系统处于安全状态，否则，处于不安全状态。

流程图：

系统初始化 银行家算法流程图 输入进程个数no1 输入资源类数no2 输入进程最大需求矩阵Max、已分配矩阵Allocation和可利用资源矩阵Available Need[][]=Max[][]-Allocation[][] 打印输出此时资源分配情况表 输入欲申请资源进程号 N 输入是否合法 Y 输入该进程申请的资源量 Y Y Request[]>Need[][]? 继续分配(Y)? or Y 退出(N)? N Request[]>Available[][]? N 预分配 N 调用check()函数进行安全性检查 退出系统 调用check()函数 安全性检查流程图 work[]=available[] finish[]=false N need[][]<=work[] finish[]=false ? Y work[]=work[]+allocation[][] finish[]=true 所有进程的finish[]==true? Y 输出安全序列，并打印出当前资源分配情况 N 输出提示：系统不安全 调用结束 实验代码：

#include #include #include

# define m 50

int no1; //进程数 int no2; //资源数 int r;

int allocation[m][m],need[m][m],available[m],max[m][m];

char name1[m],name2[m]; //定义全局变量 void main() { bool check(); void print(); int i,j,p=0,q=0; char c; int request[m],allocation1[m][m],need1[m][m],available1[m]; printf(\"**********************************************\\n\"); printf(\"* 银行家算法的设计与实现 *\\n\"); printf(\"**********************************************\\n\"); printf(\"请输入进程总数:\\n\"); scanf(\"%d\ printf(\"请输入资源种类数:\\n\"); scanf(\"%d\

printf(\"请输入Max矩阵:\\n\"); for(i=0;ido{ q=0;

p=0;

printf(\"\\n请输入请求资源的进程号(0~4)：\\n\"); for(j=0;j<=10;j++) { scanf(\"%d\ if(i>=no1) { printf(\"输入错误，请重新输入：\\n\"); continue; } else break; } printf(\"\\n请输入该进程所请求的资源数request[j]:\\n\"); for(j=0;jneed[i][j]) p=1; //判断请求是否超过该进程所需要的资源数 if(p) printf(\"请求资源超过该进程资源需求量，请求失败！\\n\"); else { for(j=0;javailable[j]) q=1; //判断请求是否超过可用资源数 if(q) printf(\"没有做够的资源分配，请求失败！\\n\"); else //请求满足条件 { for(j=0;j//系统尝试把资源分配给请求的进程 }

print(); if(check()) { bool empty=true; for(int k=0;k//还原已分配的资源数，仍需要的资源数和可用的资源数 } printf(\"返回分配前资源数\\n\"); print(); } } }printf(\"\\n你还要继续分配吗？Y or N ?\\n\"); //判断是否继续进行资源分配 c=getche(); }while(c=='y'||c=='Y'); } }

bool check() //安全算法函数 {

int k,f,v=0,i,j; int work[m],a[m]; bool finish[m]; r=1; for(i=0;iwork[j]) f=0; if(f==1) //找到还没有完成且需求数小于可提供进程继续运行的资源数的进程 { finish[i]=true; a[v++]=i; //记录安全序列号 for(j=0;j0); f=1; for(i=0;i} else { printf(\"\\n系统当前为安全状态，安全序列为：\\n\"); for(i=0;ivoid print() //输出函数 { int i,j; printf(\"\\n\"); printf(\"*************此时刻资源分配情况*********************\\n\"); printf(\"进程名/号 | Max | Allocation | Need |\\n\"); for (i = 0; i < no1; i++) { printf(\" p%d/%d \

for (j = 0; j < no2; j++) {printf(\"%d \ for (j = 0; j < no2; j++) {printf(\" %d \ for (j = 0; j < no2; j++) {printf(\" %d \ printf(\"\\n\"); } printf(\"\\n\"); printf(\"各类资源可利用的资源数为:\"); for (j = 0; j < no2; j++) {printf(\" %d\ printf(\"\\n\"); }

实验结果：

实验分析：

1.主函数

void main() { bool check(); void print(); int i,j,p=0,q=0; char c; int request[m],allocation1[m][m],need1[m][m],available1[m]; printf(\"**********************************************\\n\"); printf(\"* 银行家算法的设计与实现 *\\n\"); printf(\"**********************************************\\n\"); printf(\"请输入进程总数:\\n\"); scanf(\"%d\ printf(\"请输入资源种类数:\\n\"); scanf(\"%d\

printf(\"请输入Max矩阵:\\n\"); For...... if...... else...... }

其中用到的函数操作有三个

bool check() //安全算法函数 void print() //输出函数

safeAlgorithm() //安全性检测算法

2.安全性检查

程序中安全性算法的描述如下： （1） 设置如下两个工作向量：

Work：表示系统可提供给进程继续运行的各类资源的空闲资源数目，它含有m个元素，执行安全性算法开始时，Work＝Available。

Finish：表示系统是否有足够的资源分配给进程，使之运行完成。开始时，Finish[i]＝false；当有足够的资源分配给进程Pi时，令Finish[i]＝true。

（2） 从进程集合中找到一个能满足下列条件的进程： Finish[i]＝＝false； Need i<= Work；，

如果找到了就执行步骤（3），否则执行步骤（4）。

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

Work = Work + Allocation; Finish[i]＝false； 然后转向第（2）步骤。

（4） 若所有进程中的Finish[i]都是true，则表示系统处于安全状态；否则，系统处于不安全状态。

此过程由一个安全性检测函数实现：safeAlgorithm();//安全性检测算法 3.对进程申请资源的处理

当某一进程提出资源申请时，系统须做出判断，能否将所申请资源分配给该进程。设request为进程i的请求向量，如果request[j]=K，表示进程i需要K个j资源。当系统发出请求后，系统按下述步骤开始检查：

（1） 如果request[j]<=need[i][j],转向步骤2；否则报告出错，申请的资源大于它需要的最大值。

（2） 如果request[j]<=available[j],转向步骤3；否则报告出错，尚无足够的资源。

（3）系统试探着把资源分配给p[i]，并修改下列数据结构中的值： available[j]=available[j]-request[j]

allocation[i][j]=allocation[i][j]+request[j] need[i][j]=need[i][j]-request[j]

（4）系统进行安全性算法，检查此次分配后，系统是否还处于安全状态，若安全，把资源分配给进程i；否则，恢复原来的资源分配状态，让进程i等待。 整个过程由银行家算法实现：bankerAlgorithm()//利用银行家算法对申请资源对进行判定