银行家算法课程设计报告

操作系统课程设计报告题目：银行家算法设计与实现

院（系）：计算机科学与工程学院

专业：对日软件

班级：080612

学生：闫建军

学号：080608115

指导教师：姜虹

2010年12月

银行家算法设计与实现

摘要

银行家算法是一个用来预防系统进入死锁状态的算法，用它可以判断系统的安全性，如果系统当前处于安全状态，则可以为申请资源的进程分配资源，如果不是安全状态，则不能为申请资源的进程分配资源。

银行家算法执行过程中，首先判断申请资源的进程所申请的资源数目是否合法，若是合法的，则可以为其进行试分配，再利用安全性算法求出安全序列，·如果存在安全序列，则说明可以给申请资源的进程分配资源，分配成功，继续为其它进程服务。如果找不到安全序列，则说明为该进程分配资源后系统会进入不安全状态，所以不能为该进程分配资源，使该进程进入阻塞状态。若申请资源的进程申请的资源数目不合法，则不需要进行试分配，直接使其进入阻塞状态，处理其他申请资源的进程。

论文首先对算法的设计从总体上进行了分析，然后分析各个细节，再对算法分模块设计，并对各个模块的算法思想通过流程图表示，分块编写代码，并进行调试和测试，最后进行组装测试及系统测试，使其成为一个可以用来判断系统安全状态的程序。

关键词：可用资源最大需求矩阵分配矩阵需求矩阵请求向量试分配安全性算法安全序列

目录

银行家算法设计与实现 (1)

摘要 (1)

目录 (2)

1 绪论 (5)

1.1课题背景 (5)

1.2课题意义 (5)

1.3运行环境 (5)

2 需求分析 (1)

2.1问题描述 (1)

2.2基本要求 (1)

2.3概要分析 (2)

3 算法思想 (3)

3.1安全性算法的算法思想 (3)

3.1.1设置两个向量： (3)

3.1.2安全性检测 (3)

3.2银行家算法的算法思想 (4)

3.2.1 银行家算法的思路 (4)

3.2.2 银行家算法 (4)

3.2.3 安全性检查算法 (5)

4详细设计 (6)

4.1银行家算法中用到的主要数据结构设计 (6)

4.2算法整体设计与调用 (6)

4.3模块设计与时间复杂度分析 (8)

4.3.1 int check_distribution(int* p,int k)函数 (8)

4.3.2 int check_safe()银行家算法 (8)

4.3.2 void print()输出函数 (8)

4.4程序流程图 (8)

4.5.1 主函数void main（）函数流程图 (9)

4.5.2判断试分配函数int check_distribution(int* p,int k)流程图 (9)

4.5.3银行家算法int check_safe()流程图 (10)

4.5.4 输出函数void print() 流程图 (11)

5 程序调试、分析与修改 (12)

5.1分模块调试与分析 (12)

5.1.1进程信息的输入与输出调试 (12)

5.1.2 进程请求资源输入出错提示信息处理 (13)

5.1.3 判断试分配函数int check_distribution(int* p,int k) (13)

5.1.4 求安全序列函数int check_safe() (14)

6 结论 (15)

7 小结 (16)

参考文献 (17)

附录（源代码） (18)

绪论

1 绪论

1.1课题背景

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

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

1.2 课题意义

（1）从课程设计上讲，提高自己的分析问题，解决问题和动手能力；

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

1.3 运行环境

Turbo C; Visual C++ 6.0

2 需求分析

2.1 问题描述

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

2.2 基本要求

（1）对各个进程的进程名，最大需求资源，已分配资源，系统可用资源等进行有序的输入。

（2）对申请资源的进程要有合法性判断（如进程名，申请资源数等）。

（3）若有进程申请资源，首先要对它申请的资源数进行判断。

（4）在上面判断合法的前提下进行试分配，利用银行家算法求出安全序列。

如果可以求出安全序列，则为该进程分配资源，否则使它进入阻塞状态。

2.3 概要分析

在避免死锁的算法中，允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会使系统进入不安全状态，便将资源分配给该进程否则进程等待。

所谓安全状态是指系统能按某种顺序如（称为安全序列），就这样来为每个进程分配资源，直至最大需求。使每个进程都可以顺序地执行完毕。若系统不存在这样一个安全序列，那么系统此时会进入不安全状态。

虽然并非所有的不安全状态都会产生死锁状态，但当系统进入不安全状态后，便可能进而进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质在于，如何使系统不进入不安全状态，银行家算法就是用来判断某种情况会不会进入不安全状态。

3 算法思想

3.1 安全性算法的算法思想

思想:系统在进行资源分配之前，应先计算此次资源分配后状态的安全性。

若此次分配后的状态是安全状态，则将资源分配给进程；否则，令进程等待。 3.1.1设置两个向量

（1）工作向量Work[m]: 它表示系统可提供给进程继续运行所需的各类资源

数目， Work 初∶=Available;

（2） Finish[n]: 它表示系统是否有足够的资源分配给进程，使之运行完成。

false 表示未完成， true 表示完成。

3.1.2安全性检测

Work ＝Available

寻找进程i ，满足 Finish [ i]＝ false

返回安全状态

y

Work=work+Allocation i Finish [ i] ＝ true

找到

所有进程的

没找到

n 返回不安全状态

3.2 银行家算法的算法思想

3.2.1 银行家算法的思路

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

3.2.2 银行家算法

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

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

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

Available[i,j]= Available[i,j]- Request i[j]；

Allocation[i][j]= Allocation[i][j]+ Request i[j]；

need[i][j]= need[i][j]- Request i[j]；

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

(4)用while 循环语句实现输入字符Y/N判断是否继续进行资源申请。

3.2.3 安全性检查算法

(1)设置向量：

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

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

(2)在进程中查找符合以下条件的进程：

条件1：Finish[i]=0；

条件2：need[i][j]<=Work[j]

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

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

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

Finish[i]=1；

goto step 2；

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

4详细设计

4.1银行家算法中用到的主要数据结构设计

(1）进程名向量 char processnema[N]; //进程名

(2）可利用资源向量 int Available[M]; //资源清单——系统中现有各资源

空闲个数。

(3）最大需求矩阵 int Max[N][M]; //最大需求矩阵——每个进程对各

资源的最大需求数分配矩阵

(4）已分配矩阵 int Allocation[N][M];//分配矩阵——系统给每个进程已

分配的各类资源数

(5）需求矩阵 int Need[N][M]; //需求矩阵——每个进程还需要每种

资源的个数申请各类资源数量

(6）申请向量 int Request [M] //进程申请资源的向量

(7）工作向量int Work[N][M]; //初始第一个向量为

Available[],随寻找安全序列时为其余每个向量赋值，可

以防止安全序列未找到而丢了初始状态的值

(8）安全序列向量 int sequence[N]={0};//存放安全序列号

(9）标志向量 int Finish[N] //求安全序列时记录每个进程是否可以顺

利执行

4.2算法整体设计与调用

主函数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 []<=need[]或Request []<=available[]条件，不能为该进程进行试分配。

（2）int check_safe()：这个函数用来求安全序列，首先初始化Work[0][i]= Available[i]，然后循环找满足条件Finish[i]==0 && Need[i][0] <= Work[k][0]的进程，k表示最近执行的进程的进程号，找到后将进程i 加入sequence[]向量，再将Finish[i]=1，表示进程可以顺利执行则Work[k][j]=Work[k-1][j]+Allocation[i][j]，k表示同上。再继续找下一个满足条件的进程。如果单循环结束时每个进程的Finish[i]都等于1，则说明可以找到安全序列，返回1，如果不是每个Finish[i]都等于1，则说明找不到一个安全序列，返回0

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

（4）系统模块输入每个进程信息，调用银行家算法int

check_safe()判断初始状态是否安全。

主

函数若有进程申请资源，首先用int check_distribution(int* p,int k)判断是否可以试分配

4.3模块设计与时间复杂度分析

4.3.1 int check_distribution(int* p,int k)：检查是否可以试分配函数

用for(i=0; i

4.3.2 int check_safe()银行家算法

(1)用for(i=0; i

矩阵

(2)用for(m=0; m

Work[k][0] && Need[i][1] <= Work[k][1] && Need[i][2] <= Work[k][2]）条件的进程，修改各资源信息。因为是N个进程，所以最多循环N次就可以找出所有矩阵。

(3)用for(i=0; i

则finish值等于1。

(4)由上面执行可以得出int check_safe()函数时间复杂度为O(N)或O(M)。

4.3.2 void print()输出函数

for(i=0; i

4.4程序流程图

4.5.1 主函数void main（）函数流程图

（ 4-1）

4-1

4.5.2 判断试分配函数int check_distribution(int* p,int k)流程图（4-2）

4-2

4.5.3银行家算法int check_safe()流程图

(4-3)

4-3

4.5.4 输出函数void print()

流程图（4-4）

4-4

5 程序调试、分析与修改

5.1分模块调试与分析

函数的书写分模块进行，每完成一个模块进行调试、测试直到该函数运行无误。

5.1.1进程信息的输入与输出调试

(1) 能正确无误的输入进程名向量processnema[N]，输入系统现有各类资源数量Available[M]向量，输入每个进程对各类资源的最大需求数Max[N][M]矩阵，输入系统给每个进程已分配的各类资源数Allocation[N][M]矩阵。输出程序过程如下：

(2) 在进程信息输入中没有出现多大问题，在进程信息输出时，按设计要求输出的话应该是一个表格形式，在输出函数设计最初，由于有些部分分割或空格没有填充好，导致输出表格比较乱，没有达到设计要求，经过修改后输出形式才符合了设计要求，进程信息输入完成后，初始状态各进程信息输出如下：

5.1.2 进程请求资源输入出错提示信息处理

(1) 在系统询问是否有进程申请资源时，如果有输入信息出错，系统会给与出错提示，如果输入信息正确则系统将继续执行下面操作，执行如下：

5.1.3 判断是否可以试分配函数int check_distribution(int* p,int k)

(1) 在这个函数中主要是对申请资源的进程申请的资源数量是否满足约束条件Request []<=need[]或Request []<=available[],如果不满足将打出提示信息，如果满足，则返回1继续执行下面程序，执行结果如下：

5.1.4 求安全序列函数int check_safe()

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