上一篇计算机系统010 - 操作系统之并行中讲述了并行中的多进程/线程对同一资源的竞争会引发冲突，导致程序执行结果不可预测。通过使用信号量、管程、消息传递等机制，可实现进程间的同步和通信，达成互斥基础上的合作。但事实上，进程运行过程中可能同时会同时使用多个资源，假如两个进程在占用对方所需资源的同时，去获取对方占有资源，就会形成死锁。

为便于书写，后续多进程/线程统一视为多线程，毕竟进程本身至少也是以一个主线程的形式执行的。

1. 死锁 Deadlock

从前面简短的描述来看，死锁现象中至少需要如下参与者：

• 两个进程/线程
• 两个资源

1.1 死锁的条件

死锁有三个必要条件：

• 互斥，即每个资源只能供一个线程使用
• 占有且等待，即已占有资源的线程不会释放资源
• 不可抢占，即不可抢占已被其他线程占有资源

这三个条件都只是死锁存在的必要条件，但不是充分条件。死锁的真正产生还需要第四个条件：

• 循环等待，即存在一个封闭的资源环路，互不释放、互相追求

光从理论上来讲难免过于空洞，既然说到了死锁，那就不得不说起一个经典问题：哲学家就餐。

1.2 哲学家就餐问题

有五位哲学家住在一栋房子里，在他们面前有一张餐桌，每位哲学家的生活就是思考和吃饭。通过多年的思考，所有的哲学家一致同意最有助于他们思考的食物是意大利面条。但由于动手能力有限，每位哲学家需要两把叉子来吃面条。

现在的问题是需要设计一套礼仪（算法）以允许哲学家就餐，算法必须保证互斥（没有两位哲学家同时使用同一把叉子），同时还要避免死锁和饥饿。所谓饥饿，就是指长时间得不到资源的使用权而无法完成任务，只能阻塞住白白浪费生命。

对此，通常有如下几种解法：

• 服务生解法
  引入第三者服务生，决策每个哲学家具体就餐时机。实际上，相当于通过全局管理者获取资源，而不允许线程本身直接去获取资源。

• 资源分级解法
  为资源（叉子）分配一个偏序或者分级的关系，并约定所有资源都按照这种顺序获取，按相反顺序释放，且保证不会有两个无关资源同时被后一项工作所需要。描述起来挺复杂，说到底，就是给资源排优先级，要想拥有两个资源，首先要拥有高优先级资源，然后才能去获取低优先级资源。这样一来，多个资源之间的战争就转移到了单独的高优先级资源战争，避免了只拿到低优先级的线程鱼死网破。

上述的是通用的解法，虽然解法能解决问题，但授人以鱼不如授人以渔，解法中遵循的原理还需要进一步说明。

2. 死锁解决方法

2.1 预防

死锁预防，就是排除发生死锁的可能性，即破坏4个条件之一来避免死锁的产生。预防方法可以进一步分为两种：

• 间接预防：防止三个必要条件之一形成

  • 互斥
    实际操作系统中，第一个条件通常不能禁止，毕竟互斥本身提供了对资源的保护。但某些情况下，如对于文件的读写访问中，只需要对写操作进行互斥即可，而读操作不影响数据本身可以不要求互斥。

  • 占有且等待
    为预防占有且等待的条件，可以要求线程一次性请求所有需要的资源，并阻塞线程直到所有请求同时得到满足。也就是说，如果申请时不能同时获取到所有必需资源，那么就必须等到可以全部获取了在执行，避免了既不能执行还占有着资源的情况发生。
    不过这样也就使得线程整体执行时间被拉长，且不可预测。

  • 不可抢占
    有几种方法可以预防这个条件：

    • 占有某些资源的线程进一步申请资源被拒绝时，必须释放所占有资源，如有必要，可再次申请这些资源和其他资源
    • 如一个线程请求被占有的资源，则有操作系统负责从另一线程处抢占资源。而是否抢占的标准需参考优先级信息

• 直接预防：防止充分条件形成
  循环等待条件可通过定义资源类型的线性顺序来预防，如果一个线程已获取到R类型资源，则之后只能请求排在R类型之后的资源。

从上面我们可以看到，死锁预防主要是从资源使用权本身着手，破坏四个条件之一来防止死锁的形成，但由于引入了资源等待，拉长了任务所需执行时长，造成低效后果。

2.2 避免

为了避免因为预防死锁而导致所有线程变慢，死锁避免采用了与死锁预防相反的措施。它允许三个必要条件，但通过算法判断资源请求是否可能导致循环等待的形成并相应决策，来避免死锁点的产生。因此，其前提是知道当前资源使用的整体情况，以及申请资源线程本身所占有的资源细节。

判断和决策中，主要使用两种避免方法。

• 线程启动拒绝
  如果一个线程的请求会引发死锁，则不允许其启动。
• 资源分配拒绝
  如果一个线程增加的资源请求会导致死锁，则不允许此申请。

整体来看，死锁避免是从资源和线程相互间关系着手，避免形成循环等待是其主要任务。

2.3 检测

相比前面两种方法的保守，死锁检测就要自信而奔放得多。死锁检测中，尽可能将被请求的资源分配给线程，操作系统会周期性执行算法检测是否有循环等待的产生。换句话说，就是放手去干，操作系统罩着你们。

当然，检查算法执行的频率影响着死锁被检测出的灵敏度，操作系统可以在每次资源请求是检测，也可以适当降低频率，减少消耗的CPU时间。检测到死锁后，就需要解决死锁。目前操作系统中主要采用如下几种方法：

• 取消所有死锁相关线程，简单粗暴，但也确实是最常用的
• 把每个死锁线程回滚到某些检查点，然后重启
• 连续取消死锁线程直到死锁解除，顺序基于特定最小代价原则
• 连续抢占资源直到死锁解除

2.4 综合选择

既然三种方法各有优劣，那就不如海纳百川，取其精华去其糟粕。

• 将资源分成几组不同的资源类
• 为预防在资源类之间由于循环等待产生了死锁，可使用线性排序策略
• 在一个资源类中，使用该类资源最适合的算法

翻译一下，就是说先根据资源特性分类（至于为什么要分类，前面也提过，分类是为了更细粒度的控制），类和类之间可以通过排优先级来约束，而类本身内部，再通过合适算法来选择。

说起资源，顺便多提一下。操作系统中资源通常分为如下两种：

• 可重用资源
  一次只能供一个线程使用，并且不会由于使用而耗尽。主要是硬件设备和一些数据结构，如CPU、I/O通道、内存和外存、设备、文件、数据库、信号量等。

• 可消耗资源
  指可被创建和销毁的资源，数目没有限制，但用完后通常就不复存在。主要为一些动态产生的数据，如中断、信号、消息、I/O缓冲区中信息等。

3. 总结

本篇主要介绍了死锁的形成条件、相应的解决方法及各解决方法优劣之处，相比其他篇内容，本篇略显单薄了一些，不过还是希望对于一些概念的理解能够引发共鸣，留下印象。最近两篇中讲述的是操作系统并行、死锁两个调度相关的问题，接下来就要从内存管理部分对进程调度做进一步展开。