关于银行家算法
分类: 电脑/网络 >> 操作系统/系统故障
问题描述:
谁可以给我讲讲银行家算法到底是怎么回事呀？！拜托了！
解析:
银行家算法=-- -
1. 安全状态: 在某时刻系统中所有进程可以排列一个安全序列:{P1,P2,`````Pn},刚称此时,系统是安全的.
所谓安全序列{P1,P2,`````Pn}是指对于P2,都有它所需要剩余资源数量不大于系统掌握的剩余的空间资源与所有Pi(j<i)所占的资源之和.
2.不安全状态可能产生死锁.
目前状态 最大需求 尚需
P1 3 9 6
P2 5 10 5
P3 2 4 2
在每一次进程中申请的资源,判定一下,若实际分配的话,之后系统是否安全.
3.银行家算法的思路:
1),进程一开始向系统提出最大需求量.
2),进程每次提出新的需求(分期贷款)都统计是否超出它事先提出的最大需求量.
3),若正常,则判断该进程所需剩余剩余量(包括本次申请)是否超出系统所掌握的
剩余资源量,若不超出,则分配,否则等待.
4.银行家算法的数据结构.
1),系统剩余资源量A[n],其中A[n]表示第I类资源剩余量.
2),各进程最大需求量,B[m][n],其中B[j][i]表示进程j对i
类资源最大需求.
3),已分配资源量C[m][n],其中C[j][i]表示系统j程已得到的第i资源的数量.
4),剩余需求量.D[m][n],其中D[j][i]对第i资源尚需的数目.
5.银行家算法流程:当某时刻,某进程时,提出新的资源申请,系统作以下操作:
1),判定E[n]是否大于D[j][n],若大于,表示出错.
2),判定E[n]是否大于系统剩余量A[n],若大于,则该进程等待.
3),若以上两步没有问题,尝试分配,即各变量作调整.
4),按照安全性推测算法,判断,分配过后,系统是否安全,若安全,则实际分配,否则,撤消分配,让进程等待.
6."安全性检测"算法
1),先定义两个变量,用来表示推算过程的数据.
F[n]=A[n],表示推算过程中,系统中剩余资源量的变化.
J[n]=False表示推算过程中各进程是否假设"已完成"
2),流程:
在"剩余"的进程中(在推算)过程中,一些进程假设已完成,查找D[j][n]<=F[n]的进程,找到后令J[j]=True
(假设该进程完成),F[n]+D[j][n](该进程所占资源释放),如此循环执行.
若最后,所有的F[n]=True(在推算过程中,所有进程均可以完成),则表示(分配过后)系统是安全的,否则系统是不安全的.
银行家算法
银行家算法是一种预防死锁的算法。具体算法步骤可以参考百度百科： 银行家算法 例子 ：某系统有A、B、C、D , 4类资源共5个进程（P0、P1、P2、P3、P4）共享，各进程对资源的需求和分配情况如下表所示。 输入进程的数目:5 输入资源的种类:4 输入每个进程最多所需的各类资源数: P0 : 0 0 1 2 P1 : 1 7 5 0 P2 : 2 3 5 6 P3 : 0 6 5 2 P4 : 0 6 5 6 输入每个进程已经分配的各类资源数: P0 : 0 0 1 2 P1 : 1 0 0 0 P2 : 1 3 5 4 P3 : 0 6 3 2 P4 : 0 0 1 4 请输入各个资源现有的数目: 1 5 2 0 当前系统安全! 系统安全序列是: P0->P2->P1->P3->P4 输入要申请资源的进程号(0-4)：1 输入进程所请求的各资源的数量:0 4 2 0 系统安全! 系统安全序列是: P0->P2->P1->P3->P4 同意分配请求! 系统可用的资源数为 : 1 1 0 0 各进程还需要的资源量: 进程 P0 : 0 0 0 0 进程 P1 : 0 3 3 0 进程 P2 : 1 0 0 2 进程 P3 : 0 0 2 0 进程 P4 : 0 6 4 2 各进程已经得到的资源量: 进程 P0 : 0 0 1 2 进程 P1 : 1 4 2 0 进程 P2 : 1 3 5 4 进程 P3 : 0 6 3 2 进程 P4 : 0 0 1 4 是否再次请求分配？是请按Y/y，否请按N/n: N
浅析银行家算法
作为避免死锁的一种算法，银行家算法可以说是最为出名的了。这个名字的来源是因为该算法起初是为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。在操作系统中也可以用它来实现避免死锁。
首先我们要了解银行家算法的本质也即避免死锁的原理。避免死锁作为一种事先预防死锁的策略，原理是在为各个进程分配资源的过程中不允许系统进去不安全状态，以此来避免死锁的发生。所谓安全状态，是指系统能按某种进程推进顺序为每个进程分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺利地完成。此时称该进程推进序列为安全序列，如果无法找到这样一个安全序列，则称系统处于不安全状态。
银行家算法中的数据结构。为了实现银行家算法，在系统中必须设置这样四个数据结构，分别用来描述系统中可利用的资源，所有进程对资源的最大需求，系统中的资源分配以及所有进程还需要多少资源的情况。
(1)可利用资源向量Available。这是一个含有m个元表的数组,其中的每一个元素代表一类可利用的资源数目。其数值随该类资源的分配和回收而动态地改变。如果 Available=K,则表示系统中现有Rj类资源K个。
(2)最大需求矩阵Max。这是一个nxm的矩阵,它定义了系统中n个进程中的每个进程对m类资源的最大需求。如果Max[i,j]=K,则表示进程i需要Rj类资源的最大数目为K。
(3)分配矩阵 Allocation。这也是一个nxm的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K,表示进程i当前已分得Rj类资源的数目为K。
(4)需求矩阵Need。这也是一个nxm的矩阵,用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个才能完成。
当一个进程发出请求资源的请求后，如果它所请求的资源大于目前系统可利用资源则不予分配。如果小于可利用资源，则系统试探着把资源分配给该进程，并修改分配之后的资源数值。接着系统执行安全算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给该进程，以完成本次分配。否则，将本次的试探分配作废，恢复原来的资源分配状态，让该进程等待。
