Page 100 - 《软件学报》2021年第7期

2018 Journal of Software 软件学报 Vol.32, No.7, July 2021

为例,介绍死锁、数据竞争、原子性违例和顺序性违例的触发机制.
死锁是指两个或者多个线程互相等待对方释放系统资源而陷入无限等待的状态 [16] .在操作系统内核中,为
了支持并发,开发人员采用了各种各样的同步机制.例如,在 Linux 内核中,广泛采用自旋锁(spin_lock)、互斥锁
(mutex_lock)和顺序锁(seqlock)等,这些同步原语帮助开发人员保证了内核代码的正确执行,但同时也大大增加
了死锁发生的可能性.图 2 展示了一个 Linux kernel v3.0.32 文件系统 jffs2 中的死锁实例.从图 2 可以看出,有两
个线程 Thread1 和 Thread2 并发执行函数 jffs2_garbage_collect_pass,其中,Thread1 先获取了自旋锁 c-erase_
completion_lock,然后请求互斥锁 c-alloc_sem,而 Thread2 先获取了自旋锁 c-alloc_sem,又请求自旋锁 c-
erase_completion_lock,从而造成了死锁.

Fig.2 An example of deadlock in Linux kernel v3.0.32
图 2 一个 Linux kernel v3.0.32 中的死锁实例

数据竞争是一种重要的非死锁并发错误 [17] .数据竞争的发生通常需具备 3 个必要条件:(1) 两个或者多个
线程并发地访问同一个内存位置;(2) 至少有一个写操作;(3) 没有采取适当的同步操作.数据竞争可分为良性
数据竞争和恶性数据竞争.良性数据竞争是开发人员期望或者有意设计的一种数据竞争.例如,在操作性能计数
器时允许数据竞争,这样就可以容忍计数值的小误差.恶性数据竞争是会对程序的运行时行为产生负面影响的
数据竞争.程序非确定性的运行时行为,会导致系统出现故障.图 3 展示了一个 Linux kernel v3.10.66 中的数据竞
争实例,该数据竞争发生在主线程 Thread1 和子线程 Thread2 之间,主线程调用 nlmclnt_init 函数创建了一个并
发的子线程 Thread2,Thread2 调用了函数 lockd,并对共享变量 nlmsvc_timeout 进行初始化.由于 Thread1 和
Thread2 之间没有适当的同步操作,Thread1 和 Thread2 可以并发地访问共享变量 nlmsvc_timeout,可能造成未初
始化变量访问的错误.

Fig.3 An example of data race in Linux kernel v3.10.66
图 3 一个 Linux kernel v3.10.66 中的数据竞争实例

原子性违例发生在开发人员对原子性操作的范围和粒度做出了错误的判断,而没有对那些应该出现在临
界区的访存操作进行原子性地封装 [18] .图 4 展示了一个 Linux kernel v3.12.36 中的原子性违例实例,Thread1 和
Thread2 并发地访问函数 vmpressure_work_fn,其中,Thread1 检查变量 vmpr-scanned 是否为空,此时 Thread2 调
度执行,并对变量 vmpr-scanned 赋值为 0,然后 Thread1 再次被调度执行,将 vmpr-scanned 的值赋给了 scanned,
并在后续代码中进行除法操作,从而引发除零错误.虽然线程在访问变量 vmpr-scanned 时有自旋锁 vmpr-
sr_lock 的保护,但是由于加锁的粒度太小而产生了原子性违例错误.