【操作系统】银行家算法

上次介绍了死锁的相关概念，以及各种解决办法。今天讲的是死锁避免里面的银行家算法。请多多指教~

一、算法的背景

    算法由迪杰斯特拉在1965年提出。

    在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。

二、算法的思想

    银行家算法让进程动态地申请资源，系统在每次实施资源分配之前，先计算资源分配的安全性，即分配完是否会进入不安全状态。若此次资源分配安全，便将资源分配给进程，否则不分配资源，让进程等待。

三、安全状态和不安全状态

    安全状态就是按照某种资源分配的顺序，系统所有的进程能够顺利的执行完毕，完成一些功能。

    不安全状态就是系统在某一个时刻找不到一个顺利执行下去的安全序列，着这种状态就是不安全状态。

四、算法理解

    书面理解：操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。

    通俗理解：系统有多个种资源并且每一种资源的数目有限，有多个想要申请这些资源的进程，僧多粥少，所以要好好安排分配的顺序，不然就会导致不安全状态甚至死锁。那么如何解决呢？

    首先搞出三个矩阵，一个Max各个进程需要各个资源的最大数目，Available系统有的各个资源的数目，然后就是Allocation各个进程已经得到的资源数目，然后用 

    Max - Allocation = Need,

    就可以得到各个进程仍然需要的各个资源数目。

    然后每次系统要分配资源的时候，考察两个量：1、进程请求的资源和已经分配给他的资源之和是否超过了他的Max最大需求；2、系统的资源剩下数目能否满足这次请求。

    如果请求没有超标并且系统足够满足这次请求，就分配。然后取回这个进程占有的所有资源。

    就像万恶的资本家~

五、经典的题目类型

    1）判断系统某个状态时候处于安全状态

    2）找出系统的一个安全序列

    3）判断按照某种分配后是否会进入死锁状态

六、例子讲解

    （画图太麻烦了...图片来自与维基百科）

1.首先给出在某个状态下系统的资源情况，是三个矩阵，最大需求矩阵Max,已经分配资源矩阵Allocation,系统可以分配的资源矩阵Available;

2.最大需求减去已经分配的资源，得到仍然需要的资源矩阵：

3.这个时候观察四个进程的需求情况和系统能够分配的资源情况，发现P2对于ABCD四种资源的需求都小于系统的资源数目，分配给P2不会进入不安全状态，所以满足P2的请求。然后回收P2资源，注意这里回收的是刚刚分配出去给P2的加上P2已经有的资源。得到下面的矩阵：

4.接着发现P3的需求为 0 0 0 2，小于系统的已有资源 2  9 5 2，所以分配给P3然后回收；

5.同理，接下来分配给P4，再分配给P1，就可以完成系统的任务。或者先分配给P1也可以。可见安全序列往往不唯一。

喜欢就关注吧~