银行家算法笔记

死锁

在了解银行家算法前，有必要了解一下死锁。因为银行家算法是用于避免死锁的。

什么是死锁？

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

死锁的四个必要条件

• 互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求该资源，则请求者只能等待，直至占有该资源的进程释放。
• 请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。
• 不剥夺资源：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
• 环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P₀，P₁，P₂，...，P_n}中的 P₀ 正在等待一个 P₁ 占用的资源；P₁ 正在等待 P₂ 占用的资源，......，P_n 正在等待已被 P₀ 占用的资源。

银行家算法背景简介

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

系统安全状态和不安全状态

所谓安全状态，是指系统能按某种进程顺序（P₁，P₂，…，P_n）（称<P₁，P₂，…，P_n>序列为安全序列），来为每个进程 P_i 分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。
虽然并非所有的不安全状态都必然会转为死锁状态，但当系统进入不安全状态后，便有可能进而进入死锁状态。反之，只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的状态的实质在于：系统在进行资源分配是，如何使系统不进入不安全状态。

银行家算法的数据结构

1. 可利用资源向量 Available。这是一个含有 m 个 元素的数组，其中每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源分配和回收动态地改变。如果 Available[j] = K,则表示系统中现有 R_j 类资源 K 个。
2. 最大需求矩阵 Max。这是一个 n X m 的矩阵，它定义了系统中 n 个进程中的每一个进程对 m 类资源的最大需求。如果 Max[i,j] = K ,则表示进程 i 需要 R_j 类资源的最大数目为 K。
3. 分配矩阵 Allocation。这也是一个 n X m 的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源树。如果 Allocation[i,j] = K,则表示进程 i 当前已分得 R_j 类资源的数目为 K。
4. 需求矩阵 Need。这也是一个 n X m 的矩阵，用以表示每一个进程尚需的各类资源数。如果 Need[i,j] = K，则表示进程 i 还需要 R_j 类资源 K 个，方能完成任务。

上述的三个矩阵间存在下列关系：
Need[i,j] = Max[i,j] - Allocation[i,j]

银行家算法

设 Request_i 是进程 P_i 的请求向量，如果 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）；否则，表示尚无足够资源，P_i 须等待。
（3）系统试探着把资源分配给进程 P_i，并修改下面数据结构中的数值。
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）系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程 P_i，以完成本次分配。否则，将本次的试探分配作废，恢复原来的资源分配，让进程等待。

安全性算法

系统所执行的安全性算法可描述如下：
（1）设置两个向量：
a.工作向量 Work，它表示系统可提供给进程继续运行所需的各类资源项目，它含有 m 个元素，在执行安全性算法开始时，Work = Available。
b.Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做 Finish[i] = false;当有足够资源分配给进程时，再令 Finish[i] = true。
（2）从进程集合中找到一个能满足下述条件的进程：
a.Finish[i] = false。
b.Need[i,j] ≤ Work[j]；若找到，执行步骤（3），否则，执行步骤（4）
（3）当进程 P_i获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
Work[j] = Work[j] + Allocation[i,j]；
Finish[i] = true;
go to step2；
（4）如果所有进程的 Finish[i] = true 都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

最后说两句

这篇文章的出现是因为面试的时候忘了，说不出个所以然来，所以回来翻书，抄了一遍，理解更加深入了。弱鸡的自己还需更加努力，打牢基础，慢慢拓展。

参考资料

[1] 百度百科
[2] 汤小红等编著.计算机操作系统[M]. 西安 : 西安电子科技大学出版社 , 2007.5.