银行家算法的模拟实现

银行家算法的模拟实现

一、设计目的

1、了解多道程序系统中，多个进程并发执行的资源分配。

2、掌握死锁的产生的原因、产生死锁的必要条件和处理死锁的基本方法。

3、掌握预防死锁的方法，系统安全状态的基本概念。

4、掌握银行家算法，了解资源在进程并发执行中的资源分配策略。

5、理解死锁避免在当前计算机系统不常使用的原因。

二、设计任务

① 在Window98/2000 系统的TC2.0环境下运行程序；

② 通过最有代表性的避免死锁的算法(Dijkstra)的银行家算法程序实现来理解进程并发中的资源分配，死锁避免在死锁解决中的可行性；

③ 设计程序在自动、手动方式下运行，理解银行家算法的实质。

三、设计内容与步骤

A、银行家算法设计的知识准备。

1、死锁概念。在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险━━死锁。所谓死锁(Deadlock),是指多个进程在运行中因争夺资源而造成的一种僵局(Deadly_Embrace),当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。

2、关于死锁的一些结论：

参与死锁的进程最少是两个

（两个以上进程才会出现死锁）

参与死锁的进程至少有两个已经占有资源

参与死锁的所有进程都在等待资源

参与死锁的进程是当前系统中所有进程的子集

注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。

3、资源分类。

永久性资源：

可以被多个进程多次使用（可再用资源）

可抢占资源

不可抢占资源

临时性资源：只可使用一次的资源；如信号量,中断信号，同步信号等（可消耗性资源）

“申请--分配--使用--释放”模式

4、产生死锁的四个必要条件：互斥使用（资源独占）、不可强占（不可剥夺）、请求和保持（部分分配，占有申请）、循环等待。

1) 互斥使用（资源独占）

一个资源每次只能给一个进程使用

2) 不可强占（不可剥夺）

资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放

3) 请求和保持（部分分配，占有申请）

一个进程在申请新的资源的同时保持对原有资源的占有（只有这样才是动态申请，动态分配）

4) 循环等待

存在一个进程等待队列

{P1 , P2 , … , Pn},

其中P1等待P2占有的资源，P2等待P3占有的资源，…，Pn等待P1占有的资源，形成一个进程等待环路

5、 死锁的解决方案

5.1 产生死锁的例子

申请不同类型资源产生死锁

P1：

…

申请打印机

申请扫描仪

使用

释放打印机

释放扫描仪

…

P2：

…

申请扫描仪

申请打印机

使用

释放打印机

释放扫描仪

…

申请同类资源产生死锁（如内存）

设有资源R，R有m个分配单位，由n个进程P1,P2,…,Pn（n > m）共享。假设每个进程对R的申请和释放符合下列原则：

* 一次只能申请一个单位

* 满足总申请后才能使用

* 使用完后一次性释放

m=2，n=3

资源分配不当导致死锁产生

5.2死锁预防:

定义:在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一

①破坏“不可剥夺”条件

在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请

②破坏“请求和保持”条件

要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配

③破坏“循环等待”条件

采用资源有序分配法：

把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否

则操作系统不予分配

6．安全状态与不安全状态

安全状态：

如果存在一个由系统中所有进程构成的安全序列P1，…Pn，则系统处于安全状态。一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和，系统处于安全状态 (安全状态一定是没有死锁发生的)

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

B、银行家算法

一、银行家算法中的数据结构

1．可利用资源向量Available

它是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K,则表示系统中现有Rj类资源K个。

2．最大需求短阵Max

这是—个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大

需求。如果Max(i，j)＝K，表示进程i需要Rj类资源的最大数目为K。

3．分配短阵Allocation

这是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每个进程的资源数。如果Allocation(i,j)＝K，表示进程i当前已分得Rj类资源的数目为K。

4．需求矩阵Need

它是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数，如果Need[i,j]=K，则表示进程i还需要Rj类资源k个，方能完成其任务。

上述三个矩阵间存在下述关系：

Need[i,j]=Max[i,j]-Allocation[i,j]

二、银行家算法

设Requesti是进程Pi的请求向量。如果Requesti[j]＝k，表示进程只需要k个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：

（1）如果 Requesti[j]<=Need[i,j]，则转向步骤2；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。

（2）如果Requesti[j]<=Available[j] ，则转向步骤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等待。

三、安全性算法

系统所执行的安全性算法可描述如下：

（1）设置两个向量

①、工作向量Work。它表示系统可提供给进程继续运行所需要的各类资源数目，它含有m个元素，执行安全算法开始时，Work = Available。

②、Finish。它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finish[i]:=false ；当有足够资源分配给进程时，令 Finish[i]:=true。

（2）从进程集合中找到一个能满足下述条件的进程：

①、Finish[i]=false; ②、Need[i,j]<=Work[j];如找到，执行步骤（3）；否则，执行步骤（4）。

（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

Work[j]:=Work[i]+Allocation[i,j];

Finish[i]:=true;

goto step 2；

（4）如果所有进程的Finish[i]:=true，则表示系统处于安全状态；否则，系统处于不安全状态。

四、银行家算法之例

假定系统中有五个进程：{P0，P1，P2，P3，P4}和三种类型的资源{A，B，C}，每一种资源的数量分别为10、5、7,在T0时刻的资源分配情况如图1所示。

资

源

情

况

进

程

Max

A B A B A B A B P0 7 (2 3 P1 3 (3 0 (0 2 C Allocation

C Need

C Available

C

5 3 0 1 0)

2 2 2 0 2) 1 2 2 0)

0 7 0

4 3 3 3 2

P2 9 0 2 3 0 2 6 0 0

P3 2 2 2 2 1 1 0 1 1

P4 4 3 3 0 0 2 4 3 1

(1) T0时刻的安全性：利用安全性算法对T0时刻的资源分配情况进行分析(如图2)可知，在T0时刻存在着一个安全序列｛P1，P3，P4，P2，P0｝，故系统是安全的。

资

源

情

况

进

程

Work

A B C Need

A B C Allocation

A B C Work+allocation

A B C Finish

P1 3 2 2 1 2 2 2 0 0 5 3 2 true

P3 5 3 2 0 1 1 2 1 1 7 4 3 true

P4 7 4 3 4 3 1 0 0 2 7 4 5 true

P2 7 4 5 6 0 0 3 0 2 10 4 7 true

P0 10 4 7 7 4 3 0 1 0 10 5 7 true

(2) P1请求资源：P1发出请求向量Request1(1,0,2),系统按银行家算法进行检查：

①Request1(1,0,2)<=Need1(1,2,2)

②Request1(1,0,2)<=Available1(3,3,2)

③系统先假定可为P1分配资源，并修改Available,Allocation1和Need1向量，由此形成资源变化情况如图1中的圆括号所示。

④再利用安全性算法检查此时系统是否安全。如图3所示。

资

源

情

况

进

程

Work

A B C Need

A B C Allocation

A B C Work+allocation A B C Finish

P1 2 3 0 0 2 0 3 0 2 5 3 2 true

P3 5 3 2 0 1 1 2 1 1 7 4 3 true

P4 7 4 3 4 3 1 0 0 2 7 4 5 true

P0 7 4 5 7 4 3 0 1 0 7 5 5 true

P2 7 5 5 6 0 0 3 0 2 10 5 7 true

由所进行的安全性检查得知，可以找到一个安全序列｛P1,P3,P4,P2,P0｝。因此系统是安全的，可以立即将P1所申请的资源分配给它。

(3) P4请求资源：P4发出请求向量Request4(3,3,0),系统按银行家算法进行检查：

①Request4(3,3,0)≤Need4(4,3,1);

②Request4(3,3,0)不小于等于Available(2,3,0),让P4等待。

(4) P0请求资源：P0发出请求向量Request0(0,2,0),系统按银行家算法进行检查。

①Request0(0,2,0) ≤Need0(7,4,3);

②Request0(0,2,0) ≤Available(2,3,0);

③系统暂时先假定可为P0分配资源，并修改有关数据，如图4所示。

资

源

情

况

进

程

Allocation

A B C A B C A B C P0 0 3 P1 3 0 P2 3 0 Need Available 0 7 2 0 2 6

2 3 2 0 0 0 2 1 0

P3 2 1 1 0 1 1

P4 0 0 2 4 3 1

(5) 进行安全性检查：可用资源Available(2,1,0)已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。

C、程序源代码。

#include

#include

#ifndef MY_MAX

#define MY_MAX 5

#endif

int max1[5][3]={

{7,5,3},

{3,2,2},

{9,0,2},

{2,2,2},

{4,3,3}

};/*最大分配需求矩阵*/

int allocation1[5][3]={

{0,1,0},

{2,0,0},

{3,0,2},

{2,1,1},

{0,0,2}

};/*已分配矩阵*/

int need1[5][3]={

{7,4,3},

{1,2,2},

{6,0,0},

{0,1,1},

{4,3,1}

};/*现在需求矩阵*/

int available1[3]={3,3,2};/*现可利用矩阵*/

int max[10][10],allocation[10][10],need[10][10],available[10];

int n_proc;/*进程数*/

int type_src;/*资源种类数*/

int request[10][10];/*进程请求资源*/

int work[10];/*可供进程继续运行所需资源的向量*/

int finish[10];/*标识是否有足够的资源分配给进程*/

int index[10];/*用于记录进程顺序*/

int t=0;/*记录当前的进程数*/

int serial_proc=0;/*当前请求进程*/

/*-------------------------------------------------------------------------------------------------------------*/

/*生成确定范围 [min,max]内的随机数*/

int random_num(int min,int max)

{

int i,range;

double j;

range=max-min;

i=rand();

j=((double)i/(double)RAND_MAX);

i=(int)(j*(double)range);

i+=min;

return i;

}

/*手动输入时的初始化数据*/

void init0_data(void)

{

int i,j;

n_proc=5;

type_src=3;

for(i=0;ifor(j=0;jmax[i][j]=max1[i][j];

for(i=0;ifor(j=0;jallocation[i][j]=allocation1[i][j];

for(i=0;ifor(j=0;jneed[i][j]=need1[i][j];

for(j=0;javailable[j]=available1[j];

for(i=0;iindex[i]=-1;

}

/*自动时的初始化数据*/

void init1_data(void)

{

int i,j,k1=0;

n_proc=random_num(1,MY_MAX);

type_src=random_num(1,MY_MAX);

for(i=0;ido{

for(j=0;jmax[i][j]=random_num(0,MY_MAX);

k1=0;

for(j=0;jk1+=max[i][j];

}while(k1==0);

for(i=0;ido{

for(j=0;jallocation[i][j]=random_num(0,max[i][j]+1);

k1=0;

for(j=0;jif(allocation[i][j]==max[i][j])

k1++;

}while(k1==type_src);

for(i=0;ifor(j=0;jneed[i][j]=max[i][j]-allocation[i][j];

do{

for(j=0;javailable[j]=random_num(0,MY_MAX);

k1=0;

for(i=0;i{

for(j=0;jif(need[i][j]>available[j])

{

k1++;

break;

}

}

}while(k1==n_proc);

for(i=0;iindex[i]=-1;

}

/*自动请求数据*/

void proc_require1(void)

{

int j,tmp;

serial_proc=index[0];

do{

printf(\"[%d]请求资源数：\

for(j=0;jprintf(\"%2d\

tmp=0;

for(j=0;jtmp+=request[serial_proc][j];

}while(tmp==0);

}

void proc_require0(void)

{

int j,tmp;

require0:

printf(\"\现在第?进程请求\\n\");

scanf(\"%d\

if (serial_proc<0 ||serial_proc>=n_proc)

{

printf(\"进程号非法(越界)\\n\");

goto require0;

}

tmp=0;

for(j=0;jtmp+=need[serial_proc][j];

if (!tmp)

{

printf(\"[%d]该进程处于完成状态\\n\

goto require0;

}

printf(\"\对[%d]进程,各资源要求\\n\

for(j=0;jscanf(\"%d\

printf(\"\\n\");

}

/*请求资源超过需求资源*/

int over_need()

{

int j;

for(j=0;jif(request[serial_proc][j]>need[serial_proc][j])

{

printf(\"\请求资源超过需求资源\\n\");

return 1;

}

return 0;

}

/*请求资源超过可利用资源*/

int over_avail()

{

int j;

for(j=0;jif(request[serial_proc][j]>available[j])

{

printf(\"\[%d]请求资源超过可利用资源\\n\

return 1;

}

return 0;

}

/*资源申请成功*/

int apply_success(int be_need,int be_avail)

{

if (be_need==0 && be_avail==0)

{

return 1;

}

return 0;

}

/*安全性检查*/

int check_security()

{

int i,j,tmp;

for(j=0;jwork[j]=available[j];

for(i=0;ifinish[i]=0;

t=0;

L2:

for(i=0;iif(finish[i]==0) /*没有进行安全检查*/

{

tmp=1;

for(j=0;jif(need[i][j]>work[j])

{

tmp=0;

break;

}

if(!tmp)

continue;

else

{

for(j=0;jwork[j]+=allocation[i][j];

finish[i]=1;

tmp=0;

for(j=0;jtmp+=need[i][j];

if(tmp)

index[t++]=i;

goto L2;

}

}

for(j=0;jif(finish[j]==0)

return 0;

return 1;

}

/*银行家算法主体*/

void banker()

{

int allocation_t[10],available_t[10],need_t[10];/*临时变量*/

int tmp;

int j;

/*保留当前的资源分配*/

for(j=0;j{

available_t[j]=available[j];

allocation_t[j]=allocation[serial_proc][j];

need_t[j]=need[serial_proc][j];

}

/*修改available,allocation,need矩阵*/

for(j=0;j{

available[j]-=request[serial_proc][j];

need[serial_proc][j]-=request[serial_proc][j];

allocation[serial_proc][j]+=request[serial_proc][j];

}

if(check_security(type_src,n_proc))

{

tmp=0;

for(j=0;jtmp+=need[serial_proc][j];

if(!tmp)

for(j=0;javailable[j]+=allocation[serial_proc][j];

}

else

{

for(j=0;j{

allocation[serial_proc][j]=allocation_t[j];

need[serial_proc][j]=need_t[j];

available[j]=available_t[j];

}

}

}

int finish_all(void)

{

int i,j;

for(i=0;ifor(j=0;jif(need[i][j]!=0)

return 1;

return 0;

}

/*结果输出*/

void output()

{

int i,j;

printf(\"\\n安全序列输出格式：[进程号,进程数]\\n\");

for(i=0;i{

printf(\"[%d,%d] \

}

printf(\"\\n\");

printf(\"依次为:最大需求矩阵,已分配矩阵,需求矩阵,可利用矩阵\\n\");

for(i=0;i{

printf(\"+\");

for(j=0;jprintf(\"%2d\

printf(\"+\");

for(j=0;jprintf(\"%2d\

printf(\"+\");

for(j=0;jprintf(\"%2d\

printf(\"+\");

if (i==serial_proc)

for(j=0;jprintf(\"%3d\

printf(\"+\");

printf(\"\\n\");

}

}

/*----------------------------------------------------------------------------------------------*/

/*主函数,提供开始工作界面*/

void main(void)

{

start:

printf(\"\\n\银行家算法\\n\\\设计者:李行\2003.1.1\\n请确定工作方式: '1'为自动;'0'为手动\\a\\n\");

switch(getche()){

case '1': do{

init1_data();

}while(!check_security(type_src,n_proc));/*确定进程初始是可推进的*/

output();

do{

proc_require1();

if(apply_success(over_need(),over_avail()))

banker();

output();

}while(finish_all());

break;

case '0': do{

init0_data();

}while(!check_security(type_src,n_proc));

output();

do{

proc_require0();

if(apply_success(over_need(),over_avail()))

banker();

output();

}while(finish_all());

break;

default:

printf(\"\请按提示操作啦!\\n\");

break;

}

printf(\"继续?y/n\\n\");

if(getche()=='y')

goto start;

}

四、测试与评价

1、程序运行及结果测评：

在自动、手动方式下都能正确得出结果，但在自动模式下，当值MY＿MAX增大时，计算时间长，增加了系统的开销，这也就说明了在实际系统中不常用银行家算法――死锁避免在死锁解决中的这一原因。

2、 程序框架测评：

主要使用了函数将每个模块分开，便于理解。但由于，程序设计了自动实现模式，导致程序显得过长。每个模块之间的信息交换主要通过全局变量平实现，从这个角度讲，模块的划分并不严格。对于自动与手动这两种工作方式，解题思路是冗余的，但程序却为了避免之间的干扰冗余设计了函数，因而各个函数内聚度不高，功能也还有相容点，所以在函数设计也不十分合理。尽管如此，本设计严格从银行家算法出发，能很好地帮助读者理解银行家算法在多进程并行为死锁避免采取的资源分配、安全性检测的策略。特别，在自

动方式下，资源分配利用第一次安全检测的结果避免了后继执行进程的不确定，有效地解决了自动请求的过重盲目的特点。当然，这部分有违银行家算法，但并没有增加额外的空间开销，还减少了时间上的开销，个人觉得是成功的。

3、设计特点

① 数据结构：数组；

② 全局变量

③ 在自动方式下，采用do{}while(条件)以保证进程能够推进。

④ getche()在调试时产生Warnings但能编译通过，getchar()对于键的接收不好确定，而getche()则一按即可。

4、设计心得：

为准确理解，应该以手动模式下运行为准，这样的交互性较好！而自动实现下，更接近于机器的工作方式。程序在设计初，只是用了手动这一模式，后来听取同学的意见以随机数实现自动模式，在设计时出了好些问题，但想多了问题也就通了，而新的问题又出现，却总能解决。在这种模式下能更彻底理解银行家算法中的资源分配策略。