一、目的
通过编写一个模拟动态资源分配的银行家算法程序,进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念,并掌握避免死锁的具体实施方法。
二、实验内容
- (1)模拟一个银行家算法: 设置数据结构 设计安全性算法
- (2) 初始化时让系统拥有一定的资源
- (3) 用键盘输入的方式申请资源
- (4)如果预分配后,系统处于安全状态,则修改系统的资源分配情况
- (5)如果预分配后,系统处于不安全状态,则提示不能满足请求
三、要点说明
数据结构
- 可利用资源向量 int Available[m] m为资源种类
- 最大需求矩阵 int Max[n][m] n为进程的数量
- 分配矩阵 int Allocation[n][m]
- 还需资源矩阵 int need[i][j]=Max[i][j]- Allocation[i][j]
- 申请资源数量 int Request [m]
- 工作向量 int Work[m] int Finish[n]
银行家算法bank()函数
Requesti:进程Pi的请求向量。 0<=j<=m-1
- (1) 若 Requesti[j] ≤ Need[i,j],转向(2),否则出错。
- (2) 若 Requesti[j] ≤ Available[j],转向(3),否则等待。
- (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等待。
安全性算法safe()函数
- (1) 初始化:设置两个向量Work(1×m)和Finish(1×n)
- Work – 系统可提供给进程继续运行所需各类资源数,初态赋值Available
- Finish – 系统是否有足够资源分配给进程,初值false.
- (2) 从进程集合中满足下面条件进程:
- Finish[i] = false; Need[i,j] ≤ Work[j];
- 若找到,执行(3),否则,执行(4)。
- (3) 进程Pi获得资源,可顺利执行,完成释放所分配的资源。
- Work[j] = Work[j]+Allocation[i,j]; Finish[i] = true; go to (2).
- (4) 若所有进程Finish[i] = true,表示系统处于安全状态,否则处于不安全状态。
先对用户提出的请求进行合法性检查,即检查请求的是否不大于需要的,是否不大于可利用的。 若请求合法,则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。 若安全,则分配,否则,不分配,恢复原来状态,拒绝申请。
银行家算法实例
假定系统中有五个进程{P0、P1、P2、P3、P4}和三种类型资源{A、B、C},每一种资源的数量分别为10、5、7。各进程的最大需求、T0时刻资源分配情况如下所示。
试问:
- ①T0时刻是否安全?
- ② T0之后的T1时刻P1请求资源Request1(1,0,2)是否允许?
- ③ T1之后的T2时刻P4请求资源Request4(3,3,0)是否允许?
- ④ T2之后的T3时刻P0请求资源Request0(0,2,0)是否允许?
解:
① T0时刻是否安全? 工作向量Work.它表示系统可提供给进程继续运行所需要的各类资源的数目
(1) T0时刻安全性分析
存在安全序列{P1, P3, P4, P0, P2},系统安全。
(2) T0之后的T1时刻P1请求资源Request1(1,0,2)可否允许?
- ①Request1(1,0,2) ≤ Need1(1,2,2),P1请求在最大需求范围内
- ②Request1(1,0,2) ≤ Available1(3,3,2),可用资源可满足P1请求需要
- ③假定可为P1分配,修改Available,Allocation1,Need1向量
- Available(2,3,0) = Available(3,3,2)-Request1(1,0,2);
- Need1(0,2,0) = Need1(1,2,2)-Request1(1,0,2);
- Allocation1(3,0,2) =Allocation1(2,0,0)+Request1(1,0,2);
- ④利用安全性算法检查试探将资源分配后状态的安全性
存在安全序列{P1, P3, P4, P0, P2},所以试探将资源分配给进程P1后的状态是安全的,可将资源分配给进程P1。
③ T1之后的T2时刻P4请求资源Request4(3,3,0)是否允许?
- Request4(3,3,0)≤Need4(4,3,1),P4请求在最大需求范围内。
- Request4(3,3,0)≤Available(2,3,0)不成立,即可用资源暂不能满足P4请求资源需要,P4阻塞等待。
P4请求资源Request4(3,3,0)不允许。
④ T2之后的T3时刻P0请求资源Request0(0,2,0)是否允许?
- Request0(0,2,0)≤Need0(7,4,3);
- Request0(0,2,0)≤Available(2,3,0);
系统暂时先假定可为P0分配资源,并修改有关数据,如下图所示:
进行安全性检查:可用资源Available(2,1,0)已不能满足任何进程的需要,故系统进入不安全状态,此时系统不分配资源。
程序结构
程序共有以下五个部分:
- (1).初始化init():输入进程数量、资源种类、资源可利用量、进程资源已分配量、进程最大需求量
- (2).当前安全性检查safe():用于判断当前状态安全
- (3).银行家算法bank():进行银行家算法模拟实现的模块
- (4).显示当前状态show():显示当前资源分配详细情况
- (5).主程序main():逐个调用初始化、显示状态、安全性检查、银行家算法函数,使程序有序的进行
四、代码
/** * @Author:小码哥 * @Package:PACKAGE_NAME * @Project:JavaProject * @name:Banker * @Date:2022/12/28 14:38 * @Filename:Banker * @Description:银行家算法 */ import java.util.Scanner; public class Banker { Scanner sc = new Scanner(System.in); int m; int n=3; char zy[] = new char[100]; //存放资源的名字 int Max[][] = new int[100][100]; //p[i]对j类资源的最大需求量 int Allocation[][]=new int[100][100]; //p[i]已分配到的j类资源数量 int Need[][]=new int[100][100]; //p[i]尚需的j类资源数量 int Available[]=new int[100]; //某类资源的可用量 int Request[]=new int[100]; //进程对某类资源的申请量 int Work[]=new int[100]; //存放某一时刻系统可提供的资源量 int Finish[]=new int[100]; //标记系统是否有足够的资源分配给各个进程 int flag[] = new int[100]; //P[i]进程是否已经满足全部所需资源 int Security[]=new int[100]; //存放安全序列 //初始化资源数和每个进程的最大需求量 public void init() { System.out.print("请输入进程数:"); m = sc.nextInt(); char x = 'A'; for(int j=0;j<n;j++) { zy[j] = x; x++; } System.out.print("请输入"+n+"类资源初始化的资源数:"); for(int i=0;i<n;i++) { Available[i] = sc.nextInt(); } System.out.println("请输入"+m+"个进程的:"); System.out.println("进程名 最大需求量:"); System.out.print(" "); for(int i=0;i<n;i++) { System.out.print(zy[i] + " "); } System.out.println(); for(int i=1;i<=m;i++) { System.out.print("进程p["+i+"]" + " "); for(int j=0;j<n;j++) { Max[i-1][j] = sc.nextInt(); } } } //尝试分配资源 public void test(int i) { for(int j=0;j<n;j++) { //尝试分配资源 Available[j]=Available[j]-Request[j]; Allocation[i][j]=Allocation[i][j]+Request[j]; Need[i][j]=Need[i][j]-Request[j]; } } //试探性分配资源作废,与test操作相反 public void retest(int i){ for(int j=0;j<n;j++){ Available[j]=Available[j]+Request[j]; Allocation[i][j]=Allocation[i][j]-Request[j]; Need[i][j]=Need[i][j]+Request[j]; } } //安全性算法 public int safe() { int l = 0; //设置work for(int j=0;j<n;j++) { Work[j] = Available[j]; } //初始化finish for(int i=0;i<m;i++) { Finish[i]=0; } //将已满足的进程标记为1 for(int i=0;i<m;i++) { int tem = 0; for(int j=0;j<n;j++) { if(Need[i][j]==0) { tem++; } if(tem == n) { flag[i] = 1; } } } for(int i=0;i<m;i++){ int apply=0; //用于记录已经全部满足的资源数 for(int j=0;j<n;j++){ if(Finish[i]==0 && Need[i][j]<=Work[j]){ apply++; //直到每类资源尚需数都小于当前系统可利用资源数才可分配 if(apply == n){ //apply等于资源类数,说明可以满足该进程的所有资源 for(int k=0;k<n;k++){ Work[k]=Work[k]+Allocation[i][k]; //更改当前可分配资源 } Finish[i]=1; if(flag[i] == 0) { Security[l++]=i; //尚未完成的进程序号存入安全序列 }else if(flag[i] == 1) { for(int k=0;k<n;k++) { Allocation[i][k] = 0; } } i=-1; //保证每次查询均从第一个进程开始 } } } } for(int i=0;i<m;i++){ if(Finish[i]==0){ //当前情况只要有一个进程不能得到执行完成说明系统不安全 return 0; } } return 1; } //打印申请资源成功后的相关信息 public void print(int z) { //如果该进程结束了,就回收它释放的资源 if(flag[z]==1) { for(int j=0;j<n;j++) { Available[j] = Available[j] + Max[z][j]; } } System.out.print("申请成功!安全序列为:"); int m1 = 0;//记录尚未完成的进程 for(int i=0;i<m;i++) { if(flag[i]==0) { m1++; } } for(int k=0;k<m1;k++) { Security[k] = Security[k] + 1; } for(int k=0;k<m1;k++){ System.out.print("p["+Security[k]+"]"); if(k<m1-1){ System.out.print("->"); } } System.out.println(); System.out.println("进程名 最大需求量 尚需求量 已分配量 执行结束否"); int t1=0; System.out.print(" "); while(t1!=3) { for(int j=0;j<n;j++) { System.out.print(zy[j] + " "); } System.out.print(" "); t1++; } System.out.println(); for(int k=0;k<m;k++) { int t2 = k+1; System.out.print("进程p["+t2+"]" + " "); for(int j=0;j<n;j++) { System.out.print(Max[k][j] + " "); } System.out.print(" "); for(int j=0;j<n;j++) { System.out.print(Need[k][j] + " "); } System.out.print(" "); for(int j=0;j<n;j++) { System.out.print(Allocation[k][j] + " "); } System.out.print(" "); if(flag[k] == 0) { System.out.print("working"); }else { System.out.print("finished"); } System.out.println(); } System.out.print("剩余资源数:" + " "); for(int j=0;j<n;j++) { System.out.print(Available[j] + " "); } } //第一次申请 public void first() { for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { Need[i][j] = Max[i][j];//未申请之前尚需求量等于最大需求量 } } System.out.println("请输入"+m+"个进程的:"); System.out.println("进程名 第一次的申请量:"); System.out.print(" "); for(int j=0;j<n;j++) { System.out.print(zy[j] + " "); } System.out.println(); for(int i=0;i<m;i++) { int t=i+1; System.out.print("进程p["+t+"]" + " "); for(int j=0;j<n;j++) { Request[j] = sc.nextInt(); } test(i);//试探性分配 if(safe()==1) { print(i); }else { retest(i);//不安全则试探性分配作废 System.out.println("无安全序列,申请不成功"); } System.out.println(); } } public static void main(String[] args) { int flag = 0; Scanner sc = new Scanner(System.in); int s = 1; Banker banker = new Banker(); banker.init(); banker.first(); while(s != 0) { System.out.println(); System.out.print("是否需要再申请资源?(1/0):"); s = sc.nextInt(); if(s == 1) { System.out.print("请输入进程编号(1-5)p:"); int z = sc.nextInt(); int z1 = z-1; //z1充当数组下标,比进程名少1 System.out.print("请输入进程p["+z+"]对"+banker.n+"类资源的申请量:"); for(int j=0;j<banker.n;j++) { banker.Request[j] = sc.nextInt(); } banker.test(z1); //尝试分配 if(banker.safe()==1) { banker.print(z1); }else { banker.retest(z1); //不安全则尝试分配作废 for(int j=0;j<banker.n;j++) { if(banker.Request[j]>banker.Available[j]) { System.out.println("申请资源超过系统可用资源,您的"+banker.zy[j]+"类可用资源为"+banker.Available[j]); break; } } System.out.print("请重新输入这个进程的申请信息!:"); for(int j=0;j<banker.n;j++) { banker.Request[j] = sc.nextInt(); } banker.test(z1); //尝试分配 if(banker.safe()==1) { banker.print(z1); }else { banker.retest(z1); System.out.println("无安全序列,申请不成功"); } } } } } }
五、结果展示
标签:Available,Java,操作系统,int,详解,进程,new,100,资源 From: https://www.cnblogs.com/huanghanyu/p/17010139.html