银行家算法是一种最有代表性的避免死锁的算法。

要解释银行家算法，必须先解释操作系统安全状态和不安全状态。

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

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

那么什么是安全序列呢？

安全序列：一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j <i )当前占有资源量之和。

银行家算法：

我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。

算法：

n：系统中进程的总数

m：资源类总数

Available: ARRAY[1..m] of integer

Max: ARRAY[1..n,1..m] of integer

Allocation: ARRAY[1..n,1..m] of integer

Need: ARRAY[1..n,1..m] of integer

Request: ARRAY[1..n,1..m] of integer

符号说明：

Available 可用剩余资源

Max 最大需求

Allocation 已分配资源

Need 需求资源

Request 请求资源

当进程pi提出资源申请时，系统执行下列

步骤：(“=”为赋值符号，“==”为等号)

step（1）若Request<=Need, goto step（2）；否则错误返回

step（2）若Request<=Available, goto step（3）；否则进程等待

step（3）假设系统分配了资源，则有：

Available=Available-Request

Allocation=Allocation+Request

Need=Need-Request

若系统新状态是安全的，则分配完成

若系统新状态是不安全的，则恢复原状态，进程等待

为进行安全性检查，定义数据结构：

Work:ARRAY[1..m] of integer

Finish:ARRAY[1..n] of Boolean

安全性检查的步骤：

step (1):

Work=Available

Finish=false

step (2) 寻找满足条件的i：

a.Finish==false

b.Need<=Work

如果不存在，goto step(4)

step(3)

Work=Work+Allocation

Finish=true

goto step(2)

step (4) 若对所有i,Finish=true,则系统处于安全状态，否则处于不安全状态

/* 银行家算法，操作系统概念(OS concepts Six Edition)

reedit by Johnny hagen，SCAU，run at vc6.0

*/

#include "malloc.h"

#include "stdio.h"

#include "stdlib.h"

#define alloclen sizeof(struct allocation)

#define maxlen sizeof(struct max)

#define avalen sizeof(struct available)

#define needlen sizeof(struct need)

#define finilen sizeof(struct finish)

#define pathlen sizeof(struct path)

struct allocation

{

int value

struct allocation *next

}

struct max

{

int value

struct max *next

}

struct available /*可用资源数*/

{

int value

struct available *next

}

struct need /*需求资源数*/

{

int value

struct need *next

}

struct path

{

int value

struct path *next

}

struct finish

{

int stat

struct finish *next

}

int main()

{

int row,colum,status=0,i,j,t,temp,processtest

struct allocation *allochead,*alloc1,*alloc2,*alloctemp

struct max *maxhead,*maxium1,*maxium2,*maxtemp

struct available *avahead,*available1,*available2,*workhead,*work1,*work2,*worktemp,*worktemp1

struct need *needhead,*need1,*need2,*needtemp

struct finish *finihead,*finish1,*finish2,*finishtemp

struct path *pathhead,*path1,*path2

printf("\n请输入系统资源的种类数:")

scanf("%d",&colum)

printf("请输入现时内存中的进程数:")

scanf("%d",&row)

printf("请输入已分配资源矩阵:\n")

for(i=0i<rowi++)

{

for (j=0j<columj++)

{

printf("请输入已分配给进程 p%d 的 %c 种系统资源:",i,'A'+j)

if(status==0)

{

allochead=alloc1=alloc2=(struct allocation*)malloc(alloclen)

alloc1->next=alloc2->next=NULL

scanf("%d",&allochead->value)

status++

}

else

{

alloc2=(struct allocation *)malloc(alloclen)

scanf("%d,%d",&alloc2->value)

if(status==1)

{

allochead->next=alloc2

status++

}

alloc1->next=alloc2

alloc1=alloc2

}

}

}

alloc2->next=NULL

status=0

printf("请输入最大需求矩阵:\n")

for(i=0i<rowi++)

{

for (j=0j<columj++)

{

printf("请输入进程 p%d 种类 %c 系统资源最大需求:",i,'A'+j)

if(status==0)

{

maxhead=maxium1=maxium2=(struct max*)malloc(maxlen)

maxium1->next=maxium2->next=NULL

scanf("%d",&maxium1->value)

status++

}

else

{

maxium2=(struct max *)malloc(maxlen)

scanf("%d,%d",&maxium2->value)

if(status==1)

{

maxhead->next=maxium2

status++

}

maxium1->next=maxium2

maxium1=maxium2

}

}

}

maxium2->next=NULL

status=0

printf("请输入现时系统剩余的资源矩阵:\n")

for (j=0j<columj++)

{

printf("种类 %c 的系统资源剩余:",'A'+j)

if(status==0)

{

avahead=available1=available2=(struct available*)malloc(avalen)

workhead=work1=work2=(struct available*)malloc(avalen)

available1->next=available2->next=NULL

work1->next=work2->next=NULL

scanf("%d",&available1->value)

work1->value=available1->value

status++

}

else

{

available2=(struct available*)malloc(avalen)

work2=(struct available*)malloc(avalen)

scanf("%d,%d",&available2->value)

work2->value=available2->value

if(status==1)

{

avahead->next=available2

workhead->next=work2

status++

}

available1->next=available2

available1=available2

work1->next=work2

work1=work2

}

}

available2->next=NULL

work2->next=NULL

status=0

alloctemp=allochead

maxtemp=maxhead

for(i=0i<rowi++)

for (j=0j<columj++)

{

if(status==0)

{

needhead=need1=need2=(struct need*)malloc(needlen)

need1->next=need2->next=NULL

need1->value=maxtemp->value-alloctemp->value

status++

}

else

{

need2=(struct need *)malloc(needlen)

need2->value=(maxtemp->value)-(alloctemp->value)

if(status==1)

{

needhead->next=need2

status++

}

need1->next=need2

need1=need2

}

maxtemp=maxtemp->next

alloctemp=alloctemp->next

}

need2->next=NULL

status=0

for(i=0i<rowi++)

{

if(status==0)

{

finihead=finish1=finish2=(struct finish*)malloc(finilen)

finish1->next=finish2->next=NULL

finish1->stat=0

status++

}

else

{

finish2=(struct finish*)malloc(finilen)

finish2->stat=0

if(status==1)

{

finihead->next=finish2

status++

}

finish1->next=finish2

finish1=finish2

}

}

finish2->next=NULL/*Initialization compleated*/

status=0

processtest=0

for(temp=0temp<rowtemp++)

{

alloctemp=allochead

needtemp=needhead

finishtemp=finihead

worktemp=workhead

for(i=0i<rowi++)

{

worktemp1=worktemp

if(finishtemp->stat==0)

{

for(j=0j<columj++,needtemp=needtemp->next,worktemp=worktemp->next)

if(needtemp->value<=worktemp->value)

processtest++

if(processtest==colum)

{

for(j=0j<columj++)

{

worktemp1->value+=alloctemp->value

worktemp1=worktemp1->next

alloctemp=alloctemp->next

}

if(status==0)

{

pathhead=path1=path2=(struct path*)malloc(pathlen)

path1->next=path2->next=NULL

path1->value=i

status++

}

else

{

path2=(struct path*)malloc(pathlen)

path2->value=i

if(status==1)

{

pathhead->next=path2

status++

}

path1->next=path2

path1=path2

}

finishtemp->stat=1

}

else

{

for(t=0t<columt++)

alloctemp=alloctemp->next

finishtemp->stat=0

}

}

else

for(t=0t<columt++)

{

needtemp=needtemp->next

alloctemp=alloctemp->next

}

processtest=0

worktemp=workhead

finishtemp=finishtemp->next

}

}

path2->next=NULL

finishtemp=finihead

for(temp=0temp<rowtemp++)

{

if(finishtemp->stat==0)

{

printf("\n系统处于非安全状态!\n")

exit(0)

}

finishtemp=finishtemp->next

}

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

printf("\n安全序列为: \n")

do

{

printf("p%d ",pathhead->value)

}

while(pathhead=pathhead->next)

printf("\n")

return 0

}

把1作为参数传给yanzheng（） yanzheng（int m)

然后验证函数里修改：

i=m

while(i<m)

 { 

  if (Finish[i]==false&&Need[i]<=work)

  {

         work=work+Allocation[i]

         Finish[i]=true

         anquan[k]=i

         k++

         i = 0

   }

   else

       i++

 }

#include <string>

#define M 3 //资源的种类数

#define N 5 //进程的个数

void output(int iMax[N][M],int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N])//统一的输出格式

bool safety(int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N])

bool banker(int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N])

int main()

{

int i,j

//当前可用每类资源的资源数

int iAvailable[M]={3,3,2}

//系统中N个进程中的每一个进程对M类资源的最大需求

int iMax[N][M]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}}

//iNeed[N][M]每一个进程尚需的各类资源数

//iAllocation[N][M]为系统中每一类资源当前已分配给每一进程的资源数

int iNeed[N][M],iAllocation[N][M]={{0,1,1},{2,0,0},{3,0,2},{2,1,1},{0,0,2}}

//进程名

char cName[N]={'a','b','c','d','e'}

bool bExitFlag=true//退出标记

char ch//接收选择是否继续提出申请时传进来的值

bool bSafe//存放安全与否的标志

//计算iNeed[N][M]的值

for(i=0i<Ni++)

for(j=0j<Mj++)

iNeed[i][j]=iMax[i][j]-iAllocation[i][j]

//输出初始值

output(iMax,iAllocation,iNeed,iAvailable,cName)

//判断当前状态是否安全

bSafe=safety(iAllocation,iNeed,iAvailable,cName)

//是否继续提出申请

while(bExitFlag)

{

cout<<"\n"<<"继续提出申请？\ny为是；n为否。\n"

cin>>ch

switch(ch)

{

case 'y':

//cout<<"调用银行家算法"

bSafe=banker(iAllocation,iNeed,iAvailable,cName)

if (bSafe) //安全，则输出变化后的数据

output(iMax,iAllocation,iNeed,iAvailable,cName)

break

case 'n':

cout<<"退出。\n"

bExitFlag=false

break

default:

cout<<"输入有误，请重新输入：\n"

}

}

}

//输出

void output(int iMax[N][M],int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N])

{

int i,j

cout<<"\n\t Max \tAllocation\t Need \t Available"<<endl

cout<<"\tA B C\tA B C\tA B C\t A B C"<<endl

for(i=0i<Ni++)

{

cout<<cName[i]<<"\t"

for(j=0j<Mj++)

cout<<iMax[i][j]<<" "

cout<<"\t"

for(j=0j<Mj++)

cout<<iAllocation[i][j]<<" "

cout<<"\t"

for(j=0j<Mj++)

cout<<iNeed[i][j]<<" "

cout<<"\t"

cout<<" "

//Available只需要输出一次

if (i==0)

for(j=0j<Mj++)

cout<<iAvailable[j]<<" "

cout<<endl

}

}

//安全性算法，进行安全性检查；安全返回true，并且输出安全序列，不安全返回false，并输出不安全的提示；

bool safety(int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N])

{

}

//定位ch对应的进程名在数组中的位置

//没找见返回－1，否则返回数组下标

int locate(char cName[N],char ch)

{

int i

for(i=0i<Ni++)

if (cName[i]==ch) //找到

return i

//未找到

return -1

}

//提出申请,返回提出申请的进程名对应的下标

int request(char cName[N],int iRequest[M])

{

int i,loc

char ch

bool bFlag=true

//判断输入的进程名是否有误

while(bFlag)

{

//输出进程名

for(i=0i<Ni++)

cout<<cName[i]<<"\t"

//输入提出申请的进程名

cout<<"\n输入提出资源申请的进程名：\n"

cin>>ch

//定位ch对应的进程名在进程名数组中的位置

loc=locate(cName,ch)

//没找到，重新输入

if (loc==-1)

cout<<"\n您输入的进程名有误！请重新输入"

//找到，退出循环

else

bFlag=false

}

//输入提出申请的资源数

cout<<"输入申请各类资源的数量：\n"

for(i=0i<Mi++)

cin>>iRequest[i]

//返回提出申请的进程名对应的下标

return loc

}

bool banker(int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N])

{

}

这个是c++的 我的报告