操作系统课程设计--银行家算法.docx

操作系统课程设计--银行家算法

———————————————————————————————— 作者：
———————————————————————————————— 日期：

2

qwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmrtyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmrtyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmrtyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmrtyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmrtyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmrtyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmrtyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnm

操作系统课程设计
银行家算法
指导老师：罗俊松
2011/10/1
软件工程三班
USER

目录
1绪论 3
1.1前言 3
1.2研究意义 3
1.3结构安排 4
2需求分析 5
2.1题目描述 5
2.2银行家算法 5
2.3基本要求 5
2.4目的 6
3概要设计 7
3.1基本思路 7
3.2银行家算法步骤 7
3.3安全型算法步骤 7
3.4数据结构 8
3.4.1主要用到的数据结构 8
3.4.2程序模块 8
3.4.3各模块间的调用关系 9
4详细设计 10
4.1主要函数的核心代码 10
4.1程序流程图 10
5测试 13
5.1测试用例 13
5.1测试结果分析和截图 13
6总结 18
参考文献 19
附录：原程序清单 20

5

1绪论

1．1前言 ：
Dijkstra (1965)提出了一种能够避免死锁的调度算法，称为银行家算法。
它的模型基于一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，每个客户都有一个贷款额度，银行家知道不可能所有客户同时都需要最大贷款额，所以他只保留一定单位的资金来为客户服务，而不是满足所有客户贷款需求的最大单位。
这里将客户比作进程，贷款比作设备，银行家比作系统。
客户们各自做自己的生意，在某些时刻需要贷款。在某一时刻，客户已获得的贷款和可用的最大数额贷款称为与资源分配相关的系统状态。一个状态被称为是安全的，其条件是存在一个状态序列能够使所有的客户均得到其所需的贷款。如果忽然所有的客户都申请，希望得到最大贷款额，而银行家无法满足其中任何一个的要求，则发生死锁。不安全状态并不一定导致死锁，因为客户未必需要其最大贷款额度，但银行家不敢抱这种侥幸心理。
银行家算法就是对每一个请求进行检查，检查如果满足它是否会导致不安全状态。若是，则不满足该请求；否则便满足。
检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户。如果可以，则这笔投资认为是能够收回的，然后接着检查下一个距最大需求最近的客户，如此反复下去。
如果所有投资最终都被收回，则该状态是安全的，最初的请求可以批准。

1．2研究意义 ：

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

[键入文字]

6

要预防死锁，有摒弃“请求和保持”条件，摒弃“不剥夺”条件，摒弃“环路等待”条件等方法。
但是，在预防死锁的几种方法之中，都施加了较强的限制条件；而在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统状态分为安全状态和不安全状态，便可避免死锁的发生。
而最具代表性的避免死锁的算法，便是Dijkstra的银行家算法。
利用银行家算法，我们可以来检测CPU为进程分配资源的情况，决定CPU是否响应某进程的的请求并为其分配资源，从而很好避免了死锁的产生。

1．3结构安排 ：

一、绪论： 介绍了题目背景以及研究意义。
二、需求分析： 介绍了题目描述、银行家算法、以及基本要求和所需达到的目的。
三、概要设计：介绍了基本的算法思路、步骤，以及数据结构和主要的函数模块及其调用关系。
四、详细设计：介绍了主要函数及其核心代码，以及程序流程图。
五、测试
六、总结
参考文献
附录：原程序清单

[键入文字]

8

2 需求分析

2．1题目描述 ：

银行家算法是一种最具有代表性的避免死锁的算法。
要解释银行家算法，必须先解释操作系统的安全状态和不安全状态。
所谓安全状态，是指系统能按照某种进程顺序{P1,P2,…，Pn}（称{P1,P2,…，Pn }序列为安全序列），来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺利完成。安全状态一定没有死锁发生。
如果系统无法找到这样一个安全序列，则称系统处于不安全状态。
那么，什么是安全序列呢？
如果对每一个进程Pi(1<i<=n)，它以后尚需要的资源量不超过系统当前可利用的资源量与所有的进程Pj(j<n)所占有的资源量之和，则称此进程序列{P1,P2,…，Pn}是安全的，称作安全序列。

2．2银行家算法 ：

我们可以把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求资源相当于客户向银行家贷款。
操作系统按银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程尚需求的资源量，若是系统现存的资源可以满足它尚需求的资源量，则按当前的申请量来分配资源，否则就推迟分配。
当进程在执行中继续申请资源时，先测试该进程申请的资源量是否超过了它尚需的资源量。若超过则拒绝分配，若没有超过则再测试系统尚存的资源是否满足该进程尚需的资源量，若满足即可按当前的申请量来分配，若不满足亦推迟分配。

2．3基本要求 ：

（1）可以输入某系统的资源以及T0时刻进程对资源的占用及需求情况的表项，以及T0时刻系统的可利用资源数。

（2）对T0时刻的进行安全性检测，即检测在T0时刻该状态是否安全。

（3）进程申请资源，用银行家算法对其进行检测，分为以下三种情况：
A. 所申请的资源大于其所需资源，提示分配不合理不予分配并返回。
[键入文字]

9

B. 所申请的资源未大于其所需资源，但大于系统此时的可利用资源，提示分配不合理不予分配并返回。
C. 所申请的资源未大于其所需资源，亦未大于系统此时的可利用资源，预分配并进行安全性检查：
a. 预分配后系统是安全的，将该进程所申请的资源予以实际分配并打印后返回。
b. 与分配后系统进入不安全状态，提示系统不安全并返回。

（4）对输入进行检查，即若输入不符合条件，应当报错并返回重新输入。

2．4目的：

根据设计题目的要求，充分地分析和理解题目，叙述系统的要求，明确程序要求实现的功能以及限制条件。
明白自己需要用代码实现的功能，清楚编写每部分代码的目的，做到有的放矢，有条理不遗漏的用代码实现银行家算法。

[键入文字]

10

3 概要设计

3．1算法思路：

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

3．2银行家算法步骤
（1）如果Request<Need,则转向步骤(2)；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。
（2）如果Request<Available,则转向步骤（3）；否则，表示系统中尚无足够的资源，进程必须等待。
（3）系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值：
    x.Available[i] -= Request[i];
x.Need[number-1][i] -= Request[i];
x.Allocation[number-1][i] += Request[i];
(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。

3．3安全性算法步骤
（1）设置三个向量
①安全序列向量safeprocess。它用来存储安全序列向量;
②空闲资源矩阵work。开始时可利用资源向量就是空闲资源矩阵work=Available;
③布尔向量Finish。它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finish[i]=false，当有足够资源分配给进程时，令Finish[i]=true。

[键入文字]

12

（2）从进程集合中找到一个能满足下述条件的进程：
①Finish[i]=false
②Need<=Work
如找到，执行步骤（3）；否则，执行步骤（4）。
（3）当进程P获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
safeprocess[k++]=i;
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) 安全序列向量safeprocess[]
(7) 空闲资源矩阵work[]
(8) 布尔型向量Finish[]
3．4. 2程序模块：
//程序主函数
bank current; //申请结构化对象
Initilize(current); //初始化对象
Safety(current); //检查安全性
while(1) //循环执行银行家算法四步骤
{
Bank(current);
if(tag) return 0; //若可利用资源向量为空则退出系统
}
3．4. 3各模块间的调用关系：

主函数int main()
要调用: Initilize(),Safety()，Resoure_allocate().

初始化函数Initilize()
要调用: Maxoutput(),Allocationoutput(),Needoutput(),
Availableoutput().

银行家算法函数Bank()
要调用Safety(),Allocationoutput(),Needoutput().

[键入文字]

13

4 详细设计

4．1主要函数的核心代码：
1. 进行初始化输入的函数并打印输出此刻资源分配情况
2. 利用安全性算法进行检测的函数
3. 利用银行家算法进行资源分配及进行判定并打印输出
实际分配情况
注：具体代码请见附录—源程序清单。

4．2程序流程图：
1、初始化过程流程图
键盘输入最大需求矩阵Max
调用void Initilize函数

调用结束
调用函数打印输出各矩阵和向量
键盘输入可利用资源向量Available
键盘输入需求矩阵Need
键盘输入分配矩阵Allocation

[键入文字]

14

输入欲申请的进程号
调用void Bank()函数
输入：
1.继续分配
2.退出
2、银行家算法流程图
调用Safety()判断是否安全?
输入是否合法?
调用结束
输出分配后的矩阵的向量
预分配
Request[i]>Available[i]?
Request[i]>Need[i]?
输入该进程申请的资源向量Request[]

[键入文字]

15

3、安全性算法流程图

[键入文字]

16

5 测试

5．1测试用例：

分配成功
关系&&

Request<=Need
Request<=Max
Request<=Available

分配失败
关系||

Request>Need
|Available|==0
(直接退出系统)
找不到安全序列
Request>
Available
Request>Max

5．2测试结果截图：

1. 开始界面

[键入文字]

28

2. 初始化并打印输出。

3. 用例测试a：进程1发出请求Request(3,1,2)——Request>Need，不予分配。

4．用例测试b：进程1发出请求Request(1,1,1)——Request<Availabl
&&Request<Need， 允许分配。

5．用例测试c：进程2发出请求Request(2,2,2)——Request<Availabl
&&Request=Need， 允许分配。

6．用例测试d：进程2发出请求Request(1,0,0)——Request>Need,
不允许分配。

7．用例测试e：进程3发出请求Request(1,1,1)——分配成功后使可利用资源向量小于一进程的最大需求向量，再向进程4发出请求(2,1,0)——Request>Available, 不予分配。

8．用例测试f：进程5发出请求Request(1,1,1)——|Available|==0，系统退出。

9．用例测试g：重新启动系统使需求矩阵一需求值大于相应的可利用资源向量值——找不到安全序列。

6 总结

在银行家算法这个系统之中，所采用的数据结构应是最基本的部分。银行家算法的数据结构我们采用了一维数组与二维数组来存储，比如最大需求量Max[][]、已分配资源数Allocation[][]、仍需求资源数Need[][]、以及系统可利用的资源数、申请各类资源等数组。

数据结构虽然重要但却只是基础，而最主要的用以实现系统功能的应该有两个部分，一是用银行家算法来判断，二是用安全性算法来检测系统的安全性。

在本程序代码中，银行家算法用judge( )函数来实现。
首先，输入欲申请资源的进程以及其所申请的资源数，存放在Request数组中。
然后，判断进程请求的资源数是否大于其所需的资源数，若大于则报错并返回，若不大于则继续判断它是否大于系统在此时刻可利用的资源数，同样，如果大于则报错并反回，如果不大于则进行预分配，之后再调用安全型算法safty检查。
最后，若可利用资源向量为空则退出系统。

安全性检测我们是用safty( )函数来实现的。
首先，Finish[]为布尔型，默认是False，即该进程未完成。而Work——即该系统中可以用来工作的资源数——最开始为系统最初可以用的资源数。
然后，我们从第一个进程开始判断该进程未完成且其所需求的资源量不大于该系统中可以用来工作的资源量这个条件是否成立，即Finish[]=False且Need[][]<=Work[]是否成立。成立的话则将当前在工作的资源量与该进程已分配的资源量相加，存放于当前可用来工作的资源量当中，即Work[]=Work[]+Allocation，并将Finish[]的值改为True。
否则便将此进程的优先级减一，排在队位，然后开始往后循环。
待所有的进程循环完毕，我们再次判断是否还存在进程的Finish[]=False，如果仍存在，则说明系统没有安全序列，处于不安全状态，不可以进行分配；否则，系统处于安全状态，将预分配变为实际分配，求出安全序列并且将实际分配后的资源分配情况打印输出。

除此之外，在程序当中，我们也得强调一下对输入的合法性的判断。比如，我们输入的欲申请资源的进程号没有在系统已存在的进程当中，或者进程号定义为整型，但是却错输成字母等情况，我们需要对这些情况进行判断，让程序报错返回而并非因错误而中断。
这样的情况处理起来比较麻烦，相当于对每次输入针对各种不同的情况都得做判断。我也没有涵盖全部的输入，仅仅只是对输入的进程号不在已存在进程当中、以及输入的操作选择不存在两种情况分别作了判断，并且针对第二种情况设定了五次输入错误的话系统关闭的功能。而因为对于某些——比如进程号——本来设定就是整型，因此对输入的是字母的判别因比较复杂而未能加上。

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

参考文献

[1] 汤小丹，梁红兵，哲凤屏，汤子瀛.计算机操作系统. 西安：西安电子科技大学出版社，2007.
[2] 严蔚敏，吴伟民.数据结构. 北京：清华大学出版社，2006..
[3] (百度文库：银行家算法报告)
[4] （志文工作室： 银行家算法模拟实现）

附录：源程序清单
#include<iostream>
using namespace std;
/***********************************************************************
数据定义与函数原型说明
***********************************************************************/
#define m 5 //总进程数
#define n 3 //总资源数
int tag=0; //标识符，如果可利用资源向量全为0，则退出系统。
struct bank //定义结构体
{
int Available[n]; //可利用资源向量
int Max[m][n]; //最大需求矩阵
int Allocation[m][n]; //分配矩阵
int Need[m][n]; //需求矩阵
};
void Initilize(bank &); //初始化
int Safety(bank); //检查安全性
void Bank(bank &); //银行家算法对进程资源申请的处理
/***********************************************************************
输出某时刻最大需求矩阵
***********************************************************************/
void Maxoutput(bank &s)
{
int i,j;
cout<<" A B C\n";
for(i=0;i<5;i++)
{
cout<<"P"<<i;
for(j=0;j<3;j++)
{
cout<<" "<<s.Max[i][j];
}
cout<<endl;
}
}
/***********************************************************************
输出某时刻分配矩阵
***********************************************************************/
void Allocationoutput(bank &s)
{
int i,j;
cout<<" A B C\n";
for(i=0;i<5;i++)
{
cout<<"P"<<i;
for(j=0;j<3;j++)
{
cout<<" "<<s.Allocation[i][j];
}
cout<<endl;
}
}
/***********************************************************************
输出某时刻需求矩阵
***********************************************************************/
void Needoutput(bank &s)
{
int i,j;
cout<<" A B C\n";
for(i=0;i<5;i++)
{
cout<<"P"<<i;
for(j=0;j<3;j++)
{
cout<<" "<<s.Need[i][j];
}
cout<<endl;
}
}
/***********************************************************************
输出某时刻可利用资源向量
***********************************************************************/
void Availableoutput(bank &s)
{
int i;
cout<<"进行资源申请前的可利用资源向量:";
for(int i=0;i<3;i++)
cout<<" "<<s.Available[i];
cout<<endl;
}
/***********************************************************************
初始化
***********************************************************************/
void Initilize(bank &x)
{
int i,j;
cout<<"初始化过程，输入相关数据\n";
cout<<"输入最大需求矩阵Max:"<<endl;
for(i=0;i<m;i++) //设置最大需求矩阵
{
for(j=0;j<n;j++)
{
cin>>x.Max[i][j];
}
}
cout<<"输入分配矩阵Allocation:"<<endl;
for(i=0;i<m;i++) //设置分配矩阵
{
for(j=0;j<n;j++)
{
cin>>x.Allocation[i][j];
}
}
for(i=0;i<m;i++) //设置需求矩阵
{
for(j=0;j<n;j++)
{
x.Need[i][j]=x.Max[i][j]-x.Allocation[i][j];
}
}
cout<<"输入可利用资源向量:"<<endl;
for(i=0;i<n;i++) //设置可利用资源向量
{
cin>>x.Available[i];
}
cout<<"******************************初始化资源分配情况********************************";
cout<<" MAX\n";
Maxoutput(x);
cout<<" Allocation\n";
Allocationoutput(x);
cout<<" Need\n";
Needoutput(x);
Availableoutput(x);
cout<<"******************************初始化资源分配情况********************************";
}
/***********************************************************************
检查安全性
***********************************************************************/
int Safety(bank x)
{
int i,j;
int safeprocess[m]; //安全序列向量
int work[n]; //空闲资源矩阵
int Finish[m]; //进程完成标志矩阵
for(i=0;i<n;i++) //开始时可利用资源向量就是空闲资源矩阵
work[i]=x.Available[i];
for(i=0;i<m;i++) //初始化标志矩阵为false
Finish[i]=false;

int k=0; //安全序列排列号
for(i=0;i<m;i++) //每次都从第一个进程开始做循环
{
if(Finish[i]==false)
{
for(j=0;j<n;j++)
{
if(x.Need[i][j]>work[j]) //判断当前进程需求矩阵能否得到满足
break; //不满足则跳出
}
if(j==n) //第i个进程满足执行条件
{
safeprocess[k++]=i; //将进程号存入安全序列向量
for(int q=0;q<n;q++) //修改空闲资源矩阵
work[q]+=x.Allocation[i][q];
Finish[i]=true; //标志该进程可完成
i=-1; //下次检查从第一个进程重新查起
}
}
}
for(i=0;i<m;i++) //检查标志数组，若有一个为false则找不到安全序列
if(!Finish[i])
{
cout<<"找不到安全序列,系统处于不安全状态!\n";
return 0;
}
cout<<"找到安全序列:"; //找到安全序列并显示该序列
for(i=0;i<m;i++)
{
cout<<"进程"<<safeprocess[i]+1;
if(i<m-1)cout<<"->";
}
cout<<"\n系统处于安全