操作系统实验二：银行家算法

实验二  银行家算法

一、实验目的

1、了解什么是操作系统安全状态和不安全状态；

2、了解如何避免系统死锁；

3、理解银行家算法是一种最有代表性的避免死锁的算法，掌握其实现原理及实现过程。

二、实验内容

根据银行家算法的基本思想，编写和调试一个实现动态资源分配的模拟程序，并能够有效避免死锁的发生。

三、实验原理

进程申请资源时，系统通过一定的算法判断本次申请是否不可能产生死锁（处于安全状态）。若可能产生死锁（处于不安全状态），则暂不进行本次资源分配，以避免死锁。算法有著名的银行家算法。

1、什么是系统的安全状态和不安全状态？

所谓安全状态，是指如果系统中存在某种进程序列＜P1，P2，…，Pn＞，系统按该序列为每个进程分配其所需要的资源，直至最大需求，则最终能使每个进程都可顺利完成，称该进程序列＜P1，P2，…，Pn，＞为安全序列。

如果不存在这样的安全序列，则称系统处于不安全状态。

2、银行家算法

   把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。

为保证资金的安全，银行家规定:  

(1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客;  

(2) 顾客可以分期贷款，但贷款的总数不能超过最大需求量;  

(3) 当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款;  

(4) 当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金。

操作系统按照银行家制定的规则设计的银行家算法为：

（1）进程首次申请资源的分配：如果系统现存资源可以满足该进程的最大需求量，则按当前的申请量分配资源，否则推迟分配。

（2）进程在执行中继续申请资源的分配：若该进程已占用的资源与本次申请的资源之和不超过对资源的最大需求量，且现存资源能满足该进程尚需的最大资源量，则按当前申请量分配资源，否则推迟分配。

（3）至少一个进程能完成：在任何时刻保证至少有一个进程能得到所需的全部资源而执行到结束。

银行家算法通过动态地检测系统中资源分配情况和进程对资源的需求情况来决定如何分配资源，并能在确保系统处于安全状态时才把资源分配给申请者，从而避免系统发生死锁。

四、实验中用到的系统调用函数（包括实验原理中介绍的和自己采用的），自己采用的系统调用函数要按照指导书中的格式说明进行介绍。

　　模拟程序没有用到系统调用函数

五、实验步骤

   要求写出实验过程和思路。 

流程图：

银行家算法数据结构：

1、系统可利用资源向量Available[m]

这是一个含有m个元素的数组，其中每一个元素代表一类系统可利用资源数目，其初始值随机生成，其数值随该类资源的分配和回收而动态的改变。Available[i]=N表示系统中现有第i类资源N个。

2、最大需求矩阵Max

这是一个含有n*m大小的矩阵，其定义了每个进程对系统某类资源的最大需求量。Max[i][j]=N表示进程i对第j类资源的需求为N个。

3、进程已拥有资源矩阵Allocation

这是一个含有n*m大小的矩阵，其定义了每个进程对系统某类资源的已拥有个数。Allocation[i][j]=N表示进程i对第j类资源的已拥有数为N。

4、进程需求矩阵Need

这是一个含有n*m大小的矩阵，其定义了每个进程对系统某类资源的需求数量，Need[i][j]=N表示进程i对第j类资源的需求为N。

其中，Need、Allocation、Max矩阵的关系为：Need[i][j]=Max[i][j]-Allcation[i][j]

以上数组全部由C++对内存空间申请动态数组实现。

5、进程请求向量request

这是一个含有m个元素的数组，其中每一个元素代表此时某进程对每一类系统可利用资源的申请数量，数值大小不超过系统可利用的资源数。request[i]=N表示某进程对第i类资源的申请数为N。

6、Temp

这是一个含有m个元素的数组，其初始值为Available，将对Available的操作代替在Temp上进行。

7、进程满足需求的标志数组Finish

在安全性检测中对每个进程进行检测分配时，可满足的进程即标志位置1。

Finish[i]=1表示此次尝试分配资源后系统可利用资源能满足第i个进程的需求。

银行家算法思路：

申请资源RequestRes()：

1、产生申请向量

2、与系统可利用资源对比(request[i]