操作系统原理课程设计银行家算法.docx

操作系统原理课程设计银行家算法.docx

《操作系统原理课程设计银行家算法.docx》由会员分享，可在线阅读，更多相关《操作系统原理课程设计银行家算法.docx（24页珍藏版）》请在冰点文库上搜索。

操作系统原理课程设计银行家算法

课程设计

课程名称操作系统原理课程设计

题目编程序模拟银行家算法

专业计算机网络

班级

姓名

成绩

指导教师

2009年7月6日至2009年7月10日

课程设计任务书

设计题目：

编程序模拟银行家算法

设计目的

1、银行家算法是避免死锁的一种重要方法，本实验要求用高级语言编写和调试一个简单的银行家算法程序。

加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。

2、提高学生的程序设计能力、提高算法设计质量与程序设计素质；

设计任务（在规定的时间内完成下列任务）

思想：

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

银行家对客户的借款可以推迟支付，但是能够使客户在有限的时间内得到借款，客户得到所有的借款后能在有限的时间内归还。

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

时间安排

1月14日布置课程设计任务；分配题目后，查阅资料、准备程序；

1月15～1月17日上机调试程序、书写课程设计报告；

1月18日提交课程设计报告及相关文档。

具体要求

1.课程设计报告按统一通用格式书写，具体格式要求请在网络上查阅；

2.每位学生应独立完成各自的任务且每天至少在设计室工作半天；

指导教师签名：

09年7月6日

教研室主任（或责任教师）签名：

09年7月10日

1.需求分析

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

集体要求如下：

（1）模拟一个银行家算法；

（2）初始化时让系统拥有一定的资源；

（3）用键盘输入的方式申请资源；

（4）如果预分配后，系统处于安全状态，则修改系统的资源分配情况；

（5）如果预分配后，系统处于不安全状态，则提示不能满足请求，

此次课程设计的主要内容时模拟实现动态资源分配。

同时要求编写和调试一个系统动态资源的简单模拟程序，观察死锁产生的条件，并使用适当的算法，有效的防止和避免死锁的发生。

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

死锁的产生，必须同时满足四个条件，即一个资源每次只能由一个进程张勇；第二个为等待条件，即一个进程请求资源不能满足时，它必须等待，单它仍继续宝石已得到的所有其他资源；第三个为非剥夺条件，即在出现死锁的系统中一定有不可剥夺使用的资源；第四个为循环等待条件，系统中存在若干个循环等待的进程，即其中每一个进程分别等待它前一个进程所持有的资源。

防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会发生死锁。

通过这个算法可以用来解决生活中的实际问题。

死锁会引起计算机工作僵死，因此操作系统中必须防止。

本实验的目的在于让学生独立的使用高级语言编写和调试一个系统动态分配资源的简单模拟程序，了解死锁产生的条件和原因，并采用银行家算法有效地防止死锁的发生，以加深对课堂上所讲授的知识的理解。

1.1设计原理：

死锁产生的条件

1．互斥控制，进程对其所要求的资源进行排他控制，一个资源仅能被一个进程独占。

2．非剥夺控制，进程所获得的资源在未被释放之前，不能被其他进程剥夺，即使该进程处于阻塞状态，他所占用的资源野不能被其他进程使用，而其他进程只能等待该资源的释放；

3．逐次请求，进程以随意的零星方式逐次取得资源，而不是集中性的一次请求，这样有利于提高资源的利用率；

4.环路条件，在发生死锁时，必然存在一个进程——资源的环形链。

不断有资源在等待被占用的资源；

我们只要破坏以上四个条件之一，既可以预防死锁。

银行家算法是避免死锁的方法中，施加的限制条件较弱的，有利于获得令人满意的系统性能的方法。

在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。

Dijkstra（1965）年提出了一种能够避免死锁的调度方法，称为银行家算法，描述如下：

假定一个银行家拥有资金，数量为Ё，被N个可户共享。

银行家对可户提出下列约束条件：

Ⅰ.每个客户必须预先说明自己所要求的最大资金量；

Ⅱ.每个客户每次提出部分资金量申请和获得分配；

Ⅲ.如果银行家满足了客户对资金的最大需求量，那么，客户在资金运作后，应在有限时间内全部归还银行。

把一个进程需要和已占有资源的情况记录在进程控制中，假定进程控制块PCB其中“状态”有就绪态、等待态和完成态。

当进程在处于等待态时，表示系统不能满足该进程当前的资源申请。

“资源需求总量”表示进程在整个执行过程中总共要申请的资源量。

显然，，每个进程的资源需求总量不能超过系统拥有的资源总数,银行算法进行资源分配可以避免死锁.

1.2设计思想：

假设在进程并发执行时进程i提出请求j类资源k个后，表示为Requesti[j]=k。

系统按下述步骤进行安全检查：

（1）如果Requesti≤Needi则继续以下检查，否则显示需求申请超出最大需求值的错误。

（2）如果Requesti≤Available则继续以下检查，否则显示系统无足够资源，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等待。

（5）设置两个向量：

①工作向量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;

Øgotostep2;

（4）如果所有进程的Finish［i］=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

1.3程序结构：

A.字符判断模块：

判断输入的字符是否为数字，如果不是则提示出错并重新输入，主要处理输入为非数字时程序出现运行错误现象。

此模块功能由数字判断函数（intshuzi（intsz）;）实现。

B.程序初始化模块：

用于程序开始进行初始化输入数据：

进程数量、资源种类、各种资源可利用数量、各进程的各种资源已分配数量、各进程对各类资源最大需求数等。

此模块功能在系统初始化函数（voidchushihua（）;）中实现。

C.当前安全性检查模块：

用于判断当前状态安全性，根据不同地方的调用提示处理不同，在安全性算法函数（voidsafe（）;）中实现。

D.银行家算法模块：

进行银行家算法模拟实现的模块，调用其他各个模块进行银行家算法模拟过程，在银行家算法函数（voidbank（）;）中实现。

E.显示分配模块：

显示当前资源分配详细情况，包括：

各种资源的总数量（all）、系统目前各种资源可用的数量、各进程已经得到的资源数量、各进程还需要的资源量，在显示分配情况函数（voidshowdata（）;）中实现。

1.4程序流程图：

图1银行家算法的流程图

1.5数据结构：

1.5.1定义全局变量

constintx=50,y=100;//定义常量，便于修改

intAvailable[x];//各种资源可利用的数量

intAllocation[y][y];//各进程当前已分配的资源数量

intMax[y][y];//各进程对各类资源的最大需求数

intNeed[y][y];//还需求矩阵

intRequest[x];//申请各类资源的数量

intWork[x];//工作向量，表系统可提供给进程运行所需各类资源数量

intFinish[y];//表系统是否有足够的资源分配给进程，0为否，1为是

intp[y];//存储安全序列

inti,j;//全局变量，主要用于循环语句中

intn,m;//n为进程的数量,m为资源种类数

intl=0,counter=0;

1.5.2函数声明

intshuzi（intsz）;//数字判断函数，还可使用voidshuzi（int&sz）;方式

voidchushihua（）;//系统初始化函数

voidsafe（）;//安全性算法函数

voidbank（）;//银行家算法函数

voidshowdata（）;//函数showdata,输出当前资源分配情况

1.5.3主函数结构

intmain（）{

system（"color06f"）;//设置当前窗口的背景色和前景色

cout<<……//显示程序开始提示信息

chushihua（）;//初始化函数调用

cout<

showdata（）;//输出初始化后的状态

safe（）;//安全性算法函数调用

if（l

!

!

!

!

"<

cout<

system（"pause"）;

return0;//break;}

else{

inti;//局部变量

l=0;

cout<<"\n安全的状态!

!

!

"<

cout<<"安全序列为:

";

cout<

for（i=1;i

cout<<"==>>"<<"进程"<<"（"<

}

for（i=0;i

cout<

}

bank（）;//银行家算法函数调用

return0;

}

1.5.4银行家算法：

设Requesti是进程Pi的请求向量，如果Requesti[j]=K，表示进程Pi需要K个Ri类型的资源。

当Pi发出资源请求后，系统按下述步骤进行检查：

（1）如果Requesti[j]<=Need[i,j]，便转向步骤2；否则认为出错，因为它所需的资源数已经超过了它所宣布的最大值。

（2）如果Requesti[j]<=Available[j]，便转向步骤3；否则表示尚无足够资源，Pi需等待。

（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值。

      Available[j]=Available-Requesti[j];

      Allocation[i,j]=Allocation[i,j]+Requesti[j];

      Need[i,j]=Need[i,j]-Request[j];

（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。

若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来资源的分配状态，让进程Pi等待。

1.5.5源程序：

#include

#include

#include

#include

#include

//===定义全局变量===

constintx=50,y=100;//定义常量，便于修改

intAvailable[x];//各种资源可利用的数量

intAllocation[y][y];//各进程当前已分配的资源数量

intMax[y][y];//各进程对各类资源的最大需求数

intNeed[y][y];//还需求矩阵

intRequest[x];//申请各类资源的数量

intWork[x];//工作向量，表示系统可提供给进程继续运行所需的各类资源数量

intFinish[y];//表示系统是否有足够的资源分配给进程，0为否，非0为是

intp[y];//存储安全序列

inti,j;

intn,m;//n为进程的数量,m为资源种类数

intl=0,counter=0;

//函数声明

intshuzi（intsz）;//数字判断函数或者使用voidshuzi（int&sz）;方式

voidchushihua（）;//系统初始化函数

voidsafe（）;//安全性算法函数

voidbank（）;//银行家算法函数

voidshowdata（）;//函数showdata,输出当前资源分配情况

//===数字判断函数===

intshuzi（intsz）{//输入数据并判断是否为数字

char*temp;

temp=newchar;//临时指针，存放输入字符

intlen;//存储取字符的长度

sz=0;//清零

chars;//

do{//输入赌注，只能输入数字

//gets（temp）;//getline（cin,temp）

cin>>temp;

len=strlen（temp）;//取字符长度

for（inti=0;i

s=*（temp+i）;

if（s<'0'||s>'9'）{

cout<<"笨蛋，输错了!

你输入的是数字吗?

!

\n\n";

cout<<"请重新输入：

";

break;

}

}

}while（s<'0'||s>'9'）;

for（inti=0;i

intt=1;

for（intj=1;j

sz+=（*（temp+i）-48）*t;

}

returnsz;

}

//===系统初始化函数===

voidchushihua（）{

//===系统初始化输入===

cout<<"%%程序开始，系统初始化输入%%"<

cout<<"=========================================="<

cout<<"请输入进程的数量:

";//从此开始输入有关数据

n=shuzi（n）;

cout<<"请输入资源种类数:

";

m=shuzi（m）;

cout<

"<

cout<

for（j=0;j

cout<<"输入资源"<

";

Available[j]=shuzi（Available[j]）;

Work[j]=Available[j];//初始化Work[j]

}

cout<

cout<<"请输入各进程当前已分配的资源数量Allocation["<

"<

for（i=0;i

for（j=0;j

cout<<"请输入进程"<

";

Allocation[i][j]=shuzi（Allocation[i][j]）;

}

cout<

Finish[i]=0;//初始化Finish[i]

}

cout<

cout<<"请输入各进程对各类资源的最大需求数Max["<

"<

for（i=0;i

for（j=0;j

cout<<"请输入进程"<

";

Max[i][j]=shuzi（Max[i][j]）;

if（Max[i][j]>=Allocation[i][j]）//

Need[i][j]=Max[i][j]-Allocation[i][j];//计算还需求量

else

Need[i][j]=0;//最大需求量小于已分配量时还需求量为0,即此类资源已足够不需再申请

}

}

cout<<"%%初始化完成!

%%"<

}

//===安全性算法函数===

voidsafe（）{

l=0;

for（i=0;i

if（Finish[i]==0）{//寻找Finish[i]==0的进程条件一

counter=0;//记数器

for（j=0;j

if（Work[j]>=Need[i][j]）;//可用大于等于需求

else{

counter=1;

break;

}

if（counter!

=1）{//进程的每类资源量都符合条件Work[j]>=Need[i][j]条件二

p[l]=i;//存储安全序列

Finish[i]=1;//标志为可分配

for（j=0;j

Work[j]=Work[j]+Allocation[i][j];//释放资源

}

l=l+1;//记数,当L=N时说明满足安全序列,即都符合条件Work[j]>=Need[i][j]

i=-1;//从第一个进程开始继续寻找满足条件一二的进程

}

}

i++;//for循环继续寻找

}

}

//===显示分配情况函数===

voidshowdata（）//函数showdata,输出当前资源分配情况

{

inti,j;//局部变量

intAll[y];//各种资源的总数量

intl2;//局部变量l1,

cout<<"============================================="<

cout<

%%"<

cout<<"%%各种资源的总数量（all）:

"<

for（j=0;j

cout<<"资源"<

";

All[j]=Available[j];//初始化先赋值加上可利用量

for（i=0;i

All[j]+=Allocation[i][j];//再加上每个进程已分配量计算J类资源总量

}

cout<

if（（j+1）%5==0）cout<

=0

}

cout<

cout<<"%%系统目前各种资源可用的数为（available）:

"<

for（j=0;j

cout<<"资源"<

"<

if（（j+1）%5==0）cout<

=0

}

cout<

cout<<"%%各进程已经得到的资源量（allocation）:

"<

//l1=0;//归零

for（i=0;i<=m/5;i++）{//设计每行最多显示五种资源

for（j=i*5;j

cout<

for（l2=0;l2

cout<<"进程"<

";

for（j=i*5;j

cout<

}

}

cout<

cout<<"%%各进程还需要的资源量（need）:

"<

for（i=0;i<=m/5;i++）{//设计每行显示五种资源

for（j=i*5;j

cout<

for（l2=0;l2

cout<<"进程"<

";

for（j=i*5;j

cout<

}

}

cout<

cout<<"============================================="<

cout<

system（"pause"）;//暂停

}

//===银行家算法函数===

voidbank（）{

cout<<"=============================================="<

cout<<"%%以下开始为进程进行资源分配申请%%"<

//===申请资源===

intk=0;//用于输入进程编号

boolr=false;//初值为假，输入Y继续申请则置为真

do{

//输入请求

cout<<"请输入申请资源的进程编号（输入0--"<

";

k=shuzi（k）;

cout<

while（k>n-1）{//输入异常处理

cout<

"<

cout<

";

k=shuzi（k）;

cout<