银行家算法实验报告
实验类型: 验证性实验
学 时： 4
适用对象: 信息与计算科学专业
一、实验目的 （黑体，小4号字）
熟悉银行家算法，理解系统产生死锁的原因及避免死锁的方法,加深记意。
二、实验要求 （黑体，小4号字）
用高级语言编写和调试一个描述银行家算法的程序。
设计五个进程{P0，P1，P2，P3，P4}共享三类资源{A，B，C}的系统，{A，B，C}的资源数量分别为10，5，7。进程可动态地申请资源和释放资源，系统按各进程的申请动态地分配资源。要求程序具有显示和打印各进程的某一时刻的资源分配表和安全序列；显示和打印各进程依次要求申请的资源号以及为某进程分配资源后的有关资源数据。
三、实验原理（黑体，小4号字）
利用银行家算法避免死锁
1、银行家算法中的数据结构
（1）可利用资源向量Available
（2）最大需求规阵Max
（3）分配矩阵Allocation
（4）需求矩阵Need
2、银行家算法
（1）如果Requesti＜或=Need,则转向步骤2；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。
（2）如果Request＜或=Available,则转向步骤（3）；否则，表示系统中尚无足够的资源，P1必须等待。
（3）系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值：
Available:=Available-Requesti;
Allocation:=Allocationi+Request;
Needi:=Needi-request;
(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。
3、安全性算法
系统所执行的安全性算法可描述如下：
（1）设置两个向量
①工作向量Work。它表示系统可提供进程继续运行所需要的各类资源数目，它含有m个元素，执行安全算法开始时，Work:=Allocation;
②Finish。它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finish[i]:=false;当有足够资源分配给进程时，令Finish[i]:=true。
（2）从进程集合中找到一个能满足下述条件的进程：
①Finish[i]:=false
②Need</=Work
如找到，执行步骤（3）；否则，执行步骤（4）。
（3）当进程P获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
Work：=Work+Allocation;
Finish[i]：=true;
Go to step 2;
（4）如果所有进程的Finish[i]=true,则表示系统处于安全状态；否则，系统处于不安全状态。
4、银行家算法之例
假设有五个进程{P0,P1,P2,P3,P4}和三种类型的资源{A，B，C}，每一种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图1所示。
图1
（1）T0时刻的安全性
利用安全性算法对T0时刻的资源分配情况进行分析，可得下表所示的T0时刻的安全性分析，从中得知，T0时刻存在着一个安全序列{P1，P3，P4，P2，P0}，故系统是安全的，如图2所示。
图2
（2） P1请求资源
P1发出请求向量Request(1,0,2),系统按银行家 算法进行检查：
(1)Request1(1,0,2)≤Need(1,2,2)
(2)Request1(1,0,2)≤Available(3,3,2)
(3)系统先假定可为P1分配资源，并修改Aailable，Allocation1和Need1向量，由此形成的资源变化情况如图1中的圆括号所示。
（4）我们再利用安全性检查此时系统是否安全。
由所进行的安全性检查得知，可以找到一个安全序列{P1，P3，P4，P2，P0}。因此，系统是安全的，可以立即将P1所申请的资源分配给它。
（3）P4请求资源
P4发出请求向量Request(3,3,0),系统按银行家算法进行检查：
(1)Request4(3,3,0)≤Need4(4,3,1)。
(2)Request4(3,3,0)>Available(2,3,0)，让P4等待。
（4） P0请求资源
P0发出请求向量Request0(0,2,0),系统按银行家算法进行检查：
（1）Request0(o,2,0)<或=Need0(7,4,3));
（5）进行安全性检查
可用资源Available{2,1,0}已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。
如果在银行家算法中，把P0发出的请求向量改为Request(0,1,0),系统是否能将资源分配给它，请读者考虑
四、实验所需仪器、设备、材料
PC机
五、实验预习要求、实验条件、方法及步骤
1）熟练掌握死锁相关的基本概念。
2）熟练掌握避免死锁的有关算法。
3）熟练掌握银行家算法所需的数据结构和算法流程；
4）熟练掌握某一门编程语言，如C、C＋＋或者Dephi等。479