【Linux实践2】实验三：死锁的避免

---

深入理解死锁与银行家算法：动态资源分配模拟

实验目的

本实验旨在通过编写一个模拟动态资源分配的银行家算法程序，帮助我们更深入地理解死锁、产生死锁的必要条件、安全状态等关键概念，并掌握如何具体实施避免死锁的方法。

实验内容

1. 银行家算法模拟

我们将设计一个银行家算法来模拟资源的动态分配过程。这包括设置必要的数据结构和设计一个安全性检查算法。

2. 系统资源初始化

在实验开始时，我们将为系统配置一定量的资源。

3. 资源申请

我们将通过键盘输入的方式，模拟进程对资源的申请。

4. 资源预分配

如果预分配后系统处于安全状态，我们将更新系统的资源分配情况。如果不安全，则提示无法满足请求。

实验要点说明

数据结构

• 可利用资源向量：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()函数

1. 对于进程Pi的请求向量Requesti，如果Requesti[j]小于等于Need[i,j]，则继续下一步；否则出错。
2. 如果Requesti[j]小于等于Available[j]，则进行下一步；否则等待。
3. 试探性地将资源分配给进程Pi，并更新Available、Allocation和Need。
4. 试分配后，执行安全性算法检查系统是否处于安全状态。如果安全，则正式分配；否则，撤销试探性分配，进程Pi等待。

安全性算法safe()函数

1. 初始化Work和Finish向量。
2. 从进程集合中找到满足Need[i,j] ≤ Work[j]的进程。
3. 如果找到，执行资源分配，更新Work和Finish。
4. 如果所有进程的Finish[i]为true，表示系统处于安全状态；否则，处于不安全状态。

银行家算法实例

假设系统中有五个进程{P0、P1、P2、P3、P4}和三种类型资源{A、B、C}，每种资源的数量分别为10、5、7。以下是各进程的最大需求和某一时刻的资源分配情况。

在T0时刻，我们通过银行家算法检查系统是否安全。工作向量Work代表系统当前可用资源，我们需要确认是否存在一个进程执行序列，使得每个进程都能在不导致死锁的情况下完成。由于存在安全序列{P1, P3, P4, P0, P2}，我们可以确认T0时刻系统是安全的。

T1时刻P1请求资源分析

在T0时刻后，P1在T1时刻请求资源Request1(1,0,2)。这个请求是合理的，因为它没有超过P1的最大需求，并且系统有足够的可用资源来满足这个请求。我们假设可以为P1分配这些资源，并更新了Available、Allocation和Need向量。更新后，Available变为(2,3,0)，P1的Allocation变为(3,0,2)，Need变为(0,2,0)。接下来，我们使用安全性算法来检查这次分配后系统是否仍然安全。由于存在安全序列{P1, P3, P4, P0, P2}，我们可以确认即使在为P1分配资源后，系统仍然安全。因此，可以允许P1的资源请求。简而言之，P1的请求被允许，系统保持安全状态。

在T1时刻之后，P4在T2时刻提出了资源请求Request4(3,3,0)，但由于系统当时的Available资源(2,3,0)无法满足P4的请求，因此P4的请求被拒绝，P4必须等待。

随后，在T2时刻之后，P0在T3时刻请求资源Request0(0,2,0)。这个请求没有超出P0的最大需求Need0(7,4,3)，同时系统当前的Available资源(2,3,0)也能够满足P0的请求。因此，我们假设系统可以临时为P0分配这些资源，并相应地更新了资源分配的数据。这样，P0的请求被允许，系统资源分配状态也随之更新。简而言之，P0的请求得到了满足，系统资源分配得以继续进行。

当我们进行安全性检查时，发现可用资源Available(2,1,0)已经不足以满足任何进程的进一步需求，这意味着系统已经进入了不安全状态。在这种情况下，为了保证系统资源分配的安全性，避免潜在的死锁，系统不会进行资源分配。

程序的结构设计如下：

1. 初始化函数init()：这个部分负责输入所有的初始数据，包括进程的数量、资源的种类、系统可利用的资源总量、已经分配给各个进程的资源量以及每个进程的最大资源需求。这是程序运行的基础，确保我们有一个明确的起点状态。

2. 安全性检查函数safe()：此函数的核心任务是评估当前的资源分配状态是否安全。它会根据当前的资源分配和需求情况，判断系统是否能够找到一个安全的执行序列，以确保所有进程都能顺利完成。

3. 银行家算法函数bank()：这个模块实现了银行家算法的核心逻辑，用于模拟和处理进程的资源请求。它会根据进程的请求和当前的资源状态，决定是否分配资源，并更新系统的资源分配情况。

4. 显示当前状态函数show()：这个功能允许用户查看当前的资源分配详情，包括每个进程已分配的资源、还需要的资源以及系统的可用资源。这有助于用户直观地理解系统的状态。

5. 主程序main()：作为程序的入口点，main()函数负责协调程序的运行流程。它将依次调用初始化、显示状态、安全性检查和银行家算法函数，确保程序按照既定的逻辑顺序执行。
   
   代码：

#include <stdio.h>
#include <stdlib.h>#define False 0
#define True 1// 定义最大进程数和资源数
#define MAX_PROCESS 100
#define MAX_RESOURCE 100// 全局变量定义
char resourceName[MAX_RESOURCE]; // 资源名称
int Max[MAX_PROCESS][MAX_RESOURCE]; // 最大需求矩阵
int Allocation[MAX_PROCESS][MAX_RESOURCE]; // 已分配资源矩阵
int Need[MAX_PROCESS][MAX_RESOURCE]; // 还需资源矩阵
int Available[MAX_RESOURCE]; // 可用资源向量
int Request[MAX_RESOURCE]; // 请求资源向量
int Work[MAX_RESOURCE]; // 工作向量
int Finish[MAX_PROCESS]; // 完成向量
int SafetySequence[MAX_PROCESS]; // 安全序列int processCount = 0; // 进程数量
int resourceCount = 0; // 资源种类// 初始化数据
void init() {int i, j, m, n;int number, flag;char name; // 资源名称int temp[MAX_RESOURCE] = {0}; // 已分配资源临时存储// 输入资源种类和每种资源的初始数量printf("请输入资源种类数：");scanf("%d", &n);resourceCount = n;for (i = 0; i < n; i++) {printf("资源%d的名称：", i);scanf("%c", &name);resourceName[i] = name;printf("资源%c的初始数量：", name);scanf("%d", &number);Available[i] = number;}// 输入进程数量和最大需求矩阵printf("\n请输入进程数量：");scanf("%d", &m);processCount = m;printf("\n请输入各进程的最大需求矩阵(Max)：\n");do {flag = False;for (i = 0; i < m; i++)for (j = 0; j < n; j++) {scanf("%d", &Max[i][j]);if (Max[i][j] > Available[j])flag = True;}if (flag)printf("资源最大需求量大于系统中资源最大量，请重新输入!\n");} while (flag);// 输入各进程已分配的资源量，并计算还需资源量do {flag = False;printf("\n请输入各进程已分配的资源量(Allocation)：\n");for (i = 0; i < m; i++) {for (j = 0; j < n; j++) {scanf("%d", &Allocation[i][j]);if (Allocation[i][j] > Max[i][j])flag = True;Need[i][j] = Max[i][j] - Allocation[i][j];temp[j] += Allocation[i][j]; // 统计已分配资源}}if (flag)printf("分配的资源大于最大量，请重新输入!\n");} while (flag);// 计算系统中可利用的资源量for (j = 0; j < n; j++)Available[j] -= temp[j];
}// 显示资源分配矩阵
void showData() {int i, j;printf("系统目前可用的资源[Available]：\n");for (i = 0; i < resourceCount; i++)printf("%c  ", resourceName[i]);printf("\n");for (j = 0; j < resourceCount; j++)printf("%d  ", Available[j]);printf("\n");printf("系统当前的资源分配情况如下：\n");printf("进程名     Max     Allocation    Need\n");for (j = 0; j < 3; j++) {for (i = 0; i < resourceCount; i++)printf("%c  ", resourceName[i]);printf("     ");}printf("\n");for (i = 0; i < processCount; i++) {printf("P%d        ", i);for (j = 0; j < resourceCount; j++)printf("%d  ", Max[i][j]);printf("      ");for (j = 0; j < resourceCount; j++)printf("%d  ", Allocation[i][j]);printf("      ");for (j = 0; j < resourceCount; j++)printf("%d  ", Need[i][j]);printf("\n");}
}// 试探性分配资源
int test(int i) {for (int j = 0; j < resourceCount; j++) {Available[j] -= Request[j];Allocation[i][j] += Request[j];Need[i][j] -= Request[j];}return True;
}// 试探性分配资源作废
int Retest(int i) {for (int j = 0; j < resourceCount; j++) {Available[j] += Request[j];Allocation[i][j] -= Request[j];Need[i][j] += Request[j];}return True;
}// 安全性算法
int safe() {int i, j, k = 0, m, apply;for (j = 0; j < resourceCount; j++)Work[j] = Available[j];for (i = 0; i < processCount; i++)Finish[i] = False;for (i = 0; i < processCount; i++) {apply = 0;for (j = 0; j < resourceCount; j++) {if (Finish[i] == False && Need[i][j] <= Work[j]) {apply++;if (apply == resourceCount) {for (m = 0; m < resourceCount; m++)Work[m] += Allocation[i][m];Finish[i] = True;SafetySequence[k++] = i;i = -1;}}}}for (i = 0; i < processCount; i++) {if (Finish[i] == False) {printf("系统不安全\n");return False;}}printf("系统是安全的!\n");printf("存在一个安全序列：");for (i = 0; i < processCount; i++) {printf("P%d", SafetySequence[i]);if (i < processCount - 1)printf("->");}printf("\n");return True;
}// 利用银行家算法对申请资源进行试分
void bank() {int flag = True;int i, j;printf("请输入请求分配资源的进程号(0-%d):", processCount - 1);scanf("%d", &i);printf("请输入进程P%d要申请的资源个数:\n", i);for (j = 0; j < resourceCount; j++) {printf("%c:", resourceName[j]);scanf("%d", &Request[j]);}for (j = 0; j < resourceCount; j++) {if (Request[j] > Need[i][j]) {printf("进程P%d申请的资源大于它需要的资源", i);printf("分配不合理，不予分配！\n");flag = False;break;} else if (Request[j] > Available[j]) {printf("进程%d申请的资源大于系统现在可利用的资源", i);printf("\n系统尚无足够资源，不予分配!\n");flag = False;break;}}if (flag) {test(i);showData();if (!safe()) {Retest(i);showData();}}
}int main() {printf("银行家算法的实现\n");init();showData();if (!safe()) exit(0);char choice;do {printf("请选择操作：R(请求资源)/E(退出)：");scanf("%c", &choice);switch (choice) {case 'R':case 'r':bank();break;case 'E':case 'e':exit(0);break;default:printf("无效输入，请重新选择！\n");break;}} while (1);return 0;
}