银行家算法

原理

死锁会引起计算机工作僵死，因此操作系统中必须防止。本实验的目的在于让学生独立的使用高级语言编写和调试一个系统动态分配资源的简单模拟程序，了解死锁产生的条件和原因，并采用银行家算法有效地防止死锁的发生，以加深对课堂上所讲授的知识的理解。

在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。

银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。
要解释银行家算法，必须先解释操作系统安全状态和不安全状态。
安全序列是指一个进程序列{P1，…，Pn}是安全的，即对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。

安全状态
如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。

不安全状态
不存在一个安全序列。不安全状态不一定导致死锁。

分析

在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。
银行家算法的基本思想是分配资源之前，判断系统是否是安全的；若是，才分配。它是最具有代表性的避免死锁的算法。
设进程cusneed提出请求REQUEST [i]，则银行家算法按如下规则进行判断。
(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，则转（2)；否则，出错。
(2)如果REQUEST [cusneed] [i]<= AVAILABLE[i]，则转（3)；否则，等待。
(3)系统试探分配资源，修改相关数据：
AVAILABLE[i]-=REQUEST[cusneed][i];
ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];
NEED[cusneed][i]-=REQUEST[cusneed][i];
(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。

安全检测方法：
（1)设置两个工作向量Work=AVAILABLE;FINISH
(2)从进程集合中找到一个满足下述条件的进程，
FINISH==false;
NEED<=Work;
如找到，执行（3)；否则，执行（4)
(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。
Work=Work+ALLOCATION;
Finish=true;
GOTO 2
(4)如所有的进程Finish= true，则表示安全；否则系统不安全。

程序代码：
banker.h

#pragma warning(disable:4996)
typedef int bool;
#define false 0
#define true !false//系统中所有进程数量
#define PROCESSES_NUMBER    5
typedef struct {int A;int B;int C;int D;}RESOURCE;//最大需求矩阵  MaxRESOURCE Max[PROCESSES_NUMBER];//已分配资源数矩阵 AllocationRESOURCE Allocation[PROCESSES_NUMBER];//需求矩阵RESOURCE Need[PROCESSES_NUMBER];//可用资源向量RESOURCE Available = {1,0,2,0};int safe[PROCESSES_NUMBER];

main.c

#include <stdio.h>
#include <string.h>
#include "banker.h"void inputMax()
{int i;printf("请输入最大需求矩阵\n");for (i = 0; i < PROCESSES_NUMBER; i++){scanf("%d%d%d%d",&Max[i].A,&Max[i].B,&Max[i].C,&Max[i].D);}
}
void inputAllocation(){int i;printf("请输入已分配资源数矩阵\n");for (i = 0; i < PROCESSES_NUMBER; i++){scanf("%d%d%d%d",&Allocation[i].A,&Allocation[i].B,&Allocation[i].C,&Allocation[i].D);}}
void inputAllocaltion(){int i;printf("请输入已分配资源数矩阵\n");for (i = 0; i < PROCESSES_NUMBER; i++){scanf("%d%d%d%d",&Allocation[i].A,&Allocation[i].B,&Allocation[i].C,&Allocation[i].D);}}//试探分配
void ProbeAlloc(int process,RESOURCE *res){Available.A -= res->A;Available.B -= res->B;Available.C -= res->C;Available.D -= res->D;Allocation[process].A += res->A;Allocation[process].B += res->B;Allocation[process].C += res->C;Allocation[process].D += res->D;Need[process].A -= res->A;Need[process].B -= res->B;Need[process].C -= res->C;Need[process].D -= res->D;}
void Back(int process,RESOURCE *res)
{Available.A+=Allocation[process].A;Allocation[process].A=0;Available.B+=Allocation[process].B;Allocation[process].B=0;Available.C+=Allocation[process].C;Allocation[process].C=0;Available.D+=Allocation[process].D;Allocation[process].D=0;
}//若试探分配后进入不安全状态，将分配回滚
void RollBack(int process,RESOURCE *res){Available.A += res->A;Available.B += res->B;Available.C += res->C;Available.D += res->D;Allocation[process].A -= res->A;Allocation[process].B -= res->B;Allocation[process].C -= res->C;Allocation[process].D -= res->D;Need[process].A += res->A;Need[process].B += res->B;Need[process].C += res->C;Need[process].D += res->D;}//安全性检查
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 && Need[i].D <= Work.D){//有则使其执行完成，并将已分配给该进程的资源全部回收Work.A += Allocation[i].A;Work.B += Allocation[i].B;Work.C += Allocation[i].C;Work.D += Allocation[i].D;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&& res->D <= Need[process].D){//request向量需小于Available向量if(res->A <= Available.A && res->B <= Available.B && res->C <= Available.C && res->D <= Available.D){//试探分配ProbeAlloc(process,res);//如果安全检查成立，则请求成功，否则将分配回滚并返回失败if(SafeCheck()){return true;}else{printf("安全性检查失败。原因：系统将进入不安全状态，有可能引起死锁。\n");printf("正在回滚...\n");RollBack(process,res);}}else{printf("安全性检查失败。原因：请求向量大于可利用资源向量。\n");}}else{printf("安全性检查失败。原因：请求向量大于需求向量。\n");}return false;}//输出资源分配表
void PrintTable(){printf("\t\t\t*********资源分配表*********\n");printf("Process       Max                  Allocation             Need                Available\n");printf("          A    B    C    D     A    B    C    D      A    B    C    D     A    B    C   D\n");printf("  P0      %d    %d    %d    %d     %d    %d    %d    %d      %d    %d    %d    %d     %d    %d    %d   %d\n",Max[0].A,Max[0].B,Max[0].C,Max[0].D,Allocation[0].A,Allocation[0].B,Allocation[0].C,Allocation[0].D,Need[0].A,Need[0].B,Need[0].C,Need[0].D,Available.A,Available.B,Available.C,Available.D);printf("  P1      %d    %d    %d    %d     %d    %d    %d    %d      %d    %d    %d    %d\n",Max[1].A,Max[1].B,Max[1].C,Max[1].D,Allocation[1].A,Allocation[1].B,Allocation[1].C,Allocation[1].D,Need[1].A,Need[1].B,Need[1].C,Need[1].D);printf("  P2      %d    %d    %d    %d     %d    %d    %d    %d      %d    %d    %d    %d\n",Max[2].A,Max[2].B,Max[2].C,Max[2].D,Allocation[2].A,Allocation[2].B,Allocation[2].C,Allocation[2].D,Need[2].A,Need[2].B,Need[2].C,Need[2].D);printf("  P3      %d    %d    %d    %d     %d    %d    %d    %d      %d    %d    %d    %d\n",Max[3].A,Max[3].B,Max[3].C,Max[3].D,Allocation[3].A,Allocation[3].B,Allocation[3].C,Allocation[3].D,Need[3].A,Need[3].B,Need[3].C,Need[3].D);printf("  P4      %d    %d    %d    %d     %d    %d    %d    %d      %d    %d    %d    %d\n",Max[4].A,Max[4].B,Max[4].C,Max[4].D,Allocation[4].A,Allocation[4].B,Allocation[4].C,Allocation[4].D,Need[4].A,Need[4].B,Need[4].C,Need[4].D);printf("\n");}
int main(){int i;int ch;inputMax();inputAllocation();for (i = 0; i < PROCESSES_NUMBER; i++){Need[i].A = Max[i].A - Allocation[i].A;Need[i].B = Max[i].B - Allocation[i].B;Need[i].C = Max[i].C - Allocation[i].C;Need[i].D = Max[i].D - Allocation[i].D;}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");goto over;}do{int     process;RESOURCE    res;PrintTable();printf("请依次输入请求分配的进程和对四类资源的请求数量：");scanf("%d%d%d%d%d",&process,&res.A,&res.B,&res.C,&res.D);if (request(process,&res)){ printf("分配成功。\n");if(Allocation[process].A==Max[process].A&&Allocation[process].B==Max[process].B&&Allocation[process].C==Max[process].C&&Allocation[process].D==Max[process].D){Back(process,&res);}}else{printf("分配失败。\n");}printf("是否继续分配？(Y/N):");fflush(stdin);              //虽然C标准不支持这种用法，但是VC++支持ch = getchar();} while (ch == 'Y' || ch == 'y');over:printf("执行完毕。");return 0;}/*测试数据 max        4 1 1 1 0 2 1 2 4 2 1 0 1 1 1 1 2 1 1 0allocation 3 0 1 1 0 1 0 0 1 1 1 0 1 1 0 1 0 0 0 0request测试 eg1:   1   1 0 1 0       failed         request > needeg2:   1   0 1 0 1       failed         request > avaliableeg3:   1   0 0 1 0    successful*/