Page 52 - 《软件学报》2021年第12期

3716 Journal of Software 软件学报 Vol.32, No.12, December 2021

例如:图 3 中,当下推自动机处于状态 q 0 、当前输入字符为 r 且栈顶符号为 Z 0 时,则下推自动机由状态 q 0
转移到 q 1 ,并把字符 R 压入栈中.
+
在锁模式定义之前,为了简化表示终态所识别的符号集,首先定义符号串集合 S rc ={r,c} 为字符 r 和 c 组成
+
+
+
的正闭包,S rc ={r,e} 为字符 r 和 e 组成的正闭包,S wc ={r,w,c} 为字符 r,w 和 c 组成的正闭包,S we ={r,w,e} 为字符
r,w 和 e 组成的正闭包,S={S wc S we },其中,字符 c 和字符 e 数量相等.
定义 2(写锁模式的定义). 一个临界区被推断为写锁,当且仅当读写模式序列被终态 q 3 所接受.
+
终态 q 3 所识别的序列为 S w1 ={w} ,表示临界区只包含写操作,将使用写锁进行同步保护.
定义 3(读锁模式的定义). 一个临界区被推断为读锁,当且仅当读写模式序列被终态 q 1 所接受.
+
终态 q 1 所接受的序列集为 S r ={S rc S re } ,其中,字符 c 和字符 e 的数量相同.序列集 S r 不包含字符 w,表示临界
区没有产生负面效应,所以使用读锁.
定义 4(锁降级模式的定义). 一个临界区被推断为锁降级,当且仅当读写模式序列被终态 q 7 所接受.
+
*
+
终态 q 7 所接受的序列集为 S d ={r cS er },表示临界区首先包含读操作或没有,之后是一个 if 判断语句块,其
中,判断语句为读操作,语句块内包含其他操作但至少有一个写操作,if 块之后包含至少一个读操作且只包含读
操作.
定义 5(锁分解模式的定义). 一个临界区被推断为锁分解,当且仅当读写模式序列被终态 q 5 ,q 4 ,q 6 所接受.
*
+
终态 q 5 识别的序列集为 S s1 ={r cS e},表示临界区首先包含读操作或没有,之后是一个 if 判断语句块,判断
语句为读操作,语句块内包含其他操作但至少有一个写操作;终态 q 4 和 q 6 识别的序列表示读写操作分离的临界
区,终态 q 4 所识别的序列集为 S s2 ={S r S w1 },代表临界区前半部分为读操作后半部分为写操作,终态 q 6 所识别的序
列集为 S s3 ={S w1 S r },代表临界区前半部分为写操作后半部分为读操作.
定义 6(下推自动机停机的定义). 当输入读写模式序列为空,或栈顶符号为 V 时,下推自动机停止对读写模
式序列的识别.
当读写模式序列为空时,表示临界区没有操作,则对临界区使用读锁;当栈顶符号为 V 时,所识别的序列集为
S w2 ={C S (S w1 ∪S r ∪S d ∪S s1 ∪S s2 ∪S s3 )},表示读写模式序列不符合细粒度锁规则,临界区将使用写锁进行同步保护.
2.5 重构算法

本节给出了重构算法的设计,首先对相关代码建立 AST;之后遍历 AST 的所有方法节点,找到同步方法和包
含同步块的方法节点;最后,根据负面效应分析得到的读写串对应的锁模式进行重构.重构算法如算法 2 所示.具
体流程如下.
1) 首先获取当前的监视器对象(第 1 行),并判断锁集 LockSet 中是否存在监视器对象所对应的锁对象(第
2 行):如果存在,则从锁集 LockSet 中获得监视器对象对应的锁对象(第 3 行);否则生成一个新的锁对
象,并把监视器对象与锁对象的对应关系存入锁集 LockSet 中(第 5 行、第 6 行);
2) 通过负面效应分析获得 c 对应的临界区读写模式序列 str(第 8 行);
3) 如果 c 为同步方法或同步块,则移除 synchronized 锁,并通过下推自动机识别临界区读写模式序列 str,
根据识别结果进行重构(第 9 行~第 13 行);
4) 最后对重构前临界区 c 和重构后的 c_r 进行一致性检测(第 17 行):如果符合一致性检测规则,返回重
构结果 c_r(第 15 行);否则,将使用写锁对临界区 c 进行重构(第 16 行~第 19 行),其中,Consistency 方法
基于一致性检测规则进行定义(第 3 节给出).
算法 2. 重构算法.
输入:临界区 c;
输出:临界区 c 的重构结果.
1. 获取到临界区 c 对应的监视器对象 M;
2. if m∈LockSet then
3. lockfiled←LockSet(m);