银行家算法课程设计

操作系统课程设计报告

题目：银行家算法的设计与实现

院 （系）： 计算机信息与技术 专 业： 计算机科学与技术 班 级： B090601 学 生： 学 号： B090601 指导教师： 姜虹

2012年 6月

摘 要

Dijkstra提出的银行家算法，是最具代表性的避免死锁的算法。

本文对如何用银行家算法来处理操作系统给进程分配资源做了详细的说明，包括需求分析、概要设计、详细设计、测试与分析、总结、源程序清单。

首先做了需求分析，解释了什么是银行家算法，并指出它在资源分配中的重要作用。

然后给出了银行家算法的概要设计，包括算法思路、步骤，以及要用到的主要数据结构、函数模块及其之间的调用关系等。

在概要设计的基础上，又给出了详细的算法设计，实现概要设计中定义的所有函数,对每个函数写出核心算法，并画出了流程图。

接着对编码进行了测试与分析（并在最后附上Java编写的程序代码）。 最后对整个设计过程进行了总结。

关键词：安全状态；安全序列；银行家算法；安全性算法；安全序列；流程图。

目录

摘 要 ................................................................................................................................................ 1 1 绪论............................................................................................................................................... 1

1.1前言 ..................................................................................................................................... 1 1.2研究意义 ............................................................................................................................. 1 2 需求分析....................................................................................................................................... 3

2.1题目描述............................................................................................................................ 3 2.2银行家算法 ........................................................................................................................ 3 2.3基本要求............................................................................................................................ 3 2.4目的.................................................................................................................................... 3 3 概要设计....................................................................................................................................... 5

3.1算法思路： ........................................................................................................................ 5 3.2银行家算法步骤 ................................................................................................................ 5 3.3安全性算法步骤 ................................................................................................................ 5 3．4数据结构： ...................................................................................................................... 6 4 详细设计....................................................................................................................................... 8

4.1主要函数的核心代码： .................................................................................................... 8 4.2系统主要过程流程图 ........................................................................................................ 8 4.3银行家算法流程图 ............................................................................................................ 9 5 测试与分析................................................................................................................................. 10

5.1测试数据 ........................................................................................................................... 10 5.2银行家算法的演示 ........................................................................................................... 10 5.3分配资源由于大于可利用资源则失败。 ...................................................................... 11 5.4 增加一个作业得到不安全序列。 ................................................................................. 12 5.5分配资源由于大于最大资源则失败。 .......................................................................... 12 附录 源程序清单........................................................................................................................... 15

绪论 1 绪论

1.1前言

Dijkstra (1965)提出了一种能够避免死锁的调度算法，称为银行家算法。 它的模型基于一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，每个客户都有一个贷款额度，银行家知道不可能所有客户同时都需要最大贷款额，所以他只保留一定单位的资金来为客户服务，而不是满足所有客户贷款需求的最大单位。

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

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

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

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

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

1.2研究意义

在多道程序系统中，多个进程的并发执行来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险——死锁。所谓死锁(Deadlock)，是指多个进

程在运行过程中因争夺资源而造成的一种僵局（DeadlyEmbrace），当进程处于这种状态时，若无外力作用，他们都无法在向前推进。

要预防死锁，有摒弃“请求和保持”条件，摒弃“不剥夺”条件，摒弃“环

1

西安工业大学北方信息工程学院 路等待”条件等方法。

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

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

需求分析 2 需求分析

2.1题目描述

银行家算法是一种最具有代表性的避免死锁的算法。

要解释银行家算法，必须先解释操作系统的安全状态和不安全状态。 所谓安全状态，是指系统能按照某种进程顺序{P1,P2,„，Pn}（称{P1,P2,„，Pn }序列为安全序列），来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺利完成。安全状态一定没有死锁发生。

如果系统无法找到这样一个安全序列，则称系统处于不安全状态。 那么，什么是安全序列呢？

如果对每一个进程Pi(12.2银行家算法

我们可以把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求资源相当于客户向银行家贷款。

操作系统按银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程尚需求的资源量，若是系统现存的资源可以满足它尚需求的资源量，则按当前的申请量来分配资源，否则就推迟分配。

当进程在执行中继续申请资源时，先测试该进程申请的资源量是否超过了它尚需的资源量。若超过则拒绝分配，若没有超过则再测试系统尚存的资源是否满足该进程尚需的资源量，若满足即可按当前的申请量来分配，若不满足亦推迟分配。

2.3基本要求

（1）设计用来保存：可利用资源向量Available、最大需求矩阵 Max、分配矩阵 Allocation 、需求矩阵 Need。（2）编写银行家算法，安全性检测算法。要求在不安全时输出错误信息。

（3）编写输出函数，能对进程申请后的系统状态进行输出。

2.4目的

根据设计题目的要求，充分地分析和理解题目，叙述系统的要求，明确程序

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;

5

西安工业大学北方信息工程学院

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

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

①Finish[i]=false

②Need< =Work;如找到，执行步骤（3）；否则，执行步骤（4）。 （3）当进程P获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

Work=Work+Allocation;

Finish[i]=true; 转向步骤（2）。

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

3．4数据结构：

3.4.1主要用到的数据结构： (1) 最大需求矩阵Max[][] (2) 已分配矩阵Allocation[][]

(3) 仍需求矩阵Need[][]=Max[][]-Allocation[][] (4) 可利用资源向量Available[] (5) 申请各类资源向量Request[]

(6) 工作向量 work[] , Finish[]

（7）存放安全序列 temp[] (8) 存放系统可提供资源 work[] (9)资源的名字 name[] 3.4.2程序模块： int main()//主函数

西安工业大学北方信息工程学院 void showdata()//显示资源矩阵 int changdata(int i)//进行资源分配 int safe()//安全性算法

void share()//利用银行家算法对申请资源对进行判定 void addresources(){//添加资源 void changeresources(){//修改资源函数

void addprocess(){//添加作业

3.4.3各模块间的调用关系： 主函数void main()

要调用： showdata()，safe()，addresources()，

addprocess(),changeresources(),changdata(int i)

安全性检测函数safe() 银行家算法函数share()

要调用 changdata(int i), showdata(),safe()

7

西安工业大学北方信息工程学院 4 详细设计

4.1主要函数的核心代码：

1. 进行初始化输入的函数 2. 输出的函数

3. 利用安全性算法进行检测的函数 4. 进行资源分配的函数

5. 利用银行家算法进行判定的函数

4.2系统主要过程流程图

图4.1 主要流程图

西安工业大学北方信息工程学院 4.3银行家算法流程图

图4.2 银行家流程图

9

西安工业大学北方信息工程学院 5 测试与分析

5.1测试数据

本次测试一共5个进程，分别为p0、p1、p2、p3、p4.，资源分配情况如下表： 资源情况 Max Allocation Need Available A B C A B C A B C A B C 进程 P0 P1 P2 P3 P4 结果截图：

7 5 3 3 2 2 0 9 2 2 2 2 4 3 3 0 1 0 2 0 0 3 0 2 2 1 1 0 0 2 7 4 3 1 2 2 6 0 0 0 1 1 4 3 1 3 3 2 图5.1

5.2银行家算法的演示

测试与分析 进行资源的分配，为进程1分配了（1，0，2），进行安全算法得到如下的结果。

图5.2

5.3分配资源由于大于可利用资源则失败。

图5.3

11

西安工业大学北方信息工程学院 5.4 增加一个作业得到不安全序列。

图5.4

5.5分配资源由于大于最大资源则失败。

图5.5

总结

6 总结

操作系统的基本特征是并发与共享。系统允许多个进程并发执行，并且共享系统的软、硬件资源。为了最大限度的利用计算机系统的资源，操作系统应采用动态分配的策略，但是这样就容易因资源不足，分配不当而引起“死锁”。而我本次课程设计就是得用银行家算法来避免“死锁”。银行家算法就是一个分配资源的过程，使分配的序列不会产生死锁。此算法的中心思想是：按该法分配资源时，每次分配后总存在着一个进程，如果让它单独运行下去，必然可以获得它所需要的全部资源，也就是说，它能结束，而它结束后可以归还这类资源以满足其他申请者的需要。

在程序当中，我们也得强调一下对输入的合法性的判断。比如，我们输入的欲申请资源的进程号没有在系统已存在的进程当中，或者进程号定义为整型，但是却错输成字母等情况，我们需要对这些情况进行判断，让程序报错返回而并非因错误而中断。

这样的情况处理起来比较麻烦，相当于对每次输入针对各种不同的情况都得做判断。我也没有涵盖全部的输入，仅仅只是对输入的进程号不在已存在进程当中、以及输入的操作选择不存在两种情况分别作了判断，并且针对第二种情况设定了五次输入错误的话系统关闭的功能。而因为对于某些——比如进程号——本来设定就是整型，因此对输入的是字母的判别因比较复杂而未能加上。

总之，银行家算法是避免死锁的主要方法，其思路在很多方面都非常值得我们来学习借鉴。

13

西安工业大学北方信息工程学院 参考文献

[1] 汤小丹，梁红兵，哲凤屏，汤子瀛.计算机操作系统. 西安：西安电子科技大学出版社，2007.

[2] 严蔚敏，吴伟民.数据结构. 北京：清华大学出版社，2006.

14

附录：原程序清单 附录 源程序清单

#include #include #include #define False 0 #define True 1

int Max[100][100]={0};//各进程所需各类资源的最大需求 int Avaliable[100]={0};//系统可用资源 char name[100]={0};//资源的名称

int Allocation[100][100]={0};//系统已分配资源 int Need[100][100]={0};//还需要资源 int Request[100]={0};//请求资源向量 int temp[100]={0};//存放安全序列

int Work[100]={0};//存放系统可提供资源 int M=100;//作业的最大数为100 int N=100;//资源的最大数为100 void showdata()//显示资源矩阵 { int i,j;

cout<<\"系统目前可用的资源[Avaliable]:\"<cout<for (j=0;jcout<cout<<\" Max Allocation Need\"<cout<for(i=0;icout<<\" \"<cout<cout<15

西安工业大学北方信息工程学院

for(j=0;jcout<int changdata(int i)//进行资源分配 { int j;

for (j=0;jAvaliable[j]=Avaliable[j]-Request[j];

Allocation[i][j]=Allocation[i][j]+Request[j]; Need[i][j]=Need[i][j]-Request[j]; }return 1; }

int safe()//安全性算法 {

int i,k=0,m,a,Finish[100]={0}; int j;

int flag=0;

Work[0]=Avaliable[0]; Work[1]=Avaliable[1]; Work[2]=Avaliable[2]; for(i=0;ifor(j=0;jif (Finish[i]==False&&Need[i][j]<=Work[j]){ a++;

if(a==N){

for(m=0;mWork[m]=Work[m]+Allocation[i][m];//变分配数 Finish[i]=True; temp[k]=i; i=-1; k++; flag++; } } } }

for(i=0;iif(Finish[i]==False){

cout<<\"系统不安全\"<16

西安工业大学北方信息工程学院 } }

cout<<\"系统是安全的!\"<for(i=0;i\"; }

cout<void share()//利用银行家算法对申请资源对进行判定 {

char ch; int i=0,j=0; ch='y';

cout<<\"请输入要求分配的资源进程号(0-\"<>i;//输入须申请的资源号

cout<<\"请输入进程 \"<cout<cin>>Request[j];//输入需要申请的资源 }

for (j=0;jif(Request[j]>Need[i][j])//判断申请是否大于需求，若大于则出错 {

cout<<\"进程 \"<break; }

else {

if(Request[j]>Avaliable[j])//判断申请是否大于当前资源，若大于则 { //出错

cout<<\"进程\"<if(ch=='y') {

changdata(i);//根据进程需求量变换资源

17

西安工业大学北方信息工程学院 showdata();//根据进程需求量显示变换后的资源 safe();//根据进程需求量进行银行家算法判断 } }

void addresources(){//添加资源 int n,flag;

cout<<\"请输入需要添加资源种类的数量:\"; cin>>n; flag=N; N=N+n;

for(int i=0;i>name[flag]; cout<<\"数量:\";

cin>>Avaliable[flag++]; }

showdata(); safe(); }

void delresources(){//删除资源 char ming; int i,flag=1;

cout<<\"请输入需要删除的资源名称：\"; do{

cin>>ming; for(i=0;iif(ming==name[i]){ flag=0; break; } if(i==N)

cout<<\"该资源名称不存在，请重新输入：\"; }

while(flag);

for(int j=i;jname[j]=name[j+1];

Avaliable[j]=Avaliable[j+1]; } N=N-1; showdata(); safe(); }

void changeresources(){//修改资源函数

18

西安工业大学北方信息工程学院 cout<<\"系统目前可用的资源[Avaliable]:\"<cout<>Avaliable[0]>>Avaliable[1]>>Avaliable[2]; cout<<\"经修改后的系统可用资源为\"<cout<void addprocess(){//添加作业 int flag=M; M=M+1;

cout<<\"请输入该作业的最大需求量[Max]\"<>Max[flag][i];

Need[flag][i]=Max[flag][i]-Allocation[flag][i];} showdata(); safe(); }

int main()//主函数 {

int i,j,number,choice,m,n,flag; char ming;

cout<<\"*****************资源管理系统的设计与实现*****************\"<>n; N=n;

for(i=0;i{ cout<<\"资源\"<>ming; name[i]=ming;

cout<<\"资源的数量:\"; cin>>number;

Avaliable[i]=number; }

cout<cout<<\"请输入作业的数量:\"; cin>>m;

M=m; cout<<\"请输入各进程的最大需求量(\"<19

西安工业大学北方信息工程学院 cin>>Max[i][j]; do{ flag=0;

cout<<\"请输入各进程已经申请的资源量(\"<cin>>Allocation[i][j];

if(Allocation[i][j]>Max[i][j]) flag=1;

Need[i][j]=Max[i][j]-Allocation[i][j]; } if(flag)

cout<<\"申请的资源大于最大需求量，请重新输入!\\n\"; }

while(flag);

showdata();//显示各种资源

safe();//用银行家算法判定系统是否安全 while(choice)

{ cout<<\"**************银行家算法的演示***************\"<cout<<\"*******************************************\"<>choice; switch(choice) {

case 1: addresources();break; case 2: delresources();break; case 3: changeresources();break; case 4: share();break;

case 5: addprocess();break; case 0: choice=0;break;

default: cout<<\"请正确选择功能号(0-5)!\"<} return 1; }

20