银行家算法

#include<stdio.h>

#include "stdlib.h"

#defineM5

#defineN3

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

intneed[M][N]={{7,4,3},{1,2,2},{6,0,0},{0,1,1},{4,3,1}}

intallocation[M][N]={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}}

intrequest[N]={0}

intfinish[M]={0}

intavailable[N]={3,3,2}

intwork[N]={3,3,2}

intsafe[M]={0}

int n=1,m=1

void showdata()

{

int i,j

printf("系统可用的资源数为:\n")

for (j=0j<Nj++)

printf("资源%c: %d \n",j+65, work[j])

printf("\n")

printf("进程还需要的资源量: \n")

printf(" A B C\n" )

for(i=0i<Mi++)

{

printf("进程p%d:",i)

for(j=0j<Nj++)

printf(" %d ", need[i][j])

printf("\n")

}

printf("进程已经得到的资源量:\n")

printf(" A B C\n" )

for(i=0i<Mi++)

{

printf("进程%d:",i)

for(j=0j<Nj++)

printf(" %d ",allocation[i][j])

printf("\n")

}

}

void fp(int i){

for(int j=0j<Nj++){

work[j]=work[j]+allocation[i][j]

finish[i]=1

}

}

void secure(){

showdata()

int y=0,flag=6,h,i,j

while(flag){

for(i=0i<Mi++){

for(j=0j<Nj++){

if((finish[i]==0)&&(need[i][j]<=work[j]))

continue

else

j=15

}

if(j==N){

fp(i)

safe[y++]=i

i=15

}

else

continue

}

flag--

}

for( h=0h<Mh++){

if(finish[h]==1)

continue

else

h=M+1

}

if(h==M){

printf("该状态安全！安全序列是:\n")

for(int l=0l<Ml++){

if(l==M-1)

printf("p%d",safe[l])

else

printf("p%d-->",safe[l])

}

n=1

}

else

{

n=0

printf("该状态不安全！！")

}

}

void sfp(int k){

for(int i=0i<Ni++){

work[i]=work[i]-request[i]

allocation[k][i]+=request[i]

need[k][i]-=request[i]

}

secure()

if(n==1){

printf("给与分配！\n")

}

else if(n==0){

printf("不给与分配！\n")

}

}

int choice(int k){

int e=1

printf("输入选择的量:\n")

while(e){

for(int i=0i<Ni++){

printf("资源%c:",65+i)

scanf("%d",&request[i])

}

for(int j=0j<Nj++){

if((request[j]<=need[k][j])&&(request[j]<=work[j]))

continue

else{

printf("资源%c申请超量！不与分配!",65+j)

return 0

e=0

}

}

if(j==N){

printf("可以试申请！\n")

return 1

e=0

}

}

}

void recover(int k){

for(int i=0i<Ni++){

work[i]=available[i]

need[k][i]+=request[i]

allocation[k][i]-=request[i]

}

}

void main(){

int p=1,k=1,i=0,c,f

while(k){

printf("请选择：1:显示进程情况；2:判断此时状态是否安全；3:选择进程进行申请资源；4：结束程序！")

scanf("%d",&c)

switch(c){

case 1:showdata()break

case 2:secure()work[0]=3for(i=0i<Ni++) work[i]=available[i]

break

case 3: for(i=0i<Mi++)

finish[i]=0

printf("请选择进程（0--4）:\n")

scanf("%d",&f)

if(choice(f)){

sfp(f)

recover(f)

}

else{

printf("不与分配")

}

break

case 4:k=0

break

default:k=0break

}

printf("\n")

}

}

不会分配，看一下银行家算法的流程。

可以看到 在step(1)若Request<=Need, goto step(2)否则错误返回.

原因如下，每个进程开始之前，都必须声明自己需要的各类资源的最大值Max。

Need 需求资源 = Max 最大需求 - Allocation 已分配资源

进程运行过程中，不能再要比Need还多的资源。

参考书 *** 作系统概念(OS concepts Six Edition)

算法:

n:系统中进程的总数

m:资源类总数

符号说明:

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, 则系统处于安全状态, 否则处于不安全状态

银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系 银行家算法统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。

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

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

我们可以把 *** 作系统看作是银行家， *** 作系统管理的资源相当于银行家管理的资金，进程向 *** 作系统请求分配资源相当于用户向银行家贷款。

为保证资金的安全，银行家规定：

(1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客；

(2) 顾客可以分期贷款，但贷款的总数不能超过最大需求量；

(3) 当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款；

(4) 当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金.

*** 作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。

银行家算法

在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。

银行家算法的基本思想是分配资源之前，判断系统是否是安全的；若是，才分配。它是最具有代表性的避免死锁的算法。

设进程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=AVAILABLEFINISH

(2)从进程集合中找到一个满足下述条件的进程，

FINISH==false

NEED<=Work

如找到，执行（3)；否则，执行（4)

(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。

Work=Work+ALLOCATION

Finish=true

GOTO 2

(4)如所有的进程Finish= true，则表示安全；否则系统不安全。

银行家算法流程图

算法（C语言实现）

#include<STRING.H>

#include<stdio.h>

#include<stdlib.h>

#include<CONIO.H>/*用到了getch()*/

#defineM5/*进程数*/

#defineN3/*资源数*/

#defineFALSE0

#defineTRUE1

/*M个进程对N类资源最大资源需求量*/

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

/*系统可用资源数*/

intAVAILABLE[N]={10,5,7}

/*M个进程已分配到的N类数量*/

intALLOCATION[M][N]={{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0}}

/*M个进程已经得到N类资源的资源量*/

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

/*M个进程还需要N类资源的资源量*/

intRequest[N]={0,0,0}

voidmain()

{

inti=0,j=0

charflag

voidshowdata()

voidchangdata(int)

voidrstordata(int)

intchkerr()

showdata()

enter:

{

printf("请输入需申请资源的进程号（从0到")

printf("%d",M-1)

printf("）:")

scanf("%d",&i)

}

if(i<0||i>=M)

{

printf("输入的进程号不存在，重新输入!\n")

gotoenter

}

err:

{

printf("请输入进程")

printf("%d",i)

printf("申请的资源数\n")

printf("类别:ABC\n")

printf("")

for(j=0j<Nj++)

{

scanf("%d",&Request[j])

if(Request[j]>NEED[i][j])

{

printf("%d",i)

printf("号进程")

printf("申请的资源数>进程")

printf("%d",i)

printf("还需要")

printf("%d",j)

printf("类资源的资源量!申请不合理，出错!请重新选择!\n")

gotoerr

}

else

{

if(Request[j]>AVAILABLE[j])

{

printf("进程")

printf("%d",i)

printf("申请的资源数大于系统可用")

printf("%d",j)

printf("类资源的资源量!申请不合理，出错!请重新选择!\n")

gotoerr

}

}

}

}

changdata(i)

if(chkerr())

{

rstordata(i)

showdata()

}

else

showdata()

printf("\n")

printf("按'y'或'Y'键继续,否则退出\n")

flag=getch()

if(flag=='y'||flag=='Y')

{

gotoenter

}

else

{

exit(0)

}

}

/*显示数组*/

voidshowdata()

{

inti,j

printf("系统可用资源向量:\n")

printf("***Available***\n")

printf("资源类别:ABC\n")

printf("资源数目:")

for(j=0j<Nj++)

{

printf("%d",AVAILABLE[j])

}

printf("\n")

printf("\n")

printf("各进程还需要的资源量:\n")

printf("******Need******\n")

printf("资源类别:ABC\n")

for(i=0i<Mi++)

{

printf("")

printf("%d",i)

printf("号进程:")

for(j=0j<Nj++)

{

printf("%d",NEED[i][j])

}

printf("\n")

}

printf("\n")

printf("各进程已经得到的资源量:\n")

printf("***Allocation***\n")

printf("资源类别:ABC\n")

for(i=0i<Mi++)

{

printf("")

printf("%d",i)

printf("号进程:")

/*printf(":\n")*/

for(j=0j<Nj++)

{

printf("%d",ALLOCATION[i][j])

}

printf("\n")

}

printf("\n")

}

/*系统对进程请求响应，资源向量改变*/

voidchangdata(intk)

{

intj

for(j=0j<Nj++)

{

AVAILABLE[j]=AVAILABLE[j]-Request[j]

ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j]

NEED[k][j]=NEED[k][j]-Request[j]

}

}

/*资源向量改变*/

voidrstordata(intk)

{

intj

for(j=0j<Nj++)

{

AVAILABLE[j]=AVAILABLE[j]+Request[j]

ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j]

NEED[k][j]=NEED[k][j]+Request[j]

}

}

/*安全性检查函数*/

intchkerr()//在假定分配资源的情况下检查系统的安全性

{

intWORK[N],FINISH[M],temp[M]//temp[]用来记录进程安全执行的顺序

inti,j,m,k=0,count

for(i=0i<Mi++)

FINISH[i]=FALSE

for(j=0j<Nj++)

WORK[j]=AVAILABLE[j]//把可利用资源数赋给WORK[]

for(i=0i<Mi++)

{

count=0

for(j=0j<Nj++)

if(FINISH[i]==FALSE&&NEED[i][j]<=WORK[j])

count++

if(count==N)//当进程各类资源都满足NEED<=WORK时

{

for(m=0m<Nm++)

WORK[m]=WORK[m]+ALLOCATION[i][m]

FINISH[i]=TRUE

temp[k]=i//记录下满足条件的进程

k++

i=-1

}

}

for(i=0i<Mi++)

if(FINISH[i]==FALSE)

{

printf("系统不安全!!!本次资源申请不成功!!!\n")

return1

}

printf("\n")

printf("经安全性检查，系统安全，本次分配成功。\n")

printf("\n")

printf("本次安全序列：")

for(i=0i<Mi++)//打印安全系统的进程调用顺序

{

printf("进程")

printf("%d",temp[i])

if(i<M-1)

printf("->")

}

printf("\n")

return0

}

---