本文讨论了操作系统中的死锁问题，探讨了死锁发生的条件和系统模型。通过资源类型、进程资源分配图和死锁特征的介绍，阐述了死锁产生的原因和可能性。最后强调了死锁发生的必要条件，并指出即使满足这些条件也不一定导致死锁的发生。
死锁问题
一组阻塞的进程持有一种资源，并等待获取另一个进程所占有的一个资源。这导致它们无法继续执行，进入一种僵局状态。
例如，系统有 2 个磁带驱动器，进程 P1 和进程 P2 各持有一个，但都需要另一个。
为什么会发生死锁？由于进程的并发执行抢占资源。
系统模型
资源类型 R1，R2，…，Rm
每个资源类型 Ri 有 Wi 个实例
每个进程可使用的资源如下：
- require/get <= free resource
- use/hold <= requested/used resource
- release <= free resource
可重复使用的资源
- 在一个时间只能有一个进程使用，且不能被删除
- 进程获得资源，后来释放由其他进程重用
- 处理器、I/O 通道、主和副存储器、设备和数据结构（如文件，数据库和信号量）
- 如果每个进程拥有一个资源并请求其他资源，死锁可能发生
使用资源
- 创建和销毁
- 在 I/O 缓存区的中断、信号、消息、信息
- 如果接收消息阻塞可能会发生死锁
- 可能少见的组合事件会引起死锁
资源分配图
一组顶点 V 和边 E 的集合，V 有两种类型、E 有两种指向：
- 系统中的所有进程集合：P = {P1, P2, …, Pn}
- 系统中的所有资源类型集合：R = {R1, R2, …, Rm}
- 进程请求资源：Pi -> Rj
- 分配或保持资源给进程：Rj -> Pi
资源分配实例：无死锁、有环有死锁、有环无死锁
基本情况
如果图中不包含循环：没有死锁。
如果图中包含循环：
- 如果每个资源类只有一个实例，那么死锁。
- 如果每个资源类有多个实例，可能 死锁。
无环一定不会死锁，但有环不一定死锁，即有环是死锁的必要不充分条件。
死锁特征
死锁出现时，一定出现以下四个条件，但出现以下四个条件不一定发生死锁：
- 互斥：在一个时间只能有一个进程使用资源。
- 持有并等待：进程保持 至少一个资源 正在等待 获取其他进程持有的额外资源。
- 无抢占：一个资源只能被进程自己释放（进程已经完成了它的任务之后）。
- 循环等待 ：存在等待进程集合 {P1, P2, …, Pn}，P1 正在等待 P2 所占用的资源，P2 正在等待 P3 占用的资源，…，Pn-1 在等待 Pn 的资源，Pn 正在等待 P1 所占用的资源。
死锁处理方法
- 确保系统永远不会进入死锁状态。
- 运行系统进入死锁状态，然后恢复。
- 忽略这个问题，假装系统中从来没有发生死锁，用于大多数操作系统，包括 UNIX。
系统忽略死锁是因为检查并避免死锁的代价太大，因此忽略并让应用程序（程序员）保证不会发生死锁。
死锁预防
死锁预防（Deadlock Prevention）至少会打破死锁的四个必要条件中的一个，以确保系统不会进入死锁状态。
打破互斥：共享资源不是必须的，必须占用非共享资源
打破持有并等待：必须保证当一个进程请求的资源拿不到时，它不再持有任何其他资源
- 进程在不同时间段所需的资源可能不同，要么持有全部资源、要么被迫放弃所有资源，这会导致系统资源利用率低，可能发生饥饿
打破无抢占：进程可以抢占其他进程的资源，如何抢占？比如 kill 掉这个进程（暴力了哈）
打破循环等待：对所有资源类型进行排序，并要求每个进程按照资源的递增顺序进行申请（这样就不会产生循环了）
- 通用操作系统用的不多，但在应用比较少的嵌入式操作系统用的较多；但同样面临系统资源利用率较低的问题
死锁避免
死锁避免 需要系统具有一些额外的先验信息提供。
-
最简单有效的先验信息获取方法是：要求每个 进程声明 它可能需要的每个类型资源的最大数目。
-
资源的分配状态是通过 限定提供与分配 的资源数量以及进程的最大需求量。
-
死锁避免 算法动态检查 的资源分配状态，以确保永远不会出现一个环形等待状态。
-
当一个进程请求可用资源时，系统必须判断立即分配是否能使系统处于安全状态。
系统处于安全状态是指：针对所有进程存在一个安全有序序列 {P1, P2, …, Pj, …, Pi, …, Pn}。针对每个 Pi 要求的资源，能够由当前可用的资源 + 所有 Pj 持有的资源来满足。
- 如果 Pi 资源的需求不是立即可用，那么 Pi 可以等待 所有 Pj 完成。
- 当 Pi 完成后，Pi+1 可以得到所需要的资源并执行、释放所分配的资源并终止。
- 用同样的方法，Pi+k 能获得其所需的资源。
如果系统处于安全状态：无死锁，处于不安全状态：可能死锁。避免死锁：确保系统永远不会进入不安全状态。