Page 113 - 《软件学报》2021年第6期

鲁法明 等:基于锁增广分段图的多线程程序死锁检测 1687

集不会包含 n;同理,threadC 欲获取锁 q 必须先获取 m,而锁 m 的释放导致了 threadB 获取 p 时的持有锁集不会
包含 m,这就导致了他们的持有锁集交集为空,而已有方法仅根据持有锁集是否相交排除门锁环误报,所以会认
定其构成一个潜在死锁.而实际上,若要真正触发上述死锁,则锁 n 需要被 threadB 获取并释放后才能授权给
threadC.类似地,锁 m 需要被 threadC 获取并释放后才能授权给 threadB,也就是说,对于同时存在于线程 u 之历
史持有锁集与另一线程 v 之持有锁集中的锁对象 o 而言,历史持有锁的获取操作 acg(u,o)应先于持有锁的获取
操作 acg(v,o),我们称这种关系为“历史持有锁-持有锁”耦合因果依赖关系,其严格定义稍后给出.Program 1 中,
这种依赖关系要求操作 26:acq(threadB,n)先于 33:acq(threadC,n)执行;同时,操作 34:acq(threadC,m)先于 25:
acq(threadB,m)执行.又因为 33:acq(threadC,n)与 34:acq(threadC,m)同属一个线程,语句顺序在前的操作 33:
acq(threadC,n)必然先于 34:acq(threadC,m)执行,由此可得 26:acq(threadB,n)需要先于 25:acq(threadB,m)执行.然
而这是不可能的,因为作为同一线程 threadB 的两步操作,第 26 行语句对应的 26:acq(threadB,n)不可能先于第
25 行语句对应的操作 25:acq(threadB,m)执行.这说明本例中的“历史持有锁-持有锁”耦合因果依赖关系无法得
到满足,此时,即使多个锁获取操作构成环路也无法真正触发死锁.已有的分段图和扩展锁图等模型均未对这种
“历史持有锁-持有锁”耦合因果依赖关系进行刻画和可满足性判定,故导致了本例的第 2 种死锁误报.

(a) 分段图

(b) 扩展锁图
Fig.1 Segment graph and extended lock graph corresponding to the running trace in Table 2
图 1 表 2 运行轨迹对应的分段图和扩展锁图

一般而言,死锁误报产生的原因就是程序模型遗漏了上述某些因果依赖或互斥关系,本文将上述实例中展