银行家算法的研究与应用文献综述和参考文献(2)

2.2.3银行家算法的进一步改进:

对于进程pi 的当前请求Request[i]执行如下步骤：

（1）若Request[i]<=Need[i],进行步骤(2)，否则进程申请超量，pi 带错返回；

（2）若Request[i]<=Available,进行步骤(3),否则当前请求无法满足,pi 等待

（3）假定实施分配，即执行下述操作:

Allocation[i]=Allocation[i]+Request[i];

Need[i]=Need[i]-Request[i];

Available=Available-Request[i];

（4）若Need[i]<=Available,则算法结束，否则进行步骤(5);

（5）进行安全性检查，若安全确定分配，Request[i]=0;否则执行下述操作：

Allocation[i]= Allocation[i]-Request[i];

Need[i]=Need[i]+Request[i];

Available=Available+Request[i];

取消分配，之后pi 进程等待。

定理 : 设系统在安全状态下接收到进程pi 发出的资源申请命Request[i],若Max[i]-Allocation[i]=Need[i]<=Available,则在实施分配后系统仍然处于安全状态.

证明：因为分配之前系统处于安全状态,所以存在一个安全进程序列,设其为

（Pk1 ，Pk2 ，，，，， Pkn）.令Pki=Pi ,由于Need[i]<=Available,可知在其它进程不释放其占有资源的条件下,进程pi 可以进行完，因而（P1 ，Pk1 ，Pk2 ，，，，， Pkn）也是一个安全进程序列.在实施分配Need[i]=Need[i]-Request[i], Available=Available-Request[i]之后，Need[i]<=Available依然成立，故此时（Pi ，Pk1 ，Pk2 ，，，，， Pkn）仍是一个安全进程序列,即在实施资源分配之后系统状态仍是安全的.

根据上述定理，若当申请资源进程Pi尚需资源Need[i]不超过系统当前剩余资源Available 时可以直接实施分配，不必进行安全性检查.

设进程个数为n,资源类个数为m,则对于改进前的银行家算法和安全性检测算法，所需执行的计算量为：

(7m ~ 10m)+[(m+1)(n+2)/2]n=mn2/2

对于改进后的算法,在最佳情况下(不需进行安全性检测)所需的计算量为：5m;在最差的情况下（安全性检测涉及所有进程）所需的计算量与改进前的算法相同；在一般情况下(安全性检测涉及所有进程)所需的计算量约为：kmn/2,其中

K(1<=k<=n)为安全性检测所涉及到进程的个数.

由此可见,减少不必要的安全性检测和缩小检测范围可以在较大幅度上减少系统开销.容易证明,上述改进的安全性检测算法和银行家算法不受进程动态产生与动态撤消等素的影响.

2.2.4银行家算法在高校排课系统中的应用

针对高校中越来越多的公共选修课进行教室的安排,该算法引入了两个向量：Recourse(资源总量)、Available(剩余资源量)以及两个矩阵：Claim(每个进程的最大需求量)、Allocation(已为每个进程分配的数量)。它们共同构成了任一时刻系统对资源的分配状态。

(1)进程一开始向系统提出最大需求量。

(2)进程每次提出新的需求(分期贷款)都检测是否超出它事先提出的最大需量。

(3)若没有超出它的最大需求量，则判断该进程所需剩余量(包括本次申请)是否超出系统所掌握的剩余资源量，若不超出，则分配，否则等待。由于选修课设计的学生班级，专业多，所以可以安排上课的时间就相对比较少。而且为了保证选修课程的教学质量，规定只能小班授课，也就是说每个上课的班级人数不能多于 max 人，如果超过人数就再增加一个班。如果少于 min 人，不开该选修课。假设教室资源(Recourse)为 A 教室 n1个（表示能容纳 m1 人上课）、B 教室 n2 个（表示能容纳 m2人上课）、C 教室 n3个（表示能容纳 m3 人上课，这样的教室尽量少用，所以仅有一个）。在一个所有选课的学生都有时间上课的时间段内有 x 门选修课程，学生数分别为s1人、s2 人、s3 人和 s4 人，相当于 4 个进程，提出的请求 Request 就是他们的最大请求 Claim。银行家算法应用到我们选修课教室的安排中主要就是系统判断可使用教室资源是否能满足所有学生上课的需求，最终找到一个能满足所有申请的方案，即一个安全的序列。银行家算法的研究与应用文献综述和参考文献(2):http://www.751com.cn/wenxian/lunwen_45896.html