银行家算法JAVA版本
银行家算法
摘要：银行家算法来源于银行的借贷业务，一定数量的本金要应多个客户的借贷周转，为了防止银行家资金无法周转而倒闭，对每一笔贷款，必须考察其是否能限期归还。在操作系统中研究资源分配策略时也有类似问题，系统中有限的资源要供多个进程使用，必须保证得到的资源的进程能在有限的时间内归还资源，以供其他进程使用资源。如果资源分配不得到就会发生进程循环等待资源，则进程都无法继续执行下去的死锁现象。
关键词：操作系统 银行家算法 java语言程序设计 进程 死锁
Banker Algorithm
Abstract : The banker algorithm comes from the loan business of the bank. A certain amount of principal should be used for the loan turnover of multiple customers. In order to prevent the banker's capital from failing to be turned over, it is necessary to investigate whether each loan can be returned within a time limit. There are similar problems in the study of resource allocation strategy in operating system. If the limited resources in the system are to be used by multiple processes, it is necessary to ensure that the processes that get the resources can return the resources in a limited time for other processes to use the resources. If the resource allocation is not obtained, the process will cycle to wait for the resource, and the process cannot continue to execute.
Key words: Operating system Banker algorithm Java Process Dead-lock
一、引言
在现代操作系统中，当用户在短时间内连续点击执行多个任务的时候，操作系统会启动多个进程去完成这些任务，进程必须在准备工作做完之后才可以去执行任务，也就是已拥有所需的全部资源之后，但是进程可能会由于彼此同时都需要的资源没有完全得到，而触发一种永久互相等待的情况，这种现象就是死锁。
操作系统在解决死锁问题的时候，有四个大的方向，分别是预防死锁，避免死锁，检测死锁和解除死锁。而银行家算法就是其中避免死锁算法的代表。其实呢，银行家算法的思想可以用一句话来表达，那就是当一个进程申请使用资源的时候，银行家算法通过先试探分配给该进程资源，然后通过安全性算法判断分配后的系统是否处于安全状态，若不安全则试探分配作废，让该进程继续等待。
执行程序中两个或多个线程发生永久堵塞（等待），每个线程都在等待被其他线程占用并堵塞了的资源。因此产生了死锁。产生了死锁我们就要对其进行预防。
程序实现思路银行家算法顾名思义是来源于银行的借贷业务，一定数量的本金要应多个客户的借贷周转，为了防止银行家资金无法周转而倒闭，对每一笔贷款，必须考察其是否能限期归还。在操作系统中研究资源分配策略时也有类似问题，系统中有限的资源要供多个进程使用，必须保证得到的资源的进程能在有限的时间内归还资源，以供其他进程使用资源。如果资源分配不得到就会发生进程循环等待资源，则进程都无法继续执行下去的死锁现象。
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。
银行家算法是避免死锁的很好很有效的方法，下面我们来了解一下银行家算法。
当用户在短时间内点击多个任务事件的时候，操作系统会在后台启动相应的进程去完成这些任务，进程在做好准备工作之后就会开始执行任务，即在获取到需要的全部资源的时候，进程会向操作系统发出资源申请，如果需要多个资源就发出多个申请，操作系统在收到请求之后会检查该资源是否被占用，如果没有被占用，就分配资源，如果资源被其他进程所占用，就必须得等到其他进程用完之后才能使用该资源，如果进程彼此都需要同样的进程，且各自都占有一部分资源，就会陷入一直等待的状态，这个时候就发生了死锁，如果没有人为的干预，就可能一直处于等待状态。
图1 计算机工作图
死锁是进程彼此间占据着一部分或很少资源，但没有得到运行任务所需的全部资源而发生的一种一直互相等待的情况。
所以接下来我们介绍一下死锁发生的几个必要条件。
1）互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。
2）请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。
3）不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
4）环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。
所以进程请求申请资源时，为避免发生死锁需进行银行家算法验证是否存在安全序列，系统是否安全，若安全，则实际分配,否则，撤消分配，让进程等待。
接下来我们来介绍一下安全状态和不安全状态
安全状态：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。
不安全状态：不存在一个安全序列。不安全状态不一定导致死锁。
安全序列是指一个进程序列{P1，…，Pn}是安全的，即对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。
图2 银行家类图
银行家算法的类为BankerClass，TestBankerClass中由主方法调用BankerClass类的setSystemVariable方法，然后调用其中的setMax和setAlloction用于初始化资源矩阵，并调用SecurityAlgorithm方法判断是否存在安全序列。其中Available代表系统所拥有的资源矩阵，Max代表各进程最大需求资源矩阵，Allocation代表各进程还所拥有的资源矩阵，Need代表各进程还需要的资源矩阵。
三、软件体系设计
银行家算法的思路:
1.进程一开始初始化并向系统提出资源请求
2.进程每次提出新的需求(分期贷款)都统计是否超出它事先提出的最大需求量.
3.若正常,则判断该进程所需剩余剩余量(包括本次申请)是否超出系统所掌握的剩余资源量,若不超出,则分配,否则等待.
4.银行家算法的数据结构.
1）可利用资源向量Available
这是个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果Available[j]=K，则表示系统中现有Rj类资源K个。
2）最大需求矩阵Max
这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。
3）分配矩阵Allocation
这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的 数目为K。
4）需求矩阵Need。
这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。
Need[i,j]=Max[i,j]-Allocation[i,j]
5.银行家算法流程:当某时刻,某进程时,提出新的资源申请,系统作以下操作:
1) 判断请求资源是否小于还需要的资源
2) 判断请求资源是否小于系统拥有的资源
3) 若以上两步没有问题,尝试分配,即各变量作调整.
4) 系统试探分配资源，并修改下列数据
Available = Available - K；表示分配给 P1 K 个资源后，还剩多少系统可分配资源
Allocation = Allocation + K；表示 P1 已经获得的资源
Need = Need - K；表示进程 P1 还需要获得的资源
5) 此时系统执行安全性算法，计算进程是否处于安全性状态
6."安全性检测"算法
对进程逐个进行扫描，判断finish[i],查看当前进程是否被检查过，如果检查过，就扫描下一个，如果没有检查过，就继续判断请求资源是否小于系统资源，如果满足要求，设置标志位表示当前进程已被检查过，满足进程数count加1，如果不满足要求，则进入下一次循环。循环检查之后，判断满足要求进程数是否和请求进程数相等，如果相等，则存在安全序列，如果不等，则不存在。
图3 银行家算法实现流程活动图
/*
* 死锁安全检查算法
*/
public void SecurityAlgorithm() {// 安全算法
boolean[] Finish = { false, false, false };// 初始化Finish
int count = 0;// 完成进程数
int circle = 0;// 循环圈数
int[] S = new int[3];// 安全序列
for (int i = 0; i < 3; i++) {// 设置工作向量
Work[i] = Available[i];
}
boolean flag = true;
while (count < 3) {
if (flag) {
System.out.println("进程 " + " Work " + " Alloction " + " Need " + " Work+Alloction ");
flag = false;
}
for (int i = 0; i < 3; i++) {
if (Finish[i] == false && Need[i][0] <= Work[0] && Need[i][1] <= Work[1] && Need[i][2] <= Work[2]) {// 判断条件
System.out.print("P" + i + " ");
for (int k = 0; k < 3; k++) {
System.out.print(Work[k] + " ");
}
System.out.print("| ");
for (int j = 0; j < 3; j++) {
Work[j] += Alloction[i][j];
}
Finish[i] = true;// 当当前进程能满足时
S[count] = i;// 设置当前序列排号
count++;// 满足进程数加1
for (int j = 0; j < 3; j++) {
System.out.print(Alloction[i][j] + " ");
}
System.out.print("| ");
for (int j = 0; j < 3; j++) {
System.out.print(Need[i][j] + " ");
}
System.out.print("| ");
for (int j = 0; j < 3; j++) {
System.out.print(Work[j] + " ");
}
System.out.println();
}
}
circle++;// 循环圈数加1
if (count == 3) {// 判断是否满足所有进程需要
System.out.print("此时存在一个安全序列：");
for (int i = 0; i < 3; i++) {// 输出安全序列
System.out.print("P" + S[i] + " ");
}
System.out.println("故当前可分配！");
break;// 跳出循环
}
if (count < circle) {// 判断完成进程数是否小于循环圈数
count = 5;
System.out.println("当前系统处于不安全状态，故不存在安全序列。");
break;// 跳出循环
}
}
}
五、运行结果
1.有安全序列：
图 4有安全序列的结果显示
说明：根据系统现有资源，可以依次对P1,P2,P0进行资源分配，不发生死锁，存在一个安全序列。
2.死锁：
图 5没有安全序列的结果显示
说明：即使按照任何方式系统去对进程分配资源，都不可避免的发生死锁，所以不存在一个安全序列。
六、软件测试
用判定节点覆盖法测试：
1.判断是否超出最大资源需求量
说明：P2需要2号资源4个，但P2进程却申请2号资源6个，不符合申请规定，所以不存在安全序列。
图 6判断是否超出最大需求量
2.判断是否超出系统剩余量
说明：进程P1请求2号资源6个，系统现有资源4个，系统资源不足，无法启动任务，进程等待，继续向系统请求资源。
图 7判断是否超出系统剩余量
3.判断系统是否安全
说明：各进程拥有总资源超过系统最大资源，系统不稳定，发生错误。
图 8判断系统是否安全
七、结论
操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。
参考文献：
[1]计算机操作系统教程（第4版）清华大学出版社
[2]java语言程序设计 机械工业出版社
[3]软件需求（第2版）清华大学出版社
[4]实用软件测试教程（第2版）清华大学出版社+