银行家算法实验报告.doc

银行家算法实验报告
设计目的
银行家算法是是最具有代表性的避免死锁的算法，由于该算法能用于银行系统现金贷款而得名。该算法能够进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念。
设计要求
根据银行家算法的基本思想，编写和调试一个动态分配的模拟程序，并能够有效的防止和避免死锁的发生。
设计思想
　银行家算法：
　　我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。
银行家算法中的数据结构
1）可利用资源向量Available
是个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果Available[j]=K，则表示系统中现有Rj类资源K个。
　2）最大需求矩阵Max
　　这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。
3）分配矩阵Allocation
　　这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的 数目为K。
4）需求矩阵Need
　　这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。
Need[i,j]=Max[i,j]-Allocation[i,j]
银行家算法
设进程P[i]提出请求Request(i) [j]，如果Request(i)[j]=k,表示进程P[i]需要K个R(j)类型的资源。当P[i]发出请求后，系统按下述步骤进行判断：
(1)如果Request (i) [j]<= Need[i][j]，则转(2)；否则，出错。
(2)如果Request (i) [j]<= Available[j]，则转(3)；否则，出错。
　　 (3)系统试探分配资源，修改相关数据：
　　 Available [j]= Available [j]-Request (i) [j];
　　Allocation[i][j]= Allocation[i][j]+Request (i) [j];
　　Need[i][j]= Need[i][j]-Request (i) [j];
(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。
3、安全算法
1)设置两个工作向量Work:=Available;Finish
　　(2)从进程集合中找到一个满足下述条件的进程，
　　Finish[i]==false;
　　Need[i][]j<=Work[j];
　　如找到，执行(3)；否则，执行(4)
　　(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。
　　Work[j]= Work[j]+Allocation[i,j];
　　Finish[i]=true;
　 Go to 2
(4)如所有的进程Finish[i]= true，则表示安全；否则系统不安全。
四、流程图
初始化函数input()开始
输入资源种类数
输入进程的数量
输入可利用的资源数
输入最大需求Max
所需要的Need<0
Error;
初始化函数input（）结束，银行家函数Resquest()
提出请求Request[i]
Error;
Request[i]<=Need[i]
RequestT[i]<=Available[[i]
Error;
分配错误！
IsSafe();

分配成功！
Available[i]-=Request[i]；Allocation[i]-=Request[i];
Need[i]+=Request[i]；