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

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2021,32(12):3710−3727 [doi: 10.13328/j.cnki.jos.006132] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

∗
基于下推自动机的细粒度锁自动重构方法

张 杨, 邵 帅, 张冬雯

(河北科技大学 信息科学与工程学院,河北 石家庄 050018)
通讯作者: 张杨, E-mail: zhangyang@hebust.edu.cn

摘 要: 针对粗粒度锁会严重影响并发程序的可伸缩性问题,提出一种面向细粒度锁的自动重构方法.该方法借
助访问者模式分析、别名分析、负面效应分析等多种程序分析技术获取临界区代码的读写模式,然后使用下推自动
机构建不同锁模式的识别方法,根据识别结果进行代码重构.与以往锁重构方法的不同之处在于,该方法考虑了锁降
级模式,使重构适用性更广.基于此方法,在 Eclipse JDT 框架下,以插件的形式实现了自动重构工具 FLock.在实验中,
从重构个数、改变的代码行数、重构时间、准确性和重构后程序性能等方面对 FLock 进行了评估,并与已有的重
构工具 Relocker 和 CLOCK 进行了对比.对 HSQLDB,Jenkins 和 Cassandra 等 11 个大型实际应用程序的重构结果表
明: FLock 共重构了 1 757 个内置监视器对象,每个程序重构平均用时 17.5s.该重构工具可以有效地实现粗粒度锁到
细粒度锁的转换,与手动重构相比,有效提升了细粒度锁的重构效率.
关键词: 细粒度锁;读写锁;重构;下推自动机;程序分析
中图法分类号: TP311

中文引用格式: 张杨,邵帅,张冬雯.基于下推自动机的细粒度锁自动重构方法.软件学报,2021,32(12):3710−3727. http://www.
jos.org.cn/1000-9825/6132.htm
英文引用格式: Zhang Y, Shao S, Zhang DW. Automated refactoring approach for fine-grained lock based on pushdown
automaton. Ruan Jian Xue Bao/Journal of Software, 2021,32(12):3710−3727 (in Chinese). http://www.jos.org.cn/1000-9825/
6132.htm

Automated Refactoring Approach for Fine-grained Lock Based on Pushdown Automaton

ZHANG Yang, SHAO Shuai, ZHANG Dong-Wen
(School of Information Science and Engineering, Hebei University of Science and Technology, Shijiazhuang 050018, China)
Abstract: As coarse-grained locks have a negative impact on the scalability of concurrent programs, this study proposes an automatic
refactoring approach to convert a coarse-grained lock into a fine-grained one. Several static analyses, such as visitor pattern analysis, alias
analysis, and side-effect analysis are employed in this approach. The read and write pattern of a critical section is inferred by side effect
analysis, and then a push down automaton is proposed to identify the read and write pattern. Finally, refactoring is conducted based on
these results. An automatic tool FLock is implemented as the Eclipse plug-in. The proposed approach is evaluated by eleven open-source
projects including HSQLDB, Jenkins, and Cassandra, by presenting results such as the number of refactored locks, changed lines of code,
refactoring time, accuracy, program performance after refactoring. FLock is also compared with the existing tools Relocker and CLOCK.
The experimental results show that a total of 1757 built-in monitors are refactored and each refactoring takes an average of 17.5 seconds.
The experiments reveal that the proposed tool can help developers convert coarse-grained locks into fine-grained locks effectively.
Key words: fine-grained lock; read-write lock; refactoring; pushdown automaton; program analysis

∗ 基金项目: 国家自然科学基金(61440012); 河北省自然科学基金(18960106D); 河北省高等学校科学研究计划(ZD2019093);
河北省研究生创新资助项目(CXZZSS2020094)
Foundation item: National Natural Science Foundation of China (61440012); National Natural Science Foundation of Hebei
Province (18960106D); Scientific Research Foundation of Hebei Educational Department (ZD2019093); Innovation Foundation Project of
Hebei Province (CXZZSS2020094)
收稿时间: 2020-03-04; 修改时间: 2020-05-10, 2020-06-04; 采用时间: 2020-08-13