王道操作系统笔记，视频链接：2.4.3 死锁的处理策略—避免死锁

知识总览

1. 死锁的处理：
   • 不允许死锁发生：
     • 静态策略：预防死锁
     • 动态策略：避免死锁（本节内容）
       • 什么是安全序列
       • 什么是系统的不安全状态，与死锁有何联系
       • 如何避免系统进入不安全状态——银行家算法
   • 允许死锁发生：
     • 死锁的检测和解除

什么是安全序列

1. 你是一位成功的银行家，手里掌握着100个亿的资金：
   • 有三个企业想找你贷款，分别是企业B、企业A、企业T，为描述方便，简称BAT。
   • B表示：“大哥，我最多会跟你借70亿…”
   • A表示：“大哥，我最多会跟你借40亿…”
   • T表示：“大哥，我最多会跟你借50亿…”
   • 然而，江湖中有个不成文的规矩：如果你借给企业的钱总数达不到企业提出的最大要求，那么不管我之前给企业借了多少钱，那些钱都拿不回来了。
   • 刚开始，BAT三个企业分别从你这儿借了20、10、30亿。
   • 表：

2. 假设手里还有40亿：
   • 此时B还想借30亿，应该借吗？
     • 如果答应了B，那么手里只剩下10亿
     • 此时如果BAT都提出再借20亿的请求，
     • 那么任何一个企业的需求都得不到满足。
     • 也就是都没有回款，所以不该借。
   • 此时A还想借20亿，应该借吗？
     • 如果答应了A，那么手里还有20亿
     • 可以先把20亿全借给T，等T把钱全部还回来了，
     • 手里就会有50亿，再把这些钱全借给B，
     • B还钱后会有70亿，最后再借给A，这样就会全部回款
     • PS：当然也可以有其他顺序，T$\to$B$\to$A或者A$\to$T$\to$B都可以
3. 所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。
   • 只要能找出一个安全序列，系统就是安全状态。
   • 当然，安全序列可能有多个。
4. 如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。
   • 这就意味着之后可能所有进程都无法顺利的执行下去。
   • 当然，如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态，
     • 比如A先归还了10亿
   • 不过我们在分配资源之前总是要考虑到最坏的情况。
5. • 如果系统处于安全状态，就一定不会发生死锁。
   • 如果系统进入不安全状态，就可能发生死锁。
   • 处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态。
6. 因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求，这也是“银行家算法”的核心思想。

银行家算法

1. 银行家算法是荷兰学者 Dijkstra 为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。后来该算法被用在操作系统中，用于避免死锁。
2. 核心思想：在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。
3. 思考：
   • BAT 的例子中，只有一种类型的资源——钱，
   • 但是在计算机系统中会有多种多样的资源，
   • 应该怎么把算法拓展为多种资源的情况呢？
   • 解决方法：
     • 可以把单维的数字拓展为多维的向量。
4. 例子：系统中有5个进程 P0到P4，3种资源 R0到R2，初始数量为 (10, 5, 7)，
   • 假设某一时刻的情况可表示如下：

5. 根据以上表格：
   • 已知：资源总数 (10, 5, 7)，剩余可用资源 (3, 3, 2)
   • 问题：此时系统是否处于安全状态？
   • 思路：尝试找出一个安全序列。
     • 依次检查剩余可用资源 (3, 3, 2) 是否能满足各进程的需求
       • P0分配不行，P1可以分配，
       • 说明可以优先把资源分配给P1，然后等P1结束会得到更多资源，
       • 此时资源数为(2, 0, 0) + (3, 3, 2) = (5, 3, 2)
     • 可满足P1需求，将 P1 加入安全序列，并更新剩余可用资源值为 (5, 3, 2)
     • 依次检查剩余可用资源 (5, 3, 2) 是否能满足剩余进程的需求
       • 这里以及后续类似步骤，都不包括已加入安全序列的进程
     • 可满足P3需求，将 P3 加入安全序列，并更新剩余可用资源值为 (7, 4, 3)
     • 依次检查剩余可用资源 (7, 4, 3) 是否能满足剩余进程的需求
     • ……
     • 以此类推，共五次循环检查即可将5个进程都加入安全序列中，最终可得一个安全序列。
       • 该算法称为安全性算法。
       • 可以很方便地用代码实现以上流程，每一轮检查都从编号较小的进程开始检查。
       • 实际做题(手算)时可以更快速的得到安全序列：
         • 就是一次性对比多项，
         • 比如第一次(3, 3, 2) 的资源可以满足P1和P3，
         • 就把P1和P3都加入安全序列，然后继续计算
     • 说明此时系统处于安全状态，暂不可能发生死锁

6. 上面的表格是一个找不到安全序列的例子：
   • 已知：资源总数 (10, 5, 7)，剩余可用资源 (3, 3, 2)
   • 经对比发现，(3, 3, 2) 可满足 P1、P3，
   • 说明无论如何，这两个进程的资源需求一定是可以依次被满足的，
   • 因此P1、P3一定可以顺利的执行完，并归还资源。
   • 可把 P1、P3 先加入安全序列。
   • 返还后剩余可用资源总数为(2, 0, 0) + (2, 1, 1) + (3, 3, 2) = (7, 4, 3)
   • 剩下的 P0 需要 (8, 4, 3)，P2 需要 (6, 5, 0)，P4 需要 (4, 3, 4)
   • 任何一个进程都不能被完全满足
   • 于是，无法找到任何一个安全序列，
   • 说明此时系统处于不安全状态，有可能发生死锁。
7. 代码实现方法：
   • 假设系统中有 n 个进程，m 种资源
   • 每个进程在运行前先声明对各种资源的最大需求数，
   • 则可用一个 n*m 的矩阵 (可用二维数组实现) 表示所有进程对各种资源的最大需求数。
   • 不妨称为最大需求矩阵 Max，Max[i, j]=K 表示进程 $P_i$ 最多需要 K 个资源 $R_j$。
   • 同理，系统可以用一个 n*m 的分配矩阵 Allocation 表示对所有进程的资源分配情况。
   • Max - Allocation = Need 矩阵，表示各进程最多还需要多少各类资源。
   • 另外，还要用一个长度为 m 的一维数组 Available 表示当前系统中还有多少可用资源。
   • 某进程 $P_i$ 向系统申请资源，可用一个长度为 m 的一维数组 $Reques{t}_i$ 表示本次申请的各种资源量。

8. 如上表格所示，可用银行家算法预判本次分配是否会导致系统进入不安全状态：
   • ①如果 $Request[i,j]\le Need[i,j]$ (0≤j≤m) 便转向②；否则认为出错。
     • 也就是算出来发现进程所需的资源数已经超过它所宣布的最大值
   • ②如果 $Request[i,j]\le Available[i,j]$ (0≤j≤m)，便转向③；
     • 否则表示尚无足够资源，$P_i$必须等待。
   • ③系统试探着把资源分配给进程$P_i$，并修改相应的数据
     • 并非真的分配，修改数值只是为了做预判
       $Available=Available-Request;$
       $Allocation[i,j]=Allocation[i,j]+Request[i,j];$
       $Need[i,j]=Need[i,j]-Request[i,j]$
   • ④操作系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。
     • 若安全，才正式分配；
     • 否则，恢复相应数据，让进程阻塞等待。

知识回顾与重要考点

1. 数据结构：
   • 长度为 $m$ 的一维数组 $Available$ 表示还有多少可用资源
   • $n\ast m$ 矩阵 $Max$ 表示各进程对资源的最大需求数
   • $n\ast m$ 矩阵 $Allocation$ 表示已经给各进程分配了多少资源
   • $Max-Allocation=Need$ 矩阵表示各进程最多还需要多少资源
   • 用长度为 $m$ 的一位数组 $Request$ 表示进程此次申请的各种资源数
2. 银行家算法步骤：
   • ①检查此次申请是否超过了之前声明的最大需求数
   • ②检查此时系统剩余的可用资源是否还能满足这次请求
   • ③试探着分配，更改各数据结构
   • ④用安全性算法检查此次分配是否会导致系统进入不安全状态
3. 安全性算法步骤：
   • 检查当前的剩余可用资源是否能满足某个进程的最大需求，
   • 如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。
   • 不断重复上述过程，看最终是否能让所有进程都加入安全序列。
   • PS：安全性算法是银行家算法中的核心子步骤，当然安全性算法也可以单独用。
4. 考察银行家算法时：
   • 一般会告诉此时系统当中还有多少可用资源 $Available$
   • 并且告诉 $Max$ 和 $Allocation$ 矩阵
     • 可以根据这两个矩阵计算 $Need$
   • 之后就可以根据前面的流程判断系统安全性如何
5. 注意事项：
   • 先理解算法逻辑再钻研代码逻辑
   • 死锁和不安全状态的关系：（经常在选择题中考察）
     • 系统处于不安全状态未必死锁，但死锁时一定处于不安全状态。
     • 系统处于安全状态一定不会死锁。