操作系统银行家算法实验报告_(1)

银行家算法实验报告

【实验目的】

（1）根据设计题目的要求，充分地分析和理解题目，叙述系统的要求，明确程序要求实现的功能以及限制条件。

（2）明白自己需要用代码实现的功能，清楚编写每部分代码的目的，做到有的放矢，有条理不遗漏的用代码实现银行家算法。 【实验要求】

（1）了解和理解死锁；

（2）理解利用银行家算法避免死锁的原理； （3）会使用某种编程语言。 【实验原理】 一、安全状态

指系统能按照某种顺序如(称为序列为安全序列)，为每个进程分配所需的资源，直至最大需求，使得每个进程都能顺利完成。

二、银行家算法

假设在进程并发执行时进程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等待。 三、安全性算法

（1）设置两个向量：

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

② Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish［i］∶=false; 当有足够资源分配给进程时， 再令Finish［i］∶=true。

（2）从进程集合中找到一个能满足下述条件的进程： ① Finish［i］=false;

② Need［i,j］≤Work［j］； 若找到， 执行步骤(3)， 否则，执行步骤(4)。 （3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资

1

源，故应执行：

➢ Work［j］∶=Work［i］+Allocation［i,j］; ➢ Finish［i］∶=true; ➢ go to step 2;

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

【实验步骤】

参考实验步骤如下：

（1）参考图1-1所示流程图编写安全性算法。 开始 初始化Work和Finish N 存在Finish[i] =false &&Need[i][j]<= Available[j] Y Finish[i]=true，Work[j]=Work[j]+ Allocation[i][j] N 所有进程都找完了？ Y N 所有finish都为true？ Y 输出系统不安全 输出安全序列 图1-1 安全性算法流程图

2

（2）银行家算法流程图 开始 输入初始参数（资 源分配及请求情 出错返 Y Requesti[j]> Need[i][j] 回： N 出错返回：(进程阻Y Requesti[j]> Available[j] 塞) N 假定分配： Available[j] = Available[j] – Requesti[j] Allocation[i][j]= Allocation[i][j] + Requesti[j] Need[i][j] = Need[i][j] – Requesti[j] 是 否 假定分配之后，系统安 全吗？ 申请成功。输出各种申请失败。 数据的变化 以上分配作废，恢复原来的分配状态： Available[j] = Available[j] + Requesti[j] Allocation[i][j]= Allocation[i][j]－Requesti[j] Need[i][j] = Need[i][j]+Requesti[j] 结束 图1-2银行家算法流程图

（3）编写统一的输出格式。

每次提出申请之后输出申请成功与否的结果。如果成功还需要输出变化前后的各种数据，并且输出安全序列。

3

（4）参考图1-2所示流程图编写银行家算法。 （5）编写主函数来循环调用银行家算法。 【参考代码】

部分参考代码如下： #include #include

#define M 3 //资源的种类数 #define N 5 //进程的个数 void output(int iMax[N][M],int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N]); //统一的输出格式

bool safety(int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N]);

bool banker(int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N]); void main() {

int i,j;

//当前可用每类资源的资源数 int iAvailable[M]={3,3,2};

//系统中N个进程中的每一个进程对M类资源的最大需求 int iMax[N][M]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}}; //iNeed[N][M]每一个进程尚需的各类资源数

//iAllocation[N][M]为系统中每一类资源当前已分配给每一进程的资源数 int iNeed[N][M],iAllocation[N][M]={{0,1,1},{2,0,0},{3,0,2},{2,1,1},{0,0,2}}; //进程名

char cName[N]={'a','b','c','d','e'}; bool bExitFlag=true; //退出标记 char ch; //接收选择是否继续提出申请时传进来的值 bool bSafe; //存放安全与否的标志 //计算iNeed[N][M]的值 for(i=0;ioutput(iMax,iAllocation,iNeed,iAvailable,cName); //判断当前状态是否安全

bSafe=safety(iAllocation,iNeed,iAvailable,cName); //是否继续提出申请 while(bExitFlag) { cout<<\"\\n\"<<\"继续提出申请？\\ny为是；n为否。\\n\"; cin>>ch; switch(ch) {

4

case 'y':

//cout<<\"调用银行家算法\"; bSafe=banker(iAllocation,iNeed,iAvailable,cName); if (bSafe) //安全，则输出变化后的数据 output(iMax,iAllocation,iNeed,iAvailable,cName); break; case 'n': cout<<\"退出。\\n\"; bExitFlag=false; break; default: cout<<\"输入有误，请重新输入：\\n\"; } } }

//输出 void output(int iMax[N][M],int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N]) {

int i,j;

cout<<\"\\n\ Max \Allocation\ Need \ Available\"<cout<<\"\A B C\A B C\A B C\ A B C\"<//安全性算法，进行安全性检查；安全返回true，并且输出安全序列，不安全返

5

回false，并输出不安全的提示；

bool safety(int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N]) {

int i,j,flag,x=0; char num[5]; int Work[M];

bool Finish[N]; //定义基本变量 for(j=0;j<3;j++) Work[j]=iAvailable[j]; //将iAvailable的值赋给Work for(i=0;i<5;i++) //将Finish全部置为False Finish[i]=false;

while(true) //执行无限循环，满足条件时跳出 { flag=0; //每次循环开始时将记录本次循环中是否有使有满足条件iAllocation的标志置为0，若为0表示不存在，若不为0表示存在 for(i=0;i<5;i++) //执行循环，看有没有满足条件的iAllocation {

if(Finish[i]==false&&Work[0]>=iNeed[i][0]&&Work[1]>=iNeed[i][1]&&Work[2]>=iNeed[i][2]) { for(j=0;j<3;j++) { Work[j]+= iAllocation[i][j] ; //Work[j]+= Work[j]+iAllocation[i][j] } Finish[i]=true; //将 Finish置true flag++; //标志加1 num[x++]=cName[i]; //将该序列名赋给数组num[] } } if(flag==0) { cout<<\"无安全序列\"; //标志为0，证明已无满足条件iAllocation ，退出循环，返回false return false; }

if(Finish[0]==true&&Finish[1]==true&&Finish[2]==true&&Finish[3]==true&&

6

Finish[4]==true) //若所有Finish置为true，输出安全数列，返回True { cout<<\"\\n\"; cout<<\"安全序列为：\"; for(x=0;x<5;x++) cout<return true; }

//安全返回true，不安全返回false

bool banker(int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N]) {

int iMax[N][M]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}}; int t,i,Request[3],check_1[3];

char x; //定义变量

cout<<\"请输入进程名：\"; //输入进程名 cin>>x;

if(x=='a')i=0; if(x=='b')i=1; if(x=='c')i=2; if(x=='d')i=3; if(x=='e')i=4;

cout<<\"请输入各资源数量：\"; //输入变量名 for(t=0;t<3;t++) cin>>Request[t];

for(t=0;t<3;t++) //检查数值 { check_1[t]=Request[t]+iAllocation[i][t]; }

for(t=0;t<3;t++) {

if((iMax[i][t]-check_1[t])<0) {

cout<<\"\\n资源申请超过最大需求量\\n\"; return false; } }

7

for(t=0;t<3;t++) //检查数值 {

if((iAvailable[t]-Request[t])<0) {

cout<<\"\\n不能满足进程\\n\"; return false; } }

for(t=0;t<3;t++) //将该变量的 iAvailable、iAllocation、iNeed重新赋值 {

iAvailable[t]-=Request[t]; iAllocation[i][t]+=Request[t]; iNeed[i][t]-=Request[t]; }

safety(iAllocation,iNeed,iAvailable,cName); //执行安全数列算法 return true; return true; }

实验结果

【实验小结】

通过这次实验，让我更深的了解了银行家算法，银行家算法是避免死锁的主要方法，其思路在很多方面都非常值得我们来学习借鉴。

8

。

9