读书笔记
🕰️《Operating System:Three Easy Pieces》第三十二章 常见并发问题
00 分钟
2023-1-19
2023-4-15
type
status
date
slug
summary
tags
category
icon
password
Property
Apr 15, 2023 03:23 PM

有哪些类型的缺陷

notion image

非死锁缺陷

违反原子性原则

违反了多次内存访问中预期的可串行性(即代码段本意是原子的,但在执行中并没有强制实现原子性)
通过加解决

违反顺序缺陷

两个内存访问的预期顺序被打破了(即 A 应该在 B 之前执行,但是实际运行中却不是这个顺序)
如果 mState = mThread->State 语句先执行,则 mThread 为空。通过加条件变量(或信号量)解决

死锁缺陷

notion image
两个线程互相等待

为什么会发生死锁:

  • 在大型的代码库里,组件之间会有复杂的依赖。
    • 以操作系统为例。虚拟内存系统在需要访问文件系统才能从磁盘读到内存页;文件系统随后又要和虚拟内存交互,去申请一页内存,以便存放读到的块。
  • 封装(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)。我们需要了解全局的信息,包括不同线程在运行中对锁的需求情况,从而使得后续的调度能够避免产生死锁。
notion image
只要 T1 和 T2 不同时运行,就不会产生死锁。,T3 和 T1 重叠,或者和 T2 重叠都是可以的。虽然 T3 会抢占锁 L2,但是由于它只用到一把锁,和其他线程并发执行都不会产生死锁。
notion image
我们再来看另一个竞争更多的例子。在这个例子中,对同样的资源(又是锁 L1 和 L2)有更多的竞争。锁和线程的竞争如表 32.3 所示。
notion image
特别是,线程 T1、T2 和 T3 执行过程中,都需要持有锁 L1 和 L2。下面是一种不会产生死锁的可行方案:
notion image
你可以看到,T1、T2 和 T3 运行在同一个处理器上,这种保守的静态方案会明显增加完成任务的总时间。尽管有可能并发运行这些任务,但为了避免死锁,我们没有这样做,付出了性能的代价。

检查和恢复

最后一种常用的策略就是允许死锁偶尔发生,检查到死锁时再采取行动。
很多数据库系统使用了死锁检测和恢复技术。死锁检测器会定期运行,通过构建资源图来检查循环。当循环(死锁)发生时,系统需要重启。如果还需要更复杂的数据结构相关的修复,那么需要人工参与。

参考

上一篇
《Operating System:Three Easy Pieces》第三十三章 基于事件的并发(进阶)
下一篇
《Operating System:Three Easy Pieces》第三十一章 信号量

评论
Loading...