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

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

2 面向细粒度读写锁的重构

本节首先给出了重构的整体框架,之后对程序分析方法、基于下推自动机的锁模式推断以及重构算法进行
了介绍.
2.1 重构框架
在重构过程中,首先通过访问者模式对源码对应的抽象语法树进行遍历,主要用到的程序静态分析方法包
括锁集分析、别名分析和负面效应分析:锁集分析用来对监视器对象进行收集,并存储监视器对象和锁对象的
对应关系;别名分析用来解决锁集中的别名问题;负面效应分析用来分析临界区是否产生负面效应,并生成对应
的临界区读写模式序列.下推自动机对临界区读写模式序列进行识别,进而进行锁推断,在读锁、写锁、锁降级、
锁分解这 4 种加锁模式中选择相应的加锁模式并进行重构.在重构之后,需要对重构前后的一致性进行检测,以
保证重构的正确性.面向细粒度锁的重构框架如图 2 所示.

程序分析
AST解析 锁集分析
别名分析 负面效应分析
源程序

下推自动机
读写模式序列
锁推断
写锁 读锁 锁分解 锁降级

重构算法

一致性检测
重构后的程序
Fig.2 Refactoring framework
图 2 重构框架图
2.2 AST解析
在重构框架中,首先对源程序进行解析,生成一个抽象语法树(abstract syntax tree,简称 AST).在具体的解析
过程中,首先通过 Eclipse JDT [14] 获取用户在进行重构操作时所选择的对象,然后将用户选择的对象存放到
ICompilationUnit 对象中,最后将 ICompilationUnit 对象对应的元素解析成 AST.AST 节点的类型很多,每个节点
表示一个源程序中的一个语法结构,包括类型、表达式、语句、声明等.使用访问者模式分析对 AST 上的同步
方法节点以及同步块语句进行遍历,找到同步方法和同步块.在具体的实现过程中,通过继承 EclipseJDT 中提供
的抽象类 ASTVisitor 实现了一个子类作为具体访问者,用于具体类型节点的遍历.
2.3 程序分析方法
2.3.1 锁集分析
在进行重构之前,首先通过访问者模式遍历程序中所有的方法,并对监视器对象进行收集.在重构过程中,
还需要对监视器对象是否产生别名进行判断,进行别名分析.别名是指监视器对象名称不同,但是同时指向相同
的内存地址.对于监视器对象不同的临界区,需要使用不同的锁对象进行重构;对监视器对象相同的临界区,则
使用相同的锁对象进行重构.使用一个键-值对集合对监视器对象和读写锁锁对象的映射关系进行存储,监视器
对象作为键-值对集合的键,监视器对象对应的读写锁对象为键-值对集合的值.
监视器集合定义为 MonitorSet={m 1 ,m 2 ,…,m n },其中,m i 为监视器对象,i∈{1,2,…,n}.监视器 m i 的指向集定义
为 PoniterSet i ,如果对于任意的 m i 和 m j ,i≠j,存在 PoniterSet i ∩PoniterSet j ≠∅,则认为 m i 和 m j 互为别名,并把 m i 和