概念

定义

在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象

产生死锁的条件

1）互斥条件：争抢必须互斥使用的资源

2）不剥夺条件：进程占据互斥资源后只能主动释放而不能被强行剥夺

3）请求和保持条件：进程已经占有至少一个资源，又提出了新的资源请求，而该资源又被其他进程占有

4）循环等待条件：存在进程资源的循环等待链，链中的每一个进程已获得的资源同时被另一个进程所请求

注意：发生死锁时一定有循环等待，但是发生循环等待时未必死锁

预防

破坏互斥条件

使用特定技术将只能互斥使用的资源改造为允许共享使用

破坏不剥夺条件

申请资源得不到时，主动释放所占有资源（可能导致进程饥饿）

申请资源被其他进程占用时，由 OS 协助剥夺

破坏请求和保持条件

进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行

缺点：进程在整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。也有可能导致某些进程饥饿

破坏循环等待条件

首先为系统中的资源编号，要求进程只能按编号递增顺序请求资源

原理分析：

一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源

按此规则，已持有大编号资源的进程不可能逆向地回来申请小编号的资源，就不会产生循环等待的现象

缺点：

不方便增加新的设备，需要重新分配所有的编号

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

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

避免

概念

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

安全状态：系统存在安全序列，则处于安全状态，安全状态一定不发生死锁。安全序列可能有多个

不安全状态：如果分配资源后，系统中找不出任何一个安全序列，系统就进入了不安全状态。可能发生死锁

死锁的避免：在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁

银行家算法

核心思想：

在分配资源前，预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求，从而使得系统避免死锁

银行家算法步骤：
1）检查此次申请是否超过之前声明的最大需求数，若超过则拒绝
2）检查此时系统剩余的可用资源是否还能满足这次请求，若不足则阻塞
3）试探着分配，用安全性算法检查此次分配是否会导致系统进入不安全状态。若会进入则阻塞
安全性算法步骤：
1）检查当前的剩余可用资源是否能满足某个进程的最大需求（加上该进程原来持有的资源），如果可以，就把该进程加入安全序列并把该进程持有的资源全部回收
2）不断重复上述过程，看最终是否能让所有进程都加入安全序列。

检测

资源分配图

1.构成：

圆代表一个进程，框代表一类资源，框中圆个数代表一类资源的个数

请求边（进程的出边）：表示进程还需要申请几个资源（每条边代表一个）

分配边（资源的出边）：表示已经为进程分配了几个资源（每条边代表一个）

2.化简：

尝试满足进程的请求边，若该进程所有请求边都能全部满足，则删去该进程，归还所有资源。

重复上述过程直到没有进程可以删去

死锁定理

如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁

解除

1）资源剥夺法：挂起（暂时放到外存上）某些死锁进程，并释放它的资源

2）撤销进程法（或称终止进程法）：强制杀死部分甚至全部死锁进程，释放这些资源

3）进程回退法：让一个或多个死锁进程回退到足以避免死锁的地步