多線程并發程序數據競爭修復方法的研究

張曉萱　趙鈺瑋　李天慧　常琳珂　孫瑞男

摘要：針對多線程并發程序中的數據競爭問題，本文提出了一種基于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