银行家算法课程设计

武汉工程大学 计算机科学与工程学院

综合设计报告

设计名称： 操作系统综合设计 设计题目： 进程死锁 学生学号： 专业班级：

学生姓名：

学生成绩： 指导教师（职称）： 张立（讲师） 完成时间：至

武汉工程大学计算机科学与工程学院 制

说明：

1、报告中的第一、二、三项由指导教师在综合设计开始前填写并发给每个学生；四、五两项（中英文摘要）由学生在完成综合设计后填写。 2、学生成绩由指导教师根据学生的设计情况给出各项分值及总评成绩。 3、指导教师评语一栏由指导教师就学生在整个综合设计期间的表现、设计完成情况、报告的质量及答辩等方面，给出客观、全面的评价。 4、所有学生必须参加综合设计的答辩环节。凡不参加答辩者，其成绩一律按不及格处理。答辩小组成员应由2人及以上教师组成。

5、报告正文字数一般应不少于5000字，也可由指导教师根据本门综合设计的情况另行规定。

6、平时表现成绩低于6分的学生，其综合设计成绩按不及格处理。 7、此表格式为武汉工程大学计算机科学与工程学院提供的基本格式（适用于学院各类综合设计），各教研室可根据本门综合设计的特点及内容做适当的调整，并上报学院批准。

答辩记录表

成绩评定

目录

摘 要 ……………………………………………………………………………………… I 第一章 课题概述 …………………………………………………………………………1 1.1 课题背景 ………………………………………………………………………………1 1.2 课题意义 ………………………………………………………………………………1 第二章 设计简介及设计方案论述 ………………………………………………………2 2.1 设计描述 ………………………………………………………………………………2 2.2 设计思想 ………………………………………………………………………………2 2.3 设计要求 ………………………………………………………………………………2 2.4 设计流程图 …………………………………………………………………………3 第三章 详细设计 …………………………………………………………………………4 3.1 银行家算法的算法思想…………………………………………………………………4 3.2 安全性检查算法 ……………………………………………………………………4 3.3算法整体设计与调用 …………………………………………………………………5 第四章 设计结果及分析 …………………………………………………………………6 4.1 程序输入部分 …………………………………………………………………………6 4.3 资源分配成功结果输出 …………………………………………………………………7 4.4 资源分配失败结果输出…………………………………………………………………7 总 结 致 谢

……………………………………………………………………………………8 ……………………………………………………………………………………9

参考文献 …………………………………………………………………………………10 附录： ………………………………………………………………………………………11

摘 要

银行家算法是一个避免死锁的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。在银行家算法执行过程中，首先判断申请资源的进程所申请的资源数目是否合法，若是合法的，则可以为其进行试分配，再利用安全性算法求出安全序列，如果存在安全序列，则说明可以给申请资源的进程分配资源，分配成功，继续为其它进程服务。如果找不到安全序列，则说明为该进程分配资源后系统会进入不安全状态，所以不能为该进程分配资源，使该进程进入阻塞状态。若申请资源的进程申请的资源数目不合法，则不需要进行试分配，直接使其进入阻塞状态，处理其他申请资源的进程。

关键词：计算机操作系统；安全性算法；银行家算法

Abstract

Banker algorithm is a famous algorithm to avoid deadlock, by Ezra pound, dijkstra in 1965 to T.H.E system design of a kind of avoid deadlock algorithm. It is based on bank lending system allocation strategy, determine and ensure the safe operation of the system. In the execution of a banker algorithm, first determine the number to apply for the application of the process of resources is legal, if it is legal, you can try to carry out distribution, recycling security algorithm and security sequence, if there is a safe sequence, then to apply for the process of resource allocation of resources, distribution of success, to continue to serve other processes. If you cannot find security sequence, after the allocation of resources for the process system will enter the unsafe condition, so can't for the process allocation of resources, blocking the process into the state. If applying for the process of resource for the number of resources, illegal trial distribution is not required, and make it into the blocked state directly, to handle the applications for other resources.

Keywords：Banker algorithm；OS；Security algorithm

第一章 课题概述

1.1 课题背景

在预防死锁的各种算法中，总的来说，都是施加了较强的限制条件，从而使实现简单，但却严重地损害了系统的性能。在避免死锁的算法中，施加的条件较较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统处于安全状态，便可避免死锁的发生。

最具有代表性的避免死锁的算法是Dijkstra的银行家算法。这是因为该算法能用于银行系统现金贷款的发放而得名，在这一次的课程设计中就要对银行家算法从分析到实现，整体做一个详细的描述。

1.2 课题意义

从课程设计上讲，该课程设计可以提高自己的分析问题，解决问题和动手能力，并对银行家算法有更深刻的理解。

从银行家算法上本身讲，通过算法可以判断系统的安全性，对申请资源的进程进行限制，从而避免系统进入死锁状态。

第二章 设计简介及设计方案论述

2.1 设计描述

当系统在进行资源管理时，如果对进城申请的资源分配不当，可能会使系统进入死锁状态，因而后面到来的进程也无法顺利执行。银行家算法中，要对当前申请资源的进程申请资源的数目进行判断，如果可以试分配，则试求出一个安全序列，如果可以求出，则说明给这个进程分配资源后系统不会进入不安全状态，将该进程申请的资源分配给他，若求不出安全序列，则说明将资源分配给该进程后系统会进入不安全状态，所以就使该进程进入阻塞状态，等待以后可以分配资源时再执行该进程，然后系统继续服务其它进程。通过这样一个过程，可以有效避免系统进入死锁状态。

2.2 设计思想

在避免死锁的算法中，允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会使系统进入不安全状态，便将资源分配给该进程否则进程等待。所谓安全状态是指系统能按某种顺序如，就这样来为每个进程分配资源，直至最大需求。使每个进程都可以顺序地执行完毕。若系统不存在这样一个安全序列，那么系统此时会进入不安全状态。虽然并非所有的不安全状态都会产生死锁状态，但当系统进入不安全状态后，便可能进而进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质在于，如何使系统不进入不安全状态，银行家算法就是用来判断某种情况会不会进入不安全状态。

2.3 设计要求

（1）对各个进程的进程名，最大需求资源，已分配资源，系统可用资源等进行的输入。 （2）对申请资源的进程要有合法性判断（如进程名，申请资源数等）。 （3）若有进程申请资源，首先要对它申请的资源数进行判断。

（4）在上面判断合法的前提下进行试分配，利用银行家算法求出安全序列。如果可以求出安全序列，则为该进程分配资源，否则使它进入阻塞状态。

2.4 设计流程图

否

图2.4 程序总体流程图

第三章 详细设计

3.1 银行家算法的算法思想

先对用户提出的请求进行合法性检查，即检查请求的是不大于需要的，是否不大于可利用的。若请求合法，则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态，拒绝申请。 当进程i发出申请资源请求：

(1)调用分配检查函数检查申请量是否不大于需求量再检查检查申请量是否小于系统中的可利用资源数量：若条件不符重新输入，不允许申请大于需求量。

(2)若以上条件都满足，则系统试探着将资源分配给申请的进程，并修改Available，Allocation和Need中的数值。

3.2 安全性检查算法

首先设置变量：工作数组Work，它表示系统可提供给进程继续运行所需的各类资源数目，在执行安全性算法开始时，Work[]= Available[]。Finish[]，它表示系统是否有足够的资源分配给每个进程，使之运行完成。开始时先做Finish[i]=0；当有足够的资源分配给进程时，再令Finish[i]=1。

然后再在进程中查找符合以下条件的进程：

条件1：Finish[i]=0； 条件2：Need[i][j]

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

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

Work[j]= Work[j]+ Allocation[i][j]； Finish[i]=1；

最后循环检查是否所有的Finish[i]=1都满足，如果是，则返回1表示系统处于安全状态，否则，返回0表示系统处于不安全状态。

3.3算法整体设计与调用

主函数void main()，首先输入每个进程信息，然后判断是否有进程申请资源，若有，则调用int check_distribution(int* p,int k)函数判断是否可以进行试分配，如果满足试分配条件，调用int check_safe()函数求安全序列，如果可以求出安全序列，则说明分配后系统不会进入不安全状态，正式将资源分配给申请资源的进程，最后用void print()函数输出分配资源后每个进程的信息。如果求不出安全序列，说明分配后系统会处于不安全状态，则不能将资源分配给该进程，让其等待，系统恢复原始状态。如果申请资源的数量不满足条件，则让该进程等待。继续判断其他申请资源的进程。

其他函数：

（1）int check_distribution(int* p,int k)：这个函数用来判断是否可以进行试分配，如果函数结果返回1，说明可以进行试分配，如果函数返回0，说明申请资源的进程申请的资源数目不满足Request []

（2）int check_safe()：这个函数用来求安全序列，首先初始化Work[0][i]= Available[i]，然后循环找满足条件 Finish[i]==0 && Need[i][0]

( 3 ) void print()：这个函数用来输出进程信息，按表格形式输出，并且输出顺序和安全序列相同，便于查看进程执行的执行过程，并且在执行过程中各矩阵信息变化也很容易跟踪查看。

第四章 设计结果及分析

4.1 程序输入部分

图4.1 程序输入部分

如图4.1所示，输入进程名向量processnema[N]，输入系统现有各类资源数量Available[M]向量，输入每个进程对各类资源的最大需求数Max[N][M]矩阵，输入系统给每个进程已分配的各类资源数Allocation[N][M]矩阵。

4.2 输出资源分配矩阵

图4.2 输出资源分配矩阵

进程信息输入完成后，初始状态各进程信息输出如图4.2所示。

4.3 资源分配成功结果输出

图4.3 资源分配成功结果

如果申请资源的进程申请的资源数目满足试分配条件，则再用check_safe()函数来求试分配后的安全序列，如果可以求出安全序列，则说明这次分配不会使系统进入不安全状态，正式将资源分配给该进程，修改系统资源信息。如果求不出安全序列，说明这次分配后系统会进入不安全状态，不能给该进程分配资源，系统恢复初始状态，打印出提示信息，执行结果如图4.3所示。

4.4 资源分配失败结果输出

图4.4 资源分配失败结果

由图4.1、图4.2、图4.3、图4.4运行结果举例可以看出本系统界面简洁明了大方，而且在人机交互上化繁为简。结果输出准确无误，自然得体，让用户一目了然。

总 结

课程设计是每一个大学生在大学生涯中都不可或缺的，它使我们在实践中了巩固了所学的知识、在实践中锻炼自己的动手能力；实习又是对每一位大学生所学专业知识的一种拓展手段，它让我们学到了很多在课堂上根本就学不到的知识,不仅开阔了自己的视野，增长了自己的见识，也为我们以后进一步走向社会打下了坚实的基础，是我们走向以后走向工作岗位的奠基石。

在这一个星期的课程设计的时间中，我得到了很多收获，这是一次难得的经历。我的编程技巧和能力在这一次的设计中进步了很多。

致 谢

在课程设计中，要特别感谢张老师给予我这次设计的机会，并且在他的悉心的监督和指导下，本次课程设计才能圆满完成。同时也要感谢各位同学们的指导，和同学们的讨论和交流是完成我这次课程设计不可忽视的一部分。还要感谢给我提供良好实验环境的学校。如果没有老师们和同学们还有学校的支持与帮助，本次课程设计不能这么顺利的完成。再次感谢老师和同学的帮助，使我能够圆满完成这次课程设计，为我以后的专业学习打下了良好的基础。

参考文献

[1] 汤子瀛，哲凤屏，汤小丹．计算机操作系统[M]．西安电子科技大学出版社，2007． [2] 谭浩强．C语言程序设计[M]．清华大学出版社，2010． [3] 苏仕华．数据结构课程设计[M]．机械工业出版社，2005

附录：

#include #include #define N 5 //进程个数 #define M 3 //资源种类数 void print(); int check_safe();

int check_distribution(int* p, int k); char Process_Name[N]; //进程名 int Request[M]; int Finish[N]; 而丢了初始状态的值

int Available[M]; //资源清单——系统中现有各资源空闲个数 int Work_Allocation[N][M];

int Max[N][M]; //最大需求矩阵——每个进程对各类资源的最大需求数 int Allocation[N][M]; //分配矩阵——系统给每个进程已分配的各类资源数 int Need[N][M]; //需求矩阵——每个进程还需要每种资源的个数 int sequence[N] = { 0 }; //存放安全序列号 void main() {

printf("->请输入现有各资源空闲个数:\n"); for (i = 0; i

//请求数组

//标记某一个进程是否可以执行

int Work[N][M]; //初始为Available[][],随寻找安全序列而变化，防止安全序列未找到

int i = 0, j = 0, k = 0; //记录申请资源的进程的序列号 int flag = 0; //标记输入的进程名是否存在

int safe = 0; //标志系统是否出于安全状态,0表示不安全，1表示安全 int distribution = 0; //标志是否可以进行试分配0表示可以，1表示不可以 char flag1; //标记是否有进程申请资源 char name; //要请求资源的进程名

printf("----------------------------------------\n"); printf("*********** 银行家算法 ***********\n"); printf("----------------------------------------\n\n"); printf("->请输入各进程的进程名:\n"); //进程名连续输入 for (i = 0; i

scanf("%c", &Process_Name[i]);

scanf("%d", &Available[i]);

//输出界面 print(); //检查初始状态是否安全 safe = check_safe(); if (0 == safe) { }

- 12 - printf("->请分别输入每个进程对各类资源的最大需求数:\n"); for (i = 0; i请分别输入系统给每个进程已分配的各类资源数\n"); for (i=0; i

{ } while (1) { safe = 0; getchar(); printf("是否有进程请求系统资源...? (Y/N) \n"); flag1 = getchar(); if ('Y' == flag1 || 'y' == flag1) { } else if ('N' == flag1 || 'n' == flag1) { }

- 13 - printf("系统处于安全状态，可以为进程分配资源。\n"); printf("请输入进程名:"); getchar(); while (1) { } scanf("%c", &name); for (i = 0; i

{ } printf("请输入该进程请求各类资源的数量\n"); for (i = 0; i

- 14 -

} } } printf("该进程申请的资源太多，无法分配，请等待。。。\n"); continue;

void print()

{

");

}

int check_distribution(int* p, int k) {

int i = 0; int safe1 = 0, safe2 = 0;

- 15 - int i, j; printf(" 资源 Work Need\tAllocation\tWork+Allocation\t Finish\n"); printf(" 进程名 A B C A B C \t A B C \t A B C\n"); printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\nfor (i = 0; i

}

for (i = 0; i

int check_safe() //检查是否安全，求安全序列 {

if (0 == Finish[i] && Need[i][0]

- 16 - int i = 0, j = 0, k = 0, m = 0; int finish = 0; for (i = 0; i

}

} } } } } Work[k][j] = Work[k - 1][j] + Allocation[i][j]; //更新WOrk值 for (i = 0; i

- 17 -