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

1694 Journal of Software 软件学报 Vol.32, No.6, June 2021

依赖关系与“历史持有锁-持有锁”耦合因果依赖关系无法同时满足,从而意味着“ID 为 11 的弧对应的锁获取操
作”与“ID 为 15 的弧对应的锁获取操作”无法并发,故弧{11,15}构成之有向环路对应的潜在死锁非真实死锁.
基于上述分析,可得基于锁增广分段图和时序增广锁图的死锁检测算法如下,检测本质是如下 5 条规则.
(1) 时序增广锁图中多个锁申请操作构成一条有向环路(对应算法第 1 步);
(2) 环路中的锁申请操作分属于的不同的线程(对应算法第 3 步);
(3) 环路中任意两个锁申请操作无线程间因果依赖和“锁-start”耦合因果依赖,即,在锁增广分段图中无路
径相连(对应算法第 17 步);
(4) 环路中的任意两个锁申请操作对应的持有锁集互不相交(对应算法第 28 步);
(5) 环路对应的“历史持有锁-持有锁”耦合因果关系图不存在有向环(对应算法第 30 步).
算法 1. 基于锁增广分段图和时序增广锁图的死锁检测.
输入:锁增广分段图 SegG_Order σ ,时序增广锁图 LockG_Order σ 及其中的环路集合 Cycles(LockG_Order σ );
输出:LG_Order σ 中与潜在死锁对应的环路的集合 DeadlockCycles(LockG_Order σ ).
步骤:
1. FOR EACH (c∈Cycles(LockG_Order σ )){
2. 记 c 中的有向弧集合为ε={ε 1 ,ε 2 ,ε 3 ,...,ε n };
3. IF (ε中各条弧对应的操作都属于不同的线程){
4. SegDepFLAG:=0; //SegDepFLAG 用以标记ε中各操作在锁增广分段图中是否具有因果依赖关系
5. FOR EACH (ε i ∈ε){
6. FOR EACH (ε j ∈ε){
7. IF (i≠j){
8. 记ε i 和ε j 对应的操作在段图中所属段的段号为 s i 和 s j ;
9. IF ((s i s j )∨(s j s j )){ //在锁增广段图中两个操作存在执行顺序上的先后依赖关系
10. SegDepFLAG:=1; //SegDepFLAG 为 1,意味着两个操作在分段图中存在因果依赖
11. BREAK;
12. } //IF
13. } //IF
14. } //FORE ACH
15. IF (SegDepFLAG ==1) BREAK;
16. } //FOR EACH
17. IF (SegDepFLAG==0){ //环路中任意两个操作在锁增广段图中均不存在执行因果依赖
18. LockExclusiveFlag=0; //用以标记环路中的锁操作是否存在锁集互斥关系
19. FOR EACH (ε i ∈ε){
20. FOR EACH (ε j ∈ε){
21. IF (i ≠ j ,&&(lockSet ∩ lockSet ≠ ∅ )) {
i ε j ε
22. LockExclusiveFlag=1; //表示任意两个操作对应的持有锁集的交集不为空
23. BREAK
24. } //IF
25. } //FOR EACH
26. IF (LockExclusiveFlag==1) break;
27. } //FOR EACH
28. IF (LockExclusiveFlag==0){ //环路中的操作相互之间均不存在锁集互斥关系
29. 根据定义 4 构造环路 c 对应的“历史持有锁-持有锁”耦合因果关系图 DependG_Lock c ;