银行家算法

什么是银行家算法

银行家算法是一种用来避免操作系统死锁出现的有效算法。

死锁

死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。

死锁产生的四个必要条件：

1） 互斥条件：在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。 2） 请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。 3） 不可剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。 4） 循环等待条件：指在发生死锁时，必然存在一个进程—资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。

安全序列：

是指一个进程序列{P1，…，Pn}是安全的，即对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。

安全状态：

如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。

不安全状态：

不存在一个安全序列。不安全状态不一定导致死锁。

银行家算法实现的数据结构：

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]

两个向量：

1）工作向量Work：表示系统可提供给进程继续运行所需的各类资源数目，安全算法开始时，Work:=Available。 2）Finish[]：表示系统是否有足够的资源分配给进程,使之运行完成。开始时先令Finish[i]:=false，当有足够资源分配给进程时，再令Finish[i]:=true。

银行家算法：

设Request(i)是进程Pi的请求向量，如果Request(i)[j]=k，表示进程Pi需要K个R(j)类型的资源。当Pi发现资源请求后系统将进行下列步骤：

1. 如果Request(i)[j] <= Need[i,j],边转向步骤2),否则认为出错，因为它所请求的资源数已超过它所宣布的最大值。
2. 如果Request(i)[j] <= Available[i,j]，便转向步骤3)，否则，表示尚无足够资源，Pi需等待。
3. 系统试探着把资源分配给进程Pi，并需要修改下面数据结构中的数值； 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. 系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。