操作系统课程设计报告--死锁避免算法设计.docx

操作系统课程设计报告--死锁避免算法设计.docx

《操作系统课程设计报告--死锁避免算法设计.docx》由会员分享，可在线阅读，更多相关《操作系统课程设计报告--死锁避免算法设计.docx（13页珍藏版）》请在冰点文库上搜索。

操作系统课程设计报告

计算机与信息工程学院

08 级计算机科学与技术专业题目 死锁避免算法设计

学生刘彦军 学号200820722282

指导教师 潘娟

2011年1月7日

设计题目：

死锁避免算法设计

设计目的：

1、 了解多道程序系统中，多个进程并发执行的资源分配。

2、 掌握死锁产生的原因，产生死锁必要条件和处理死锁的基本方法。

3、 掌握预防死锁的方法，系统安全状态的基本概念。

4、 掌握银行家算法，了解资源在进程并发执行中的资源分配策略。

5、 理解避免死锁在当前计算机系统不常使用的原因。

设计任务

一、要求

1．复习银行家算法，设计一个具有若干（不少于3种）资源和若干

（不少于5个）进程的系统。

2．定义系统的初始状态，即进程获得的资源数，还需要的资源数以及系统可用的资源数。

3．以用户输入的方式提出资源请求，并用银行家算法避免可能发生的死锁，若系统安全，允许用户继续申请资源。

4．设计的系统要求结构清晰，与用户的交互界面友好，能动态地实现资源的申请和分配。

二、思想

将一定数量的资金供多个用户周转使用，当用户对资金的最大申请量不超过现存资金时可接纳一个新客户，客户可以分期借款，但借款总数不能超过最大的申请量。

银行家对客户的借款可以推迟支

付，但是能够使客户在有限的时间内得到借款，客户得到所有的借款后能在有限的时间内归还。

用银行家算法分配资源时，测试进程对资源的最大需求量，若现存资源能满足最大需求就满足当前进程的申请，否则推迟分配，这样能够保证至少有一个进程可以得到所需的全部资源而执行到结束，然后归还资源，若OS能保证所有进程在有限的时间内得到所需资源则称系统处于安全状态。

设计思路和过程

1.概要设计

1.1程序流程图

1.2设计原理及方法

银行家算法的设计思想是：

当用户申请一组资源时，系统必须做出判断；如果把这些资源分出去，系统是否还处于安全装他。

若是，就可以分出这些资源；否则，该申请暂不能满足。

实现银行家算法要有若干数据结构，它们用来表示资源分配系统的状态。

令n表示系统中进程的数目，m表示资源的分类数。

还需要以下数据结构：

1.Available是一个长度为m的向量，它表示每类资源可用的数量。

Available[j]=k，表示rj类资源可用的数量为k。

2.Max是一个n×m矩阵，它表示每个进程对资源的最大需求。

Max[i，j]=k，表示进程pi至多可以申请k个rj类资源单位。

3.Allocation是一个n×m矩阵，它表示当前分给每个进程的资源数目。

Allocation[i，j]=k，表示进程pi当前分到k个rj类资源。

4.Need是一个n×m矩阵，它表示每个进程还缺少多少资源。

Need[i，j]=k，表示进程pi尚需k个rj类资源才能完成其任务。

显然Need[i，j]=Max[i，j]-Allocation[i，j]。

这些数据结构的大小和数值随时间推移而改变。

系统所执行的安全性算法描述如下：

1.设置2个向量：

工作向量Work：

它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available。

Finish[i]：

它表示系统是否有足够的资源分配给进程，使之完成运行。

开始时先做Finish[i]=true。

2.从进程集合中找到一个满足下述条件的进程：

Finish[i]

=flase；Need[i,j]≤Work[j]；若找到，则执行步骤3，否则，执行步骤4。

3.当进程pi获得资源后，可顺利执行，直至完成，并释放分配给它的资源。

4.如果所有进程的Finish[i]=true都满足。

则表示系统处于安全状态；否则，系统处于不安全状态。

2.详细设计

2.1程序源代码

#include#include#includeusingnamespacestd;#defineFalse0

#defineTrue1

intMax[100][100]={0};//各进程所需各类资源的最大需求intAvaliable[100]={0};//系统可用资源

charname[100]={0};//资源的名称

intAllocation[100][100]={0};//系统已分配资源intNeed[100][100]={0};//还需要资源

intRequest[100]={0};//请求资源向量inttemp[100]={0};//存放安全序列

intWork[100]={0};//存放系统可提供资源intM=100;//作业的最大数为100

intN=100;//资源的最大数为100voidshowdata（）//显示资源矩阵

{

inti,j;

cout<<"系统目前可用的资源[Avaliable]:

"<

for（i=0;i

cout<

for（j=0;j

cout<

cout<

cout<<" Max Allocation Need"<

cout<<"进程名 ";

for（j=0;j<3;j++）{for（i=0;i

cout<<" ";

}

cout<

cout<<""<

cout<

}

}

intchangdata（inti）//进行资源分配

{

intj;

for（j=0;j

Avaliable[j]=Avaliable[j]-Request[j];Allocation[i][j]=Allocation[i][j]+Request[j];Need[i][j]=Need[i][j]-Request[j];

}

return1;

}

intsafe（）//安全性算法

{

inti,k=0,m,apply,Finish[100]={0};intj;

intflag=0;Work[0]=Avaliable[0];Work[1]=Avaliable[1];

Work[2]=Avaliable[2];for（i=0;i

apply=0;for（j=0;j

if（Finish[i]==False&&Need[i][j]<=Work[j]）{apply++;

if（apply==N）{for（m=0;m

Work[m]=Work[m]+Allocation[i][m];//变分配数

Finish[i]=True;temp[k]=i;

i=-1;

k++;

flag++;

}

}

}

}

for（i=0;i

cout<<"系统不安全"<

return-1;

}

}

cout<<"系统是安全的!

"<

cout<<"分配的序列:

";

for（i=0;i

cout<";

}

cout<

}

voidshare（）//利用银行家算法对申请资源对进行判定

{

charch;

inti=0,j=0;ch='y';

cout<<"请输入要求分配的资源进程号（0-"<

";

cin>>i;//输入须申请的资源号

cout<<"请输入进程"<

"<

{

cout<

";

cin>>Request[j];//输入需要申请的资源

}

for（j=0;j

if（Request[j]>Need[i][j]）//判断申请是否大于需求，若大于则出错

{

cout<<"进程"<

cout<<"分配不合理，不予分配！

"<

break;

}

else{

if（Request[j]>Avaliable[j]）//判断申请是否大于当前资源，若大于

则

{ //出错

cout<<"进程"<

cout<<"分配出错，不予分配!

"<

break;

}

}

}

if（ch=='y'）{

changdata（i）;//根据进程需求量变换资源

showdata（）;//根据进程需求量显示变换后的资源

safe（）;//根据进程需求量进行银行家算法判断

}

}

voidaddresources（）{//添加资源

intn,flag;

cout<<"请输入需要添加资源种类的数量:

";

cin>>n;flag=N;N=N+n;

for（inti=0;i

cout<<"名称:

";

cin>>name[flag];

cout<<"数量:

";

cin>>Avaliable[flag++];

}

showdata（）;safe（）;

}

voidchangeresources（）{//修改资源函数

cout<<"系统目前可用的资源[Avaliable]:

"<

for（inti=0;i

"<

cout<<"输入系统可用资源[Avaliable]:

"<

cin>>Avaliable[0]>>Avaliable[1]>>Avaliable[2];

cout<<"经修改后的系统可用资源为"<

for（intk=0;k

"<

showdata（）;safe（）;

}

voiddelresources（）{//删除资源

charming;inti,flag=1;

cout<<"请输入需要删除的资源名称：

";

do{

cin>>ming;

for（i=0;i

break;

}

if（i==N）

cout<<"该资源名称不存在，请重新输入：

";

}

while（flag）;

for（intj=i;j

{

name[j]=name[j+1];

Avaliable[j]=Avaliable[j+1];

}N=N-1;

showdata（）;safe（）;

}

voidaddprocess（）{//添加作业intflag=M;

M=M+1;

cout<<"请输入该作业的最大需求量[Max]"<

for（inti=0;i

";cin>>Max[flag][i];

Need[flag][i]=Max[flag][i]-Allocation[flag][i];

}

showdata（）;safe（）;

}

intmain（）//主函数

{

inti,j,number,choice,m,n,flag;charming;

cout<<"*****************资源管理系统的设计与实现*****************"<

cout<<"请首先输入系统可供资源种类的数量:

";cin>>n;

N=n;

for（i=0;i

{

cout<<"资源"<

";

cin>>ming;name[i]=ming;

cout<<"资源的数量:

";

cin>>number;Avaliable[i]=number;

}

cout<

cout<<"请输入作业的数量:

";

cin>>m;

M=m;

cout<<"请输入各进程的最大需求量（"<

"<

for（i=0;i>Max[i][j];

do{



flag=0;

cout<<"请输入各进程已经申请的资源量（"<

"<

for（i=0;i

cin>>Allocation[i][j];if（Allocation[i][j]>Max[i][j]）flag=1;

Need[i][j]=Max[i][j]-Allocation[i][j];

}

if（flag）

cout<<"申请的资源大于最大需求量，请重新输入!

\n";

}

while（flag）;

showdata（）;//显示各种资源

safe（）;//用银行家算法判定系统是否安全while（choice）

{

cout<<"**************银行家算法演示***************"<

cout<<"

1:

增加资源

"<

cout<<"

2:

删除资源

"<

cout<<"

3:

修改资源

"<

cout<<"

4:

分配资源

"<

cout<<"

5:

增加作业

"<

cout<<"

0:

离开

"<

cout<<"*******************************************"<

cout<<"请选择功能号：

";

cin>>choice;switch（choice）

{

case1:

addresources（）;break;

case2:

delresources（）;break;

case3:

changeresources（）;break;

case4:

share（）;break;

case5:

addprocess（）;break;

case0:

choice=0;break;

default:

cout<<"请正确选择功能号（0-5）!

"<

}

}

return1;

}

3.调试及运行结果

3.1程序调试及运行结果

经过调试，改正了越界错误，定义错误，死循环和一些语法错误。

程序最终运行成功。

检测结果如下：

总结和体会

为期四天的课程设计结束了。

在这一周里，我做一个模拟银行家算法。

我觉得在着手设计前设计的思路是很重要的。

只有思路清晰才能进行下一阶段的设计。

这样才能完成整个程序的设计，完成整个文报告的书写。

课程设计这几天学到的东西还真不少。

以前不清楚的现在都暴露出来了。

以前认为学了没用的东西现在也用到了。

这次的课程设计使我进一步了解了调度与死锁的问题。

以及有关资源申请的问题、避免死锁的具体实施方法。

深入了解了银行家算法的资源申请和资源分配的过程及原则。

保证系统处于安全状态。

参考文献

1、 颜彬 计算机操作系统实验教程 北京 清华大学出版社

2008.10

2、 汤小丹 计算机操作系统 西安 西安电子科技大学出版社

2007.5

3、 袁宝华操作系统实验教程北京 清华大学出版社2010.1

4、 谭浩强C语言程序设计北京 清华大学出版社