银行家算法课程设计报告样本.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。
《操作系统原理》课程设计报告
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;
goto step 2;
(4)如果所有进程的Finish[i]:=true, 则表示系统处于安全状态; 否则, 系统处于不安全状态。

5设计思路
（1） 进程一开始向系统提出最大需求量;
（2） 进程每次提出新的需求都统计是否超出它事先提出的最大需求量;
( 3) 若正常, 则判断该进程所需剩余量( 包括本次申请) 是否超出系统所掌握的剩余资源量, 若不超出, 则分配, 否则等待。
6算法流程图
6.1银行家算法流程图

开始

提出进程i的请求
向量Resquest[*]

alloc[i] [*] +Request[*}<=claim No ERROR
[i][*]

Yes

Request[*]<=available[*] no ERROR

yes

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

is_safe() No

yes available[*]+=Request[*]
alloc[*]-=Request[*]

同意本次分配
拒绝本次分配

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

开始

tmp_avail[*]=available[*]

寻找进程k满足
Claim[k][*]-alloc[k][*]<tmp_avail[*]

是否存在这样 返回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
A B C
A B C
A B C
A B C
P0
7 5 3
0 1 0
7 4 3

3 3 2
( 2 3 0)
P1
3 2 2
2 0 0
(3 0 2)
1 2 2
(0 2 0)
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
图3 T0时刻的资源分配表
(1)T0时刻的安全性: 利用安全性算法对T0时刻的资源分配情况进行分析(如图
可知, 在T0时刻存在着一个安全序列｛P1, P3, P4, P2, P0｝, 故系统是安全的。
资源情况
进程
Work
Need
Allocation
Work+Allocation
Finish
A B C
A B C
A B C
A B C
P1
3 3 2
1 2 2
2 0 0
5 3 2
true
true
true
true
true
P3
5 3 2
0 1 1
2 1 1
7 4 3
P4
7 4 3
4 3 1
0 0 2
7 4 5
P2
7 4 5
6 0 0
3 0 2
10 4 7
P0
10 4 7
7 4 3
0 1 0
10 5 7
图4 T0时刻的安全序列
(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
A B C
A B C
A B C
A B C
P1
2 3 0
0 2 0
3 0 2
5 3 2
true
true
true
true
true
P3
5 3 2
0 1 1
2 1 1
7 4 3
P4
7 4 3
4 3 1
0 0 2
7 4 5
P0
7 4 5
7 4 3
0 1 0
7 5 5
P2
7 5 5
6 0 0
3 0 2
10 5 7
图5 P1申请资源时的安全性检查
由所进行的安全性检查得知, 能够找到一个安全序列｛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
A B C
A B C
A B C
P0
0 3 0
7 3 2
2 1 0
P1
3 0 2
0 2 0
P2
3 0 2
0 0 0
P3
2 1 1
0 1 1
P4
0 0 2
4 3 2
图6为P0分配资源后的有关资源数据
(5) 进行安全性检查: 可用资源Available(2,1,0)已不能满足任何进程的需要, 故系统进入不安全状态, 此时系统不分配资源。
8程序测试结果

图7

图8

图9
图10
源程序清单:

#include <string.h>
#include <stdio.h>
#include <iostream.h>
#define FALSE 0
#define TRUE 1
#define W 10
#define R 10
int M ;
int N ;
int ALL_RESOURCE[W];
int MAX[W][R];
int AVAILABLE[R];
int ALLOCATION[W][R];
int NEED[W][R];
int Request[R];
void output()
{
int i,j;
cout<<endl<<"━━━━━━━━━━━━━━━━━━"<<endl;
cout<<"各种资源的总数量:"<<endl;
for (j=0;j<N;j++)
cout<<" 资源"<<j<<": "<<ALL_RESOURCE[j];
cout<<endl;
cout<<"━━━━━━━━━━━━━━━━━━"<<endl;
cout<<"当前各种资源可利用的数量为:"<<endl;
for (j=0;j<N;j++)
cout<<" 资源"<<j<<": "<<AVAILABLE[j];
cout<<endl;
cout<<"━━━━━━━━━━━━━━━━━━"<<endl;
cout<<"各进程还需要的资源数量:"<<endl<<endl;
for(i=0;i<N;i++)
cout<<" 资源"<<i;
cout<<endl;
for (i=0;i<M;i++)
{
cout<<"进程"<<i<<": ";
for (j=0;j<N;j++)
cout<<NEED[i][j]<<" ";
cout<<endl;
}
cout<<endl;
cout<<"━━━━━━━━━━━━━━━━━━"<<endl;
cout<<"各进程已经得到的资源量: "<<endl<<endl;
for(i=0;i<N;i++)
cout<<" 资源"<<i;
cout<<endl;
for (i=0;i<M;i++)
{
cout<<"进程"<<i<<": ";
for (j=0;j<N;j++)
cout<<ALLOCATION[i][j]<<" ";
cout<<endl;
}
cout<<endl;
}

void distribute(int k)
{
int j;
for (j=0;j<N;j++)
{
AVAILABLE[j]=AVAILABLE[j]-Request[j];
ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j];
NEED[k][j]=NEED[k][j]-Request[j];
}
}

void restore(int k)
{
int j;
for (j=0;j<N;j++)
{
AVAILABLE[j]=AVAILABLE[j]+Request[j];
ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j];
NEED[k][j]=NEED[k][j]+Request[j];
}
}

int check()
{
int WORK[R],FINISH[W];
int i,j;
for(j=0;j<N;j++) WORK[j]=AVAILABLE[j];
for(i=0;i<M;i++) FINISH[i]=FALSE;
for(i=0;i<M;i++)
{
for(j=0;j<N;j++)
{
if(FINISH[i]==FALSE&&NEED[i][j]<=WORK[j])
{
WORK[j]=WORK[i]+ALLOCATION[i][j];
}
}

FINISH[i]=TRUE;
}
for(i=0;i<M;i++)
{
if(FINISH[i]==FALSE)
{
cout<<endl;
cout<<" 系统不安全!!! 本次资源申请不成功!!!"<<endl;
cout<<endl;
return 1;
}
else
{
cout<<endl;
cout<<" 经安全性检查, 系统安全, 本次分配成功。"<<endl;
cout<<endl;
return 0;
}

}
}

void bank() // 银行家算法
{
int i=0,j=0;
char flag='Y';
while(flag=='Y'||flag=='y')
{
i=-1;
while(i<0||i>=M)
{
cout<<"━━━━━━━━━━━━━━━━━━"<<endl;
cout<<endl<<" 请输入需申请资源的进程号:";
cin>>i;
if(i<0||i>=M) cout<<" 输入的进程号不存在, 重新输入!"<<endl;
}
cout<<" 请输入进程"<<i<<"申请各类资源的数量:"<<endl;
for (j=0;j<N;j++)
{
cout<<" 资源"<<j<<": ";
cin>>Request[j];
if(Request[j]>NEED[i][j])
cout<<endl<<" 进程"<<i<<"申请的资源数大于进程"<<i<<"还需要"<<j<<"类资源的数量!";
cout<<" 若继续执行系统将处于不安全状态!"<<endl;
flag='N';
break;
}
else
{
if(Request[j]>AVAILABLE[j])
{
cout<<endl<<" 进程"<<i<<"申请的资源数大于系统可用"<<j<<"类资源的数量!";
cout<<" 若继续执行系统将处于不安全状态!"<<endl;
flag='N';
break;
}

}

}
if(flag=='Y'||flag=='y')
{
distribute(i);
if(check())
{
restore(i);
output();
}
else
output();
}
else
cout<<endl;
cout<<" 是否继续银行家算法演示,按'Y'或'y'键继续,按'N'或'n'键退出演示: ";
cin>>flag;
}
}

void version()
{
cout<<endl;
cout<<"\t 　　　　　　 　银 行 家 算 法　 　　　　　　　"<<endl;
}

void main()
{
int i=0,j=0,p;
version();
getchar();
cout<<endl<<"请输入总进程数:";
cin>>M;
cout<<endl<<"━━━━━━━━━━━━━━━━━━"<<endl;
cout<<"请输入总资源种类:";
cin>>N;
cout<<endl<<"━━━━━━━━━━━━━━━━━━"<<endl;
cout<<"请输入各类资源总数:(需要输入数为"<<N<<"个)";
for(i=0;i<N;i++)
cin>>ALL_RESOURCE[i];
cout<<endl<<"━━━━━━━━━━━━━━━━━━"<<endl;
cout<<"输入各进程所需要的各类资源的最大数量:(需要输入数为"<<M*N<<"个)";
for (i=0;i<M;i++)
{
for (j=0;j<N;j++)
{
do
{
cin>>MAX[i][j];
if (MAX[i][j]>ALL_RESOURCE[j])
cout<<endl<<"占有资源超过了声明的该资源总数,请重新输入"<<endl;
}
while (MAX[i][j]>ALL_RESOURCE[j]);
}
}
cout<<endl<<"━━━━━━━━━━━━━━━━━━"<<endl;
cout<<"输入各进程已经占据的各类资源的数量:(需要输入数为"<<M
*N<<"个)";
for (i=0;i<M;i++)
{
for (j=0;j<N;j++)
{
do
{
cin>>ALLOCATION[i][j];
if (ALLOCATION[i][j]>MAX[i][j])
cout<<endl<<"占有资源超过了声明的最大资源,请重新输入"<<endl;
}
while (ALLOCATION[i][j]>MAX[i][j]);
}
}
for (j=0;j<N;j++)
{
p=ALL_RESOURCE[j];
for (i=0;i<M;i++)
{
p=p-ALLOCATION[i][j];
AVAILABLE[j]=p;
if(AVAILABLE[j]<0)
AVAILABLE[j]=0;
}
}
for (i=0;i<M;i++)
for(j=0;j<N;j++)
NEED[i][j]=MAX[i][j]-ALLOCATION[i][j];
output();
bank();
}