银行家算法完整版本.docVIP

。

-可编辑修改-

操作系统银行家算法

课后作业

一、实验目的

加深对多实例资源分配系统中死锁避免方法——银行家算法的理解，掌握Windows环境下银行家算法的实现方法。强调对于资源的管理、申请、比较来避免出现死锁的情况，保证系统的正常运行。

二、实验内容

1.在Windows操作系统上，利用DEVC++编写应用程序实现银行家算法。

2.创建n个线程来申请或释放资源，只有保证系统安全，才会批准资源申请。

三、实验步骤

（一）设计思路：

银行家算法可分为个主要的功能模块，其描述如下：

1.初始化

由用户输入数据，分别对运行的进程数、总的资源种类数、总资源数、各进程所需要的最大资源数量（Max），已分配的资源数量赋值。

2.安全性检查算法

(1)设置两个工作向量Work=AVAILABLE;FINISH=false;

(2)从进程集合中找到一个满足下述条件的进程，

FINISH==false;

NEED=Work;

如找到，执行(3)；否则，执行(4)

(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。

Work+=ALLOCATION;

Finish=true;

(4).如所有的进程Finish=true，则表示安全；否则系统不安全。

3.银行家算法

在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。

银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。

设进程j提出请求REQUEST[i]，则银行家算法按如下规则进行判断。

(1).如果REQUEST[j][i]=NEED[j][i]，则转(2)；否则，出错。

(2).如果REQUEST[j][i]=AVAILABLE[j][i]，则转(3)；否则，出错。

(3).系统试探分配资源，修改相关数据：

AVAILABLE[i]-=REQUEST[j][i];

ALLOCATION[j][i]+=REQUEST[j][i];

NEED[j][i]-=REQUEST[j][i];

用到的数据结构：

实现银行家算法要有若干数据结构，它们用来表示资源分配系统的状态。令n表示系统中进程的数目，m表示资源的分类数。还需要以下数据结构：

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

2).Max是一个n×m矩阵，它表示每个进程对资源的最大需求。Max[i，j]=k，表示进程pi至多可以申请k个j类资源单位。

3).Allocation是一个n×m矩阵，它表示当前分给每个进程的资源数目。Allocation[i，j]=k，表示进程i当前分到k个j类资源。

4).Need是一个n×m矩阵，它表示每个进程还缺少多少资源。Need[i，j]=k，表示进程pi尚需k个j类资源才能完成其任务。显然Need[i，j]=Max[i，j]-Allocation[i，j]。

（二）流程图

四、运行结果示例

这里以书上的例子为例，初值如下表：

Allocation

Max

Available

ABC

ABC

ABC

P0

010

753

332

P1

200

322

P2

301

900

P3

211

222

P4

002

433

将Available数列输入，每个资源的数量，线程的数目

输入每个进程的最大资源需求量

输入每个线程的资源量

仅输入一个例子

再输入一个不安全的状态

申请资源量大于最大需求资源量

输入一个申请资源大于资源系统现有可分配资源的情况

成功触发银行家算法的条件

系统显示不安全

以上实例，很好证明了对于银行家算法的实例。

代码附录：

//感谢CSDN论坛的代码资源

#includestdio.h

#includestdlib.h

#includeconio.h

intAvailable[10];//可使用资源向量

intMax[10][10];//最大需求矩阵

intAllocation[10][10]={0};//分配矩阵

intNeed[10][10]={0};//需求矩阵

intWork[10];//工作向量

intFinish[10];//状态标志

intRequest[10][10];//进程申请资源向量

intPause[10