银行家算法课程设计实验报告

滁州学院

课程设计报告

课程名称： 操作系统

设计题目： 银行家算法的设计与实现 系 别： 计算机与信息工程学院 专 业： 计算机科学与技术 组 别： 第二组 起止日期: 2012年5月14日 ~ 2012年6月19日 指导教师: 马丽生

1

课程设计题目 组长 张震 系别 计算机 李梦 2010211102 马岩 2010211109 组员 蒋路路 2010211095 严路路 2010211132 指导教师 课程设计目的 课程设计所需环境 课程设计任务要求 马丽生 熟练掌握银行家算法 Vc++，windows xp 编写带有界面的银行家算法程序 课程设计工作进度计划 序号 起止日期 1 2012/5/14~2012/5/21 工 作 内 容 查询相关资料，了解银行家算法的主要目的及编写方式 分工情况 张震负责对银行家算法的整体思想过程以及了解函数总体编写 李梦、严路路负责查找银行家算法的输出算法的实现编写过程 马岩、蒋路路负责对安全性检测的方式的实现查找 各个组员对各自部分的代码编写 共同解决程序中的相应错误 编写word文档，仔细检查发现各类问题 银行家算法的设计和实现 学号 2010211148 班级 10计科2班 专业 计算机科学与技术 2 3 4 2011/5/22~2011/6/5 2011/6/6~2011/6/13 进行代码设计 调试程序 2011/6/13~2011/6/19 文档编写及最终修订 指导教师签字： 年 月 日 教研室审核意见： 教研室主任签字： 年 月 日 2

目录

1. 引言 ................................................................................................................................................................ 4 2. 设计要求 ....................................................................................................................................................... 4 2.1.问题描述 .................................................................................................................................................. 4 2.2.基本要求 .................................................................................................................................................. 4 3.设计分析 .......................................................................................................................................................... 5 3.1.安全性算法的算法思想 ............................................................................................................................... 5

3.1.1.设置向量 .................................................................................................................. 5

3.1.2.安全性检测流程图 .................................................................................................. 6

3.2.银行家算法的算法思想 ............................................................................................................................... 7

3.2.1.银行家算法的思路 .................................................................................................. 7

3.2.2. 银行家算法 ............................................................................................................ 7 3.2.3. 银行家算法流程图 ................................................................................................ 8

4.详细设计 ........................................................................................................................................................ 10 4.1.银行家算法中用到的主要数据结构设计....................................................................................................... 10 4.2.算法整体设计与调用 ................................................................................................................................ 10 4.3.模块设计 ................................................................................................................................................ 11

4.3.1.安全性算法 ............................................................................................................ 11

4.3.2.输出算法 ................................................................................................................ 13 4.3.3.整体函数设计 ........................................................................................................ 14

5.调试与操作说明 ............................................................................................................................................... 19 5.1运行程序 ................................................................................................................................................. 19 6.课程设计的总结与体会 ..................................................................................................................................... 21 6.1.总结....................................................................................................................................................... 21 6.2.体会....................................................................................................................................................... 21

3

1. 引言

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

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

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

2. 设计要求

2.1.问题描述

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

2.2.基本要求

1) 创建用来保存资源和进程的数据结构，本实验用二维数组实现。所要保存的项目包括进程名称、数目、资源数目、最大需求数目、已分配数目、仍需数目及当前状态可利用数目。

2) 编写格式输出函数，本实验输入的数据以矩阵的方式输出。编写安全状态判断函数，

4

要求对输入的可用资源数目进行安全性判断，以及对进程提出的请求进行判断是否符合安全性原则。若存在，则输出一个安全序列。编写银行家算法函数，要求对资源申请后的系统状态进行对应的输出，包括正确的情况输出和错误情况输出。 3) 在用户输入所有初始化信息后，首先对信息以矩阵形式输出，再输入一组可用资源

数目，此时系统判断是否存在安全序列，若有则输出一个安全路径；若无，则表示初始化不正确，请重新输入。在已经安全的前提下，某进程提出资源盛情，包括进程名称、盛情资源项目，在判断是否安全，进而给出资源分配以及安全路径，输出分配后系统状态。若不能，返回。

3.设计分析

3.1.安全性算法的算法思想

思想:系统在进行资源分配之前，应先计算此次资源分配后状态的安全性。若此次分配后的状态是安全状态，则将资源分配给进程；否则，令进程等待。

3.1.1.设置向量

⒈设置向量：

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

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

⒉在进程中查找符合以下条件的进程： 条件1：Finish[i]=ture； 条件2：need[i][j]<=work[j]

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

⒊当进程获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： work[j]= work[j]+ allocation[i][j]； Finish[i]=ture； goto step 2；

5

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

3.1.2.安全性检测流程图

调用check()函数 work[]=available[] finish[]=false N need[][]<=work[] finish[]=false ? Y work[]=work[]+allocation[][] finish[]=true 所有进程的finish[]==true? Y N 输出安全序列，并打印输出提示：系统不安全 出当前资源分配情况 调用结束

6

3.2.银行家算法的算法思想

3.2.1.银行家算法的思路

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

3.2.2. 银行家算法

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

⒈ 利用通过request[m]和available[m]的关系检查申请量是否不大于需求量再检查检查申请量是否不大于系统中的可利用资源数量：若条件不符重新输入，不允许申请大于需求量。

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

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]；

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

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

7

3.2.3. 银行家算法流程图

8

系统初始化 输入进程个数no1 输入资源类数no2 输入进程最大需求矩阵Max、已分配矩阵Allocation和可利用资源矩阵Available Need[][]=Max[][]-Allocation[][] 打印输出此时资源分配情况表 输入欲申请资源进程号 N 输入是否合法 Y 输入该进程申请的资源量 Y Y Request[]>Need[][]? 继续分配(Y)? or Y 退出(N)? N Request[]>Available[][]? N 预分配 N 调用check()函数进行安全性检查 退出系统 9

4.详细设计

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

⒈进程向量 int no1; //进程数 2.资源数向量 int no2; //资源数

3.可利用资源向量 int available[m]; //资源清单——系统中现有各资源空闲个数。

⒊最大需求矩阵 int max[m][m]; //最大需求矩阵——每个进程对各资源的最大需求数分配矩阵

⒋已分配矩阵 int allocation[m][m];//分配矩阵——系统给每个进程已分配的各类资源数

⒌需求矩阵 int need[m][m]; //需求矩阵——每个进程还需要每种资源的个数申请各类资源数量

⒍申请向量 int request [m] //进程申请资源的向量

⒎工作向量 int work[m][m]; //初始第一个向量为Available[],随寻找安全序列时为其余每个向量赋值，可以防止安全序列未找到而丢了初始状态的值

⒏安全序列向量 int a[m]={0};//存放安全序列号

⒐标志向量 int Finish[m] //求安全序列时记录每个进程是否可以顺利执行

4.2.算法整体设计与调用

主函数void main()，首先输入每个进程信息，然后判断是否有进程申请资源，若有，则通过request[m]和available[m]的关系判断是否可以进行试分配，如果满足试分配条件，调用void check()函数求安全序列，如果可以求出安全序列，则说明分配后系统不会进入不安全状态，正式将资源分配给申请资源的进程，最后用void print()函数输出分配资源后每个进程的信息。如果求不出安全序列，说明分配后系统会处于不安全状

10

态，则不能将资源分配给该进程，让其等待，系统恢复原始状态。如果申请资源的数量不满足条件，则让该进程等待。继续判断其他申请资源的进程。

1.void check()这个函数用来判断是否可以进行试分配，通过其中的do{}while()语句进行安全性分配，并用a[m]记录安全性序列，然后通过for()语句进行检查是否所有的进程都已分配用int f来判断，如果f返回1，说明可以进行试分配系统处于安全状态，如果f返回0，说明所剩资源不足以满足所有进程全部执行，系统处于不安全状态。 不能进行进程进的资源分配。

2.void print()这个函数用来输出各类资源分配情况信息，按类似于表格形式输出，滨且输出各类资源的可利用资源数，便于查看进程执行执行过程，并且在执行过程中各矩阵信息变化也很容易跟踪查看。

4.3.模块设计

4.3.1.安全性算法

void check() //安全算法函数 {

int g,f,v=0,i,j; int work[m],a[m]; bool finish[m]; r=1; g=no1;

for(i=0;i

finish[i]=false; // 初始化进程均没得到足够资源数并完成

for(i=0;i

work[i]=available[i]; //work[i]表示可提供进程继续运行的各类资源数

do{

for(i=0;i

if(finish[i]==false)

11

{

f=1;

for(j=0;j

if(need[i][j]>work[j])

f=0;

if(f==1) //找到还没有完成且需求数小于可提供进程继续运行的资源数的进程

}

{ }

finish[i]=true;

a[v++]=i; //记录安全序列号 for(j=0;j

work[j]+=allocation[i][j]; //释放该进程已

分配的资源

}

g--; //每完成一个进程分配，未完成的进程数就减1

}while(g>0); f=1;

for(i=0;i

{ }

if(f==0) //若有进程没完成，则为不安全状态

if(finish[i]==false) { }

f=0; break;

12

{ printf(\系统处在不安全状态！\ r=0;

} else { printf(\系统当前为安全状态，安全序列为：\\n\ for(i=0;i

printf(\ \ //输出安全序列

}

} 4.3.2.输出算法

void print() //输出函数

{

int i,j; printf(\ printf(\此时刻资源分**********************\\n\ printf(\进程名/号 | Max | Allocation |\\n\

for (i = 0; i < no1; i++) { printf(\ p%d/%d \

for (j = 0; j < no2; j++) {

printf(\ \}

for (j = 0; j < no2; j++)

{

printf(\ \}

for (j = 0; j < no2; j++) {

配情况| Need 13

printf(\ \

}

}

printf(\ printf(\各类资源可利用的资源数为:\ for (j = 0; j < no2; j++) {printf(\ printf(\

}

printf(\

4.3.3.整体函数设计

#include #include #include # define m 50

int no1; //进程数 int no2; //资源数 int r;

int allocation[m][m],need[m][m],available[m],max[m][m];

char name1[m],name2[m]; //定义全局变量 void main() { void check(); void print(); int i,j,p=0,q=0; char c; int request[m],allocation1[m][m],need1[m][m],available1[m]; printf(\ printf(\ 银行家算法的设计与实现 *\\n\ printf(\ printf(\请输入进程总数: \ scanf(\ printf(\请输入资源种类数: \ scanf(\

printf(\请输入Max矩阵:\\n\ for(i=0;i

14

for(j=0;j

p=0; printf(\请输入请求资源的进程号(0~4)：\\n\ for(j=0;j<=10;j++) { scanf(\ if(i>=no1) { printf(\输入错误，请重新输入：\\n\ continue; } else break; } printf(\请输入该进程所请求的资源数request[j]:\\n\ for(j=0;jneed[i][j]) p=1; //判断请求是否超过该进程所需要的资源数 if(p) printf(\请求资源超过该进程资源需求量，请求失败！\\n\ else { for(j=0;javailable[j]) q=1; //判断请求是否超过可用资源

15

数 if(q) printf(\没有足够的资源分配，请求失败！\\n\ else //请求满足条件 { for(j=0;j

/*系统尝试把资源分配给请求的进程*/ } print(); check(); //检测分配后的安全性 if(r==0) //如果分配后系统不安全 { for(j=0;j

//还原已分配的资源数，仍需要的资源数和可用的资源数 } printf(\返回分配前资源数\\n\ print(); } } }printf(\你还要继续分配吗？Y or N ?\\n\ //判断是否继续进行资源分配 c=getche(); }while(c=='y'||c=='Y'); } }

void check() //安全算法函数 {

16

int g,f,v=0,i,j; int work[m],a[m]; bool finish[m]; r=1; g=no1; for(i=0;iwork[j]) f=0; if(f==1) //找到还没有完成且需求数小于可提供进程继续运行的资源数的进程 { finish[i]=true; a[v++]=i; //记录安全序列号 for(j=0;j0); f=1; for(i=0;i

17

r=0; } else { printf(\系统当前为安全状态，安全序列为：\\n\ for(i=0;i

void print() //输出函数 { int i,j; printf(\ printf(\此时刻资源分配情况**********************\\n\ printf(\进程名/号 | Max | Allocation | Need |\\n\

for (i = 0; i < no1; i++) { printf(\ p%d/%d \

for (j = 0; j < no2; j++) {printf(\ \ for (j = 0; j < no2; j++) {printf(\ \ for (j = 0; j < no2; j++) {printf(\ \ printf(\ } printf(\ printf(\各类资源可利用的资源数为:\ for (j = 0; j < no2; j++) {printf(\ printf(\}

18

5.调试与操作说明

5.1运行程序

1.运行banker.cpp文件，并输入进程总数和资源种类数，可出现如下图

3. 然后通过矩阵的方式输入max[][],allocation[][],available[]如图：

4. 输入完成并确认后便出现如下图

19

从图中可知道当前资源的分配情况，各类资源可利用的资源数以及系统当前的安全性序列。

5. 根据上一步的输入提示可以输入请求资源的进程号、该进程所请求的资源数，确认后可

得到请求以后资源的分配情况、各类资源可利用的资源数以及系统当前的安全性序列如图所示：

6.通过上一步的提示可以选择是否继续分配。

20

6.课程设计的总结与体会

6.1.总结

银行家算法是通过检查试分配，求安全序列，从而判断是否可以为申请资源的进程分配资源，从而有效地避免系统进入死锁状态。

6.2.体会

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

21

评语： 评阅教师签名： 年 月 日 成 绩

22

本文来源：https://www.bwwdw.com/article/60x7.html