多线程并发程序数据竞争修复方法的研究

张晓萱　赵钰玮　李天慧　常琳珂　孙瑞男

摘要：针对多线程并发程序中的数据竞争问题，本文提出了一种基于Java抽象语法树的数据竞争修复办法。首先利用抽象语法树对需要进行插锁的ast节点进行查找，这一过程包括：寻找发生数据竞争的变量所在方法;对发生数据竞争的变量所在的语句进行搜索;对需要加锁的位置进行确定。找到加锁位置后，对需要加锁的位置进行自动加锁操作，从而实现对数据竞争问题的自动修复。

关键词：并发程序;数据竞争;抽象语法树;重构

中图分类号：TP311.53 文献标识码：A 文章编号：1007-9416（2019）03-0058-02

0 引言

多线程并发程序设计随着多核处理器的出现而普及，它能够显著提高系统的资源利用率，是现代程序设计中不可或缺的重要技术[1]。但并发程程序内部固有的并发性和不确定性仍然会带来一些难以避免的问题。数据竞争在所有种类的并发缺陷中占有较大的比例，而且常常是引起其他非死锁类缺陷的根本原因。数据竞争是指多个线程同时访问一个共享内存位置，并且至少有一个线程执行写操作[2]。

当开发人员面对大量缺陷无从入手的时候，自动修复数据竞争问题，可以有效减少开发人员的程序调试时间，因此数据竞争的修复逐渐成为当前软件维护领域中的一个研究热点，目前，并发编程的数据竞争修复问题已经引起国内外研究人员的重视，虽然数据竞争修复技术取得了一定的成果，但仍处于起步阶段，许多问题如修复后程序的一致性和正确性问题等，还有待于进一步研究。

1 数据竞争的修复

1.1 利用抽象语法树进行重构

抽象语法树（abstract syntax tree或者缩写为AST），是源代码的抽象语法结构的树状表现形式，这里特指编程语言的源代码。

1.2 对需要进行插锁的ast节点进行查找

本文利用Java的抽象语法树对插锁的位置进行查找，将程序的源代码解析为抽象语法树，对树上的节点进行操作，可以更加方便、直观的对程序源代码进行修复：

（1）寻找发生数据竞争的变量所在方法。首先找到具有数据竞争的类文件，利用Eclipse AST提供的ASTVisitor中的一系列重载的visit（）和endVisit（）方法在这个类中对发生数据竞争的变量所在的方法进行搜索。在访问到该类型的节点时执行visit（）方法，访问完该类型节点后执行endVisit（）方法。其中，visit（）方法需返回boolean类型的返回值，表示是否继续访问子节点。通过以上思路就可以得到发生数据竞争的变量所在的方法。

（2）对发生数据竞争的变量所在的语句进行搜索。搜索对应的语句需要对MethodDeclaration这个节点所包含的语句进行遍历，遍历的方式为获取MethodDeclaration的Block，Block中的Statements（一个java.util.List集合）包含了方法中的语句，可以通过循环将包含的语句进行遍历。由于一些语句比如while语句中依旧可以包含其它的语句，所以需要对包含子语句的语句进行判断，并遍历这些子语句（这些可以包含子语句的语句也具有Block，可以用相同的方法进行遍历）。

对于每个语句，我们还需要对其中包含的表达式进行分析，识别其是否对发生数据竞争的变量进行了操作或者读取。首先判断是否声明了相同名字的局部变量，再通过ASTVisitor遍历表达式中所包含的simpleName，获得simpleName的名称以及类型并进行判断就可以确定这个语句是否需要被加锁。

（3）对需要加锁的位置进行确定。为了找到需要加锁的位置，我们在遍历语句的同时，将相应的语句储存在一个树的数据结构之中。在这个数据结构中除了记录语句的同时，我们还记录了语句在方法中所处的深度以及这条语句是否需要加上锁。通过这些参数我们可以找到一个合适的插锁位置。

首先找到所有需要加锁的语句，判断它们的深度是否相同，若这些语句的深度不同，深度更深的语句替换为它的父节点，不断的循环此步骤直到所有的语句深度相同。然后判断这些语句的父节点是否为同一个，如不是将这些语句替换为它们的父节点。不断的循环此步骤直到所有的语句的父节点相同。

1.3 加锁

根据分析产生数据竞争的位置，本文提出了一种利用抽象语法树进行重构从而实现对数据竞争的自动插锁功能的方法，以实现对存在数据竞争的语句进行自动修复。

（1）加入Synchronized锁。本文首先利用ast生成synchronized语句，设置synchronized的表达式语句为this，利用ast生成block语句，设置synchronized的body為block。之后将需要加锁的语句加入生成的block语句的statement参数之中，将原来发生数据竞争的语句移除即可实现加锁。

（2）加入ReentrantLock锁。加入ReentrantLock需要引入相应的package，再找到的可编译单元中的imports参数中加入生成的import节点即可。首先利用抽象语法树生成import语句，并设置import语句引入的包为java.util.concurrent.locks.Lock再用相同方法导入java.util.concurrent.locks.ReentrantLock包，将生成的import语句加入编译单元中。

之后实例化ReentrantLock：首先利用ast声明一个VariableDeclaration-Fragment节点，设置名称为lock，被实例化的类为ReentrantLock，设置其修饰符为public，类型为Lock。

最后对相应的语句进行加锁：首先利用ast生成try语句，其次利用ast生成MethodInvocation，用来调用lock方法，并将这个节点加入到try语句的block之中，随后加入需要加锁的语句（同Synchronized加入语句的过程）。

2 結语

多线程并发程序的普及使得数据竞争的修复逐渐成为当前软件维护领域中的一个研究热点。本文提出了一种面向并发程序的数据竞争修复办法，该方法利用抽象语法树进行重构，可以实现对并发程序数据竞争问题的自动修复，有效减少人工修复数据竞争所带来的额外开销，对于并发程序设计水平的提高具有重大意义。

参考文献

[1] M. Batty， K. Memarian， K. Nienhuis， et al. The Problem of Programming Language Concurrency Semantics. Proceedings of European Symposium on Programming Languages and Systems. Berlin： Springer，2015：283-307.

[2] S. LU， S. PARK， E. SEO， et al. Learning from Mistakes： A Comprehensive Study on Real World Concurrency Bug Characteristics. ACM SIGARCH Computer Architecture News，2008，44（3）：11-21.

Research on Data Race Repair Method for Multi-thread Concurrent Programs

ZHANG Xiao-xuan， ZHAO Yu-wei， LI Tian-hui，CHANG Lin-ke，SUN Rui-nan

（College of Information Science and Engineering， Hebei University of Science and Technology， Shijiazhuang Hebei  050000）

Abstract：In order to solve the problem of data competition in multi-thread concurrent programs， this paper proposes a method of repairing data competition based on Java abstract syntax tree. Firstly， the abstract syntax tree is used to find the ast nodes which need to be interlocked. This process includes： finding the method of finding the variables in which the data competition occurs， searching the statements of the variables in which the data competition occurs， and searching the statements of the variables in which the data competition takes place. Determine the location where the lock is required. After finding the locked position， we can automatically fix the problem of data competition by automatically locking the position that needs to be locked.

Key words：concurrent program; data competition; abstract syntax tree; reconstruction