操作系统实验之银行算法
一、实验目的
采用高级语言编写一个动态分配系统资源的程序，模拟死锁现象，观察死锁发生的条件，并采用适当的算法，有效地防止死锁的发生。
二、实验内容
本次实验采用银行算法防止死锁的发生。设有3个并发进程共享10个系统资源。在3个进程申请系统资源之和不超过10时，当然不可能发生死锁，因为各个进程资源都能满足。在有一个进程申请的系统资源数超过10时，必然会发生死锁。应该排队这两种情况。程序采用人工输入各进程的申请资源序列。如果随机给各进程分配资源，就可能发生死锁，这也就是不采用防止死锁算法的情况。假如，按照一定的规则，为各进程分配资源，就可以防止死锁的发生。
三、实验步骤
3.1任务分析
3.1.1 实验任务
- 设计一个几个并发进程共享m个系统资源的系统。进程可动态的申请资源和释放资源，系统按各进程的申请动态的分配资源。
- 系统应能显示各进程申请和释放资源的过程，能显示系统动态分配资源的过程，便于观察和分析。
- 系统应能选择是否采用防止死锁的算法，应设计多种防止死锁的算法，并能任意选择其中任何一种投入运行，同时要求，在不采用防止死锁算法时观察死锁现象发生的过程，在使用防止死锁的算法时，了解在同样条件下防止死锁发生的过程。
3.2 概要设计
抽象数据类型的定义：
1）资源：
属性：名称（name）、数量（amount）
操作：
初始化资源（InitResource(name, amount)）
获取资源名称（GetName()）
获取资源数量（GetAmount()）
设置资源数量（SetAmount(amount)）
2）进程：
属性：进程编号（ID）、最大需求资源（Max）、已分配资源（Allocation）、还需资源（Need）
操作：
初始化进程（InitProcess(ID, Max, Allocation)）
获取进程编号（GetID()）
获取最大需求资源矩阵（GetMax()）
获取已分配资源矩阵（GetAllocation()）
获取还需资源矩阵（GetNeed()）
3）系统状态：
属性：可用资源（Available）、进程集合（Processes）
操作：
初始化系统状态（InitSystemState(Available, Processes)）
获取可用资源矩阵（GetAvailable()）
获取进程集合（GetProcesses()）
主程序流程：
- 初始化系统状态：
输入资源种类数量和初始资源量、进程数量、每个进程的最大资源需求、已分配给每个进程的资源
- 显示初始系统状态：
调用显示系统状态函数（ShowSystemState()）
- 安全性检查：
调用安全性算法函数（CheckSafety()）
- 功能选择循环：
进入功能选择循环，直到用户选择离开。用户可以选择增加资源、删除资源、修改资源、分配资源、增加作业等功能
程序模块调用关系：
主程序根据用户选择调用相应的功能函数
- 增加资源：调用增加资源函数（AddResource()）
- 删除资源：调用删除资源函数（DeleteResource()）
- 修改资源：调用修改资源函数（ModifyResource()）
- 分配资源：调用分配资源函数（AllocateResource()）
- 增加作业：调用增加作业函数（AddJob()）
3.3详细设计
银行算法：顾名思义是来源于银行的借贷业务，一定数量的本金要应付各种客户的借贷周转，为了防止银行因资金无法周转而倒闭，对每一笔贷款，必须考察其最后是否能归还。研究死锁现象时就碰到类似的问题，有限资源为多个进程共享，分配不好就会发生每个进程都无法继续下去的死锁僵局。
银行算法的原理是先假定某一次分配成立，然后检查由于这次分配是否会引起死锁，即剩下的资源是不是能满足任一进程完成的需要。如这次分配是安全的（不会引起死锁），就实施本次分配，再作另一种分配试探，一直探索到各进程均满足各自的资源请求，防止了死锁的发生。
主要函数设计：
main() 函数作为程序的入口，首先提示用户输入系统资源种类和数量，并进行初始化。用户需要输入作业数量和每个进程的最大需求量，以及每个进程已经申请的资源量。程序提供了一个菜单，让用户选择不同的功能，如增加资源、删除资源、修改资源、分配资源、增加作业等。
showdata函数用于展示当前系统的资源分配状况，包括每个进程的最大需求、已分配资源和尚需资源。
changdata函数用于变更资源分配情况，主要在资源请求得到批准后调用。
safe函数实现了银行家算法的核心，即安全性算法。这个函数检查在当前资源分配情况下，系统是否处于安全状态。使得每个进程都可以按需求获得资源，执行完毕后释放资源，从而避免死锁。
share函数处理资源请求，首先检查请求是否合理（即请求量不超过需求量和可用量），然后尝试分配资源，并调用safe函数检查系统是否仍然安全。
addresources、delresources、changeresources和addprocess函数提供了添加、删除、修改资源和添加作业的功能，以适应动态变化的资源需求。
3.4调试分析
改进设想：
- 引入异常处理机制，处理用户输入错误、系统状态异常等情况，提高程序的健壮性。
- 在用户输入时进行更严格的检查，防止非法输入导致程序崩溃或不稳定。
3.5测试结果
测试结果和预期相同
3.6使用说明
运行程序，输入系统可供资源种类数量，名称，资源数量
输入作业数量，各进程最大需求量，已申请的资源量
输出系统目前可用资源，以及各进程资源分配
根据需求选择功能
四、实验总结
通过本次实验，我学习了。在实践中，我通过代码实现和调试更深刻地理解了银行家算法的工作原理和优缺点,也更直观的了解死锁发生的原因，初步掌握防止死锁、解除死锁的简单方法，加深理解教材中有关死锁的内容。
银行家算法是用于避免死锁的一种资源分配算法，它根据系统的状态和进程的资源需求来判断是否能够安全地分配资源。其可以有效地避免了死锁情况的发生，通过检查资源分配的请求，只有在分配资源不会导致系统不安全状态时才进行分配。并且确保只有在系统能够提供足够资源的情况下，才会分配资源给进程，保证资源的合理利用。但是由于算法会保留一部分资源以应对未来可能的请求，因此可能导致资源的浪费。除此之外，在每次资源请求时进行安全性检查，这可能会引入一定的开销。
这次实验不仅让我更加熟悉操作系统的内部机制，也为我今后深入学习操作系统和计算机体系结构提供了基础。也意识到操作系统的设计和优化是一个复杂而细致的工作，需要综合考虑各种因素，权衡不同的算法和策略。
五、附录
#include <stdio.h>
#include <string.h>
#define False 0
#define True 1
#define MAX 100
int Max[MAX][MAX] = {0}; // 各进程所需各类资源的最大需求
int Avaliable[MAX] = {0}; // 系统可用资源
char name[MAX] = {0}; // 资源的名称
int Allocation[MAX][MAX] = {0}; // 系统已分配资源
int Need[MAX][MAX] = {0}; // 还需要资源
int Request[MAX] = {0}; // 请求资源向量
int temp[MAX] = {0}; // 存放安全序列
int Work[MAX] = {0}; // 存放系统可提供资源
int M = 100; // 作业的最大数为100
int N = 100; // 资源的最大数为100
void showdata(); // 显示资源矩阵
int changdata(int i); // 进行资源分配
int safe(); // 安全性算法
void share(); // 利用银行家算法对申请资源对进行判定
void addresources(); // 添加资源
void delresources(); // 删除资源
void changeresources(); // 修改资源
void addprocess(); // 添加作业
int main() {
int i, j, number, choice, m, n, flag;
char ming;
// 输入系统可供资源种类数量和初始资源量
printf("***********************************\n");
printf("系统可供资源种类数量:");
scanf("%d", &n);
N = n;
for (i = 0; i < n; i++) {
printf("资源%d名称:", i + 1);
scanf(" %c", &ming);
name[i] = ming;
printf("资源数量:");
scanf("%d", &number);
Avaliable[i] = number;
}
// 输入进程数量
printf("作业数量:");
scanf("%d", &m);
M = m;
// 输入每个进程的最大资源需求
printf("各进程的最大需求量(%d*%d矩阵)[Max]:\n", m, n);
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
scanf("%d", &Max[i][j]);
Need[i][j] = Max[i][j];
}
}
// 输入已分配给每个进程的资源，并验证输入的合法性
do {
flag = 0;
printf("各进程已经申请的资源量(%d*%d矩阵)[Avaliable]:\n", m, 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 = 1;
}
Need[i][j] = Max[i][j] - Allocation[i][j];
}
}
if (flag) {
printf("申请的资源大于最大需求量，请重新输入!\n");
}
} while (flag);
showdata();
safe();
choice = 1;
// 菜单驱动循环，提供不同的功能选项
while (choice) {
printf("\n");
printf("1:增加资源 \n");
printf("2:删除资源 \n");
printf("3:修改资源 \n");
printf("4:分配资源 \n");
printf("5:增加作业 \n");
printf("0:离开 \n");
printf("*\n");
printf("请选择功能：");
scanf("%d", &choice);
switch (choice) {
case 1:
addresources();
break;
case 2:
delresources();
break;
case 3:
changeresources();
break;
case 4:
share();
break;
case 5:
addprocess();
break;
case 0:
choice = 0;
break;
default:
printf("请正确选择功能(0-5)\n");
break;
}
}
return 1;
}
// 显示当前资源和进程状态的函数
void showdata() {
int i, j;
printf("系统目前可用的资源[Avaliable]:\n");
for (i = 0; i < N; i++) {
printf("%c ", name[i]);
}
printf("\n");
for (j = 0; j < N; j++) {
printf("%d ", Avaliable[j]);
}
printf("\n");
printf(" Max Allocation Need\n");
printf("进程名 ");
for (j = 0; j < 3; j++) {
for (i = 0; i < N; i++) {
printf("%c ", name[i]);
}
printf(" ");
}
printf("\n");
for (i = 0; i < M; i++) {
printf(" %d ", i);
for (j = 0; j < N; j++) {
printf("%d ", Max[i][j]);
}
printf(" ");
for (j = 0; j < N; j++) {
printf("%d ", Allocation[i][j]);
}
printf(" ");
for (j = 0; j < N; j++) {
printf(" %d ", Need[i][j]);
}
printf("\n");
}
}
// 当资源分配给进程时更新资源分配和需求的函数
int changdata(int i) {
int j;
for (j = 0; j < M; j++) {
Avaliable[j] = Avaliable[j] - Request[j];
Allocation[i][j] = Allocation[i][j] + Request[j];
Need[i][j] = Need[i][j] - Request[j];
}
return 1;
}
// 使用银行家算法检查系统是否处于安全状态的函数
int safe() {
int i, k = 0, m, apply, Finish[MAX] = {0};
int j;
int flag = 0;
// 使用可用资源初始化Work数组
Work[0] = Avaliable[0];
Work[1] = Avaliable[1];
Work[2] = Avaliable[2];
// 检查进程是否能够完成而不会导致死锁
for (i = 0; i < M; i++) {
apply = 0;
for (j = 0; j < N; j++) {
if (Finish[i] == False && Need[i][j] <= Work[j]) {
apply++;
if (apply == N) {
for (m = 0; m < N; m++) {
Work[m] = Work[m] + Allocation[i][m];
}
Finish[i] = True;
temp[k] = i;
i = -1;
k++;
flag++;
}
}
}
}
for (i = 0; i < M; i++) {
if (Finish[i] == False) {
printf("系统不安全\n");
return -1;
}
}
printf("系统是安全的\n");
printf("分配的序列:");
for (i = 0; i < M; i++) {
printf("%d", temp[i]);
if (i < M - 1) {
printf("->");
}
}
printf("\n");
return 0;
}
// 分配资源的函数
void share() {
char ch;
int i = 0, j = 0;
ch = 'y';
printf("请输入要求分配的资源进程号(0-%d):", M - 1);
scanf("%d", &i);
printf("请输入进程 %d 申请的资源:\n", i);
for (j = 0; j < N; j++) {
printf("%c:", name[j]);
scanf("%d", &Request[j]);
}
for (j = 0; j < N; j++) {
if (Request[j] > Need[i][j]) {
printf("进程 %d 申请的资源大于它需要的资源 分配不合理，不予分配！\n", i);
ch = 'n';
break;
} else {
if (Request[j] > Avaliable[j]) {
printf("进程 %d 申请的资源大于系统现在可利用的资源 分配出错，不予分配!\n", i);
ch = 'n';
break;
}
}
}
if (ch == 'y') {
changdata(i);
showdata();
safe();
}
}
// 添加资源的函数
void addresources() {
int n, flag;
printf("请输入需要添加资源种类的数量:");
scanf("%d", &n);
flag = N;
N = N + n;
for (int i = 0; i < n; i++) {
printf("名称:");
scanf(" %c", &name[flag]);
printf("数量:");
scanf("%d", &Avaliable[flag++]);
}
showdata();
safe();
}
// 删除资源的函数
void delresources() {
char ming;
int i, flag = 1;
printf("请输入需要删除的资源名称：");
do {
scanf(" %c", &ming);
for (i = 0; i < N; i++) {
if (ming == name[i]) {
flag = 0;
break;
}
}
if (i == N) {
printf("该资源名称不存在，请重新输入：");
}
} while (flag);
for (int j = i; j < N - 1; j++) {
name[j] = name[j + 1];
Avaliable[j] = Avaliable[j + 1];
}
N = N - 1;
showdata();
safe();
}
// 修改资源的函数
void changeresources() {
printf("系统目前可用的资源[Avaliable]:\n");
for (int i = 0; i < N; i++) {
printf("%c:%d\n", name[i], Avaliable[i]);
}
printf("输入系统可用资源[Avaliable]:\n");
for (int k = 0; k < N; k++) {
printf("%c:", name[k]);
scanf("%d", &Avaliable[k]);
}
printf("经修改后的系统可用资源为\n");
for (int k = 0; k < N; k++) {
printf("%c:%d\n", name[k], Avaliable[k]);
}
showdata();
safe();
}
// 添加作业的函数
void addprocess() {
int flag = M;
M = M + 1;
printf("请输入该作业的最大需求量[Max]\n");
for (int i = 0; i < N; i++) {
printf("%c:", name[i]);
scanf("%d", &Max[flag][i]);
Need[flag][i] = Max[flag][i] - Allocation[flag][i];
}
showdata();
safe();
}
原文地址：https://blog.csdn.net/qq_61012545/article/details/142622961
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！