银行家算法防止死锁-银行家算法课程名称：操作系统
课程类型：必修 实验项目名称：银行家算法
实验题目：采用银行家算法防止死锁 班级：实验学院一班 设计成绩 报告成绩 指导老师 一、实验题目
设计一个 n 个并发进程共享 m 个系统资源的系统。进程可动态 申请资源和释放资源，系统按各进程的申请动态的分配资源。要求采 用银行家算法防止死锁。
二、实验目的
死锁会引起计算机工作僵死，造成整个系统瘫痪。因此，死锁现 象是操作系统特别是大型系统中必须设法防止的。通过本次实验，使 学生掌握死锁的概念和产生死锁的原因和必要条件， 预防和避免死 锁的方法，死锁的检测与解除。通过本次实验，使学生加深了对死锁 概念的理解和掌握，深刻领会银行家算法的实质及实现过程。
三、设计思想（本程序中的用到的所有数据类型的定义，主
程序的流程图及各程序模块之间的调用关系） 1．程序流程图 开 始
收回假定分配给现 剩余资源能否满 否 行进程的资源 足现行进程？ 输出信息资源不足
是
承认已假定分配给现行 如不采用死锁预防算 当前分配状态 是 进程的资源，输出完成信 法，将现行进程死锁
安全吗？（safe） 息，置ADVANCE=true 位置 1
否
收回假定分配给现行进 采用死锁预防算法如 采用死锁预防算 是 程的资源，输出失败信 已 有 进 程 死 锁 置 法？ 息，置ADVANCE=true ADVANCE=false
否
承认已假定分配给现行进
程的资源，输出完成信息，
置ADVANCE=true
结 束
安全（safe）函数框图如下： 开 始
未完成进程的T 标志为 1
置 已完成进程的T 标志为0
置局部变量Change 为‘true ’
（即是否有进程标志位T 从1变0）
否 Change 是否为
‘true ’
是
判定是否还存在不能 置change 为‘false’
完成的进程，若不存
在，置 SAFE 为 ‘true ’，
否则为‘false’
全部进程已经完成？即 是
各进程T 标志都为0 结 束
否
剩余资源与新完成资源 否 之和是否超过某进程还
需要的资源？
是
置局部变量PROGRESS 为true
改变对应的T 值
2．逻辑设计
用结构体数组表示 3 个进程，其中包括使用数组形式的线性表
表示某个进程申请资源的列表（队列），以及进程需要的总资源数338
银行家算法防止死锁前i 个申请共计占用的资源，进程当前已经运行到的位置等信息。
模拟分配的程序部分，采用循环队列对各进程进行调度。
3、物理设计
全局变量的结构定义如下：
bool avoid; struct info//进程信息 { long tot,n;//最大占用资源, 申请次数 long list[16];// 申请资源列表 long pre[16];// 已占用资源数 long p;// 已分配状况的指针 }pro[4]; long LeftRes;
程序的结构定义如下：
int main()//主函数 { init(); lwfree.cn allot(); } void init()//函数功能:输入和初始化 void allot()//函数功能:模拟资源分配过程 allot()使用以下函数模拟分配过程： bool require(long x)//函数功能:尝试分配资源给进程x bool safe(long x)//函数功能:检查分配是否安全
可以处理3 种资源的程序全局变量结构如下：
//共有 3 种资源，3 个进程 bool avoid; struct info//进程信息 { long tot[4];//最大占用资源数 long p[4];// 已经占有的资源数 }pro[5]; long LeftRes[4];//剩余资源数 long qu[4];
四、测试结果
对于一组会导致死锁的数据，分别选择采用和不采用避免算法
结果如下：
Avoid deadlock?(Y/N)Y Please input the resourse-require lists of these 3 processes, one lists in a line: 2 3 4 2 3 3 3 1
================================================================= Process1 : 2 3 4 (Sum=9) Process2 : 2 3 3 (Sum=8) Process3 : 3 1 (Sum=4)
=================================================================
Process1 require 2 unit(s) resourse......Success! LeftResourse=8 Process2 require 2 unit(s) resourse......Success! LeftResourse=6 Process3 require 3 unit(s) resourse......Success! LeftResourse=3 Process1 require 3 unit(s) resourse......Denied! Not safe Process2 require 3 unit(s) resourse......Denied! Not safe Process3 require 1 unit(s) resourse......Success! LeftResourse=2 Process3 finish. LeftResourse=6 Process1 require 3 unit(s) resourse......Denied! Not safe Process2 require 3 unit(s) resourse......Success! LeftResourse=3 Process1 require 3 unit(s) resourse......Denied! Not safe Process2 require 3 unit(s) resourse......Success! LeftResourse=0 Process2 finish. LeftResourse=8 Process1 require 3 unit(s) resourse......Success! LeftResourse=5 Process1 require 4 unit(s) resourse......Success! LeftResourse=1 Process1 finish. LeftResourse=10
Finish lwfree.cn
如果不避免死锁：
Avoid deadlock?(Y/N)N Please input the resourse-require lists of these 3 processes, one lists in a lin e: 2 3 4 2 3 3 3 1
================================================================= Process1 : 2 3 4 (Sum=9) Process2 : 2 3 3 (Sum=8) Process3 : 3 1 (Sum=4)
=================================================================
Process1 require 2 unit(s) resourse......Success! LeftResourse=8 Process2 require 2 unit(s) resourse......Success! LeftResourse=6 Process3 require 3 unit(s) resourse......Success! LeftResourse=3 Process1 require 3 unit(s) resourse......Success! LeftResourse=0 Process2 require 3 unit(s) resourse......Denied! No enough resourse Process3 require 1 unit(s) resourse......Denied! No enough resourse Process1 require 4 unit(s) resourse......Denied! No enough resourse Already Deadlock
Finish
改进版本（可以使用3 种资源的程序）测试结果如下：
五、系统不足与经验体会
系统不能处理多种不同资源的情况，也缺乏处理大规模数据的能
力。
safe 函数的编写是程序成功的关键，其中利用 Change 标记的思
乡值得仔细体会。
六、附录：源代码（带注释）
//******************************************************* //* 操作系统实验三 死锁 * //* 实验学院一班（0436101） 张元竞(6040310110) * //* 2006-10-15 * //******************************************************/
#include
#include #include #include
//共有 3 种资源，3 个进程 bool avoid; struct info//进程信息 { long tot[4];//最大占用资源数 long p[4];// 已经占有的资源数 }pro[5]; long LeftRes[4];//剩余资源数 long qu[4];
void init()//函数功能:输入和初始化 { char tmp[128]; long i,j;
// 以下由用户选择是否采用避免死锁算法 printf("是否采用避免死锁算法?(Y/N)"); gets(tmp); avoid=(tmp[0]=='Y' || tmp[0]=='y');
//输入各进程的资源信息 printf("请输入各进程的资源信息:\n"); printf("依次输入各进程所需要的最大资源数量:\n"); for (i=1;i<=3;i++) { for (j=1;j<=3;j++) { scanf("%ld",&pro[i].tot[j]); } } printf("依次输入各进程已经占据的资源数量:\n"); for (i=1;i<=3;i++) { for (j=1;j<=3;j++) { do lwfree.cn { scanf("%ld",&pro[i].p[j]); if (pro[i].p[j]>pro[i].tot[j]) printf("\n 占有资源超过了声明的最大资源,请重新输入\n"); }while (pro[i].p[j]>pro[i].tot[j]); } }
//初始化资源数量 for (i=1;i<=3;i++)
银行家算法防止死锁-银行家算法 { LeftRes[i]=10;//初始化总资源数为 10 for (j=1;j<=3;j++) { LeftRes[i]-=pro[j].p[i];//减去已经被占据的资源 } }
// 以下输出资源状况表 printf("\n=========================================================== ====\n"); printf("%-20s","当前剩余资源"); for (i=1;i<=3;i++) { printf("%8ld",LeftRes[i]); } for (i=1;i<=3;i++) { printf("\n%s%ld%-15s","进程",i,"(占用/最大)"); for (j=1;j<=3;j++) { printf("%4ld/%3ld",pro[i].p[j],pro[i].tot[j]); } } printf("\n=========================================================== ====\n\n");
}
bool safe(long x)//函数功能:检查分配是否安全 { long i,j,y[4]; bool change=1; bool T[4]; long stack[4],top=0;
memset(T,0,sizeof(T)); for (i=1;i<=3;i++) { y[i]=LeftRes[i]-qu[i]; pro[x].p[i]+=qu[i]; }
while (change) { change=0; for (i=1;i<=3;i++) { if (T[i]) continue; if (y[1]>=pro[i].tot[1]-pro[i].p[1] && y[2]>=pro[i].tot[2]-pro[i].p[2] && y[3]>=pro[i].tot[3]-pro[i].p[3]) { for (j=1;j<=3;j++) { y[j]+=pro[i].p[j]; } T[i]=1; change=1; stack[++top]=i; } } } for (i=1;i<=3;i++) { if (!T[i]) { return 0; } } printf(" 申请成功! 安全序列为: "); for (i=1;i<=top;i++) printf("%2ld",stack[i]); return 1; }
void require(long x)//函数功能:尝试分配资源给进程x { long i,j;
if (LeftRes[1] printf("\n=========================================================== ====\n"); printf("%-20s","当前剩余资源"); for (i=1;i<=3;i++) { printf("%8ld",LeftRes[i]-qu[i]); } for (i=1;i<=3;i++) { printf("\n%s%ld%-15s","进程",i,"(占用/最大)"); for (j=1;j<=3;j++) { if (i==x && !avoid) pro[i].p[j]+=qu[i]; printf("%4ld/%3ld",pro[i].p[j],pro[i].tot[j]); } } printf("\n=========================================================== ====\n\n");
}
void allot()//函数功能:模拟资源分配过程 { long i,j;
printf("请输入申请资源的进程ID，以及申请的各种资源数量:\n"); scanf("%ld",&i); for (j=1;j<=3;j++) { scanf("%ld",&qu[j]); } require(i); }
int main() { init(); allot();
return 0; }
