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

张杨 等:基于下推自动机的细粒度锁自动重构方法 3715

15. end for
16. return r;
17. else if 指令为 if 条件判断指令&&判断语句为读操作 then
18. return c;
19. else if 指令为 if 条件判断结束指令 then
20. return e;
21. else return r;
22. end if
23. else return w;
24. end if
2.4 锁推断
在负面效应分析中,使用字符 c 表示一个 if 语句的开始,e 表示一个 if 语句的结束.由于判断语句每一个开
n
n
始对应着一个结束,负面效应分析会产生类似 c Ae (A 代表其他操作)的字符序列,其中,n>0.在匹配过程中,需要
记录 c 和 e 的对应关系,因为 n 的值是不确定的,导致状态的个数也是不确定的,所以我们使用下推自动机对负
面效应分析产生的临界区读写模式序列进行模式匹配,以确定程序重构后的加锁模式.
定义 1. 用于推断细粒度锁模式的下推自动机 M fg =(Q,Σ,Γ,δ,q 0 ,Z 0 ,F)是一个七元组模型,其中,
• Q={q 0 ,q 1 ,…,q 7 }是一个有穷状态集;
• Σ={r,w,c,e}是输入字母表,其中,r 代表一个读操作,w 代表一个写操作,c 代表一个 if 条件判断语句的开
始且条件判断为读操作,e 为一个 if 条件判断语句的结束标志;
• Γ={Z 0 ,C,R,W,D,A,B,V}是有限的堆栈字母表;
• δ=δ(q,x,X)是转移函数,一般使用规则〈q,x,X,q′,T〉代表转移函数,其中:q 为状态符号;x 为输入符号;X 和 T
为栈符号,表示当下推自动机处于状态 q、当前输入字符为 x 且栈顶符号为 X 时,则下推自动机的状态
变为 q′,并用符号串 T 代替栈顶符号 X.符号串 T 有 3 种形式,分别为 X′,X′X,ρ,其中,X′表示用字符 X′替
换栈顶元素,X′X 表示将 X′压入栈中,ρ表示弹出当前栈顶元素;
• q 0 为初始状态;
• Z 0 为初始栈顶符号;
• F={q 1 ,q 3 ,q 4 ,…,q 7 }为终态集.
下推自动机 M fg 的状态转换图如图 3 所示,其中,规则〈q,x,X,q′,T〉在图中表示为〈x,X/T〉,状态 q 到状态 q′的转
移用直线箭头表示.

Fig.3 State transition diagram of pushdown automaton M fg
图 3 下推自动机 M fg 状态转换图