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

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

———————————————————————————————— 作者：
———————————————————————————————— 日期：

2

个人收集整理 勿做商业用途
课 程 设 计 报 告

课程设计名称： 银行家算法模拟实现
系 ：
学生姓名：
班 级：
学 号:
成 绩：
指导教师:
开课时间： 学年 学期

题目要求：
一．设计题目
银行家算法模拟实现
二．主要内容
设计目的
1、 了解多道程序系统中，多个进程并发执行的资源分配。
2、 掌握思索的产生原因、产生死锁的必要条件和处理死锁的基本方法。
3、 掌握预防死锁的方法，系统安全状态的基本概念。
4、 掌握银行家算法，了解资源在进程并发执行中的资源分配策略。
5、 理解死锁避免在当前计算机系统不常使用的原因。
三．具体要求
设计一个n个并发进程共享m个系统资源的系统,进程可动态申请资源和释放资源，系统按各进程的申请动态的分配资源.要求采用银行家算法实现.
四．进度安排
序号
内 容
时间（天)
1
熟悉课题、分析课题
0。5
2
对系统进行模块分解，问题分析和确定解决方案
1
3
编程调试
3
4
测试和差错
1
5
书写课程设计报告
1
6
考核
1

合 计
7.5
五．成绩评定
考核方法：根据学生平时表现、测试检查、课程设计报告、运行演示和学生回答问题相结合的形式作为考核依据，考察学生的动手能力,独立分析解决问题的能力和创新精神,并根据学生的学习态度综合考评。平时表现（占30%），课程设计报告（占40%)，课程答辩（占30%）。
成绩评定：成绩分“优秀”、“良好”、“中等”、“及格”、“不及格”五个级别。“优秀”为100分到90分，“良好"为89分到80分，“中等"为79分到70分,“及格”为69分到60分，“不及格"为60分以下.

目录
1。需求分析 4
2。概要设计 4
3.详细设计 6
4.调试分析 12
5。总结 16
6.参考文献 16

1.需求分析
1、始化这组进程的最大资源请求和一次申请的资源序列。把各进程已占用和需求资源情况记录在进程控制块中。假定进程控制块的内容包括：进程名,状态，当前申请量，资源需求总量,已占资源量，能执行完标志。其中，进程的状态有：就绪，等待和完成。当系统不能满足进程的资源请求时，进程出于等待状态。资源需求总量表示进程运行过程中对资源的总的需求量。已占资源量表示进程目前已经得到但还为归还的资源量。因此，进程在以后还需要的剩余资源量等于资源需要总量减去已占资源量。陷入每个进程的资源需求总量不应超过系统拥有的资源总量。
2、银行家算法分配资源的原则是：当某个进程提出资源请求时，假定先分配资源给它,然后查找各进程的剩余请求，检查系统的剩余资源量是否由于进程的分配而导致系统死锁。若能，则让进程等待，否则，让进程的假分配变为真分配。
A） 查找各进程的剩余请求，检查系统的剩余资源量是否能满足其中一进程，如果能，则转B）。
B）将资源分配给所选的进程，这样，该进程已获得资源最大请求,最终能运行完成.标记这个进程为终止进程，并将其占有的全部资源归还给系统.
重复第A)步和B）步，直到所有进程都标记为终止进程,或知道一个死锁发生。若所有进程都标记为终止进程，则系统的初始状态是安全的,否则为不安全的。若安全，则正式将资源分配给它，否则，假定的分配作废,让其等待。

2。概要设计
2。1设计思想
当某个进程提出资源请求时，假定先分配资源给它，然后查找各进程的剩余请求，检查系统的剩余资源量是否由于进程的分配而导致系统死锁。若能，则让进程等待，否则，让进程的假分配变为真分配。
2.2数据结构
假设有m个进程,则有如下数据结构:
#define w 50 //宏定义
＃define r 50 //宏定义
int m； //总进程数
int all[w］；//各种资源的数目总和
int max［w］［r］; //m个进程最大资源需求量
int available[r］; //系统可用资源数
int allocation［w]［r]； //m个进程已经得到资源的资源量
int need[w］[r]; //m个进程还需要资源的资源量
int request［r］; //请求资源个数
2.3程序流程图
开始
输入进程数m，各资源总数，初始化Available向量
i=1
i<=m
输入进程i的最大需求向量max。

max<=资源总数

i++
Y
N
N
Y
错误
初始化need
任选一个进程作为当前进程（0到m-1）

该进程的Need向量为0

输入该进程的资源请求量Request

调用银行家算法，及安全性算法，完成分配，或并给出提示

N
Y
该进程已运行结束

Need矩阵为0

Y
结束

3。详细设计
3。1算法思想
银行家算法的基本思想是分配资源之前,判断系统是否是安全的；若是，才分配。否则拒绝分配.

3.2银行家算法
设Request［n]，是进程的请求向量,如果Request[n］=m，则表示该进程需要m个资源。当该进程发出资源请求后,系统按下述步骤进行检查:
（1)如果Request[n]《=Need[i，n]，便转向步骤（2）；否则认为出错，因为它所需要的资源数已经超过它所宣布的最大值。
(2)如果Request[n］>Available，则进程i进入等待资源状态,返回。
(3）假设进程i的申请已获批准，于是修改下面数据结构中的数值：
Available=Available-Request
Allocation=Allocation+Request
Need=Need-Request
(4)系统执行安全性检查,如安全，则分配成立；否则恢复原来的资源分配状态，系统恢复原状，进程等待。
程序
void bank（） //银行家算法
｛
int i=0，j=0;
char flag=’Y';
while(flag==’Y'｜|flag==’y’）
｛
i=-1;
while(i〈0｜｜i>=m）
{
cout<<” 请输入需申请资源的进程号(从0到"<<m-1<〈"）:”;
cin〉〉i；
if（i<0||i〉=m）cout〈〈" 该进程号不存在，请重新输入!”〈<endl;
}
cout<<” 请输入进程”<<i<<"申请的资源数:”；
for （j=0;j〈1；j++)
｛
cout〈〈” ”;
cin>>request［j]；
if（request[j］>need［i］［j］） //若请求的资源数大于进程还需要i类资源的资源量j
{
cout〈〈" 进程”〈〈i<<"申请的资源数大于进程”<<i〈〈"还需要资源的资源量！"；
cout〈<"申请不合理，请重新选择！"〈〈endl<〈endl；
flag=’1’;
break;
}
else
｛
if(request[j]〉available［j］) //若请求的资源数大于可用资源数
{
cout<〈” 进程"〈<i〈〈"申请的资源数大于系统可用资源的资源量!”；
cout〈〈"申请不合理！请重新选择!"〈〈endl<<endl；
flag='1’；
break;
}
}
｝
if(flag=='Y'｜｜flag=='y'）
{
change（i）； //调用change（i)函数，改变资源数
if（chkerr（i）) //若系统安全
{
rstore（i); //调用rstore(i）函数，恢复资源数
show（）; //输出资源分配情况
｝
else //若系统不安全
show(); //输出资源分配情况
｝
else //若flag=N||flag=n
show(）；
cout<<endl;
cout〈〈" 是否继续（Y/N): ”;
cin>>flag；
｝
}

3.3安全性检查算法
(1)设置两个工作向量Work=Available；Finish[M］=False
（2)从进程集合中找到一个满足下述条件的进程,
Finish ［i]=False
Need〈=Work
如找到，执行（3）；否则,执行(4）
（3)设进程获得资源，可顺利执行，直至完成，从而释放资源.
Work=Work+Allocation
Finish=True
GO TO 2
（4）如所有的进程Finish[M］=true,则表示安全；否则系统不安全.
程序
int chkerr(int s） //检查安全性
｛ int work，FInISH[w］;
int i，j,k=0;
for(i=0；i〈m;i++）FInISH［i]=false；
for(j=0；j〈1;j++)
｛
work=available［j］;
i=s；
do
｛
if(FInISH［i]==false＆&need[i][j］〈=work)
{
work=work+allocation[i］［j];
FInISH[i]=true;
i=0；
｝
else
{ i++;
｝
｝while(i<m）；
for(i=0；i〈m;i++）
if（FInISH［i］==false)
｛
cout〈〈endl；
cout<〈" 系统不安全!！！ 本次资源申请不成功!!！”<〈endl;
cout〈<endl；
return 1；
｝
}
cout〈〈endl；
cout<<" 系统安全，分配成功。”<〈endl;
cout<<endl;
return 0;
}

3。4 修改数据结构中的数值
改变可用资源和已经拿到资源和还需要的资源的值
void change(int k） ｛
int j;
for (j=0；j〈1；j++）
{
available［j］=available[j］-request［j];
allocation［k］［j]=allocation［k］[j］+request［j］;
need[k][j］=need［k][j］-request[j］；
}
｝
3。5 如果分配失败，则恢复原来的资源分配状态
恢复可用资源和已经拿到资源和还需要的资源的值
void rstore(int k)
｛int j；
available[j］=available［j]+request［j];
allocation[k］[j]=allocation[k］[j]—request［j]；
need[k］[j］=need[k]［j］+request［j]；

｝

3.6 输出显示
实现人机交互的各类资源输出显示情况.
void show（） //输出资源分配情况
｛
int i,j；
cout〈〈”资源总量:"〈〈” ";
for （j=0；j〈1;j++）cout〈<" ”<<all[j];
cout〈〈endl<〈endl;
cout〈〈"系统目前资源可用数：”〈<” "；
for (j=0;j<1；j++）cout<〈” "〈〈available[j]；
cout<<endl〈<endl；
cout〈<"进程名 各进程还需要的资源量"<〈endl；
for (i=0;i<m;i++）
for (i=0；i<m；i++)
{
cout<<"进程”<<i〈〈”: "；
for （j=0;j<1;j++)cout〈<need[i]［j]<<" ”;
cout〈<endl;
｝
cout〈<endl；
cout<〈”进程名 各进程已经得到的资源量”〈<endl；
for (i=0；i〈m;i++)
｛
cout〈〈”进程"<〈i<<"： ”;
for （j=0;j〈1;j++）cout<<allocation［i][j]<<” ";
cout〈〈endl;
｝
cout〈<endl；
}
void change(int k） //改变可用资源和已经拿到资源和还需要的资源的值
｛
int j；
for (j=0；j<1;j++)
｛
available［j］=available[j]-request[j];
allocation［k］［j]=allocation［k][j]+request[j］；
need［k］[j]=need[k]［j]-request[j］；
｝
｝

3。7 主函数
void main（） //主函数
{
int i=0,j=0,p;
cout〈〈"---—--—--——-—银行家算法模拟--————-—--—-—”<〈endl；
cout<〈”请输入总进程数:"；
cin〉>m;
cout〈〈"请输入总资源数：”；
for(i=0；i<1;i++）
cin>>all［i］；
cout〈〈”依次输入各进程所需要的最大资源数量：”〈〈endl；
for （i=0；i<m;i++）
｛
for (j=0;j<1;j++）
{
do
｛
cin〉>max[i］[j］;
if （max[i］［j]>all［j］）
cout〈〈endl〈〈"占有资源超过了声明的该资源总数，请重新输入”<<endl；
}
while （max［i］[j］>all[j］）；
}
}
cout<<"依次输入各进程已经占据的资源数量：”<<endl；
for (i=0;i<m；i++)
{
for (j=0；j〈1；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<1；j++）
｛ p=all［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<1；j++）
need[i][j］=max[i］[j]-allocation［i］[j］；
show(）;
bank()；
｝

3.8 定义全局变量
＃include "string。h”
＃include ”iostream"
using namespace std;
#define false 0
#define true 1
#define w 50 //宏定义
#define r 50 //宏定义
int m； //总进程数
int all[w］；//各种资源的数目总和
int max［w］［r］; //m个进程最大资源需求量
int available［r］; //系统可用资源数
int allocation[w］［r]; //m个进程已经得到资源的资源量
int need［w］［r]; //m个进程还需要资源的资源量
int request[r]; //请求资源个数
4。调试分析

图4-1
图4—1这里为3个进程（进程0.1.2）共用10个资源，分别需要的最大资源数为3,4,3.已经占有的资源数为：1,2，2. 分配给0号进程1个资源，系统安全，分配成功

图4—2
4—2再分配给0号进程1个资源,系统安全，分配成功

图4-3
4—3分配给1号进程3个资源，因为1号资源还需要2个即达到最大需要资源数，故申请不合理，分配不成功

图4-4
图4-4重新设定2个进程（0,1）共用5个资源。分别需要的最大资源数为4，3.已经占有的资源数为3,1。进程1申请2个资源，大于系统可用资源数。申请不合理，故申请失败.

图4—5
图4—5进程1申请1个资源,此时发生死锁，故申请失败。（发生死锁后，程序出错。)
5.总结
由于本人技术与经验的不足，在设计n类资源时出现未找到解决方法的错误，因此只把资源种类设计成只有一类。这样程序的编写得到简化.当然在实际实现时会出现很多类资源，这是这个程序需要改进的地方.进程请求资源后,若产生死锁,则程序出错。相信随着对操作系统与死锁等问题的深入了解，会更好的完善这个程序.
在上学期的数据库课程里已经初步认识了银行家算法，对它有了一定的了解。它是避免死锁的主要方法，书上的介绍也许不够详细与完整，所以在这次课程设计中，通过查阅大量书籍资料，让我对它产生了一定的深入认识，只是由于一些个人原因，未能及时完成。
在以后的学习中,这种算法还将会有很多地方要用到的。所以不能报着“学过就完事”的态度。当然,以后可能还会有比这种算法更好的算法，但是核心思想与它的目的是不会变的.所以,弄懂弄透了之后，再学习操作系统的更多知识会更容易上手。
6。参考文献
[1］。汤小丹．计算机操作系统（第三版)．西安：电子科技大学出版社；
［2］。张丽芬．操作系统实验教程．清华大学出版社。

18
18-18