admin 管理员组文章数量: 887006
一、实验目的
- 理解死锁的概念，了解导致死锁的原因。
- 掌握死锁的避免方法，理解安全状态和不安全状态的概念。
- 理解银行家算法，并应用银行家算法避免死锁。
二、实验原理
银行家算法的基本思想：分配资源之前，判断系统是否处于安全状态，若处于安全状态则分配资源，否则不进行分配。该算法是典型的避免死锁算法。
银行家算法的基本结构如下：
假设Requesti是进程 Pi 的资源请求向量， 如果Requesti [j] = k，表示进程 Pi 需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查。
（1）如果Requesti[j]£ Need[I, j]，则转向步骤（2），否则认为出错，因为进程所申请的资源数已经超过所需要的最大数。
（2）如果Requesti[j]£ Available, 则转向步骤（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等待。
银行家算法的数据结构：
Available: 长度为 m的向量。如果available[j]=k，那么资源Rj有k个实例有效；
Max: n x m 矩阵。 如果Max[i,j]=k，那么进程Pi可以最多请求资源Rj的k个实例；
Allocation: n x m 矩阵。如果Allocation[i,j]=k，那么进程Pj当前分配了k个资源Rj的实例；
Need: n x m 矩阵。如果Need[i,j]=k，那么进程Pj还需要k个资源Rj的实例；
Need [i,j] = Max[i,j] – Allocation [i,j].
银行家算法具体示例如下：
（1）5个进程P0、P1、P2 、P3、P4；3个资源类型A(10个实例），B（5个实例），C（7个实例）
（2）时刻T0的快照：
Allocation Max Available
A B C A B C A B C
P0 0 1 0 7 5 3 3 3 2
P1 2 0 0 3 2 2
P2 3 0 2 9 0 2
P3 2 1 1 2 2 2
P4 0 0 2 4 3 3
（3）矩阵的内容。Need被定义为Max– Allocation
（4）系统处在安全的状态，因为序列P1, P3, P4, P2, P0 满足安全标准
（5）检查Request £ Available，即(1, 0, 2) £(3, 3, 2)为真
Allocation Need Available
A B C A B C A B C
P0 0 1 0 7 4 3 2 3 0
P1 3 0 2 0 2 0
P2 3 0 2 6 0 0
P3 2 1 1 0 1 1
P4 0 0 2 4 3 1
（6）执行安全算法表明序列P1, P3, P4, P0, P2满足要求
三、实验内容与要求
假定有多个进程对多种资源进行请求，设计银行家算法的数据结构和程序结构，判断存在资源分配的安全序列。在Visual C++6.0集成开发环境下，使用C语言编写程序实现这个算法并进行测试。补充完整程序实现银行家算法安全性检查和资源分配请求（参照附录）
四、实验提交资料
- 定义数据结构
- 算法描述（自然语言或伪代码）
- 程序代码、测试结果与分析
- 收获与体会
要求：将以上资料收集齐后，撰写实验报告。
#include <stdio.h>
#include <string.h>
#define False 0
#define True 1
#define Process_num 5 //系统中所有进程数量
typedef struct {
int r1;
int r2;
int r3;
}Resource;
//最大需求矩阵
Resource Max[Process_num] =
{ {6,4,3}, {3,2,4}, {9,0,3}, {2,2,2}, {3,4,3} };
//已分配资源数矩阵
Resource Allocation[Process_num] =
{ {1,1,0}, {2,0,1}, {4,0,2}, {2,1,1}, {0,1,2} };
//需求矩阵
Resource Need[Process_num] =
{ {5,3,3}, {1,2,3}, {5,0,1}, {0,1,1}, {3,3,1} };
//可用资源向量
Resource Available = {3,3,2};
int safe[Process_num];
//试探分配
void ProbeAlloc(int process, Resource *res)
{
Available.r1 -= res->r1;
Available.r2 -= res->r2;
Available.r3 -= res->r3;
Allocation[process].r1 += res->r1;
Allocation[process].r2 += res->r2;
Allocation[process].r3 += res->r3;
Need[process].r1 -= res->r1;
Need[process].r2 -= res->r2;
Need[process].r3 -= res->r3;
}
//若试探分配后进入不安全状态，将分配回滚
void RollBack(int process, Resource *res)
{
Available.r1 += res->r1;
Available.r2 += res->r2;
Available.r3 += res->r3;
Allocation[process].r1 -= res->r1;
Allocation[process].r2 -= res->r2;
Allocation[process].r3 -= res->r3;
Need[process].r1 += res->r1;
Need[process].r2 += res->r2;
Need[process].r3 += res->r3;
}
//安全性检查
int SafeCheck()
{
Resource Work = Available;
int Finish[Process_num] = {False, False, False, False, False};
int i, j = 0;
int k=0;
for (i = 0; i < Process_num; i++)
{
for(j=0;j<Process_num;j++){
if(Finish[j]==true) continue;
else{
if(Need[j].r1<=Work.r1 &&Need[j].r2<=Work.r2 &&Need[j].r3<=Work.r3){
Finish[j]=true;
Work.r1+=Allocation[j].r1;
Work.r2+=Allocation[j].r2;
Work.r3+=Allocation[j].r3;
safe[k++]=j;
}
}
}
//完成编写本程序段实现银行家算法安全性检查
}
for(j=0;j<Process_num;j++){
if(Finish[j]==false) return false;
}
return True;
}
//资源分配请求
int Request(int process, Resource *res)
{
//request向量需小于Need矩阵中对应的向量
if(res->r1 <= Need[process].r1 && res->r2 <= Need[process].r2 && res->r3 <= Need[process].r3)
{
//完成编写本程序段实现银行家算法资源分配请求
ProbeAlloc(process,res);
if(SafeCheck()) return true;
else{
RollBack(process,res);
}
}
else
{
printf("安全性检查失败。原因：请求向量大于需求向量。\n");
}
return False;
}
//输出资源分配表
void PrintTable()
{
printf("\t\t\t*********资源分配表*********\n");
printf("Process Max Allocation Need Available\n");
printf(" r1 r2 r3 r1 r2 r3 r1 r2 r3 r1 r2 r3\n");
printf(" P0 %d %d %d %d %d %d %d %d %d %d %d %d\n",Max[0].r1,Max[0].r2,Max[0].r3,Allocation[0].r1,Allocation[0].r2,Allocation[0].r3,Need[0].r1,Need[0].r2,Need[0].r3,Available.r1,Available.r2,Available.r3);
printf(" P1 %d %d %d %d %d %d %d %d %d\n",Max[1].r1,Max[1].r2,Max[1].r3,Allocation[1].r1,Allocation[1].r2,Allocation[1].r3,Need[1].r1,Need[1].r2,Need[1].r3);
printf(" P2 %d %d %d %d %d %d %d %d %d\n",Max[2].r1,Max[2].r2,Max[2].r3,Allocation[2].r1,Allocation[2].r2,Allocation[2].r3,Need[2].r1,Need[2].r2,Need[2].r3);
printf(" P3 %d %d %d %d %d %d %d %d %d\n",Max[3].r1,Max[3].r2,Max[3].r3,Allocation[3].r1,Allocation[3].r2,Allocation[3].r3,Need[3].r1,Need[3].r2,Need[3].r3);
printf(" P4 %d %d %d %d %d %d %d %d %d\n",Max[4].r1,Max[4].r2,Max[4].r3,Allocation[4].r1,Allocation[4].r2,Allocation[4].r3,Need[4].r1,Need[4].r2,Need[4].r3);
printf("\n");
}
int main()
{
int ch;
printf("先检查初始状态是否安全。\n");
if (SafeCheck())
{
printf("系统处于安全状态。\n");
printf("安全序列是{P%d,P%d,P%d,P%d,P%d}。\n",safe[0],safe[1],safe[2],safe[3],safe[4]);
}
else
{
printf("系统处于不安全状态。程序将退出...\n");
printf("执行完毕。");
return 0;
}
do
{
int process;
Resource res;
PrintTable();
printf("请依次输入请求分配的进程和对三类资源的请求数量：\n");
scanf("%d%d%d%d",&process,&res.r1,&res.r2,&res.r3);
if (Request(process, &res))
{
printf("分配成功。\n");
printf("安全序列是{P%d,P%d,P%d,P%d,P%d}。\n",safe[0],safe[1],safe[2],safe[3],safe[4]);
}
else
{
printf("分配失败。\n");
}
printf("是否继续分配？(Y/N):");
ch = getchar();
ch = getchar();
} while (ch == 'Y' || ch == 'y');
return 0;
}
版权声明：本文标题：【银行家算法】超清晰代码 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1727377667h1111092.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论