银行家算法课程设计报告样本.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][*] 都被标记

返回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
#include
#include
#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<"当前各种资源可利用的数量为:"<<<" ";
cout<l;
}

void distribute(int k)
{
int j;
for (j=0;j][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;jORK[i]+ALLOCATION[i][j];
}
}

FINISH[i]=TRUE;
}
for(i=0;i
{
int i=0,j=0;
char flag='Y';
while(flag=='Y'||flag=='y')
{
i=-1;
while(i<0||i>=M)
{
cout<<"━━━━━━━━━━━━━━━━━━"<>i;
if(i<0||i>=M) cout<<" 输入的进程号不存在, 重新输入!"< ";
cin>>Request[j];
if(Request[j]>NEED[i][j])
cout<AVAILABLE[j])
{
cout<g='N';
break;
}

}

}
if(flag=='Y'||flag=='y')
{
distribute(i);
if(check())
{
restore(i);
output();
}
else
output();
}
else
cout<>flag;
}
}

void version()
{
cout<　银 行 家 算 法　 　　　　　　　"<>M;
cout<>N;
cout<>ALL_RESOURCE[i];
cout<>MAX[i][j];
if (MAX[i][j]>ALL_RESOURCE[j])
cout<ALL_RESOURCE[j]);
}
}
cout<dl<<"━━━━━━━━━━━━━━━━━━"<>ALLOCATION[i][j];
if (ALLOCATION[i][j]>MAX[i][j])
cout<MAX[i][j]);
}
}
for (j=0;j