《Operating System：Three Easy Pieces》第三十二章常见并发问题

type

status

date

slug

summary

有哪些类型的缺陷

非死锁缺陷

违反原子性原则

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

通过加锁解决

违反顺序缺陷

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

如果 mState = mThread->State 语句先执行，则 mThread 为空。通过加条件变量(或信号量)解决

死锁缺陷

两个线程互相等待

为什么会发生死锁：

在大型的代码库里，组件之间会有复杂的依赖。

以操作系统为例。虚拟内存系统在需要访问文件系统才能从磁盘读到内存页；文件系统随后又要和虚拟内存交互，去申请一页内存，以便存放读到的块。

封装（encapsulation）

软件开发者一直倾向于隐藏实现细节，以模块化的方式让软件开发更容易。然而，模块化和锁不是很契合。Jula 等人指出[J+08]，某些看起来没有关系的接口可能会导致死锁。

以 Java 的 Vector 类和 AddAll()方法为例，我们这样调用这个方法：

在内部，这个方法需要多线程安全，因此针对被添加向量（v1）和参数（v2）的锁需要获取。假设这个方法，先给 v1 加锁，然后再给 v2 加锁。如果另外某个线程几乎同时在调用 v2.AddAll(v1)，就可能遇到死锁。

产生死锁的条件：

互斥：线程对于需要的资源进行互斥的访问（例如一个线程抢到锁）。

持有并等待：线程持有了资源（例如已将持有的锁），同时又在等待其他资源（例如，需要获得的锁）。

非抢占：线程获得的资源（例如锁），不能被抢占。

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

预防死锁

循环等待

也许最实用的预防技术（当然也是经常采用的），就是让代码不会产生循环等待。最直接的方法就是获取锁时提供一个全序（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。你可以想到，全序和偏序都需要细致的锁策略的设计和实现。另外，顺序只是一种约定，粗心的程序员很容易忽略，导致死锁。

提示：通过锁的地址来强制锁的顺序当一个函数要抢多个锁时，我们需要注意死锁。比如有一个函数：do_something(mutex t *m1, mutext *m2)，如果函数总是先抢 m1，然后 m2，那么当一个线程调用 do_something(L1, L2)，而另一个线程调用 do_something(L2, L1)时，就可能会产生死锁。为了避免这种特殊问题，聪明的程序员根据锁的地址作为获取锁的顺序。按照地址从高到低，或者从低到高的顺序加锁，do_something()函数就可以保证不论传入参数是什么顺序，函数都会用固定的顺序加锁。具体的代码如下： if (m1 > m2) { // grab locks in high-to-low address order pthread_mutex_lock(m1); pthread_mutex_lock(m2); } else { pthread_mutex_lock(m2); pthread_mutex_lock(m1); } // Code assumes that m1 != m2 (it is not the same lock) 在获取多个锁时，通过简单的技巧，就可以确保简单有效的无死锁实现

持有并等待

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

非抢占

解决非抢占就是要让线程能占用其他线程没在用的锁，不能占着茅坑不拉屎。主动去占用其他线程已经占用的锁不可能实现，需要让线程能认识到自己占着锁也没用，找机会主动释放一次

假设线程要同时拥有 L1 和 L2 才能继续，获得 L1 后尝试获取 L2，如果失败就解锁 L1，重新开始。

需要加一定的随机延迟，防止活锁（livelock）（双方都不停放弃锁）。

类似于数据库中的事务和回滚

互斥

Herlihy 提出了设计各种无等待（wait-free）数据结构的思想，通过强大的硬件指令，我们可以构造出不需要锁的数据结构。

*address 的值等于 expected 值时，将其赋值为 new，这是个硬件提供的原子操作–比较并交换（compare-and-swap）指令：

假定我们想原子地给某个值增加特定的数量：

无须获取锁，更新值，然后释放锁这些操作，我们使用比较并交换指令，反复尝试将值更新到新的值。这种方式没有使用锁，因此不会有死锁（有可能产生活锁）。

一个更复杂的例子：链表插入。这是在链表头部插入元素的代码：

通过加锁解决同步：

用比较并交换指令（compare-and-swap)来实现插入操作:

这段代码，首先把 next 指针指向当前的链表头（head），然后试着把新结点交换到链表头。但是，如果此时其他的线程成功地修改了 head 的值，这里的交换就会失败，导致这个线程根据新的 head 值重试。

通过调度避免死锁

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

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

我们再来看另一个竞争更多的例子。在这个例子中，对同样的资源（又是锁 L1 和 L2）有更多的竞争。锁和线程的竞争如表 32.3 所示。

特别是，线程 T1、T2 和 T3 执行过程中，都需要持有锁 L1 和 L2。下面是一种不会产生死锁的可行方案：

你可以看到，T1、T2 和 T3 运行在同一个处理器上，这种保守的静态方案会明显增加完成任务的总时间。尽管有可能并发运行这些任务，但为了避免死锁，我们没有这样做，付出了性能的代价。

检查和恢复

最后一种常用的策略就是允许死锁偶尔发生，检查到死锁时再采取行动。

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

参考

Operating Systems: Three Easy Pieces 中文版