银行家算法实验报告

操作系统课程设计报告

题目：银行家算法

院（系）：计算机学院

专业：计算机科学与技术

班级：

学生：

学号：

指导教师：

2012年 01月

摘要

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

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

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

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

目录

一、绪论 ............................................. 1

二、需求分析 ......................................... 2

三、算法分析 ......................................... 3

四、详细设计 ......................................... 4

五、程序调试 ......................................... 7

六、总结 ............................................ 10

参考文献 ............................................ 11

附录（源代码） ...................................... 12 操作系统课程设计（银行家算法）

1

一、 绪论

1.1前言

Dijkstra (1965)提出了一种能够避免死锁的调度算法，称为银行家算法。

它的模型基于一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，每个客户都有一个贷款额度，银行家知道不可能所有客户同时都需要最大贷款额，所以他只保留一定单位的资金来为客户服务，而不是满足所有客户贷款需求的最大单位。

这里将客户比作进程，贷款比作设备，银行家比作系统。

客户们各自做自己的生意，在某些时刻需要贷款。在某一时刻，客户已获得的贷款和可用的最大数额贷款称为与资源分配相关的系统状态。一个状态被称为是安全的，其条件是存在一个状态序列能够使所有的客户均得到其所需的贷款。如果忽然所有的客户都申请，希望得到最大贷款额，而银行家无法满足其中任何一个的要求，则发生死锁。不安全状态并不一定导致死锁，因为客户未必需要其最大贷款额度，但银行家不敢抱这种侥幸心理。

银行家算法就是对每一个请求进行检查，检查如果满足它是否会导致不安全状态。若是，则不满足该请求；否则便满足。

检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户。如果可以，则这笔投资认为是能够收回的，然后接着检查下一个距最大需求最近的客户，如此反复下去。

如果所有投资最终都被收回，则该状态是安全的，最初的请求可以批准。

1.2研究意义

在多道程序系统中，多个进程的并发执行来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险——死锁。所谓死锁(Deadlock)，是指多个进程在运行过程中因争夺资源而造成的一种僵局（DeadlyEmbrace），当进程处于这种状态时，若无外力作用，他们都无法在向前推进。

要预防死锁，有摒弃“请求和保持”条件，摒弃“不剥夺”条件，摒弃“环路等待”条件等方法。

但是，在预防死锁的几种方法之中，都施加了较强的限制条件；而在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统状态分为安全状态和不安全状态，便可避免死锁的发生。

而最具代表性的避免死锁的算法，便是Dijkstra的银行家算法。 操作系统课程设计（银行家算法）

2 利用银行家算法，我们可以来检测CPU为进程分配资源的情况，决定CPU是否响应某进程的的请求并为其分配资源，从而很好避免了死锁的产生。

二、 需求分析

2.1问题描述

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

2.2基本要求

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

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

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

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

2.3概要分析

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

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

虽然并非所有的不安全状态都会产生死锁状态，但当系统进入不安全状态后，便可能进而进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死 操作系统课程设计（银行家算法）

3 锁状态。因此，避免死锁的实质在于，如何使系统不进入不安全状态，银行家算法就是用来判断某种情况会不会进入不安全状态。

三、算法分析

3.1算法思路

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

3.2银行家算法步骤

（1）如果Requesti＜or =Need,则转向步骤(2)；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。

（2）如果Request＜or=Available,则转向步骤（3）；否则，表示系统中尚无足够的资源，进程必须等待。

（3）系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值：

Available=Available-Request[i];

Allocation=Allocation+Request;

Need=Need-Request;

(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。

3.3安全性算法步骤

（1）设置两个向量

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

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

（2）从进程集合中找到一个能满足下述条件的进程：

①Finish[i]=false

②Need

如找到，执行步骤（3）；否则，执行步骤（4）。

（3）当进程P获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： 操作系统课程设计（银行家算法）

4 Work=Work+Allocation;

Finish[i]=true;

转向步骤（2）。

（4）如果所有进程的Finish[i]=true,则表示系统处于安全状态；否则，系统处于不安全状态。

四、详细设计

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 check_safe() //银行家算法函数

void print() //输出函数

4.3模块设计与复杂度分析