编程验证银行家算法

一、实验目的

银行家算法是避免死锁的一种重要方法，本设计要求编程实现银行家算法程序。了解银行家算法运行的规律币，加深对银行家算法的了解。

二、实验原理

银行家算法的思路:

1)、进程一开始向系统提出最大需求量.

2)、进程每次提出新的需求(分期贷款)都统计是否超出它事先提出的最大需求量.

3)、若正常，则判断该进程所需剩余剩余量(包括本次申请)是否超出系统所掌握的剩余资源量,若不超出,则分配,否则等待.

银行家算法的数据结构.

1)、系统剩余资源量A[n],其中A[n]表示第I类资源剩余量.

2)、各进程最大需求量,B[m][n],其中B[j][i]表示进程j对i类资源最大需求.

3)、已分配资源量C[m][n],其中C[j][i]表示系统j程已得到的第i资源的数量.

4)、剩余需求量.D[m][n],其中D[j][i]对第i资源尚需的数目.

银行家算法流程:当某时刻,某进程时,提出新的资源申请,系统作以下操作:

1)、判定E[n]是否大于D[j][n],若大于,表示出错.

2)、判定E[n]是否大于系统剩余量A[n],若大于,则该进程等待.

3)、若以上两步没有问题,尝试分配,即各变量作调整.

4)、按照安全性推测算法,判断,分配过后,系统是否安全,若安全,则实际分配,否则,撤消分配,让进程等待.

"安全性检测"算法

1)、先定义两个变量,用来表示推算过程的数据.

F[n]=A[n],表示推算过程中,系统中剩余资源量的变化.

J[n]=False表示推算过程中各进程是否假设"已完成"

2)、流程:

在"剩余"的进程中(在推算)过程中,一些进程假设已完成,查找D[j][n]<=F[n]的进程,找到后令J[j]=True(假设该进程完成),F[n]+D[j][n](该进程所占资源释放),如此循环执行.若最后,所有的F[n]=True(在推算过程中,所有进程均可以完成),则表示(分配过后)系统是安全的,否则系统是不安全的.

三、实验内容

在codeblock编译器下编写代码

首先现编写一个库文件‘s.h’，定义一个结构体：

typedef struct {

int A;

int B;

int C;

}RESOURCE;

结构体里面的三个域分别表示三种资源的数量。按书中的数据初速化三个矩阵RESOURCE Max[PROCESSES_NUMBER] =

{

{7,5,3},

{3,2,2},

{9,0,2},

{2,2,2},

{4,3,3}

};

//最大需求矩阵

RESOURCE Allocation[PROCESSES_NUMBER] =

{

{0,1,0},

{2,0,0},

{3,0,2},

{2,1,1},

{0,0,2}

};

//已分配资源数矩阵

RESOURCE Need[PROCESSES_NUMBER] =

{

{7,4,3},

{1,2,2},

{6,0,0},

{0,1,1},

{4,3,1}

};

//需求矩阵

RESOURCE Available = {3,3,2};

//可用资源向量

int safe[PROCESSES_NUMBER];

上面定义好数据后就可以开始运行代码。

运行后如图：

可以得到T0时刻的安全序列是(P1,P3,P4,P2,P0) 这里选择输入0 1 1 0，使Request0为(1,1,0)

输出结果为

可以得到安全序列为（P1,P3,P0,P2,P4）

继续输入2 1 5 7，使Request2为（1,5,7）

输出结果为

因为请求向量大于需求向量，所以此时分配失败。继续输入1 1 0 2，使Request1为(1,0,2)

此时系统进入不安全状态，有可能导致死锁。

附录：主函数代码

#include <stdio.h>

#include <string.h>

#include "s.h"

//进行试探分配

void ProbeAlloc(int process,RESOURCE *res)

{

Available.A -= res->A;

Available.B -= res->B;

Available.C -= res->C;

Allocation[process].A += res->A;

Allocation[process].B += res->B;

Allocation[process].C += res->C;

Need[process].A -= res->A;

Need[process].B -= res->B;

Need[process].C -= res->C;

}

//若进入不安全状态，则返回

void RollBack(int process,RESOURCE *res)

{

Available.A += res->A;

Available.B += res->B;

Available.C += res->C;

Allocation[process].A -= res->A;

Allocation[process].B -= res->B;

Allocation[process].C -= res->C;

Need[process].A += res->A;

Need[process].B += res->B;

Need[process].C += res->C;

}

//安全性检查

bool SafeCheck()

{

RESOURCE Work = Available;

bool Finish[PROCESSES_NUMBER] = {false,false,false,false,false};

int i;

int j = 0;

for (i = 0; i < PROCESSES_NUMBER; i++)

{

//是否已检查

if(Finish[i] == false)

{

//是否有足够的资源分配

if(Need[i].A <= Work.A && Need[i].B <= Work.B && Need[i].C <= Work.C)

{

//有则完成分配，并将资源全部回收

Work.A += Allocation[i].A;

Work.B += Allocation[i].B;

Work.C += Allocation[i].C;

Finish[i] = true;

safe[j++] = i;

i = -1;

}

}

}

//如果所有的Finish向量都为true则处于安全状态，否则为不安全状态

for (i = 0; i < PROCESSES_NUMBER; i++)

{

if (Finish[i] == false)

{

return false;

}

}

return true;

}

//资源分配请求

bool request(int process,RESOURCE *res)

{

//request向量需小于Need矩阵中对应的向量

if(res->A <= Need[process].A && res->B <= Need[process].B && res->C <= Need[process].C) {

//request向量需小于Available向量

if(res->A <= Available.A && res->B <= Available.B && res->C <= Available.C)

{

ProbeAlloc(process,res);

if(SafeCheck())

{

return true;

}

else

{

printf("安全性检查失败：系统将进入不安全状态，将有可能引起死锁。\n");

RollBack(process,res);

}

}

else

{

printf("安全性检查失败：请求向量大于可利用资源向量。\n");

}

}

else

{

printf("安全性检查失败：请求向量大于需求向量。\n");

}

return false;

}

//输出资源分配表

void Print()

{

printf("Process Max Allocation Need Available\n");

printf(" A B C A B C A B C A B C\n");

printf("

P0 %d %d %d %d %d %d %d %d %d %d %d %d\n",Max[0].A,Max[0].B,Max[0].C,Allocation[0].A,Allocation[0].B,Allocation[0].C,Need[0 ].A,Need[0].B,Need[0].C,Available.A,Available.B,Available.C);

printf("

P1 %d %d %d %d %d %d %d %d %d\n",Max[1].A, Max[1].B,Max[1].C,Allocation[1].A,Allocation[1].B,Allocation[1].C,Need[1].A,Need[1].B,Need[1].C );

printf("

P2 %d %d %d %d %d %d %d %d %d\n",Max[2].A, Max[2].B,Max[2].C,Allocation[2].A,Allocation[2].B,Allocation[2].C,Need[2].A,Need[2].B,Need[2].C );

printf("

P3 %d %d %d %d %d %d %d %d %d\n",Max[3].A, Max[3].B,Max[3].C,Allocation[3].A,Allocation[3].B,Allocation[3].C,Need[3].A,Need[3].B,Need[3].C );

printf("

P4 %d %d %d %d %d %d %d %d %d\n",Max[4].A, Max[4].B,Max[4].C,Allocation[4].A,Allocation[4].B,Allocation[4].C,Need[4].A,Need[4].B,Need[4].C );

printf("\n");

}

int main()

{

int ch;

printf("检查初始状态:");

if (SafeCheck())

{

printf("系统处于安全状态。\n");

printf("T0时刻的存在安全序列是{P%d,P%d,P%d,P%d,P%d}。\n",safe[0],safe[1],safe[2],safe[3],safe[4]);

}

else

{

printf("系统处于不安全状态。程序退出\n");

goto over;

}

do

{

int process;

RESOURCE res;

Print();

printf("请输入数据（如输入0 1 2 3则为P0 [1 2 3])：");

scanf("%d%d%d%d",&process,&res.A,&res.B,&res.C);

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):");

fflush(stdin);

ch = getchar();

} while (ch == 'Y' || ch == 'y');

over:

printf("执行完毕。");

return 0;

}