有哪些类型的缺陷
这一章的关键问题在于：在复杂的并发程序中，有哪些类型的缺陷呢？一般来说，这个问题很难回答，没有很好的定义，还好已经有一些前辈做过了相关的工作。具体来水，Lu等人他们详细的分析了一些流行的并发应用，以理解实际的应用中有哪些类型的缺陷。
他们的研究主要集中在4个重要的开源应用：MySQL，Apache，Mozilla和OpenOffice。研究人员通过检查这几个代码库已经修复的并发缺陷，将这些开发者的工作变成量化的缺陷分析。理解了这些结果，会有助于我们了解在成熟的代码库中，曾经出现过那些类型的并发问题。
下表是Lu及其同事的研究结论。可以看出，共有105个缺陷，其中大多数是非死锁相关的(74个)，剩余31个是死锁的。
应用名称 | 用途 | 非死锁 | 死锁 |
MySQL | 数据库服务 | 14 | 9 |
Apache | Web服务器 | 13 | 4 |
Mozilla | 浏览器 | 41 | 16 |
OpenOffice | 办公套件 | 6 | 2 |
总计 | ㅤ | 74 | 31 |
我们随后就会深入分析这两种类型的缺陷。对于非死锁的缺陷，我们通过上述研究的例子来讨论。对于死锁的缺陷，我们讨论大家在避免和处理死锁上做了哪些工作。
非死锁缺陷
Lu的研究其实体现了，非死锁在并发问题中占了主要部分。它是怎么发生的，又该如何修复？我们一共讨论其中的两种：违反原子性缺陷(atomicity violation)和错误顺序缺陷(order violation)。
违反原子性缺陷
这种类型的问题叫做违反原子性缺陷。这是
MySQL中出现的例子。我们可以自己先尝试找一下问题出在哪。问题显而易见，两个线程都在操作同一个变量，即进入临界区之前未加锁。具体来说，线程1在检查到proc_info非空后，在调用
fputs()前被打断。线程2运行，将其置为空。随后切换到线程1执行的时候，就会出现空指针错误。根据 Lu 等人，更正式的违反原子性的定义是: “(即代码段本意是原子的，但在执行中并没有强制实现原子性)”。在我们的例子中，在操作proc_info的时候都假设是原子的。这种问题通常修复起来很简单(有些可能会很复杂)。
对于我们这个例子来说，只需要在进入临界区时加锁，保证线程在修改变量的时候都持有锁，即可解决问题。
违反顺序缺陷
还有一种非死锁的问题叫做违反顺序(order violation)。如下例子，也可以找找看到底是哪里有缺陷。
这个例子的问题在于，线程2会假定变量mThread已经被初始化了(不会为空)。然而，如果线程1因为某些原因并没有首先执行，那么线程2就会因为引用空指针崩溃(如果mThread的初始值是空，这里就会引发空指针问题。如果它指向的内存不为空，还存留的历史数据，那可能就会引发更大的问题)。
违反顺序更正式的定义是：“两个内存访问的预期顺序被打破了(即A应该在B之前执行，但是实际运行中却不是这个顺序)”。
我们可以通过条件变量(condition variables)可以强制按照这个顺序来修复缺陷。我们可以将代码改成如下这样
这段代码我们使用了一个锁，一个条件变量，以及状态量。代码初始化时，会将mtInit设置成1，接着发出信号表示它做完了这件事。如果是线程2更先执行。就会一直等待信号发生变化，如果线程2比线程1更晚执行，线程2就会去检查mtInit是否初始化。这里其实我读的时候也很疑惑，这个mtInit看起来作用不是很大，线程2可以直接去判断mThread是否为空(即用mThread本身作为状态变量)，但是为了简洁，书上的示例并没有这样做。从这个例子中，我们也学习到了，如果两个线程之间的顺序很重要时，条件变量(或者信号量)能够很好的解决问题。
Lu 等人的研究中，大部分(97%)的非死锁问题是违反原子性和违反顺序这两种。因此，程序员仔细研究这些错误模式，应该能够更好地避免它们。此外，随着更自动化的代码检查工具的发展，它们也应该关注这两种错误，因为开发中发现的非死锁问题大部分都是这两种。(有些代码检查工具可以检查到有些值未被初始化，如前端代码检查工具的eslint)
然而，并不是所有的缺陷都像我们举的例子一样，这么容易修复。有些问题需要对应用程序的更深的了解，以及大量代码及数据结构的调整。阅读 Lu 等人的优秀(可读性强) 的论文，了解更多细节。
死锁缺陷
除了上述我们提到的并发问题之外，死锁(deadlock)是一种在很多复杂并发系统中出现的一个经典问题。如线程1持有锁L1，正在等待锁L2，线程2持有锁L2，却在等待锁L1释放，死锁就产生了。如下代码片段就可能会出现这个问题。
当然，这段代码也不是说一定就会造成死锁。只有当线程1占有锁L1，此时上下文切换到线程2。线程2立马锁住了L2，接着再次试图锁住L1。这时才产生了死锁，两个线程相互等待。如下图所示，其中的圈(cycle)表示死锁
对于这个简单的例子来说，其实很容易就能避免，那为什么死锁还会发生呢？
因为在实际的大型项目的代码库中，组件之间会有很多复杂的依赖。以操作系统为例。虚拟内存系统在需要访问文件系统才能从磁盘读到内存的页中；文件系统随后又要和虚拟内存交互，去申请一页内存，用来存放读到的块。因此，在设计大型系统的锁机制时，我们必须要仔细地去避免循环依赖导致的死锁。
另一个原因是封装。我们倾向于隐藏实现的细节，以模块化的方式让软件开发更容易。然而，模块化和锁不是很契合。Jula等人指出，某些看起来没有关系的接口可能会导致死锁。以Java的Vector类和AddAll()方法为例，如下
在这个方法内部是需要保证多线程安全的，因此针对被添加向量(v1)和参数(v2)的锁都需要获取。假设这个方法会先给v1上锁，然后再给v2上锁。如果另外一个线程几乎同时在调用v2.AddAll(v1)，就可能导致死锁。
死锁产生的条件
死锁的产生需要满足如下4个条件
- 互斥：线程对于要访问的资源需要互斥
- 持有并等待：线程持有的锁，同时又在等待其它锁
- 非抢占：线程获得的锁不能被抢占
- 循环等待：线程之间存在一个环路，环路上的每个线程都额外持有一个锁，而这个锁又是下一个 线程要申请的。
只要避免上述任一情况，就可以避免死锁。因此我们来学习一下这些情况该怎么避开。
循环条件
也许对于我们来说，预防死锁最实用的方案(也是最经常采用的)就是。最直接的方法就是在获取锁时提供一个全序(total ordering)。假设有两个锁(L1和L2)，那我们每次都会先申请L1，再申请L2，通过这个严格的顺序避免了循环等待， 就可以避免死锁。
显然，在复杂的系统中不会只有两个锁，锁的全序可能很难做到。因此，偏序(partial ordering)可能是一种有效的方法。Linux中的内存映射代码就是一个偏序锁的例子。
代码开头的注释说明了10组不同的加锁顺序，包括简单的关系，如i_mutex早于i_mmap_mutex，也包括复杂的关系，如i_mmap_mutex早于private_lock，早于swap_lock，早于mapping→tree_lock。
我们可以想象到，全序和偏序都是需要细致的锁策略和设计和实现。并且，顺序只是一种约定，程序员很容易一时粗心而忽略，从而又导致死锁。
最后，如果想要有序的加锁则需要深入理解代码库，了解各个函数的调用关系，即使一个小错误，也可能会导致”D“字(Deadlock)
通过锁的地址来强制锁的顺序
当一个函数要抢多个锁时，我们需要注意死锁。我们来看一个简单的函数:
do_something(mutex t *m1, mutex t *m2)，如果函数每次都会保证先抢m1，再抢m2，那么当一个线程调用do_something(m1, m2)，另一个线程调用do_something(m2, m1)时，就会造成死锁。为了避免这种问题，我们可以根据锁的地址作为获取锁的顺序。用地址从高到底的顺序，或者从低到高的顺序加锁，这样的话，
do_something()函数就可以保证无论传入的参数是什么顺序，函数都会有固定的顺序来加锁，代码如下：持有并等待
死锁的 持有并等待条件，可以通过原子地抢锁来实现。即再多增加一个锁，先抢到这个锁后再去抢其它的锁
只有在抢到
prevention这个锁之后，代码会保证在接下来的抢锁过程中，不会有不合时宜的线程切换，从而避免的死锁。当让，这需要所有线程在需要抢锁时，先抢到全局的prevention锁，之后再按任意顺序抢锁都不会有问题。但是，出于某些原因，这个方案也有些问题，它不适用于封装：因为这个方案需要我们明确地知道要抢哪些锁，并且提前抢到了这些锁。因为要提前抢到所有锁(同时)，而不是在真正需要的时候，所以可能降低了并发。
非抢占
线程在调用unlock之前，都认为锁是被占用的，如果一个线程需要抢多个锁时，问题可能会有些棘手，线程在等待一个锁时，同时持有另一个锁。很多线程库提供了更为灵活的接口来避免这种情况。如trylock()函数会尝试获取锁，如果锁被占用，则返回-1。可以用这个接口来实现一个无死锁的方案：
如上代码就解决了死锁的问题。但它可能会导致新的问题：活锁(livelock)。另一个线程可能也在抢这两个锁，但是顺序不同(先抢L2，再抢L1)。两个线程一直在重复这一序列，又同时都抢失败。这种情况下，系统一直在运行这段代码(因为它不是死锁),但是又一直不回有进展，所以叫做活锁。
当然也有解决的方案：如在循环结束时候，先随机等待一个时间，然后再重复整个动作，这样就可以降低线程之间的相互干扰。
除了活锁的问题之后，使用trylock的方案依旧还有一些问题，还是封装问题：如果其中一个锁是封装在函数内部的，那么这个跳回(goto)开始就很难实现。如果代码在中间获取了某些资源(如分配了内存)，必须确保也能释放这些资源。即在抢L2失败时，在返回到开头前，需要释放掉这些内存。当然，在某些场景下(例如，之前提到的 Java 的 vector 方法)，这种方法很有效。
互斥
最后的方案就是完全避免互斥，即在进入临界区时不需要排斥其它线程。Herlihy提出了设计各种无等待(wait-free)数据结构的思想。他的想法很简单：通过强大的硬件指令，我们可以构造出不需要锁的数据结构。如比较并交换(compare-and-swap)指令，是一种硬件提供的原子指令。
当我们想要原子地更新某个值时，我们可以这样实现
这样的话，我们就不需要锁了，通过直接使用比较并交换指令，反复尝试将值更新到新的值。这种方式就不需要锁(但可能会导致活锁)。
我们再来考虑一个更复杂的例子：链表插入。这是在链表插入元素的代码:
这段代码在多个线程同时调用的时候，会有临界区(猜猜看是哪个位置)。我们可以在相关代码加锁来解决问题。
上面的方案我们使用了传统的锁，这里我们其实也可以用比较并交换指令来实现，如下：
这段代码会把next指针指向当前的链表头(head)，然后试着把新节点(n)交换到链表头，如果在此时有其它线程修改了head的值，这里的交换就会失败，导致这个线程根据新的head值重试。
通过调度避免死锁
除了上述那些预防死锁的情况，有些场景更适合避免死锁(avoidance)。但是我们需要了解全局的信息，即不同线程在运行中对锁的需求，从而使得后续的调度可以避免死锁
假设我们有一颗双核心的CPU，一共有4个线程需要调度。更进一步假设，我们知道线程1(T1)需要用锁L1和L2，T2也需要锁L1和L2，T3只需要L2，T4不需要锁。
ㅤ | T1 | T2 | T3 | T4 |
L1 | y | y | n | n |
L2 | y | y | y | n |
有一种比较聪明的调度方式，只要T1和T2不同时运行，就不会产生死锁。如下
注意看，T3可以和T1或者T2重叠都是可以的。虽然T3抢的锁可能会影响T2，但是它只会用到一把锁，所以和其它线程并发都不会出现死锁。
我们再来看一个竞争更多的例子，在这个例子中，对同样的资源(锁L1和L2)有更多的竞争。锁和线程的竞争如下表：
ㅤ | T1 | T2 | T3 | T4 |
L1 | y | y | y | n |
L2 | y | y | y | n |
这个例子中其实也很好解决，我们只需要让T1，T2，T3这三个线程串行执行就OK了
显然，我们把T1，T2，T3三个线程调度在同一颗处理器上确实避免了死锁的情况，但是这种保守的静态方案增加了完成任务的总时间。尽管我们是有可能并发运行这些任务的，但是为了避免死锁，我们牺牲了一些性能作为代价。这也是一种折中。
Dijkstra 提出的银行家算法[D64]是一种类似的著名解决方案，文献中也描述了其他类似的方案。遗憾的是，这些方案的适用场景很局限。例如，在嵌入式系统中，你知道所有任务以及它们需要的锁。另外，和上文的第二个例子一样，这种方法会限制并发。因此，通过调度来避免死锁不是广泛使用的通用方案。
检查和恢复
最后一种常见的策略就是允许死锁偶尔发生，当发生了死锁时再采取行动。举个例子，如果一个操作系统一年死机一次，你会重启系统，然后开心地(或者郁闷地)继续工作。如果死锁的情况很少见，这种不是办法的办法也是很实用的。
很多数据库系统都使用了死锁检查和恢复技术。死锁检查器会定期运行，通过构建资源图来检查循环。当循环(死锁)发生时，系统则需要重启。如果还有更复杂的数据结构相关的修复，那么则需要人工参与。
提示：不要总是完美(TOM WEST定律)
Tom West 是经典的计算机行业小说《Soul of a New Machine》[K81]的主人公，有一句很棒的工程格言: “不是所有值得做的事情都值得做好”。如果坏事很少发生，并且造成的影响很小，那么我们不应该花费大量的精力去预防它。
当然，如果你在制造航天飞机，事故可能会导致航天飞机爆炸，那么则不适用这条建议
截止目前，我们简要地讨论了死锁：为何会发生，以及如何处理。这个问题几乎和并发一样古老，已经有成百上千的相关论文了。实践中是自行设计抢锁的顺序，从而避免死锁发生。无等待的方案也很有希望，在一些通用库和系统中，包括 Linux，都已经有了一些无等待的实现。
然而，这种方案不够通用，并且设计一个新的无等待的数据结构极其复杂，以至于不够实用。也许，最好的解决方案是开发一种新的并发编程模型：在类似 MapReduce(来自 Google)[GD02]这样的系统中，程序员可以完成一些类型的并行计算，无须任何锁。
锁必然带来各种困难，也许我们应该尽可能地避免使用锁，除非确信必须使用。