Java基础学习（五）-死锁

1、死锁

1.1、什么是死锁？

死锁是指在并发环境下，两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。

此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。

1.2、死锁、饥饿和死循环的区别

三者都是由于某种原因导致进程无法顺利向前推进的现象（故意设计的死循环除外）。

• 死锁

各进程互相等待对方手中的资源，导致出现各个进程都阻塞而无法向前推进的现象。

• 饥饿

由于长期得不到想要的资源，某进程无法向前推进的现象。

比如：在短进程优先算法（SPF）中，若有源源不断的短进程进来，那么会导致长进程一直得不到处理机，从而使长进程处于饥饿状态。

处理机：计算机系统中存储程序和数据，并按照程序规定的步骤执行指令的部件。

• 死循环

某进程执行过程中一直跳不出某个循环的现象。

有时是程序逻辑 BUG 导致的，有时是程序员故意设计的。

现象	区别
死锁	死锁一定是循环等待对方手中的资源导致的，因此如果有死锁现象，那么至少有两个或两个以上的进程同时发生死锁。另外，发生死锁的进程一定处于阻塞状态。
饥饿	可能只有一个进程发生饥饿。发生饥饿的进程极可能是阻塞态（如长期得不到需要的 I/O 设备），也可以能是就绪态（长期得不到处理机）
死循环	可能只有一个进程发生死循环。死循环的进程可以上处理机上运行（可能是运行态），只不过无法想期待的那般顺利推进。死锁和饥饿问题是由于操作系统分配资源的策略不合理导致的，而死循环是由代码逻辑的错误导致的。死锁和饥饿是管理者（操作系统）的问题，而死循环是被管理者的问题。

1.3、死锁产生的必要条件

产生死锁必须同时满足以下四个条件，只要其中一个条件不成立，那么死锁就不会发生。

• 资源互斥条件

只有对必须互斥使用的资源的争抢才会导致死锁（如哲学家的筷子、打印机设备）。像内存、扬声器这种可以同时被多个进程使用的资源是不会导致死锁的（因为进程不用阻塞等待这种资源）。

• 资源不剥夺条件

进程所获得的资源在没有使用完之前，不能由其他进程强行夺走，只能主动释放

• 请求和保持条件

进程已经保持了至少一个资源，但又提出了新的资源请求，而请求的资源此时又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放

• 循环等待条件

存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求

这里需要注意：发生死锁时一定有资源的循环等待对象，但是发生资源循环等待现象时不一定会产生死锁。（循环等待是死锁的必要不充分条件）

如果同类资源数大于 1 ，那么即使有循环等待，也未必发生死锁，但如果系统中每类资源都只有一个，那循环等待就是死锁的充分必要条件了

代入到上面的情景中，如果此时有一个在圈外的六号哲学家也持有一根筷子，同时三号哲学家既在等待 4 号的筷子，也在等待 6 号的筷子，当 6 号放下筷子时， 3 号就可以拿到 6 号的筷子然后向下推进，此时虽然有循环等待，但没有出现死锁。

1.4、什么时候会发生死锁

对不可剥夺资源的不合理分配，可能导致死锁。

• 对系统中不可剥夺的资源的竞争

各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资源（CPU）的竞争是不会引起死锁的。

• 进程推进顺序非法

请求和释放资源的顺序不当，也会导致死锁。

假如并发执行的两个进程 P1 和 P2 分别申请并占有了资源 R1 和 R2 ，之后进程 P1 又申请了资源 R2 ，而进程 P2 又申请了资源 R1 ，此时两者会因为申请的资源被对方占用而阻塞，从而发生死锁。

• 信号量的使用不当也会造成死锁

1.5、死锁的处理策略

• 预防死锁

破坏死锁产生的四个必要条件中的一个或者几个。

• 避免死锁

用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）

• 死锁的检测和解除

允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某些措施解除死锁。

2、死锁的处理策略 – 预防死锁

2.1、破坏互斥条件

可以将只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。

比如：SPOOLing 技术，操作系统可以采用SPOOLing 技术把独占设备在逻辑上改造成共享设备（将打印机改造为共享设备…）

1. 使用SPOOLing 技术之前

在使用SPOOLing 技术之前，如果进程 1 先抢到了打印机的使用权，那么在进程 1 使用完打印机之前，进程 2 申请使用打印机时会被阻塞

2. 使用SPOOLing 技术之后

在使用SPOOLing 技术之后，进程 1 和进程 2 分别将请求发送到输出进程中，然后就可以继续执行自己下面的逻辑了，在它们看来，在将请求输出到输出进程后，自己对打印机资源的使用请求就立即被接收处理了，不需要再阻塞等待。

输出进程接收到两个进程的请求后，会将请求排队，然后依次送达到打印机中进行工作。

该策略的缺点：并不是所有资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性，因此，很多时候都无法破坏互斥条件。

2.2、破坏不剥夺条件

• 方案一：得不到就放手

当某个进程请求新资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。

• 方案二：我找人帮我抢过来

当某个进程需要的资源被其他进程占有时，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级。（比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用）

• 缺点

1. 这种方案实现起来比较复杂
2. 同时释放已获得的资源可能会造成前一阶段工作的失效，**因此这种方法一般只适用于易保存和恢复状态的资源，如 CPU **
3. 反复地申请和释放资源会增加系统开销，降低系统吞吐量。
4. 如果采用方案一，那么意味着只要暂时得不到某个资源，之前获取的那些资源就需要全部放弃，以后再重新申请，如果一直发生这种情况，那么就会导致进程饥饿

2.3、破坏请求和保持条件

可以采用静态分配方法来破坏这个条件，即进程在运行前一次申请完它所需要的全部资源，在它所需要的资源没有得到满足前，不让它投入运行。

一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了。

1. 优点：实现起来简单
2. 缺点

有些资源可能只需要用很短的时间，因此如果在整个进程的运行期间都保持着所有资源，那么就会造成严重的资源浪费，资源利用率极低。另外，该策略也可能导致某些进程饥饿。

2.4、破坏循环等待条件

可以采用顺序资源分配法来破坏这个条件，首先给系统中的资源编号，规定每个进程必须按编号递增的顺序来请求资源，同类资源（编号相同的资源）需要一次性申请完。

• 原理分析

一个进程只有已占有小编号资源时，可有资格申请更大编号的资源。按照这个规则，已持有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象。

• 缺点

1. 不方便增加新的设备，因为可能需要重新分配所有的编号

2. 进程实际使用资源的而顺序可能和编号递增的顺序不一致，会导致资源浪费

比如说一个进程需要先用到打印机（7号），然后用到扫描仪（5号），但由于打印机编号大于扫描仪，所以该进程只能先申请扫描仪，然后申请打印机，这也就造成了资源浪费。

3. 必须按照规定次序申请资源，用户编程麻烦

3、死锁的处理策略 – 避免死锁

3.1、什么是安全序列？

• 所谓安全序列，就是指系统如果按照这种序列分配资源，则每个进程都能顺利完成。

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

• 如果分配了资源后，系统中再也找不到任何一个安全序列，此时系统就进入了一个不安全状态。

这意味着之后可能所有进程都无法顺利地执行下去。当然，如果此时有进程提前归还了一些资源，那系统也有可能重新回到安全状态，但我们在分配资源之前总是要考虑到最坏的情况。

• 如果系统处于安全状态，就一定不会发生死锁；如果系统进入不安全状态，就可能发生死锁。

处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态。

• 因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源的分配请求，这也是银行家算法的核心思想。

3.2、求解一个安全序列

• 求解一个安全序列的过程

1. 假设现在有 5 个进程，其最大需求、已分配需求和最多还需要资源情况如下表，计算机中存在三种资源 R0 - R2 ，初始数量为 (10,5,7)

2. 根据初始资源和可分配资源计算出计算机当前剩余可用资源为 (10,5,7) - (7,2,5) = (3,3,2)

其中 (7,2,5) 为计算机已经为上面 5 个进程分配的资源

3. 依次检查剩余可用资源是否能满足各进程的需求

查看上表，发现剩余可用资源无法满足 P0 需求，但可以满足 P1 需求，此时将 P1 加入安全序列，在 P1 结束后，P1 释放自己的资源，此时更新剩余可用资源为 (5,3,2)，同时将 P1 从进程表中抹去

4. 依次检查剩余可用资源(5,3,2)是否能满足剩余进程（不包括已加入到安全序列的进程）的需求

此时发现剩余可用资源无法满足进程 P0 和 P2 的需求，但可以满足进程 P3 的需求，所以将资源分配给 P3 ，更新剩余可用资源为 (7,4,3) ，将 P3 加入到安全序列，同时在表中抹去 P3 ，此时安全序列为 {P1,P3}

5. 以此类推，共五轮循环检查即可将 5 个进程都加入到安全序列中，最后得到一个安全序列。

这种算法称为安全性算法，可以很方便地用代码实现以上流程，每一轮检查都从编号较小的进程开始检查，实际做题时可以更快速地得到序列。

3.3、银行家算法

• 假设系统中存在 n 个进程，m 种资源

每个进程在运行前可以声明自己对各种资源的最大需求数，可以用一个 n * m 的矩阵（用二维数组实现）表示所有进程对各种资源的最大需求数，称为最大需求矩阵 Max。

Max[i,j] = k 表示进程 Pi 最多需要 K 个 Rj 资源。

• 系统用一个 n * m 的分配矩阵 Allocation 表示对所有进程的资源分配情况

Allocation[i,j] = k 表示系统已经在 Pi 个进程分配了 K 个 Rj 资源

• Max - Allocation 可以得到一个 n * m 的 Need 矩阵，用一个长度为 m 的一维数组 Available 来表示当前系统中还有多少可用资源；

Need[i,j] = need 表示进程 Pi 还需要 need 个 Rj 资源

• 某进程 Pi 向系统申请资源时，可以用一个长度为 m 的一维数组 Request 表示本次申请的各种资源量

• 银行家算法可以用来预判本次分配会不会导致系统进入不安全状态

1. 如果 Request_i[j] <= Need[i,j] (0 <= j <= m)，便转向 2 ；否则认为出错

如果 Pi 进程要求的资源没有超过它最多需要的资源数量的话，那么可以继续进行，否则认为出错（因为它所需要的资源超过它所宣布的最大值）

2. 如果 Request_i[j] <= Available[i,j] ，转向 3 ；否则表示尚无足够资源，进程 Pi 必须等待
3. 系统试探着将资源分配给进程 Pi ，并修改相应的数据（并非真的分配，而是修改数值进行预判）

Available = Available - Request;

Allocation[i,j] = Allocation[i,j] + Request_i[j]

Need[i,j] = Need[i,j] - Request_i[j]

4. 操作系统执行安全性算法，检查本次资源分配后，系统是否处于安全状态，如果安全，才正式分配；否则，恢复相应数据并让进程阻塞等待

• 综上，银行家算法步骤可以总结为以下几个步骤

1. 检查此次申请是否超过之前声明的最大需求数
2. 检查此时系统剩余可用资源是否还能满足这次请求
3. 试探着分配，更改各数据结构
4. 用安全性算法检查此次分配是否会导致系统进入不安全状态

安全性算法步骤：检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入到安全序列中，并把该进程持有的资源全部回收，不断重复上述过程，看最终能否让所有进程都加入到安全序列。

4、死锁的处理策略 – 检测和解除

如果系统中既不采取预防死锁的措施，也不采取避免死锁的措施，系统就很可能发生死锁。在这种情况下，系统应当提供两个算法：

1. 死锁检测算法

用于检测系统状态，以确定系统中是否发生死锁

2. 死锁解除算法

当认定系统中已经发生了死锁，利用该算法可将系统从死锁状态中解脱出来。

4.1、死锁的检测

1. 用某种数据结构来保存资源的请求和分配信息；

2. 提供一种算法，利用上述信息来检测系统是否进入了死锁状态。

• 资源节点和进程节点
• 请求边和分配边

1. 从进程指向资源的有向边称为请求边，n 条请求边代表该进程向系统请求 n 个该类型资源
2. 从资源指向进程的有向边称为分配边，n 条分配边代表这种资源已经分配了 n 个给该进程

在下图中，我们可以得到的信息是：P1 已经的已获得两个 R1 资源，正在请求一个 R2 资源；而 P2 获得了一个 R2 资源和一个 R1 资源，此时正在请求一个 R1 资源

• 如果系统中剩余的可用资源数足够满足进程的需求，那么这个进程暂时不会阻塞，可以顺利地执行下去；

• 如果这个资源执行结束了将资源归还系统，就可以使某些正在被等待的进程被激活，并顺利的执行下去。

在上面的图中，如果将剩余的资源分配 P1 ，在 P1 结束并释放资源后， P2 就可以拿到 P1 释放的资源并继续进行下去

相应的，这些被激活的进程（P2）执行完之后又会归还一些资源，这样可能又会激活另外一些阻塞的进程…

• 如果按照上述过程分析，最终可以消除所有边，我们就称这个图是可完全简化的，此时一定没有发生死锁（相当于可以找到一个安全序列）
• 如果最终不能消除所有边，那么此时就是发生了死锁

1. 分配给 P3 一个 R2 资源，P3 执行完毕后归还资源，此时还剩下一个 R2 资源和 0 个 R1 资源
2. 此时 P2 请求一个 R1 资源，而 P1 请求两个 R2 资源，由于此时剩余的资源无法满足剩下进程的需求，所以进程 P1 和 P2 均阻塞，这样就发生了死锁

• 最终还连着边的那些进程就是处于死锁状态的进程。

在上面的例子中，最终还连着边的 P1 和 P2 进程处于死锁状态

4.2、死锁的解除

一旦检测出死锁的发生，就应该立即解除死锁，但不是系统中的所有进程都是死锁状态，只有那些用死锁检测算法化简资源分配图后，还连着边的那些进程才是死锁进程。

解除死锁主要有以下几种方法

• 资源剥夺法

挂起（暂时放到外存上）某些死锁进程，并抢夺它的资源，将这些资源分配给其他的死锁线程。但是应防止被挂起的线程长时间得不到资源而饥饿。

在上面出现的图中，我们可以通过剥夺一些死锁进程（比如说 P1 或者 P2 ）的资源来解除死锁

• 撤销进程法（或称终止进程法）

强制撤销部分、甚至是全部死锁进程，并剥夺这些进程的资源。

这种方式的优点是实现简单，但付出的代价可能很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可能功亏一篑，以后还得从头再来。

• 进程回退法

让一个或多个进程回退到足以避免死锁的地步，这就要求系统要记录进程的历史信息，设置还原点。

4.3、选择对哪个进程下手以解除死锁

我们可以综合以下几个因素来考虑要对哪个进程下手，从而解除死锁

• 进程优先级，选择优先级较低的进程
• 进程已执行的时间，选择已执行时间较短的进程
• 进程的完成度，还需要多久时间才能完成

对完成度较低的进程下手，然后将资源分配给那些快要执行完成的进程，以实现资源的快速释放

• 进程当前占用资源的情况

如果一个进程当前占用的资源十分多，那么对这个进程下手就可以释放更多的资源，让更多的进程继续进行工作

• 进程是交互式的还是批处理式的

如果进程是交互式的，那么将这一类进程停掉可能会影响用户体验；如果是批处理式的进程，那么用户对这个进程的结束可能不会得到及时反馈，所以我们可以优先结束那些批处理的进程。