并发-常见并发问题 | 彩潭有鲤的札记

type

status

date

slug

summary

非死锁缺陷

违反原子性缺陷

两个线程都要访问thd结构中的成员proc_info。第一个线程检查proc_info非空，然后打印出值；第二个线程设置其为空。显然，当第一个线程检查之后，在fputs()调用之前被中断，第二个线程把指针置为空；当第一个线程恢复执行时，由于引用空指针，导致程序奔溃。

违反原子性的定义是：“违反了多次内存访问中预期的可串行性（代码段本意是原子的，但在执行中并没有强制实现原子性）”。

proc_info 的非空检查和fputs()调用打印proc_info是假设原子的，当假设不成立时，代码就出问题了。

这种问题的修复通常很简单，只要给共享变量的访问加锁，确保每个线程访问proc_info 字段时，都持有锁（proc_info_lock）。当然，访问这个结构的所有其他代码，也应该先获取锁。

违反顺序缺陷

违反顺序更正式的定义是：两个内存访问的预期顺序被打破了（即A 应该在B 之前执行，但是实际运行中却不是这个顺序）

线程2 的代码中似乎假定变量mThread 已经被初始化了（不为空）。然而，如果线程1 并没有首先执行，线程2就可能因为引用空指针奔溃

通过强制顺序来修复这种缺陷，条件变量就是一种简单可靠的方式，在现代代码集中加入这种同步。可以把代码修改成这样：

死锁缺陷

例如，当线程1 持有锁L1，正在等待另外一个锁L2，而线程2 持有锁L2，却在等待锁L1 释放时，死锁就产生

当线程1占有锁L1，上下文切换到线程2。线程2 锁住L2，试图锁住L1。这时才产生了死锁，两个线程互相等待。

死锁的产生需要如下4个条件：

互斥：线程对于需要的资源进行互斥的访问

持有并等待：线程持有了资源，同时又在等待其他资源

非抢占：线程获得的资源，不能被抢占

循环等待：线程之间存在一个环路，环路上每个线程都额外持有一个资源，而这个资源又是下一个线程要申请的

如果这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。

不过，全序和偏序都需要细致的锁策略的设计和实现。另外，顺序只是一种约定，粗心的程序员很容易忽略，导致死锁。最后，有序加锁需要深入理解代码库，了解各种函数的调用关系，即使一个错误，也会导致严重的后果。

注：可以根据锁的地址作为获取锁的顺序，按照地址从高到低，或者从低到高的顺序加锁：

持有并等待

死锁的持有并等待条件，可以通过原子地抢锁来避免。实践中，可以通过如下代码来实现：

保证了某个线程先抢到prevention这个锁之后，即使有不合时宜的线程切换，其他线程也抢不到任何锁。当然，这需要任何线程在任何时候抢占锁时，先抢到全局的prevention锁。例如，如果另一个线程用不同的顺序抢锁L1 和L2，也不会有问题，因为此时，线程已经抢到了prevention 锁。

不过，这个方案的问题也显而易见。首先它不适用于封装，因为这个方案需要我们准确地知道要抢哪些锁，并且提前抢到这些锁。并且因为要提前抢到所有锁，而不是在真正需要的时候，所以可能降低了并发。

非抢占

在调用unlock之前，都认为锁是被占有的。多个抢锁操作通常会带来麻烦，因为我们等待一个锁时，可能会同时持有另一个锁。很多线程库提供更为灵活的接口来避免这种情况。具体来说，trylock()函数会尝试获得锁，返回−1则表示锁已经被占有，线程并不会挂起。

可以用这一接口来实现无死锁的加锁方法：

注意，当另一个线程使用相同的加锁方式，但是不同的加锁顺序（L2然后L1），程序仍然不会产生死锁。但是会引来一个新的问题：活锁（livelock）。两个线程有可能一直重复这一序列，又同时都抢锁失败。这种情况下，系统一直在运行这段代码，因此名为活锁。也有活锁的解决方法：例如，可以在循环结束的时候，先随机等待一个时间，然后再重复整个动作，这样可以降低线程之间的重复互相干扰。

使用trylock方法可能还会有其他一些困难。第一个问题仍然是封装：如果其中的某一个锁是封装在函数内部的，那么这个跳回开始处就很难实现。还有如果代码在中途获取了某些资源，必须要确保也能释放这些资源。例如，在抢到L1后，我们的代码分配了一些内存，当抢L2失败时，在goto之前，需要释放这些内存。当然，在某些场景下，这种方法很有效。

互斥

最后的预防方法是完全避免互斥。通常来说，代码都会存在临界区，因此很难避免互斥。那么应该怎么做呢？通过强大的硬件指令，我们可以构造出不需要锁的数据结构。

比如，可以使用比较并交换指令来实现一个无锁同步的链表插入操作。这是在链表头部插入元素的代码：

一种可能的实现是：

首先把next指针指向当前的链表头head，然后试着把新节点交换到链表头。如果此时其他的线程成功地修改了head的值，这里的交换就会失败，线程会一直重试。

通过调度避免死锁

除了死锁预防，某些场景更适合死锁避免。需要了解全局的信息，包括不同线程在运行中对锁的需求情况，从而使得后续的调度能够避免产生死锁。

例如，假设需要在两个处理器上调度4个线程，线程1（T1）需要用锁L1和L2，T2也需要抢L1和L2，T3只需要L2，T4不需要锁。

一种比较聪明的调度方式是，只要T1 和T2不同时运行，就不会产生死锁：

T3 和T1 重叠，或者和T2 重叠都是可以的。虽然T3 会抢占锁L2，但是由于它只用到一把锁，和其他线程并发执行都不会产生死锁。

死锁检查和恢复

最后一种常用的策略就是允许死锁偶尔发生，检查到死锁时再采取行动。如果死锁很少见，这种不是办法的办法也很实用。

很多数据库系统使用了死锁检测和恢复技术。死锁检测器会定期运行，通过构建资源图来检查循环。当循环（死锁）发生时，系统会根据既定的策略进行回滚甚至重启。如果还需要更复杂的数据结构相关的修复，那么需要人工参与。

注：也许最好的解决方案是开发一种新的并发编程模型：在类似MapReduce这样的系统中，程序可以完成一些类型的并行计算，无须任何锁。锁必然带来各种困难，我们应该尽可能地避免使用锁，除非确信必须使用。