一、实验概述
1. 实验名称
基于JAVA平台的银行家算法实现
2. 实验目的
（1）理解利用银行家算法避免死锁的问题；
（2）在了解和掌握银行家算法的基础上，编制银行家算法通用程序，将调试结果显示在计算机屏幕上，并检测机算和笔算的一致性。
（3）理解和掌握安全序列、安全性算法。
3. 实验内容
银行家算法：
银行家算法最初级原为银行系统设计，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。在OS设计中，也可以用它来避免死锁。 为实现银行家算法，每个新进程在进入系统时它必须申明在运行过程中，可能需要的每种资源类型的最大单元数目，其数目不应超过系统所拥有的资源总量。当某一进程请求时，系统会自动判断请求量是否小于进程最大所需，同时判断请求量是否小于当前系统资源剩余量。若两项均满足，则系统试分配资源并执行安全性检查算法。
安全性检查算法：
安全性检查算法用于检查系统进行资源分配后是否安全，若安全系统才可以执行此次分配；若不安全，则系统不执行此次分配。
安全性检查算法原理为：在系统试分配资源后，算法从现有进程列表寻找出一个可执行的进程进行执行，执行完成后回收进程占用资源；进而寻找下一个可执行进程。当进程需求量大于系统可分配量时，进程无法执行。当所有进程均可执行，则产生一个安全执行序列，系统资源分配成功。若进程无法全部执行，即无法找到一条安全序列，则说明系统在分配资源后会不安全，所以此次分配失败。
二、实验环境
操作系统：Windows 7 旗舰版 Service pick 7
编译器：NetBeans IDE 8.0.2
语言：JAVA
工具：Microsoft Word；NetBeans
三、实验过程
(一).实验原理
1、安全状态
指系统能按照某种顺序如<P1,P2,…,Pn>(称为<P1,P2,…,Pn>序列为安全序列)，为每个进程分配所需的资源，直至最大需求，使得每个进程都能顺利完成。
2、银行家算法
假设在进程并发执行时，进程i提出请求j类资源k个后，表示为Requesti[j]=k。系统按下述步骤进行安全检查：
（1）如果Requesti≤Needi则继续以下检查，否则显示需求申请超出最大需求值的错误。
（2）如果Requesti≤Available则继续以下检查，否则显示系统无足够资源，Pi阻塞等待。
（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：
Available［j］∶=Available［j］-Requesti［j］;
Allocation［i,j］∶=Allocation［i,j］+Requesti［j］;
Need［i,j］∶=Need［i,j］-Requesti［j］;
（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。
3、安全性算法
（1）设置两个向量：
① 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work∶=Available;
② Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish［i］∶=false; 当有足够资源分配给进程时， 再令Finish［i］∶=true。
（2）从进程集合中找到一个能满足下述条件的进程：
① Finish［i］=false;
② Need［i,j］≤Work［j］； 若找到， 执行步骤(3)， 否则，执行步骤(4)。
（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
-
- Work［j］∶=Work［i］+Allocation［i,j］;
- Finish［i］∶=true;
- go to step 2;
（4）如果所有进程的Finish［i］=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。
（二）设计思路
1、初始化
由用户输入数据，分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵MAX、分配矩阵ALLOCATION、需求矩阵NEED赋值。
2、银行家算法
在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。
银行家算法的基本思想是分配资源之前，判断系统是否是安全的；若是，才分配。它是最具有代表性的避免死锁的算法。
设进程cusneed提出请求REQUEST [i]，则银行家算法按如下规则进行判断。
(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，则转（2)；否则，出错。
(2)如果REQUEST [cusneed] [i]<= AVAILABLE[i]，则转（3)；否则，等待。
(3)系统试探分配资源，修改相关数据：
AVAILABLE[i]-=REQUEST[cusneed][i];
ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];
NEED[cusneed][i]-=REQUEST[cusneed][i];
(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。
3、安全性检查算法
（1)设置两个工作向量Work=AVAILABLE;FINISH
(2)从进程集合中找到一个满足下述条件的进程，
FINISH==false;
NEED<=Work;
如找到，执行（3)；否则，执行（4)
(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。
Work=Work+ALLOCATION;
Finish=true;
GOTO 2
(4)如所有的进程Finish= true，则表示安全；否则系统不安全。
（五）源程序
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package bankersalgorithm;
/**
*
* @author Administrator
*/
public class BankersAlgorithm {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
int[][] claim={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};//各线程最大需求量
int[][] allocation={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};//各线程已分配资源
int i,j,k,l=0,count=0,m=0;
int[][] C_A={{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0}};//各进程仍需要的各类资源
int[] result={-1,-1,-1,-1,-1};//存放预分配成功的线程
int[] currentavail={3,3,2};//当前可分配资源
System.out.printf("银行家总共拥有的各类资源的总数：\n A B C\n 10 5 7\n");
System.out.printf("银行目前仍剩下的各类资源的数量：\n A B C\n 3 3 2\n");
System.out.printf("各进程对各类资源的最大需求量：\n A B C\n");
for(i=0;i<5;i++)
{
System.out.printf("P%d: ",i);
for(j=0;j<3;j++)
{
System.out.printf(" %d ",claim[i][j]);
C_A[i][j]=claim[i][j]-allocation[i][j];
}
System.out.printf("\n");
}
System.out.printf("各进程已分配到的各类资源：\n A B C\n");
for(i=0;i<5;i++)
{
System.out.printf("P%d: ",i);
for(j=0;j<3;j++)
System.out.printf(" %d ",allocation[i][j]);
System.out.printf("\n");
}
System.out.printf("各进程仍需的各类资源数量：\n A B C\n");
for(i=0;i<5;i++)
{
System.out.printf("P%d: ",i);
for(j=0;j<3;j++)
System.out.printf(" %d ",C_A[i][j]);
System.out.printf("\n");
}
while(result[l]==-1)//
{
for(k=0;k<5;k++)
if(result[k]==-1)
{
for(j=0;j<3;j++)//判断各线程对各资源仍需量是否小于当前可分配资源总量,此量为正数才正常
if(C_A[k][j]<=currentavail[j]&&C_A[k][j]>=0)
{
currentavail[j]=currentavail[j]+allocation[k][j];//把满足条件的进程的已分配资源加到当前可分配资源中
m++;
if(m==3)
{
result[l]=k;//只有ABC三类资源都满足才把相应的线程记入数组result中
m=0;
}
}
else break;//否则退出循环,打印"系统不安全"
l++;
}
for(i=0;i<l;i++)
if(result[i]!=-1)
{
System.out.printf("->P%d",result[i]);//把预分配成功的先打印出来
count++;
}
l=0;//清零,为下一轮的预分配做准备
}
if(count==5)
System.out.printf("\n系统安全!上行所示为其中一个进程安全序列\n");
else
System.out.printf("\n系统不安全!\n");
}
}
更多推荐
基于JAVA的银行家算法实现实验报告
发布评论