(完整word版)操作系统银行家算法实验报告 (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;i

output(iMax,iAllocation,iNeed,iAvailable,cName); //判断当前状态是否安全

bSafe=safety(iAllocation,iNeed,iAvailable,cName); //是否继续提出申请 while(bExitFlag) { cout<<\继续提出申请?\\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<<\ Max \\tAllocation\\t Need \\t Available\

cout<<\ B C\\tA B C\\tA B C\\t A B C\ for(i=0;i

//安全性算法,进行安全性检查;安全返回true,并且输出安全序列,不安全返

5