操作系统课程设计报告

枣庄学院

计算机科学系课程设计任务书

题目：银行家算法与实现

学号： 200912230360

姓名：张海

专业：计算机网络

课程：操作系统

指导教师：李刚职称：讲师

完成时间： 20## 年 06 月----2011 年 06 月

枣庄学院计算机科学系制

20##年月日

正文

1 课程设计简介

1.1 课程设计题目

银行家算法的模拟实现。应用银行家算法验证进程安全性检查及分配资源。

1.2 课程设计目的

本设计的目的是通过编写和调试一个系统动态分配资源的简单模拟程序，观察死锁产生的条件，并采用适当的算法，有效地防止和避免死锁地发生。

A、了解进程产生死锁的原因，了解为什么要进行死锁的避免。

B、掌握银行家算法的数据结构，了解算法的执行过程，加深对银行家算法的理解。

1.3 课程设计内容

此次课程设计的主要内容时模拟实现动态资源分配。同时要求编写和调试一个系统动态分配资源有效的防止和避免死锁的发生的简单模拟程序。

设计一个n 个并发进程共享m 个系统资源的系统。进程可动态申请资源和释放资源，系统按各进程的申请动态的分配资源。要求采用银行家算法实现。

2 实验原理分析

2.1 算法的来源及基本思想

银行家算法，顾名思义是来源于银行的借贷业务，通过这个算法可以用来解决生活中的实际问题，如银行贷款等。一定数量的本金要应多个客户的借贷周转，为了防止银行加资金无法周转而倒闭，对每一笔贷款，必须考察其是否能限期归还。在操作系统中研究资源分配策略时也有类似问题，系统中有限的资源要供多个进程使用，必须保证得到的资源的进程能在有限的时间内归还资源，以供其他进程使用资源。如果资源分配不得到就会发生进程循环等待资源，则进程都无法继续执行下去的死锁现象。

2.2 死锁产生的条件

银行家算法是用来避免死锁的一种重要方法，通过编写一个简单的银行家算法程序，加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。

死锁的产生，必须同时满足四个条件：

A、即一个资源每次只能由一个进程使用；

B、第二个为等待条件，即一个进程请求资源不能满足时，它必须等待，单它仍继续宝石已得到的所有其他资源；

C、第三个为非剥夺条件，即在出现死锁的系统中一定有不可剥夺使用的资源；

D、第四个为循环等待条件，系统中存在若干个循环等待的进程，即其中每一个进程分别等待它前一个进程所持有的资源。

防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会发生死锁。银行家算法是避免死锁的方法中，施加的限制条件较弱的，有利于获得令人满意的系统性能的方法。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。

2.3 模拟进程申请资源

把一个进程需要和已占有资源的情况记录在进程控制中，假定进程控制块PCB其中“状态”有就绪态、等待态和完成态。当进程在处于等待态时，表示系统不能满足该进程当前的资源申请。“资源需求总量”表示进程在整个执行过程中总共要申请的资源量。显然，，每个进程的资源需求总量不能超过系统拥有的资源总数, 银行算法进行资源分配可以避免死锁.

3 程序结构分析

3.1 程序流程图

程序流程图是人们对解决问题的方法、思路或算法的一种描述。
流程图的优点：（a）采用简单规范的符号，画法简单；

（b）结构清晰，逻辑性强；（c）便于描述，容易理解。
流程图采用规范的符号（1）起始框（2）终止框

（3）执行框（4）判别框

本次制作流程图省略了起始框和终止框。

安全性算法流程：

银行家算法流程：

注：程序初始化流程包含在银行家流程中但未画出。

3.2 程序模块划分

A.输出资源分配情况

B.输出资源分配后后的情况

C.银行家算法:

设进程i提出请求Request[n]，则银行家算法按如下规则进行判断。

1)如果Request[n]>Need[i，n]，则报错返回。

2)如果Request[n]>Available，则进程i进入等待资源状态并返回。

3)假设进程i的申请已获批准，于是修改系统状态：

Available=Available-Request

Allocation=Allocation+Request

Need=Need-Request

4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。

D.安全性检查

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，则表示安全；

否则系统不安全。

4 数据结构分析

算法用到的主要数据结构和C语言说明。

（1）、可利用资源向量 INT AVAILABLE[M] M为资源的类型。

（2）、最大需求矩阵 INT MAX[N][M] N为进程的数量。

（3）、已分配矩阵 INT ALLOCATION[N][M]

（4）、还需求矩阵 INT NEED[N]

假设有M个进程N类资源，则有如下数据结构:

#define W 10

#define R 20

int M ; //总进程数

int N ; //资源种类

int ALL_RESOURCE[W]; //各种资源的数目总和

int MAX[W][R]; //M个进程对N类资源最大资源需求量

int AVAILABLE[R]; //系统可用资源数

int ALLOCATION[W][R]; //M个进程已经得到N类资源的资源量

int NEED[W][R]; //M个进程还需要N类资源的资源量

int Request[R]; //请求资源个数

5 各子模块相关函数代码

5.1 showdata()

void showdata() //函数showdata,输出资源分配情况

{

int i,j;

cout<<" ——————————————————————"<<endl;

cout<<"各种资源的总数量(all):"<<endl;

cout<<" ";

for (j=0;j<N;j++)cout<<" 资源"<<j<<": "<<ALL_RESOURCE[j];

cout<<endl<<endl;

cout<<"系统目前各种资源可用的数为(available):"<<endl;

cout<<" ";

for (j=0;j<N;j++)cout<<" 资源"<<j<<": "<<AVAILABLE[j];

cout<<endl<<endl;

cout<<"—————————————————————";

cout<<" 各进程还需要的资源量(need):"<<endl<<endl;

cout<<" ";

for (j=0;j<N;j++)cout<<setw(8)<<"资源"<<j;

for (i=0;i<M;i++)

{

cout<<endl<<"进程p"<<i<<":";

for (j=0;j<N;j++)cout<<setw(8)<<NEED[i][j];

}

cout<<endl;

cout<<"—————————————————————";

cout<<" 各进程已经得到的资源量(allocation): "<<endl<<endl;

cout<<" ";

for (j=0;j<N;j++)cout<<setw(8)<<"资源"<<j;

for (i=0;i<M;i++)

{

cout<<endl<<"进程p"<<i<<":";

for (j=0;j<N;j++)cout<<setw(8)<<ALLOCATION[i][j];

}

cout<<endl;

}

5.2 changdata(int k)

void changdata(int k) //函数changdata,改变可用资源和已经拿到资源和还需要的资源的值

{

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

}

5.3 rstordata(int k)

void rstordata(int k) //函数rstordata,恢复可用资源和已经拿到资源和还需要的资源的值

{ 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];

}

5.4 chkerr(int s)

int chkerr(int s) //函数chkerr,检查是否安全

{ int WORK;//FINISH[W]

int i,j,k=0;

for(i=0;i<M;i++)FINISH[i]=FALSE;

for(j=0;j<N;j++)

{

WORK=AVAILABLE[j];

i=s;

{

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<<"进程p"<<i<<"状态：阻塞"<<endl;

}

cout<<endl;

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

cout<<endl;

return 0;

}

5.5 set()

void set() //进程状态显示函数

{

int t[10];

for(int i=0;i<M;i++){

t[i]=0;

for(int j=0;j<N;j++){if(NEED[i][j]==0) t[i]+=1;}

}

for(i=0;i<M;i++)

if(t[i]==N)

{cout<<"进程p"<<i<<"状态：运行结束"<<endl;

for(int k=0;k<N;k++)

AVAILABLE[k]=AVAILABLE[k]+ALLOCATION[i][k];

ALLOCATION[i][k]=0;

}

else

cout<<"进程p"<<i<<"状态：等待调用"<<endl;

}

5.6 bank()

void bank() //银行家算法

{

int i=0,j=0;

char flag='Y';

while(flag=='Y'||flag=='y')

{

i=-1;

while(i<0||i>=M)

{

cout<<" 请输入需申请资源的进程号（从P0到P"<<M-1<<"，否则重输入!）:";

cout<<"p";cin>>i;

if(i<0||i>=M)cout<<" 输入的进程号不存在，重新输入!"<<endl;

}

cout<<" 请输入进程P"<<i<<"申请的资源数:"<<endl;

for (j=0;j<N;j++)

{

cout<<" 资源"<<j<<": ";

cin>>Request[j];

if(Request[j]>NEED[i][j]) //若请求的资源数大于进程还需要i类资源的资源量j

{

cout<<" 进程P"<<i<<"申请的资源数大于进程P"<<i<<"还需要"<<j<<"类资源的资源量!";

cout<<"申请不合理，出错!请重新选择!"<<endl<<endl;

flag='N';

break;

}

else

{

if(Request[j]>AVAILABLE[j])

//若请求的资源数大于可用资源数

{

cout<<" 进程P"<<i<<"申请的资源数大于系统可用"<<j<<"类资源的资源量!";

cout<<"申请不合理，出错!请重新选择!"<<endl<<endl;

flag='N';

break;

}

if(flag=='Y'||flag=='y')

{

changdata(i); //调用changdata(i)函数，改变资源数

if(chkerr(i)) //若系统不安全

{

rstordata(i); //调用rstordata(i)函数，恢复资源数

showdata();//调用showdata()函数，输出资源分配情况 }

else { //若系统安全

showdata(); //调用showdata()函数，输出资源分配情况

set();

}

else //若flag=N||flag=n

showdata(); //调用showdata()函数，输出资源分配情况

cout<<endl;

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

cin>>flag;

}

6 程序运行结果分析

6.1 示例数据

进程数：2

资源数：2

资源0：10

资源1：20

6.2 运行结果

输入数据完成初始化演示图6-2-1

注：初始化时，如果输入数据不符合要求，程序能给出错误提示并要求使用者重新输入数据。为简便期间，省去此功能的截屏图像。演示者可以自行上机体会。

计算机自动检测水所有进程能否构成一个安全序列。演示图6-2-2

如果能够构成安全序列，就显示出是否进行手动申请资源。

输入k 开始手动申请资源。演示图6-2-3

申请资源并进行安全性检查演示图6-2-2

继续演示演示图6-2-3

提示出错继续演示演示图6-2-4

输入N结束演示

6.3 出现问题及解决方案

A、源程序中未考虑进程状态会随着程序运行发生变化，为了完善程序专门编写了状态函数void set（）来显示进程状态。如图6-2-2与图6-2-4倒数2、3行中均显示了进程状态。

B、源程序中指定资源数必须是三种，经过改进后资源数可以为1到10中的任意数。

C、源程序资源矩阵的输出界面不能自动适应数据长度的变化，修改后资源的矩阵输出界面中的数据显示获得了改善。

7 心得体会

这次课程设计没有将程序初始化代码段分离出来，以至于程序的结构不清晰，由于初始化代码不是一个独立的函数致使程序的可读性较差。作课程设计时应尽量把功能模块设计好考虑好，使程序易于理解。

设计中得到了老师和广大同学的帮助，并参考了网络上的优秀论文和纸质文件，使我的程序设计能够较为顺利的进行下去。在此我衷心感谢我的老师同学和对以上资源的作者。

8 参考文献

网络资料百度知道：

A网址http://zhidao.baidu.com/question/30838506.html?si=2

B网址http://zhidao.baidu.com/question/5766513.html?fr=qrl3

纸质资料课本：

A 《计算机操作系统》(西安电子科大第2版) (汤子瀛)

B 《高级语言C++程序设计》（高教第2版）（刘璟周玉龙）

操作系统课程设计报告

正 文

1.1 课程设计题目

1.2 课程设计目的

1.3 课程设计内容

2.1 算法的来源及基本思想

2.2 死锁产生的条件

2.3 模拟进程申请资源

3.1 程序流程图

3.2 程序模块划分

5.1 showdata()

5.2 changdata(int k)

5.3 rstordata(int k)

5.4 chkerr(int s)

5.5 set()

5.6 bank()

6.1 示例数据

6.3 出现问题及解决方案

专栏推荐

正文