银行家算法详解

发布时间：2018-06-30 13:06:43

一、课程设计目的和意义

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

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

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

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

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

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

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

银行家算法是避免死锁的一种重要方法，通过编写一个简单的银行家算法程序，加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。死锁的产生，必须同时满足四个条件，即一个资源每次只能由一个进程张勇；第二个为等待条件，即一个进程请求资源不能满足时，它必须等待，单它仍继续宝石已得到的所有其他资源；第三个为非剥夺条件，即在出现死锁的系统中一定有不可剥夺使用的资源；第四个为循环等待条件，系统中存在若干个循环等待的进程，即其中每一个进程分别等待它前一个进程所持有的资源。防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会发生死锁。通过这个算法可以用来解决生活中的实际问题，如银行贷款等。

二、方案设计及开发过程

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

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

（二）.算法描述

1.银行家算法:
设进程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)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。
2.安全性检查
(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，则表示安全；否则系统不安全。

3.数据结构

假设有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];            //请求资源个数

4.主要函数说明

void showdata();           //主要用来输出资源分配情况

void changdata(int);       //主要用来输出资源分配后后的情况

void rstordata(int);       //用来恢复资源分配情况,如:银行家算法时,由于分配不安全则要恢复资源分配情况

int chkerr(int);           //银行家分配算法的安全检查

void bank()   ;             //银行家算法

5源程序

#include "string.h"

#include "iostream"

using namespace std;

#define FALSE 0

#define TRUE 1

#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]; //请求资源个数

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

{

int i,j;

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

cout<<" ";

for (j=0;j资源"<

cout<

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

cout<<" ";

for (j=0;j资源"<

cout<

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

cout<<" 资源0"<<" 资源1"<<" 资源2"<

for (i=0;i

for (i=0;i

{

cout<<"进程p"<

for (j=0;j

cout<

}

cout<

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

cout<<" 资源0"<<" 资源1"<<" 资源2"<

for (i=0;i

{

cout<<"进程p"<

for (j=0;j

cout<

}

cout<

}

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

{

int j;

for (j=0;j

{

AVAILABLE[j]=AVAILABLE[j]-Request[j];

ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j];

NEED[k][j]=NEED[k][j]-Request[j];}}

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

{int j;

for (j=0;j

{ AVAILABLE[j]=AVAILABLE[j]+Request[j];

ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j];

NEED[k][j]=NEED[k][j]+Request[j];}}

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

{ int WORK,FINISH[W];

int i,j,k=0;

for(i=0;i

for(j=0;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

for(i=0;i

if(FINISH[i]==FALSE)

{

cout<

cout<<" 系统不安全!!! 本次资源申请不成功!!!"<

cout<

return 1;

}

}

cout<

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

cout<

return 0;

}

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"<，否则重输入!）:";

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

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

}

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

for (j=0;j

{

cout<<" 资源"<

cin>>Request[j];

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

{

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

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

flag='N';

break;

}

else

{

if(Request[j]>AVAILABLE[j]) //若请求的资源数大于可用资源数

{

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

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

flag='N';

break;

}

}

}

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

{

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

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

{

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

showdata(); //输出资源分配情况

}

else //若系统不安全

showdata(); //输出资源分配情况

}

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

showdata();

cout<

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

cin>>flag;

}

}

void main() //主函数

{

int i=0,j=0,p;

cout<<"请输入总进程数:"<

cin>>M;

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

cin>>N;

cout<<"请输入总资源数(all_resource):"<

for(i=0;i

cin>>ALL_RESOURCE[i];

cout<<"依次输入各进程所需要的最大资源数量(max):"<

for (i=0;i

{

for (j=0;j

{

do

{

cin>>MAX[i][j];

if (MAX[i][j]>ALL_RESOURCE[j])

cout<占有资源超过了声明的该资源总数,请重新输入"<

}while (MAX[i][j]>ALL_RESOURCE[j]);

}

}

cout<<"依次输入各进程已经占据的资源数量(allocation):"<

for (i=0;i

{

for (j=0;j

{

do

{

cin>>ALLOCATION[i][j];

if (ALLOCATION[i][j]>MAX[i][j])

cout<占有资源超过了声明的最大资源,请重新输入"<

}while (ALLOCATION[i][j]>MAX[i][j]);

}

}

//初始化资源数量

for (j=0;j

{ p=ALL_RESOURCE[j];

for (i=0;i

{

p=p-ALLOCATION[i][j];//减去已经被占据的资源

AVAILABLE[j]=p;

if(AVAILABLE[j]<0)

AVAILABLE[j]=0;

}

}

for (i=0;i

for(j=0;j

NEED[i][j]=MAX[i][j]-ALLOCATION[i][j];

showdata();

bank();

}

银行家算法详解

推荐内容

相关推荐