操作系统课程设计银行家算法的模拟实现








操作系统


课程设计报告







专业
计算机科学技术
学生姓名

班级

学号

指导教师

完成日期




信息工程学院
题目： 银行家算法模拟实现
设计目
课程设计学完操作系统原理课程进行次全面综合训练通课程设计更掌握操作系统原理实现方法加深操作系统基础理重算法理解加强学生动手力
二设计容
1）概述
CC++语言编制银行家算法通程序检测状态系统安全性
1 算法介绍：数结构：
1） 利资源量 Available
2） 需求矩阵Max
3） 分配矩阵Allocation
4） 需求矩阵Need
2 功介绍
模拟实现Dijkstra银行家算法避免死锁出现分两部分组成：
第部分：银行家算法（扫描）
第二部分：安全性算法
2）设计原理
．银行家算法基概念
1死锁概念
道程序系统中助进程发执行改善系统资源利率提高系统吞吐量发生种危险━━死锁谓死锁(Deadlock)指进程运行中争夺资源造成种僵局(Deadly_Embrace)进程处种僵持状态时外力作法前推进组进程中进程限等该组进程中进程占资源永远法资源种现象称进程死锁组进程称死锁进程
2关死锁结：
Ø 参死锁进程少两
Ø （两进程会出现死锁）
Ø 参死锁进程少两已占资源
Ø 参死锁进程等资源
Ø 参死锁进程前系统中进程子集

注：果死锁发生会浪费量系统资源甚导致系统崩溃
3资源分类
永久性资源：
进程次（资源）
l 抢占资源
l 抢占资源
时性资源：次资源信号量中断信号步信号等（消耗性资源）
　　　　　　申请分配释放模式

4产生死锁四必条件：互斥（资源独占）强占（剥夺）请求保持（部分分配占申请）循环等
1) 互斥（资源独占）
资源次进程
2) 强占（剥夺）
资源申请者强行资源占者手中夺取资源资源占者愿释放
3) 请求保持（部分分配占申请）
进程申请新资源时保持原资源占（样动态申请动态分配）
4) 循环等
存进程等队列
{P1 P2 … Pn}
中P1等P2占资源P2等P3占资源…Pn等P1占资源形成进程等环路
5死锁预防
定义系统设计时确定资源分配算法保证发生死锁具体做法破坏产生死锁四必条件
①破坏剥夺条件
允许进程动态申请资源前提规定进程申请新资源立满足变等状态前必须释放已占全部资源需重新申请
②破坏请求保持条件
求进程运行前必须次性申请求资源仅该进程资源均满足时予次性分配
③破坏循环等条件
采资源序分配法：
系统中资源编号进程申请资源时必须严格资源编号递增次序进行否操作系统予分配
6．安全状态安全状态
安全状态：
果存系统中进程构成安全序列P1…Pn系统处安全状态进程序列{P1…Pn}安全果进程Pi(1≤i≤n）尚需资源量超系统前剩余资源量进程Pj (j < i )前占资源量系统处安全状态 (安全状态定没死锁发生)
安全状态存安全序列安全状态定导致死锁
二．银行家算法
1银行家算法中数结构
1）利资源量Available
含m元素数组中元素代表类利资源数目初始值系统中配置该类全部资源数目数值该类资源分配回收动态改变果Available[j]K表示系统中现Rj类资源K
2）需求短阵Max
—n×m矩阵定义系统中n进程中进程m类资源需求果Max(ij)＝K表示进程i需Rj类资源数目K
3）分配短阵Allocation
n×m矩阵定义系统中类资源前已分配进程资源数果Allocation(ij)＝K表示进程i前已分Rj类资源数目K
4）需求矩阵Need
n×m矩阵表示进程尚需类资源数果Need[ij]K表示进程i需Rj类资源k方完成务
述三矩阵间存述关系：
Need[ij]Max[ij]Allocation[ij]
2银行家算法
设Requesti进程Pi请求量果Requesti[j]＝k表示进程需kRj类型资源Pi发出资源请求系统述步骤进行检查：
1）果 Requesti[j]2）果Requesti[j]3）系统试探求资源分配进程Pi修改面数结构中数值：
Available[j]Available[j]Requesti[j]
Allocation[ij]Allocation[ij]+Requesti[j]
Need[ij]Need[ij]Requesti[j]
4）系统执行安全性算法检查次资源分配系统否处安全状态安全正式资源分配进程Pi完成次分配否试探分配作废恢复原资源分配状态进程Pi等
3安全性算法
系统执行安全性算法描述：
1）设置两量
①工作量Work表示系统提供进程继续运行需类资源数目含m元素执行安全算法开始时Work Available
②Finish表示系统否足够资源分配进程运行完成开始时先做Finish[i]false 足够资源分配进程时令 Finish[i]true
2）进程集合中找满足述条件进程：
①Finish[i]false ②Need[ij]3）进程Pi获资源利执行直完成释放出分配资源应执行：
Work[j]Work[i]+Allocation[ij]
Finish[i]true
goto step 2
4）果进程Finish[i]true表示系统处安全状态否系统处安全状态
三．银行家算法例
假定系统中五进程：{P0P1P2P3P4}三种类型资源{ABC}种资源数量分1057T0时刻资源分配情况图1示





资源情况
进程
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
图1 T0时刻资源分配表
(1)T0时刻安全性：利安全性算法T0时刻资源分配情况进行分析(图2)知T0时刻存着安全序列｛P1P3P4P2P0｝系统安全
资源情况
进程
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
图2 T0时刻安全序列
(2)P1请求资源：P1发出请求量Request1(102)系统银行家算法进行检查：
①Request1(102) ②Request1(102) ③系统先假定P1分配资源修改AvailableAllocation1Need1量形成资源变化情况图1中圆括号示
④利安全性算法检查时系统否安全图3示
资源情况
进程
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
图3 P1申请资源时安全性检查
进行安全性检查知找安全序列｛P1P3P4P2P0｝系统安全立P1申请资源分配
(3)P4请求资源：P4发出请求量Request4(330)系统银行家算法进行检查：
①Request4(330)≤Need4(431)
②Request4(330)等Available(230)P4等
(4)P0请求资源：P0发出请求量Request0(020)系统银行家算法进行检查
①Request0(020) ≤Need0(743)
②Request0(020) ≤Available(230)
③系统暂时先假定P0分配资源修改关数图4示
资源情况
进程
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
6 0 0
P3
2 1 1
0 1 1
P4
0 0 2
4 3 2
图4 P0分配资源关资源数
(5)进行安全性检查：资源Available(210)已满足进程需系统进入安全状态时系统分配资源
3）详细设计编码
1）银行家算法流程图

2）程序源代码
#include
#include
#include
#include
定义全局变量
const int x20y20 常量便修改
int Available[x] 资源利数量
int Allocation[y][y] 进程前已分配资源数量
int Max[y][y] 进程类资源需求数
int Need[y][y] 尚需少资源
int Request[x] 申请少资源
int Work[x] 工作量表示系统提供进程继续运行需类资源数量
int Finish[y] 表示系统否足够资源分配进程1
int p[y] 存储安全序列
int ij i表示进程j表示资源
int nm n进程i数量m资源j种类数
int l0 l记录进程Finish[i]1ln说明系统状态安全
int counter0

函数声明
void chushihua() 初始化函数
void safe() 安全性算法
void show() 函数show输出前状态
void bank() 银行家算法
void jieshu() 结束函数

void chushihua()
{
cout<<输入进程数量 开始输入关数
cin>>n
cout<<输入资源种类数
cin>>m
cout< for (j0 j {
cout<<输入资源 < cin>>Available[j] 输入数字程
Work[j]Available[j] 初始化Work[j]初始值前资源数
}
cout< for (i0 i {
for (j0 j {
cout<< 输入进程 < cin>>Allocation[i][j]
}
cout< Finish[i]0初始化Finish[i]
}
cout< for (i0 i {
for (j0 j {
cout<< 输入进程 < cin>>Max[i][j]
if(Max[i][j]>Allocation[i][j]) 需求已分配计算需求量
Need[i][j] Max[i][j]Allocation[i][j]
else
Need[i][j]0Max已分配时候类资源已足够需申请
}
cout< }
cout<}

安全性算法函数
void safe()
{
l0
for (i0 i { i++
if (Finish[i]0)
{ 逐查找Finish[i]0进程 条件
counter0 记数器
for (j0 j {
if (Work[j]>Need[i][j]) countercounter+1需求记数
}
if(counterm) i进程类资源符合Work[j]>Need[i][j] 条件二
{
p[l]i 存储安全序列
Finish[i]1 i进程标志分配
for (j0 j Work[j]Work[j]+Allocation[i][j] 释放资源
ll+1 记数现L进程安全LN时说明满足安全序列
i 1 第进程开始继续寻找满足条件二进程
}
}
}
}

显示前状态函数
void show() 函数show输出前资源分配情况
{
int ij 局部变量
int All[y] 种资源总数量
cout<<前状态：< cout<<种资源总数量< for (j0j {
cout<< 资源< All[j]Available[j] 总数量+已分配
for (i0i cout< }
cout< for (j0j cout<< 资源< cout<
for (j0j cout< for(i0i {
cout<<进程< for (j0j cout< }

cout< for (j0j cout< for(i0i {
cout<<进程< for (j0j cout< }

}
银行家算法函数
void bank()
{
cout< int k0 输入进程编号
bool rfalse 初值假输入Y继续申请置真
do{输入请求
cout<<输入申请资源进程(0< cin>>k
cout< while(k>n1) 输入错误处理
{
cout< cout< cin>>k
cout< }
cout< for (j0 j {
do{ do……while 循环判断申请输入情况
cout<<进程 < cin>>Request[j]
cout< if(Request[j]>Need[k][j])
{ 申请需求量时出错提示重新输入（贷款数目允许超需求数目）
cout<<申请需量< cout<<申请资源< cout<<重新输入< }
else 先判断否申请需求量判断否申请利量
if(Request[j]>Available[j])
{ 申请利量 应该阻塞等？…… ？？？
cout<<＼n没资源目前利资源< Finish[k]0 该进程等
goto ppp goto语句 跳转结束次申请
}
}while(Request[j]>Need[k][j]) Request[j]>Available[j]||
}
改变AvilableAllocationNeed值
for (j0 j {
Available[j] Available[j]Request[j]
Allocation[k][j] Allocation[k][j]+Request[j]
Need[k][j] Need[k][j]Request[j]
Work[j] Available[j]
}
判断前状态安全性
safe() 调安全性算法函数
if (l {
l0
cout<<＼n试分配状态安全予分配恢复原状态< 恢复数
for (j0 j {
Available[j] Available[j]+Request[j]
Allocation[k][j] Allocation[k][j]Request[j]
Need[k][j] Need[k][j]+Request[j]
Work[j] Available[j]
}
for (i0 i Finish[i]0 进程置未分配状态
}
else
{
l0
cout<<＼n申请资源成功< for(j0j {
if(Need[k][j]0)
else
{ 种资源没全部申请该进程执行释放拥资源
l1 置l1作判断标志
break
}
}
if(l1)
{ 进程执行释放该进程资源
for (j0j {
Available[j]Available[j]+Allocation[k][j]
Allocation[k][j]0
}
cout<<该进程已需求资源执行释放拥资源< }
l0 零
cout<<＼n安全状态< cout<<安全序列
cout< Finish[0]0
for (i1 i {
cout<<>><<进程<<(< Finish[i]0 进程置未分配状态
}
cout< }
show() 显示前状态
ppp 申请利量 应该阻塞等结束次资源申请GOTO 语句跳转
cout< char* bnew char 输入yn判断否继续申请 < cin>>b
cout< cout<<< cout< if(*b＇y＇||*b＇Y＇) rtrue
else
{
rfalse 输入非 Y 令 R false
jieshu() 调结束函数
}
} while (rtrue)
}
结束函数
void jieshu()
{
cout< cout<<＼t＼t 演示计算完毕< cout<}

函数
int main()
{
cout< chushihua() 初始化函数调
cout< show() 输出前状态
safe() 判断前状态安全性
if (l {
cout<<＼n前状态安全拒绝申请< cout< return 0
}
else
{
int i 局部变量
l0
cout< cout<<进程<<(< for (i1 i><<进程<<(< for (i0 i cout< }
bank() 调银行家算法函数
cout<<＼t＼t 演示计算完毕< return 0
}
4）运行结果分析
1．示例数
进程数量：5
资源种类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
2测试结果（表中数列）
截图：





5）设计结
次做课题银行家算法模拟实现通次课程设计仅拓宽知识面实践程中巩固加深学理知识技术素质实践力进步提高时专业水进步
时软件开发方面累积少验操作系统知识重性认识更深通设计程锻炼分析问题解决问题力锻炼提高完善知识结构加深学知识理解
通天努力次课程设计圆满结束程中学知识学中会更加努力学专业知识学知识实践中便牢固掌握知识
6）参考文献
[1]计算机操作系统(第3版)汤丹西安电子科技学出版社2007年7月
[2]Visual C++面象编程教程（第二版）王育坚清华学出版社2007年10月）














文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档