毕业论文-行银家算法避免死锁的研究与实现.doc

长治学院学士学位论文(设计)

长 治 学 院

2013届学士学位毕业论文

银行家算法避免死锁的研究与实现

学 号： 09407227
姓 名： 王子丹
指导教师： 陕粉丽
专 业： 计算机科学与技术
系 别： 计算机系

完成时间：2013年5月

银行家算法避免死锁的研究与实现
专业：计算机科学与技术 姓名：王子丹 学号：09407227
指导教师：陕粉丽

摘 要：Dijkstra的银行家算法是最有代表性的避免死锁的算法，该算法由于能用于银行系统现金贷款的发放而得名。银行家算法是在确保当前系统安全的前提下推进的。对进程请求先进行安全性检查，来决定资源分配与否，从而确保系统的安全，有效的避免了死锁的发生。该论文在理解和分析了银行家算法的核心思想以及状态的本质含义的前提下，对算法的实现在总体上进行了设计，包括对算法分模块设计，并对各个模块的算法思想通过流程图表示，分块编写代码，并进行测试，最后进行程序的测试，在设计思路上严格按照软件工程的思想执行，确保了设计和实现的可行性。
关键词：银行家算法；死锁；避免死锁；安全性序列

I

目 录
1 前言 1
1.1 课题背景 1
1.2 死锁 1
1.3 系统安全状态 2
1.4 银行家算法 2
2 需求分析 3
2.1 问题描述 3
2.2 基本要求 3
2.3 数据流模型 3
3 概要设计 4
3.1 模块的划分 4
3.2 模块调用关系 4
3.3 各模块之间的接口 4
3.4 程序流程图 5
4 详细设计 6
4.1 数据结构选取分析 6
4.2 数据结构设计 6
4.3 算法整体设计与调用 6
4.4 程序流图 7
5 程序分析测试 9
5.1 分模块分析与测试 9
5.2 集成测试 11
6 结论 12
参考文献 12
致谢 14
附录 15

II

银行家算法避免死锁的研究与实现
1 前言
1.1 课题背景
在多道程序系统中，虽可以借助多个进程的并发执行来改善系统的资源利用率，提高系统吞吐量，但可能发生一种危险——死锁。如此，寻求一种避免死锁的方法便显得很重要。死锁产生的一般原因有两点：竞争资源和进程间推进顺序非法。因此，我们只需在当前的有限资源下，找到一组合法的执行顺序，便能很好的避免死锁。而银行家算法起源于银行系统的发放贷款，和计算机操作系统的资源分配完全符合，因此可以借鉴该算法的思想，设计出一种有效的算法程序，解决该问题。
1.2 死锁
死锁是进程死锁的简称，是指多个进程循环等待它方占有的资源而无限期地僵持下去的局面。很显然，如果没有外力的作用，那么死锁涉及到的各个进程都将永远处于封锁状态。虽然进程在运行过程中会产生死锁，但死锁的发生也必须具备四个条件：（1）互斥条件；（2）请求与保持条件；（3）不剥夺条件；（4）环路与等待条件。
为保证系统中诸进程的正常运行，应事先采取必要的措施，来预防发生死锁。目前，预防死锁的方法可归结为以下两种：
（1）预防死锁。它是通过设置某些限制条件。去破坏产生死锁的四个条件中的一个或几个条件，来预防发生死锁。
（2）避免死锁。同样是实现预防的策略但是他并不是实现采取各种限制措施去破坏产生死锁的四个条件，而是在资源分配过程中，用某种方法去防止系统进入不安全的状态，从而避免死锁。
（3）检测死锁。这种方法并不须事先采取任何限制性措施，也不需检查系统是否进入不安全区，而是允许系统在运行过程中发生死锁。通过系统设置的检测机构，及时的检测出死锁的发生。然后，采取适当的手段，将死锁清除掉。
（4）解除死锁。与检测死锁相配套，当系统发生死锁的时候，将进程从死锁中解除出来。
1.3 系统安全状态
预防死锁和解除死锁都是通过施加条件限制，来预防发生死锁。但预防死锁所施加的条件较严格，这往往会影响进程的并发执行，而避免死锁所施加的限制条件则较宽松，这给进程的运行提供了较宽松的环境，有利于进程的并发执行。
要想避免死锁，就必须考虑进程是否处于安全状态，只要处于安全状态就可以避免死锁。所谓的安全状态就是指系统按某种进程顺序（P1，P2，……，Pn）（称<P1，P2，……，Pn>为安全序列），来为某种进程分配资源，直至满足每个进程对资源的最大需求，使每个进程都能够顺利完成。但如果系统无法找到这样一个安全序列，则称系统处于不安全状态。
1.4 银行家算法
银行家算法是最具有代表性的避免死锁的算法，是由于该算法能用于银行系统现金贷款的发放而得名。我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。为保证资金的安全,银行家规定：
（1）当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客；
（2）顾客可以分次贷款,但贷款的总数不能超过最大需求量；
（3）当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款；
（4）当顾客得到所需的资金后,一定能在有限的时间里归还所有的资金。
操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。
那么，安全序列在银行家算法中的实际意义在于：系统每次进行资源分配后，如果对于系统中新的资源状况，存在一个安全序列，则至少存在一条确保系统不会进入死锁的路径。
2 需求分析
2.1 问题描述
运用银行家算法避免死锁的发生是在确保当前系统安全的前提下推进的，对进程请求先进行安全性检查来决定资源分配与否，从而确保系统的安全，有效的避免了死锁的发生。
问题的关键在于安全性算法，即查找安全性序列。
2.2 基本要求
（1）从键盘输入当前系统的资源信息，包括当前可用资源，每个进程对各类资源的最大需求量，每个进程当前已分配的各个资源量和每个进程尚需要的各个资源量；
（2）输入进程请求，按照设计好的安全性算法进行检查，得到结果并输出整个执行过程的相关信息和最终结果；
（3）要求要有各种异常的处理，程序的可控制性和可连续性执行。包括对进程的存在有无检查，请求向量的不合法检查，试分配失败后的数据恢复和重新接受进程请求等。
2.3 数据流模型
用键盘输入信息，对系统资源初始化，输入进程请求，用安全性算法进行安全性检查，系统安全的话就进行试分配，再进行安全性检查；如果试分配失败则恢复系统。如图1所示。
初始化

安全性检查

输出结果
输入信息

试分配

安全性检查

图1 数据流模型
3 概要设计
3.1 模块的划分
由于该算法规模较小，所以选用结构化的设计方法，将该系统划为四块，分别是：
（1）主模块，处在整个系统的最高层，负责组织调用其他模块；
（2）初始化模块，负责从键盘读入系统资源和进程状态，并将系统初识资源分配状态打印；
（3）试分配模块，负责处理进程请求和相应的数据结构的修改，以及特殊情况的处理；
（4）安全性检查，负责试分配后的安全性检查，以及系统不安全时的资源恢复。
3.2 模块调用关系
银行家算法系统有四个模块，各模块之间的调用关系如图2所示：
主模块
Main（）

初始化
Init_process（）

试分配
Attempt_Allocation（）
安全性检查
Safety_Algorithm（）

图2 模块调用关系图
3.3 各模块之间的接口
系统的四个模块用到三个接口。分别为Flag1，pro，Flag2。它们的功能介绍如下：
29

长治学院学士学位论文（设计）
Flag1：试分配模块Attempt_Allocation与安全性检查Safety_Algorithm之间接口Attempt_Allocation通过检查 flag的真假了判断是否执行。
Pro：一个地址，Safety_Algorithm返回给主模块main的信息，不为NULL时表示试分配成功，否则系统转入相应异常处理。
Flag2：Safety_Algorithm与主模块之间的接口，为真则调用打印函数，输出最终结果，否则调用恢复函数，恢复之前系统状态。
3.4 程序流程图
假设Request是进程的请求向量，Need是需求向量，Available是可利用资源向量。如果Request[j]≥Need[i,j]，则认为出错，进入等待状态。因为它所需要的资源数已经超得过最大值，否则判断Request[j]，Available[j]。如果Request[j]≥Available[j]，则表示尚无足够资源，进程需要等待。接着，系统试探着把资源分配给进程，系统执行安全性算法。检查此次分配后系统是否处于安全状态。若安全，才正式将资源分配给进程，来完成分配。否则，将本次的试探分配作废，恢复原来的资源分配。具体程序总流程图如图3所示。
Y
Y
Y
N
开始

结束

申请资源
试探分配
安全性算法
进程等待
正式分配
恢复程序
RE<NE?
RE<AVE?

系统安全？

N
N

图3 程序总流程图
4 详细设计
4.1 数据结构选取分析
该算法中用到了较多的数据，基于程序的易实现和较好的结构，决定采用结构链表，以进程为单位（结点）。
4.2 数据结构设计
typedef struct my_process
{
int num；
int Max[M]；
int Allocation[M]；
int Need[M]；
struct my_process* next；
}process；
int Available[M]={0}；
int Request[M]={0}；
int Record_work[N][M]={0}；
int Safety[N]={0}；
4.3 算法整体设计与调用
主函数void main（）主要分四大块：
（1）首先需要初始化Init_process（process **head，int m，int* count），存储系统当前状态信息；
（2）调用安全算法Safety_Algorithm，检测当前系统安全状态，若安全则进行下一步，否则打印相关信息，程序退出；
（3）调用试分配函数Attempt_Allocation，进行试分配，若试分配成功，修改相关数据结构，打印当前系统资源分布图，转下一步。否则，打印提示信息，接收其他请求向量；
（4）再次调用安全性算法，检查试分配以后的系统安全性，若安全打印安全性序列和当前系统资源分布图，并进入新一轮的执行。否则之前的试分配作废，恢复试分配之前的数据结构，输出相关提示信息，接收下一个进程请求。
4.4 程序流图
(1)系统以及进程资源初始化Init_process的程序流程图
首先，读入当前系统可用资源；然后，读入进程资源，建立进程链表，输入-1结束初始化；最后，打印当前系统资源分配表。如图4所示。
Y
N
N
Y
开始

结束

初始化int i,j=0;

Node.num=j++;

输入数据

Break；

Node.max[0]!=-1

1

图4 初始化Init_process的程序流程图
(2)安全性算法的程序流程图
首先，初识化work,finish[]。然后，判断异常情况，利用Reasonable函数找到当前可执行的进程。最后，执行安全检查，并显示检查后结果，返回给flag。如图5所示。

Y
N
开始
结束

Int num,i;

Retumn p;

请求合法性检验
Printf(“请输入请求向量\”)
Printf(“无此进程！\n”)

试分配，修改相关数据
P==null？

Y
N
Y
N
开始
结束

初始化work，finish;
i=0；

i++;
Finish[i]=p->num;

i=0;

Work[i]=avail[i];

对不同情况进行分析

P!=null?

i<m？

图6 试分配的程序流程图

图5 安全性算法的程序流程图
(3)接受进程请求，试分配的程序流程图
首先，p指针指向弧的结点。如果为空，则输出无此进程，然后，输入请求向量，检查合法性，进行试分配。如图6所示。
(4)对试分配后的系统，进行安全性检查的程序流程图
和图5大致一样，唯一一点在于当找不到安全序列时，将本次试分配作废，恢复该次试分配之前的数据结构。如图7所示。

开始

Int i;

i=0

i < m？

m？
N

Y

恢复系统资源

i ++;

结束

图7 试分配后，安全性检查的程序流程图
5 程序分析测试
5.1 分模块分析与测试
（1)初始化系统资源模块Init_process的测试

图8 初始化系统资源模块Init_process的测试
按提示输入，以-1结束整个初始化过程，并打印结果。起初效果不理想，经过一些调整后，显示才比较理想。如图8所示。
(2)试分配模块Attempt_Allocation的测试
图9 试分配模块Attempt_Allocation的测试
试分配模块，主要是在系统进入第一次安全检查后，对系统资源的一次尝试性分配，试分配完成后，相关的数据结构被修改。如图9所示。
(3)安全模块Safety_Algorithm的调试
试分配前的安全算法，结果如果输出一个安全性序列，并且经过人工检查该安全性序列，确实有效，则该模块正确,如图10所示；如果系统不安全，打印出相关信息，返回上一层。如图11所示。
图10 安全模块Safety_Algorithm的调试的安全状态
图11 安全模块Safety_Algorithm的调试的不安全状态
‚试分配后的安全算法，结果如果输出一个安全性序列，并且经过人工检查该安全性序列，确实有效，则该模块正确，如图12所示；否则，之前的试分配作废，恢复试分配前的资源状态。如图13所示。

图12 试分配后输出一个安全性序列
图13 试分配后不安全状态的资源恢复
5.2 集成测试
各模块测试通过后，集成在一起测试，系统初始资源和模块测试时保持一致，以下是测试用例以及结果，基本包括了该算法的所有情况。
（1）06： 结果： 无此进程。
（2）01： Request(2,0,2) 结果： 系统不能满足。
（3）01： Request(1,0,2) 结果： 两次安全性检查都通过，并打印出最终结果。
（4）00： Request(0,2,0) 结果： 试分配后，系统不安全，试分配作废。
（5）00： Request(0,1,0) 结果： 两次安全性检查都通过，并打印出最终结果。

6 结论
银行家算法避免死锁的研究与实现作为我的毕业设计。首先，我在网上收集了一些关于银行家算法的资料，包括它的起源，以及在实际中多个领域的应用，加深了对它的理解。之后，确定自己设计的算法分四大模块。首先需要初识化系统资源；其次，安全性检查；再者，试分配；最后是试分配后的安全性检查。
在程序测试中出现了很多问题。譬如，死循环，逻辑关系的设计不当，还有显示效果不理想等等。但通过查阅书本，对算法细节重新建立正确的认识后，再通过单步调试后，最终解决。在集成测试中，由于之前的模块测试做的比较扎实，所以相对只是一些细节上的问题，很快也达到了预期的效果。
参考文献
[1] 严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出社,2005.
[2] 汤小丹,梁红兵,哲凤屏等.计算机操作系统(第三版)[M].西安:西安电子科技大学出版社,2007.
[3] 谭浩强.C语言程序设计[M].北京:清华大学出版社,2006.
[4] 于帆,赵妮.程序设计基础[M].北京:清华大学出版社,2006.
[5] 罗宇.操作系统课程[M].北京:设计机械工业出版社,2005.
[6] 黄水松,黄干平,曾平.计算机操作系统[M].武汉:武汉大学出版社,2003.
[7] 鞠时光.操作系统原理[M].武汉:武汉理工大学出版社,2003.
[8] 何炎祥,熊前兴.操作系统原理[M].武汉:华中科技大学出版社,2001.
[9] 张丽芬,刘美华.操作系统原理教程[M].北京:电子工业出版社,2004.
[10] 陈火.数据结构与算法[M].广东:中山大学出版社,2009.
[11] 郑扣根.操作系统概念(第七版)[M].北京:高等教育出版社,1992.
[12] 赵莉,杨国梁,孙喁喁,徐飞.Java程序设计教程[M].西安:西安科技大学出版社,2009.
[13] 陈向群,向勇,王雷.Windows操作系统原理(第二版)[M].北京:北京机械工业出版社,2004.

Bankers Algorithm To Avoid Deadlock Research and Implementation
Major:Computer Science and technology Name: Wang Zidan
Student ID: 09407227 Supervisor:Shan Fenli

Abstract:Bankers algorithm what Dijkstra put forward is the most representative of the algorithm to avoid deadlock, this algorithm can be used for the banking system because of its cash loans. Bankers algorithm is advancing in the premise of ensuring the system security. The first is that security check to process requests, to determine the allocation of resources or not, so as to ensure the safety of the system, to avoid deadlock.
This paper on the understanding and analysis of the essential meaning of bankers algorithm as well as the state of the core idea, the algorithm is implemented in the overall design, including the module design of algorithm, and the algorithm of each module through a flow chart, block coding, and testing, the final program in the test, the design ideas on strictly according to the thought of software engineering implementation, to ensure that the design and implementation of feasible, credible.

Keywords: bankers algorithm; deadlock; avoid deadlock; secure sequence

致谢
在论文的写作过程中遇到了无数的困难和障碍，都在同学和老师的帮助下度过了。尤其要感谢我的论文指导老师——陕粉丽老师，她对我进行了无私的指导和帮助，不厌其烦的帮助进行论文的修改和改进。另外，在校图书馆查找资料的时候，图书馆的老师也给我提供了很多方面的支持与帮助。在此向帮助和指导过我的各位老师表示最真诚的感谢！
此外，还要感谢我的同学和朋友，在我写论文的过程中给予我很多素材，还在论文的撰写和排版的过程中提供热情的帮助。
由于我的学术水平有限，所写论文难免有不足之处，恳请各位老师批评和指正！

附录
//银行家算法
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define M 3
#define N 10
#define D12 %5d%5d%5d%5d%5d%5d%5d%5d%5d%5d%5d%5d
typedef struct my_process
{
int num;
int Max[M];
int Allocation[M];
int Need[M];
struct my_process* next;
}process;
void Insret_Tail(process **head,process node)
{
process* p=(process*)malloc(sizeof(process));
process* last=NULL;
memcpy(p,&node,sizeof(process));
p->next=NULL;
if(NULL==*head)
{
*head=p;
}
else
{
last=*head;
while(last->next!=NULL)
{
last=last->next;
}
last->next=p;
}
}
void Init_process(process **head,int m,int* count)
{
int i,j=0;
process node;
printf("请初始化一组进程,进程编号从P0开始，输入-1 结束输入:\n");
do
{
node.num=j++;
printf("请输入第 %d个进程信息 :\n",node.num);
printf("最大需求矩阵: ");
scanf("%d",&node.Max[P0]);
if(node.Max[P0]!=-1)
{
for(i=1;i<m;i++)
{
scanf("%d",&node.Max[i]);
}
printf("分配矩阵: ");
for(i=0;i<m;i++)
{
scanf("%d",&node.Allocation[i]);
}
printf("需求矩阵: ");
for(i=0;i<m;i++)
{
scanf("%d",&node.Need[i]);
}
Insret_Tail(head,node);
(*count)++;
}
else
{
break;
}
}
while(1);
}
void Print(process *head,int *avail,int m)
{
process* p=NULL;
int i,j;
char ch;
p=head;
if(NULL==p)
{
printf("当前无进程 !\n");
exit(0);
}
else
{
printf("| Process | Max | |Allocation| | Need | |Available|\n\n");
printf("\t");
for(i=0;i<4;i++)
{
ch='A';
for(j=0;j<m;j++)
{
printf("%4c",ch++);
}
printf("\t");
}
puts("");
while(p!=NULL)
{
printf("%8.2d",p->num);
for(j=0;j<m;j++)
{
printf("%4d",p->Max[j]);
}
printf("\t");
for(j=0;j<m;j++)
{
printf("%4d",p->Allocation[j]);
}
printf("\t");
for(j=0;j<m;j++)
{
printf("%4d",p->Need[j]);
}
printf("\t");
for(j=0;j<m;j++)
{
printf("%4d",avail[j]);
}
printf("\n");
p=p->next;
}
puts("");
}
}

process* Location(process* head,int pro_num)
{
process *p=NULL;
p=head;
if(NULL==p)
{
printf("error !\n");
return p;
}
else
{
while(p!=NULL)
{
if(p->num==pro_num)
{
break;
}
else
{
p=p->next;
}
}
if(NULL==p)
{
printf("无此进程 !\n");
return p;
}
else
{
return p;
}
}
}

process* Attempt_Allocation(process* head,int *request,int *avail,int m)
{
int num,i;
process* p=NULL;
printf("请输入进程编号: \n");
scanf("%d",&num);
p=Location(head,num);
if(p==NULL)
{
printf("无此进程!\n");
return p;
}
printf("请输入该进程的请求向量: \n");
for(i=0;i<m;i++)
{
scanf("%d",&request[i]);
}

for(i=0;i<m;i++)
{
if(request[i]<=p->Need[i])
{
;
}
else
{
printf("该请求系统不能满足 !\n");
return NULL;
}
}
for(i=0;i<m;i++)
{
if(request[i]<=avail[i])
{
;
}
else
{
printf("该请求系统不能满足 !\n");
return NULL;
}
}
for(i=0;i<m;i++)
{
avail[i]=avail[i] - request[i];
p->Allocation[i]=p->Allocation[i] + request[i];
p->Need[i]=p->Need[i] - request[i];
}
return p;
}

process* Reasonable(process* head,int*finish,int*work,int m,int n)
{
int i=0,j=0,count=0;
process* p=NULL;
while(1)
{
if(finish[i]!=-1)
{
p=Location(head,finish[i]);
if(p!=NULL)
{
for(j=0;j<m;j++)
{
if(p->Need[j]>work[j])
{

break;
}
else
{
continue;
}
}
if(j==m)
{
return p;
}
else
{
i++;
}
}
}
else
{
i++;
}
if(i==n)
{
return NULL;
}
}
}

void Alter_Data(process* p,int* work,int* finish,int record[][M],int m)
{
int i;
for(i=0;i<m;i++)
{
record[p->num][i]=work[i];
work[i]=work[i]+p->Allocation[i];
}
finish[p->num]=-1;
}

int Safety_Algorithm(process* head,int *avail,int *safety,int Record[][M],int m,int n)
{
int *work=NULL;
int *finish=NULL;
process *p=NULL;
process *pro=NULL;
int i,count=0;
work=(int*)malloc(m*sizeof(int));
finish=(int*)malloc(n*sizeof(int));
//safety=(int*)malloc(n*sizeof(int));
p=head;
for(i=0;i<m;i++)
{
work[i]=avail[i];
}
i=0;
while(p!=NULL)
{
finish[i]=p->num;
p=p->next;
i++;
}
i=0;
while(count<n)
{
pro=Reasonable(head,finish,work,m,n);
if(pro!=NULL) {
Alter_Data(pro,work,finish,Record,m);
count++;
safety[i]=pro->num; //
i++;
}
else
{
printf("当前系统处于不安全状态 !\n");
// remark=1;
break;
}
}
if(count==n)
{
printf("当前系统处于安全状态,存在一个安全序列 :\n");
for(i=0;i<n;i++)
{
printf("%d,",safety[i]);
}
puts("");
}
free(finish);
free(work);
finish=NULL;
work=NULL;
if(count==n)
{
return 1;
}
else
{
return 0;
}
}

void Return_Source(process* p,int *request,int *avail,int m)
{
int i;
{
for(i=0;i<m;i++)
{
p->Allocation[i]-=request[i];
p->Need[i]+=request[i];
avail[i]+=request[i];
}
}
}

void Print_After_Safety(process *head,int *safety,int work[][M],int m,int n)
{
process* p=NULL;
int i,j;
char ch;
p=head;
if(NULL==p)
{
exit(0);
}
else
{
printf("| Process | Work | | Need | |Allocation| |Work+Allocation| | Finish |\n\n");
printf("\t");
for(i=0;i<4;i++)
{
ch='A';
for(j=0;j<m;j++)
{
printf("%4c",ch++);
}
printf("\t");
}
puts("");
for(i=0;i<n;i++)
{
p=head;
while(p!=