实验四 模拟银行家算法
前言
- 参考教材《操作系统 第四版》汤小丹
- 最近发生了些不愉快，计划寒假系统更新一些知识(还没想好，计划是就业方向类的，可以推荐推荐哇)！感觉内容质量不高，仅供参考，只放全部代码，这次就不分开讲了
实验目的
了解掌握银行家算法，学会模拟实现资源分配，同时有要求编写和调试一个系统分配资源的简单模拟程序，观察死锁产生的条件，并使用
适当的算法，有效的防止和避免死锁的发生
实验内容
1.实验背景
在多道程序系统中，虽可借助与多个进程的并发执行，来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险—死琐。
产生死锁的原因可归结为两点：
1)竞争资源。当系统中供多个进程共享的资源如打印机、公用队列等，其数目不足以满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁。
2)进程间推进顺序非法。进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁。
最有代表性的避免死锁的算法，是Dijkstra的银行家算法。这是由于该算法能用与银行系统现金贷款的发放而得名的
什么是银行家算法?
银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。
在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构
2.算法描述
设Request[i] 是进程Pi的请求向量，如果Requesti[j]=K,表示进程Pi需要K个Rj类型的资源，当Pi发出资源请求后，系统按下面步骤进行检查：
（1）如果Requesti[j]<=Need[i,j]，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
（2）如果Requesti[j]<=Available[j],便转向步骤3；否则，表示尚无足够资源，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） 可利用资源向量Available。这是一个含有n个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K,则表示系统中现有Rj类资源K个
（2）最大需求矩阵Max。这是一个m*n的矩阵，它定义了系统中n个进程中每一个进程对m类资源的最大需求。如果Max[i,j]=K,则表示进程i需要Rj类资源的最大数目为K
（3）分配矩阵Allocation。这也是一个m*n的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K,则表示进程i当前已分得Rj类资源的数目为K
（4）需求矩阵Need1。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K,则表示进程i还需要Rj类资源K个，方能完成其任务
(5) 工作数组Work。这是一个含有n个元素的数组，它代表可以提供分配的资源数，初始值是Available中的数值，随着资源的回收，它的值也会改变，公式是Work[i]=Work[i]+Allocation[i]
实验步骤
流程图
完整代码
package 操作系统实验;
import java.util.Arrays;
import java.util.Scanner;
public class 银行家算法 {
static int resourceNum = 3;
static int processNum = 5;
static int[] available = new int[] { 3, 3, 2 };
static int[][] maxRequest = new int[][] { { 7, 5, 3 }, { 3, 2, 2 }, { 9, 0, 2 }, { 2, 2, 2 }, { 4, 3, 3 } };
static int[][] allocation = new int[][] { { 0, 1, 0 }, { 2, 0, 0 }, { 3, 0, 2 }, { 2, 1, 1 }, { 0, 0, 2 } };
static int[][] need = new int[][] { { 7, 4, 3 }, { 1, 2, 2 }, { 6, 0, 0 }, { 0, 1, 1 }, { 4, 3, 1 } };
static boolean[] finish = new boolean[] { false, false, false, false, false };
static int[] safeSeries = new int[] { 0, 0, 0, 0, 0 };
static int[] request = new int[] { 0, 0, 0 };
static int num;
Scanner sc = new Scanner(System.in);
public static void showInfo() {
System.out.println("**************************************************************");
System.out.println("当前系统各类资源剩余:");
System.out.println(Arrays.toString(available));
System.out.printf("\n当前系统资源情况：\n");
System.out.printf(" PID\t\t maxRequest\tAllocation\t Need\n");
for (int i = 0; i < processNum; i++) {
System.out.printf(" P%d\t\t", i);
for (int j = 0; j < resourceNum; j++) {
System.out.printf("%2d", maxRequest[i][j]);
}
System.out.printf("\t\t");
for (int j = 0; j < resourceNum; j++) {
System.out.printf("%2d", allocation[i][j]);
}
System.out.printf("\t\t");
for (int j = 0; j < resourceNum; j++) {
System.out.printf("%2d", need[i][j]);
}
System.out.println();
}
}
public static void safeInfo(int[] work, int i) {
int j;
System.out.printf(" P%d\t\t", i);
for (j = 0; j < resourceNum; j++) {
System.out.printf("%2d", work[j]);
}
System.out.printf("\t\t");
for (j = 0; j < resourceNum; j++) {
System.out.printf("%2d", allocation[i][j]);
}
System.out.printf("\t\t");
for (j = 0; j < resourceNum; j++) {
System.out.printf("%2d", need[i][j]);
}
System.out.printf("\t\t");
for (j = 0; j < resourceNum; j++) {
System.out.printf("%2d", allocation[i][j] + work[j]);
}
System.out.println();
}
static boolean isAllZero(int i) {
num = 0;
for (int j = 0; j < resourceNum; j++) {
if (need[i][j] == 0) {
num++;
}
}
if (num == resourceNum) {
return true;
} else {
return false;
}
}
static boolean Safe() {
int safeIndex = 0;
int allFinishNum = 0;
int[] work = new int[resourceNum];
int r = 0;
int temp = 0;
int pNum = 0;
for (int j = 0; j < resourceNum; j++) {
work[j] = available[j];
}
for (int i = 0; i < processNum; i++) {
if (isAllZero(i)) {
finish[i] = true;
allFinishNum++;
} else {
finish[i] = false;
}
}
while (allFinishNum != processNum) {
num = 0;
for (int j = 0; j < resourceNum; j++) {
if (need[r][j] <= work[j] && finish[r] == false) {
num++;
}
}
if (num == resourceNum) {
allFinishNum++;
safeInfo(work, r);
safeSeries[safeIndex] = r;
safeIndex++;
finish[r] = true;
for (int j = 0; j < resourceNum; j++) {
work[j] = work[j] + allocation[r][j];
}
}
r++;
if (r >= processNum) {
r = r % processNum;
if (temp == allFinishNum) {
break;
}
temp = allFinishNum;
}
pNum = allFinishNum;
}
for (int i = 0; i < processNum; i++) {
if (finish[i] == false) {
System.out.printf("\n当前系统不安全！\n\n");
return false;
}
}
System.out.printf("\n当前系统安全~\n\n安全序列为：");
for (int i = 0; i < processNum; i++) {
if (isAllZero(i)) {
pNum--;
}
}
for (int i = 0; i < pNum; i++) {
System.out.printf("%d ", safeSeries[i]);
}
return true;
}
public static void main(String[] args) {
int curProcess = 0;
showInfo();
System.out.printf("\n\n系统安全情况分析：\n");
System.out.printf(" PID\t\t Work\t\t Allocation\t Need\t\t Work+Allocation\n");
boolean safe = Safe();
Scanner scanner = new Scanner(System.in);
while (safe) {
do {
if (curProcess >= processNum || curProcess < 0) {
System.out.printf("\n请不要输入超出进程数量的值或其他字符：\n");
}
System.out.printf("\n**************************************************************\n");
System.out.printf("\n输入要分配的进程：");
curProcess = scanner.nextInt();
System.out.println();
} while (curProcess >= processNum || curProcess < 0);
for (int j = 0; j < resourceNum; j++) {
int requestJ = 0;
do {
if (requestJ < 0 || requestJ > available[j]) {
System.out.printf("\n请不要输入超出进程所需资源数量或输入为负数或其他字符：\n");
}
System.out.printf("请输入要分配给进程 P%d 的第 %d 类资源：", curProcess, j + 1);
requestJ = scanner.nextInt();
request[j] = requestJ;
} while (requestJ < 0 || requestJ > available[j]);
}
num = 0;
for (int j = 0; j < resourceNum; j++) {
if (request[j] <= need[curProcess][j] && request[j] <= available[j]) {
num++;
} else {
System.out.printf("\n发生错误！可能原因如下：\n(1)您请求分配的资源可能大于该进程的某些资源的最大需要！\n(2)系统所剩的资源已经不足了！\n");
break;
}
}
if (num == resourceNum) {
num = 0;
for (int j = 0; j < resourceNum; j++) {
available[j] = available[j] - request[j];
allocation[curProcess][j] = allocation[curProcess][j] + request[j];
need[curProcess][j] = need[curProcess][j] - request[j];
if (need[curProcess][j] == 0) {
num++;
}
}
if (num == resourceNum) {
for (int j = 0; j < resourceNum; j++) {
available[j] = available[j] + allocation[curProcess][j];
}
System.out.printf("\n\n本次分配进程 P%d 完成,该进程占用资源全部释放完毕！\n", curProcess);
} else {
System.out.printf("\n\n本次分配进程 P%d 未完成！\n", curProcess);
}
showInfo();
System.out.printf("\n系统安全情况分析\n");
System.out.printf(" PID\t\t Work\t\tAllocation\t Need\t\tWork+Allocation\n");
if (!Safe()) {
for (int j = 0; j < resourceNum; j++) {
available[j] = available[j] + request[j];
allocation[curProcess][j] = allocation[curProcess][j] - request[j];
need[curProcess][j] = need[curProcess][j] + request[j];
}
System.out.printf("资源不足，等待中...\n\n分配失败！\n");
}
}
}
}
}
|
运行结果
总结
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构
wechat
alipay
