os-process-dead-lock

概念

死锁的定义

在开发环境下，各进程因竞争资源而造成的一种相互等待对方手里的资源，导致这些进程均阻塞，若没有外力干涉，这些进程都无法继续前进。

🚨死锁：互相等待对方手里的资源，导致各进程都堵塞，无法继续前进的现象。

🍱饥饿由于长期得不到资源，某进程一直得不到处理机的现象。

💩死（屎）循环：某一进程执行过程中一直跳不出某个循环的现象。

死锁产生的充分条件

1. 互斥条件：只有互斥资源的争论才可能导致死锁。

2. 不剥夺条件：进程中获得资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。

3. 请求和保持条件：进程已经占用了至少一个资源，同时又提出了新的资源请求，而所请求的资源被其他进程所占有，此时请求被阻塞，但是该进程仍然保持已有的资源不放。

4. 循环等待条件：存在一种进程循环等待资源的现象

🐰发生死锁时一定有循环等待，但发生循环等待未必会死锁🔒。

如果系统中还有其他同类型资源，则不会发生死锁；

如果系统中每种资源只有一个，则将会发生死锁。

死锁的预防

预防死锁的发生只需要破坏四个必要条件之一即可。

破坏互斥条件

把临界区资源变成共享资源，例如使用 SPOOLing 技术使得设备可以逻辑上共享，但是一般不常用。

SPOOLING （即外部设备联机并行操作），即Simultaneous Peripheral Operations On-Line的缩写，它是关于慢速字符设备如何与计算机主机交换信息一种技术，通常称为"假脱机技术"。

破坏剥夺条件

• 当某个进程请求新的资源得不到时，立刻释放其已有资源，以待后面再次申请。
• 为进程设置不同的优先级，当某个进程需要的资源被其他进程占有时，可以用操作系统写作将想要的资源强行剥夺。

缺点

• 实现起来比较复杂；
• 这种方式会造成前一阶段工作的失效，因此仅适用于不易保存和恢复的资源，例如 CPU;
• 反复申请和释放资源会造成较大的系统消耗。
• 若采用方案以，可能导致饥饿（某个进程一直被迫放弃已有的资源）

破坏请求和保持条件

采用静态分配方法。在运行前一次性申请所需要的全部资源，在未获得全部资源前进程不投入运行，一道投入运行，这些资源一直归此进程所有。

缺点

• 对于使用时间很短的资源会造成资源浪费，资源利用率低
• 有可能导致某些进程饥饿。

破坏循环等待条件

采用顺序资源分配法，首先给系统中的资源编号。规定每个进程必须按编号递增的顺序请求资源，同类资源（即编号相同的资源）一次申请完成。

缺点

• 不方便增加新的系统资源，有可能需要全部重新分配序号。
• 进程实际使用资源的顺序可能序号不一致，会造成资源的浪费。
• 必须依次申请资源，编程麻烦。

死锁避免

安全序列、不安全状态、死锁的联系

安全序列

如果系统按照这种序列分配资源，则每个进程都能顺利完成。

安全状态

只要能找出一个安全序列，系统就是安全状态，安全序列可能有多个。

不安全状态

如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不不安全状态，这就意味者之后可能所以有进程都无法顺利的执行下去。如果有进程提前归还了资源，系统也有可能重新回到安全状态。

安全状态与死锁的关系

• 系统如果处于安全状态，则一定不会发生死锁。
• 系统如果处于不安全状态，则可能会发生死锁。
• 因此，可以通过提前判断是否会进入不安全状态，来决定是否答应分配请求

银行家算法

假设系统中有 n 个进程，m 种资源。

每个进程在运行前事先声明各个资源的最大需求数，则可用一个 n*m 的矩阵表示所有进程对各种资源的重大需求数，称之为最大需求矩阵 Max,,表示进程 P_i,最多需要 K 个资源 R_j。

同理，系统可以用一个 n*m 的分配矩阵 Allocation 表示对所有进程的资源分配情况。Max-Allocation = Need 举证，表示各进程还需要多少资源。

另外，用一个长度为 m 的一维数组Available 表示当前系统中还有多少可用资源。

用一个长度为 m 的 一维数组 Request_i ，表示本次某进程 P_i 本次申请的各种资源。

算法步骤

1. 若 Request_i[j] < Need[i,j]，继续下一步，否则出错。(请求资源超出了最大需求)；

2. 若 Request_i[j] < Available[i,j]，继续下一步，否则表示尚无可用资源，P_i 等待；

3. 系统尝试将资源分配给 P_i，并修改相应数据:

   $$Available = Available - Request; \\ Allocation[i,j] = Allocation[i,j] + Request_i[j] \\ Need[i,j] = Need[i,j] - Request_i[j] \\$$

4. 系统执行安全算法，判断此次分配后系统是否处于安全状态，若是，则正式分配资源给 P_i，否则此次分配作废，让 P_i 等待；

   

例题

进程	最大需求	已分配	可用
P0	10	5	3
P1	4	2
P2	9	2

Max = \left[ \matrix{ 10 \ 4 \ 5 \ } \right], Allocation = \left[ \matrix{ 5 \ 2 \ 2 \ } \right], Available = \left[ \matrix{ 3 } \right], \ Need = Max - Allocation = \left[ \matrix{ 5 \ 2 \ 7 \ } \right]

接下来，将 Available 与 Need 各行进行比较，找到 Need 中比 Available 小的一行，将该进程加入安全序列，释放该进程的资源，得到新的矩阵 Available 。

对比之后得到第二行（记作 P₁）,释放 P₁，更新可用资源 Available = [5]，因为之前分配了 2 个资源（Allocation），然后继续比较，找到 P₀，继续更新 Available = [10]，继续对比，释放掉 P₃，从而得到安全序列： P₁ P₀ P₂。

死锁的检测和解除

为了能对系统是否发生了死锁进行检测，必须：

1. 用某种数据结构来保存资源的请求和分配信息；
2. 提供一种算法，利用上述信息来检测系统是否已进入死锁状态；

资源分配图

结构

两种结点

• 进程结点：对应一个进程
• 资源结点：对应一类资源

两种边

• 进程结点->资源结点：进程对资源的申请（每条代表一个）

• 资源节点->进程结点：已经为进程分配了资源（每条代表一个）

环路

• 若出现环路，意味着满足了循环等待条件，可能存在死锁。
• 若不存在环路，破坏了循环等待条件，必定不存在死锁。

死锁定理

在资源分配图中，找到既不阻塞也不是孤点的进程 P_i，消去他所有的请求边和分配边；

再找到下一个可以小区所有请求和分配的进程。

若能消去途中所有边，则称该图是可完全简化的。

随便扒拉的一道题来分析一下

对于 R1: 资源已经被使用了一个，那么再来请求的 P1 就自然被挂起，我们给它先拉黑（阻塞）

对于 R2: 已经有两个资源被分配出去，那么 P3 对于 P2 的请求就开摆，也挂起，阻塞。

对于 R3：分配了一个出去给 P2，P3 请求，不过已经在 R2 挂起了.

对于 R4：分配了一个给 P3,面对 P2 的请求，P2 只能挂起等待。

结点全挂起，漂亮的死锁🔒！艹，再换一个例子

一样的分析方法，就不赘述了：

死锁定理：系统会发生死锁的条件是当且仅当系统状态的资源分配图是不可完全简化的。

死锁的解除

在化简资源分配图后，还有边连接的进程就是死锁进程 ，对于死锁的进程，需要解除死锁：

• 资源剥夺法：挂起某些死锁进程（暂存到外存上），抢占其资源并分配给其他死锁进程。需要注意防止被挂起进程产生饥饿；
• 撤销进程法（终止进程法）：强制撤销部分甚至全部死锁进程并释放其资源。优点是实现简单，缺点是导致进程之前的努力全部莫得了（没有了）。
• **进程回退法：**让一个或多个进程回退到可以避免死锁的地步，需要系统记录进程的历史信息并设置还原点。