银行家算法课程设计报告24972.docx

银行家算法课程设计报告24972.docx

《银行家算法课程设计报告24972.docx》由会员分享，可在线阅读，更多相关《银行家算法课程设计报告24972.docx（21页珍藏版）》请在冰点文库上搜索。

银行家算法课程设计报告24972

《操作系统原理》课程设计报告

1设计目的

（1）进一步了解进程的并发执行

（2）加强对进程死锁的理解

（3）用银行家算法完成死锁检测

2设计内容

给出进程需求矩阵C、资源向量R以及一个进程的申请序列。

使用进程启动拒绝和资源分配拒绝（银行家算法）模拟该进程组的执行情况。

3设计要求

（1）初始状态没有进程启动；

（2）计算每次进程申请是否分配，如：

计算出预分配后的状态情况（安全状态，不安全状态），如果是安全状态，输出安全序列；

（3）每次进程申请被允许后，输出资源分配矩阵A和可用资源向量V；

（4）每次申请情况应可单步查看，如：

输入一个空格，继续下个申请。

4算法原理

4.1银行家算法中的数据结构

（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]

4.2银行家算法

设Requesti是进程Pi的请求向量。

如果Requesti[j]＝k，表示进程只需要k个Rj类型的资源。

当Pi发出资源请求后，系统按下述步骤进行检查：

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

（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等待。

4.3安全性算法

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

（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;

gotostep2；

（4）如果所有进程的Finish[i]:

=true，则表示系统处于安全状态；否则，系统处于不安全状态。

5设计思路

（1）进程一开始向系统提出最大需求量；

（2）进程每次提出新的需求都统计是否超出它事先提出的最大需求量;

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

6算法流程图

6.1银行家算法流程图

开始

提出进程i的请求

向量Resquest[*]

alloc[i][*]+Request[*}<=claimNoERROR

[i][*]

Yes

Request[*]<=available[*]noERROR

yes

available[*]-=Request[*]

alloc[i][*]+=Request[*]

is_safe（）No

yesavailable[*]+=Request[*]

alloc[*]-=Request[*]

同意本次分配

拒绝本次分配

图1银行家算法流程图

6.2银行家算法安全检测流程图

开始

tmp_avail[*]=available[*]

寻找进程k满足

Claim[k][*]-alloc[k][*]

是否存在这样返回false

的进程

tmp_avail[*]+=alloc[*]

标记进程k

是否所有的进程

都被标记

返回true

图2银行家算法安全检测流程图

7银行家算法之列

假定系统中有五个进程：

{P0，P1，P2，P3，P4}和三种类型的资源{A，B，C}，每一种资源的数量分别为10、5、7,在T0时刻的资源分配情况如图3所示。

资源情况

进程

Max

Allocation

Need

Available

ABC

ABC

ABC

ABC

P0

753

010

743

332

（230）

P1

322

200

（302）

122

（020）

P2

902

302

600

P3

222

211

011

P4

433

002

431

图3T0时刻的资源分配表

（1）T0时刻的安全性：

利用安全性算法对T0时刻的资源分配情况进行分析（如图

可知，在T0时刻存在着一个安全序列｛P1，P3，P4，P2，P0｝，故系统是安全的。

资源情况

进程

Work

Need

Allocation

Work+Allocation

Finish

ABC

ABC

ABC

ABC

P1

332

122

200

532

true

true

true

true

true

P3

532

011

211

743

P4

743

431

002

745

P2

745

600

302

1047

P0

1047

743

010

1057

图4T0时刻的安全序列

（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中的圆括号所示。

再利用安全性算法检查此时系统是否安全。

如图5所示

资源情况

进程

Work

Need

Allocation

Work+Allocation

Finish

ABC

ABC

ABC

ABC

P1

230

020

302

532

true

true

true

true

true

P3

532

011

211

743

P4

743

431

002

745

P0

745

743

010

755

P2

755

600

302

1057

图5P1申请资源时的安全性检查

由所进行的安全性检查得知，可以找到一个安全序列｛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分配资源，并修改有关数据，如图6所示。

资源情况

进程

Allocation

Need

Available

ABC

ABC

ABC

P0

030

732

210

P1

302

020

P2

302

000

P3

211

011

P4

002

432

图6为P0分配资源后的有关资源数据

（5）进行安全性检查：

可用资源Available（2,1,0）已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。

8程序测试结果

图7

图8

图9

图10

源程序清单：

#include

#include

#include

#defineFALSE0

#defineTRUE1

#defineW10

#defineR10

intM;

intN;

intALL_RESOURCE[W];

intMAX[W][R];

intAVAILABLE[R];

intALLOCATION[W][R];

intNEED[W][R];

intRequest[R];

voidoutput（）

{

inti,j;

cout<

cout<<"各种资源的总数量:

"<

for（j=0;j

cout<<"资源"<

"<

cout<

cout<<"━━━━━━━━━━━━━━━━━━"<

cout<<"目前各种资源可利用的数量为:

"<

for（j=0;j

cout<<"资源"<

"<

cout<

cout<<"━━━━━━━━━━━━━━━━━━"<

cout<<"各进程还需要的资源数量:

"<

for（i=0;i

cout<<"资源"<

cout<

for（i=0;i

{

cout<<"进程"<

";

for（j=0;j

cout<

cout<

}

cout<

cout<<"━━━━━━━━━━━━━━━━━━"<

cout<<"各进程已经得到的资源量:

"<

for（i=0;i

cout<<"资源"<

cout<

for（i=0;i

{

cout<<"进程"<

";

for（j=0;j

cout<

cout<

}

cout<

}

voiddistribute（intk）

{

intj;

for（j=0;j

{

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

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

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

}

}

voidrestore（intk）

{

intj;

for（j=0;j

{

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

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

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

}

}

intcheck（）

{

intWORK[R],FINISH[W];

inti,j;

for（j=0;j

for（i=0;i

for（i=0;i

{

for（j=0;j

{

if（FINISH[i]==FALSE&&NEED[i][j]<=WORK[j]）

{

WORK[j]=WORK[i]+ALLOCATION[i][j];

}

}

FINISH[i]=TRUE;

}

for（i=0;i

{

if（FINISH[i]==FALSE）

{

cout<

cout<<"系统不安全!

!

!

本次资源申请不成功!

!

!

"<

cout<

return1;

}

else

{

cout<

cout<<"经安全性检查，系统安全，本次分配成功。

"<

cout<

return0;

}

}

}

voidbank（）//银行家算法

{

inti=0,j=0;

charflag='Y';

while（flag=='Y'||flag=='y'）

{

i=-1;

while（i<0||i>=M）

{

cout<<"━━━━━━━━━━━━━━━━━━"<

cout<

";

cin>>i;

if（i<0||i>=M）cout<<"输入的进程号不存在，重新输入!

"<

}

cout<<"请输入进程"<

"<

for（j=0;j

{

cout<<"资源"<

";

cin>>Request[j];

if（Request[j]>NEED[i][j]）

cout<

";

cout<<"若继续执行系统将处于不安全状态!

"<

flag='N';

break;

}

else

{

if（Request[j]>AVAILABLE[j]）

{

cout<

";

cout<<"若继续执行系统将处于不安全状态!

"<

flag='N';

break;

}

}

}

if（flag=='Y'||flag=='y'）

{

distribute（i）;

if（check（））

{

restore（i）;

output（）;

}

else

output（）;

}

else

cout<

cout<<"是否继续银行家算法演示,按'Y'或'y'键继续,按'N'或'n'键退出演示:

";

cin>>flag;

}

}

voidversion（）

{

cout<

cout<<"\t　　　　　　　银行家算法　　　　　　　　"<

}

voidmain（）

{

inti=0,j=0,p;

version（）;

getchar（）;

cout<

";

cin>>M;

cout<

cout<<"请输入总资源种类:

";

cin>>N;

cout<

cout<<"请输入各类资源总数:

（需要输入数为"<

for（i=0;i

cin>>ALL_RESOURCE[i];

cout<

cout<<"输入各进程所需要的各类资源的最大数量:

（需要输入数为"<

for（i=0;i

{

for（j=0;j

{

do

{

cin>>MAX[i][j];

if（MAX[i][j]>ALL_RESOURCE[j]）

cout<

}

while（MAX[i][j]>ALL_RESOURCE[j]）;

}

}

cout<

cout<<"输入各进程已经占据的各类资源的数量:

（需要输入数为"<

*N<<"个）";

for（i=0;i

{

for（j=0;j

{

do

{

cin>>ALLOCATION[i][j];

if（ALLOCATION[i][j]>MAX[i][j]）

cout<

}

while（ALLOCATION[i][j]>MAX[i][j]）;

}

}

for（j=0;j

{

p=ALL_RESOURCE[j];

for（i=0;i

{

p=p-ALLOCATION[i][j];

AVAILABLE[j]=p;

if（AVAILABLE[j]<0）

AVAILABLE[j]=0;

}

}

for（i=0;i

for（j=0;j

NEED[i][j]=MAX[i][j]-ALLOCATION[i][j];

output（）;

bank（）;

}