基于下推自動機的細粒度鎖自動重構方法*

張 楊,邵 帥,張冬雯

(河北科技大學 信息科學與工程學院,河北 石家莊 050018)

鎖是并發程序中用于保護程序狀態和數據訪問正確性的必備措施,然而鎖競爭問題是目前多核/眾核時代影響并發程序性能的主要問題之一.鎖競爭是指當臨界區被一個互斥鎖保護時,如果一個線程獲得了該鎖,那么其他請求訪問該臨界區的線程都將被阻塞,直到持有該鎖的線程釋放該鎖.鎖競爭問題的存在,會嚴重降低程序并行度,損害程序的可伸縮性,降低多核/眾核處理器的執行效率.

不恰當的并發控制方式通常會進一步加劇鎖競爭,程序開發人員有時習慣于使用粗粒度鎖,例如在方法的修飾符中加入synchronized 關鍵字,使整個方法處于鎖的保護之中.這種加鎖方式雖然可以降低程序開發的復雜性,然而由于粗粒度鎖控制的臨界區代碼較長,導致其他想獲取該鎖的線程等待時間增加,往往會加劇鎖競爭.許多開發人員嘗試使用細粒度鎖,相比于粗粒度鎖,細粒度鎖只對一小部分代碼進行加鎖,可以有效減少鎖的持有時間和線程等待時間,減少鎖競爭問題的影響.

與粗粒度鎖比較,使用細粒度鎖并非一件容易的事.要想實現細粒度的加鎖方式,通?？梢圆捎蒙夋i、降級鎖、優化讀鎖等加鎖方式,也可以采用將粗粒度讀寫鎖分解為細粒度讀寫鎖的方式.程序開發人員不僅需要對代碼模式進行分析以確定使用何種細粒度鎖的加鎖方式,而且還需要在同一種方式的不同實現機制之間進行選擇,例如在JDK 中,讀寫鎖和郵戳鎖分別提供了降級鎖,這兩種鎖提供的降級鎖的實現方法截然不同,程序開發人員需要在兩種鎖機制之間進行選擇,增加了細粒度鎖的使用難度.在傳統的方法中,為了使用細粒度鎖,開發人員通常需要手工地對并發程序中使用粗粒度鎖的代碼進行重構.然而這種重構方式既費時費力,還可能會給代碼引入新的錯誤,因此迫切需要對面向細粒度鎖的重構方法進行研究.

目前,針對鎖重構的研究有很多:Tao 等人[1]提出了針對Java 程序根據類屬性域劃分鎖保護域的自動鎖分解重構方法;Yu 等人[2]在進行優化同步瓶頸的研究中提出了一種鎖分解方式;Emmi 等人[3]提出了一種自動鎖分配技術,推斷獲取鎖的位置并確保加鎖的正確性,避免發生死鎖;Kawachiya 等人[4]提出一種鎖保留算法,該算法允許鎖被線程保留;Schafer 等人[5]針對重入鎖及讀寫鎖提出了一種自動重構算法,并實現了重構工具Relocker; Zhang 等人提出了面向可定制鎖[6]和郵戳鎖[7]的自動重構方法;Arbel 等人[8]提出了并發數據結構的代碼轉換,他們的轉換采用基于鎖的代碼,并用樂觀同步替換其中的一些加鎖代碼以減少爭用;Bavarsad[9]針對軟件事務性內存,提出了一種讀寫鎖分配技術來克服全局時鐘的開銷.在工業界,集成在IntelliJ IDEA 上的重構插件LockSmith[10]和基于Eclipse JDT 的并發重構插件[11]都可以實現鎖重構.從目前國內外的研究現狀來看,許多學者已經認識到鎖競爭問題以及并發控制方式在程序設計中的重要性,并對鎖粒度問題以及鎖機制相關的問題進行了研究.但大部分研究是對鎖進行消除和對同步鎖進行分解,對細粒度鎖的重構方法還有待深入研究.

要想實現面向細粒度鎖的自動重構,需要解決以下幾個問題:(1) 代碼分析時需要對臨界區中的每一條語句進行讀寫操作分析,而不能像Relocker[5]工具那樣將整個臨界區代碼作為一個整體進行分析;(2) 在獲取讀寫模式分析后,需要研究如何對讀寫操作模式進行識別,進而推斷出使用哪一種細粒度鎖;(3) 需要研究如何構建由粗粒度鎖到細粒度鎖的重構代碼.

為了解決上述問題,本文提出基于下推自動機的細粒度鎖自動重構方法,通過訪問者模式分析、別名分析、鎖集分析、負面效應分析等程序分析方法獲取臨界區代碼的讀寫模式,然后使用下推自動機構建不同鎖模式的識別方法,根據識別結果進行代碼重構.基于此方法,在Eclipse JDT 框架下,以插件的形式實現了一個自動重構工具FLock.在實驗中,從重構個數、改變的代碼行數、重構時間、準確性和重構后程序性能等方面對FLock進行了評估,并與已有重構工具Relocker[5]和CLOCK[7]進行了對比,對HSQLDB,Jenkins 和Cassandra 等11 個大型實際應用程序的重構結果表明:FLock 共重構了1 757 個內置監視器對象,每個程序重構平均用時17.5s.該重構工具可以有效實現粗粒度鎖到細粒度鎖的轉換,與手動重構相比,有效提升了細粒度鎖的重構效率.

本文的主要貢獻有3 個方面.

1) 提出了一種面向細粒度鎖的自動重構方法;

2) 以Eclipse 插件的形式實現了自動重構工具FLock,可以實現源碼級別的重構,幫助開發者完成從粗粒度鎖到細粒度讀寫鎖的自動轉換;

3) 使用11 個大型實際應用程序對FLock 進行了評估,并與現有工具Relocker 和CLOCK 進行了對比.

本文第1 節介紹本文的研究動機.第2 節介紹面向細粒度鎖的自動重構方法.第3 節展示自動重構工具FLock 的使用界面.在第4 節給出對本文所提出的方法和工具的實驗評估.第5 節對相關工作進行介紹.第6 節是本文的總結.

1 研究動機

讀寫鎖是JDK 1.5 版本中引入的一種鎖機制,它包含一對相互關聯的鎖:讀鎖和寫鎖.寫鎖是一個排它鎖,只能由一個線程持有;讀鎖是一個共享鎖,在沒有線程持有寫鎖的情況下,讀鎖可以由多個線程同時持有,讀鎖允許在訪問共享數據時有更大的并發性.Pinto 等人[12]通過研究SourceForge 上的2 227 個含有并發結構的Java工程發現:Java 并發包還沒有得到良好的應用,只有大約23%有并發編程結構的Java 工程在使用.

為了說明細粒度鎖重構的必要性,我們在代碼結構上進行了說明.圖1 展示了processCached(·)方法的3 種實現方式,該程序段選自讀寫鎖的Java API 文檔[13],是一種典型的緩存處理操作.方法processCached(·)模擬了對數據庫及緩存的操作,首先判斷數據是否存在于緩存中:如果存在,則直接從緩存中讀取數據;如果不存在,則從數據庫中把數據寫入緩存.在圖1(a)中,該方法使用synchronized 進行同步控制,整個方法都處于該鎖的保護下,是一種粗粒度的保護.圖1(b)為使用Relocker[5]進行重構后的代碼,由于該方法中包含對緩存的寫入操作,按照Relocker 的鎖推斷策略,將使用寫鎖對其進行重構.然而我們發現:寫操作的執行僅僅發生在if 語句的條件成立時,如果條件不成立,寫鎖根本不會執行,只需要執行讀操作.如果把全部代碼使用寫鎖進行保護,可能會降低程序的性能.如果使用讀鎖,將允許多個線程同時讀,可以提高程序的并發性.圖1(c)為改進后的代碼,是一種細粒度的加鎖方式.該方式首先獲取讀鎖并判斷cacheValid(第3 行、第4 行):如果if 條件不成立,則直接讀取并釋放讀鎖(第16 行~第20 行);如果成立,則釋放讀鎖獲得寫鎖(第5 行、第6 行).為了保證程序狀態的一致性,這里需要重新對狀態進行判斷(第8 行),因為其他線程可能已經對緩存進行了修改.當從數據庫中寫入緩存之后,獲得讀鎖再釋放寫鎖,完成鎖降級操作(第9 行~第14 行).從圖1(c)可以看到:該方式將一直使用讀鎖,直到寫入的時候再加寫鎖.

Fig.1 Three implementations of the method processCached(·)圖1 processCached(·)方法的3 種實現方式

從上面的例子可以看出:使用鎖降級實現了對臨界區的細粒度保護,加鎖方式更為合理,并且可以在一定程度上減少了鎖競爭.由于讀鎖是共享鎖,允許多個線程同時訪問,在不發生寫入時可以增加程序的并發性.

2 面向細粒度讀寫鎖的重構

本節首先給出了重構的整體框架,之后對程序分析方法、基于下推自動機的鎖模式推斷以及重構算法進行了介紹.

2.1 重構框架

在重構過程中,首先通過訪問者模式對源碼對應的抽象語法樹進行遍歷,主要用到的程序靜態分析方法包括鎖集分析、別名分析和負面效應分析:鎖集分析用來對監視器對象進行收集,并存儲監視器對象和鎖對象的對應關系;別名分析用來解決鎖集中的別名問題;負面效應分析用來分析臨界區是否產生負面效應,并生成對應的臨界區讀寫模式序列.下推自動機對臨界區讀寫模式序列進行識別,進而進行鎖推斷,在讀鎖、寫鎖、鎖降級、鎖分解這4 種加鎖模式中選擇相應的加鎖模式并進行重構.在重構之后,需要對重構前后的一致性進行檢測,以保證重構的正確性.面向細粒度鎖的重構框架如圖2 所示.

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={m1,m2,…,mn},其中,mi為監視器對象,i∈{1,2,…,n}.監視器mi的指向集定義為PoniterSeti,如果對于任意的mi和mj,i≠j,存在PoniterSeti∩PoniterSetj≠?,則認為mi和mj互為別名,并把mi和mj作為別名對〈mi,mj〉存儲在可能別名集AliasSet中.在進行重構之前,首先通過別名集AliasSet構建鎖集LockSet,對別名對中的監視器對象對應的鎖對象進行實例化,并存入鎖集LockSet中.別名對中兩個監視器對象應對應相同的鎖對象,例如別名對〈mi,mj〉在LockSet中表示為兩個鍵值對組合〈mi:lockk〉,〈mj:lockk〉,其中,lockk為鎖對象;而沒有產生別名問題的監視器對象在重構過程中對鎖對象進行實例化,并存入鎖集LockSet中.

2.3.2 負面效應分析

負面效應是指對非本地環境的修改[15],例如一個操作、方法或表達式在執行過程中修改了內存單元,則程序將產生負面效應.由于本文提出的重構方法不僅要重構讀鎖和寫鎖,而且還要進行細粒度的鎖重構,因此負面效應分析需要對整個臨界區進行分析,并生成一個臨界區讀寫模式序列來表示臨界區的讀寫操作.在生成臨界區對應的讀寫模式序列時,使用字符r表示臨界區的一個讀操作,使用字符w表示一個寫操作,使用字符c表示一個if 條件判斷語句的開始且條件判斷為讀操作,使用字符e表示一個if 判斷語句的結束.

本文的負面效應分析通過WALA[16]的中間表示IR 對方法中的指令進行遍歷分析,判斷指令是否修改內存單元.在對方法調用指令進行分析時,為了保證重構工具的執行效率,將方法調用進入的層數限制為5 層.具體分析算法如算法1 所示.

1) 首先獲得臨界區所對應的指令集,調用sideEffectAnalysis方法對每一條指令進行遍歷分析(第1 行~第4 行);

2) 在sideEffectAnalysis方法中,首先對方法調用進入的層數限制進行判斷(第6 行),如果大于限制層數5層,為了保證臨界區安全,將其認定為一個寫操作,返回字符w(第23 行);

3) 之后,對每條指令進行分析,如果指令修改了靜態字段,或修改了實例字段,或修改了堆內存,則當前指令產生了負面效應,返回字符w(第7 行、第8 行);

4) 如果指令是方法調用指令,首先對調用層數的計數器加1(第11 行),之后,遞歸調用sideEffectAnalysis方法對被調用方法里的指令進行分析:若被調用方法包含寫指令,則當前方法調用指令產生了負面效應,返回字符w(第11 行~第15 行);如果當前被調用方法沒有產生負面效應,則返回字符r(第16 行);

5) 如果是if 判斷語句且判斷語句為讀操作,返回字符c;如果指令是if 條件判斷結束指令,則返回字符e(第17 行~第20 行);

6) 其他指令均返回字符r(第21 行).

算法1.負面效應分析算法.

2.4 鎖推斷

在負面效應分析中,使用字符c表示一個if 語句的開始,e表示一個if 語句的結束.由于判斷語句每一個開始對應著一個結束,負面效應分析會產生類似cnAen(A代表其他操作)的字符序列,其中,n>0.在匹配過程中,需要記錄c和e的對應關系,因為n的值是不確定的,導致狀態的個數也是不確定的,所以我們使用下推自動機對負面效應分析產生的臨界區讀寫模式序列進行模式匹配,以確定程序重構后的加鎖模式.

定義1.用于推斷細粒度鎖模式的下推自動機Mfg=(Q,Σ,Γ,δ,q0,Z0,F)是一個七元組模型,其中,

?Q={q0,q1,…,q7}是一個有窮狀態集;

? Σ={r,w,c,e}是輸入字母表,其中,r代表一個讀操作,w代表一個寫操作,c代表一個if 條件判斷語句的開始且條件判斷為讀操作,e為一個if 條件判斷語句的結束標志;

? Γ={Z0,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′壓入棧中,ρ表示彈出當前棧頂元素;

?q0為初始狀態;

?Z0為初始棧頂符號;

?F={q1,q3,q4,…,q7}為終態集.

下推自動機Mfg的狀態轉換圖如圖3 所示,其中,規則〈q,x,X,q′,T〉在圖中表示為〈x,X/T〉,狀態q到狀態q′的轉移用直線箭頭表示.

Fig.3 State transition diagram of pushdown automaton Mfg圖3 下推自動機Mfg 狀態轉換圖

例如:圖3 中,當下推自動機處于狀態q0、當前輸入字符為r且棧頂符號為Z0時,則下推自動機由狀態q0轉移到q1,并把字符R壓入棧中.

在鎖模式定義之前,為了簡化表示終態所識別的符號集,首先定義符號串集合Src={r,c}+為字符r和c組成的正閉包,Src={r,e}+為字符r和e組成的正閉包,Swc={r,w,c}+為字符r,w和c組成的正閉包,Swe={r,w,e}+為字符r,w和e組成的正閉包,S={SwcSwe},其中,字符c和字符e數量相等.

定義2(寫鎖模式的定義).一個臨界區被推斷為寫鎖,當且僅當讀寫模式序列被終態q3所接受.

終態q3所識別的序列為Sw1={w}+,表示臨界區只包含寫操作,將使用寫鎖進行同步保護.

定義3(讀鎖模式的定義).一個臨界區被推斷為讀鎖,當且僅當讀寫模式序列被終態q1所接受.

終態q1所接受的序列集為Sr={SrcSre}+,其中,字符c和字符e的數量相同.序列集Sr不包含字符w,表示臨界區沒有產生負面效應,所以使用讀鎖.

定義4(鎖降級模式的定義).一個臨界區被推斷為鎖降級,當且僅當讀寫模式序列被終態q7所接受.

終態q7所接受的序列集為Sd={r*cS+er+},表示臨界區首先包含讀操作或沒有,之后是一個if 判斷語句塊,其中,判斷語句為讀操作,語句塊內包含其他操作但至少有一個寫操作,if 塊之后包含至少一個讀操作且只包含讀操作.

定義5(鎖分解模式的定義).一個臨界區被推斷為鎖分解,當且僅當讀寫模式序列被終態q5,q4,q6所接受.

終態q5識別的序列集為Ss1={r*cS+e},表示臨界區首先包含讀操作或沒有,之后是一個if 判斷語句塊,判斷語句為讀操作,語句塊內包含其他操作但至少有一個寫操作;終態q4和q6識別的序列表示讀寫操作分離的臨界區,終態q4所識別的序列集為Ss2={SrSw1},代表臨界區前半部分為讀操作后半部分為寫操作,終態q6所識別的序列集為Ss3={Sw1Sr},代表臨界區前半部分為寫操作后半部分為讀操作.

定義6(下推自動機停機的定義).當輸入讀寫模式序列為空,或棧頂符號為V時,下推自動機停止對讀寫模式序列的識別.

當讀寫模式序列為空時,表示臨界區沒有操作,則對臨界區使用讀鎖;當棧頂符號為V時,所識別的序列集為Sw2={CS(Sw1∪Sr∪Sd∪Ss1∪Ss2∪Ss3)},表示讀寫模式序列不符合細粒度鎖規則,臨界區將使用寫鎖進行同步保護.

2.5 重構算法

本節給出了重構算法的設計,首先對相關代碼建立AST;之后遍歷AST 的所有方法節點,找到同步方法和包含同步塊的方法節點;最后,根據負面效應分析得到的讀寫串對應的鎖模式進行重構.重構算法如算法2 所示.具體流程如下.

1) 首先獲取當前的監視器對象(第1 行),并判斷鎖集LockSet中是否存在監視器對象所對應的鎖對象(第2 行):如果存在,則從鎖集LockSet中獲得監視器對象對應的鎖對象(第3 行);否則生成一個新的鎖對象,并把監視器對象與鎖對象的對應關系存入鎖集LockSet中(第5 行、第6 行);

2) 通過負面效應分析獲得c對應的臨界區讀寫模式序列str(第8 行);

3) 如果c為同步方法或同步塊,則移除synchronized 鎖,并通過下推自動機識別臨界區讀寫模式序列str,根據識別結果進行重構(第9 行~第13 行);

4) 最后對重構前臨界區c和重構后的c_r進行一致性檢測(第17 行):如果符合一致性檢測規則,返回重構結果c_r(第15 行);否則,將使用寫鎖對臨界區c進行重構(第16 行~第19 行),其中,Consistency 方法基于一致性檢測規則進行定義(第3 節給出).

算法2.重構算法.

輸入:臨界區c;

輸出:臨界區c的重構結果.

3 一致性檢測

FlexSync[17]是一個可以通過施加不同標記在不同同步機制之間進行重構轉換的工具,FlexSync 中定義了一致性檢查規則,以此來檢查在不同同步機制之間轉換的一致性.為了盡可能地保證重構的正確性,本節參照FlexSync 的一致性檢測規則,給出了FLock 重構前后的一致性檢測規則.在給出規則之前,我們首先對相關的內容進行了定義.

定義7(臨界區集合).一個應用程序P中所有臨界區的集合定義為C={c1,c2,…,cn}.對于?ci∈C(1≤i≤n),ci={ci1,ci2,…,cik}表示ci被劃分為k個細粒度的臨界區.

由于P中的代碼是有限的,因此C是一個有限集合,對于?ci∈C(1≤i≤n),ci表示某一個臨界區.ci中可以包含若干讀寫操作opi1,opi2,…,opir,表示為{opi1,opi2,…,opir}?ci.

Cbefore和Cafter分別表示重構前和重構后的臨界區集合,由于FLock 在重構時需要分割臨界區,因此|Cbefore|< |Cafter|,其中,|C|表示集合C元素個數.

定義8(重構前鎖集合).一個應用程序P中所有用于保護臨界區的鎖集合定義為集合S={s1,s2,…,sm}.

由于C是有限集合,所以S也是一個有限集合.由于一個鎖可以保護多個臨界區,故m≤n.對于?se∈S,se表示既包含加鎖操作又包含解鎖操作.

定義9(鎖保護).對于?ci∈C(1≤i≤n),?se∈S(1≤e≤m),如果臨界區ci處于鎖se的保護中,則定義保護關系為se⊙{ci}.進一步,一個鎖可以保護多個臨界區,定義為se⊙Ck,其中,Ck是Cbefore的子集,即Ck?Cbefore.

定義10(重構后鎖集合).一個應用程序P中重構之后所有的鎖集合定義為集合L={l1,l2,…,lt}.對于?la∈L(1≤a≤t),la⊙Cv,Cv是Cafter的子集,即Cv?Cafter.

定義11(鎖狀態原子性保持).對于?la∈L,如果la在沒有釋放鎖的情況下完成鎖狀態切換,則說明鎖狀態原 子性沒有被破壞,定義其為?la,否則定義為.

定義11 說明了鎖狀態的原子性問題,舉例來說:讀寫鎖在由寫鎖切換為讀鎖時,可以不用釋放該鎖,在該鎖的內部完成鎖狀態的切換.

定義 12(重構前后鎖的對應關系).重構前,對于?ck∈C(1≤k≤n),?se∈S(1≤e≤m),se⊙Ck;重構后,對于?cv∈C(1≤v≤n),?la∈L(1≤a≤t),la⊙Cv.如果Cv?Ck,則se和la之間存在一一對應關系,記為se≡la.

定義13(Happens-before 關系).對于?ci∈C,{opi1,opi2,…,opir}?ci,?u,v(1≤u≤r,1≤v≤r),如果opiu先發生于opiv,則定義Happens-before 關系為opiu≥opiv.依據Happens-before 關系的傳遞性,如果opiu≥opiv并且opiv≥opiw,則opiu≥opiw.

Happens-before 關系的定義是建立在Java 內存模型基礎上的讀寫操作發生序關系,是Java 語言內存一致性的重要準則.該關系建立的方式之一是通過程序中的同步關系,解鎖操作之前的操作先發生于解鎖之后獲取該鎖的操作.

基于如上的定義,下面給出了重構的一致性檢測規則.

規則1.對于重構前,?ci∈C(1≤i≤n),?se∈S(1≤e≤m),使得se{⊙ci};重構后,ci={ci1,ci2,…,cik},對于?cij(1≤i≤n,1≤j≤k),?la∈L(1≤a≤t),使得la{⊙cij}.

規則1 說明了重構之前處于鎖保護的臨界區,在重構之后仍處于鎖的保護中.

規則2.對于重構前,?ci∈C(1≤i≤n),?se∈S(1≤e≤m),使得se{⊙ci};重構后,ci={ci1,ci2,…,cik},對于?cij(1≤i≤n,1≤j≤k),?la∈L(1≤a≤t),如果有la{⊙cij},則se≡la.

規則2 說明:如果重構前臨界區ci在se的保護中,即使重構后ci被分割為多個臨界區,保護這些臨界區的鎖la和se之間存在一一對應的關系.如果所有的鎖都可以被重構,那么重構前后的鎖集合應滿足|S|=|L|.需要說明的是:對于FLock 重構前后鎖的一一對應關系,通常表現在同步鎖的監視器對象和讀寫鎖對象的一一對應關系上.

規則1 和規則2 從重構前后代碼結構上進行了一致性說明,保證了代碼結構的完整性.

由于FLock 在進行面向細粒度鎖重構時主要采用了降級鎖和鎖分解兩種方式,下面主要針對這兩種方式進行規則定義.

規則3.重構前,對于?ci∈C(1≤i≤n),?se∈S(1≤e≤m),使得se{⊙ci};重構后,ci={ci1,ci2,…,cik},如果?la∈L(1≤a≤t),使得se≡la,對于?cij(1≤i≤n,1≤j≤k),有(la{⊙cij})∧()成立,則鎖降級重構前后可以保證一致性.

規則3 主要針對降級鎖的重構進行了約束.雖然鎖降級過程中會由寫鎖降級為讀鎖,但該過程是在鎖的內部進行轉換的,期間并沒有釋放鎖,可以保證鎖的原子性,所以鎖降級重構前后是一致的.

規則4.重構前,對于?ci∈C(1≤i≤n),?se∈S(1≤e≤m),使得se{⊙ci};重構后,ci={ci1,ci2,…,cik},如果?la∈L(1≤a≤t),使得se≡la,且對于?cij(1≤i≤n,1≤j≤k),有(la{⊙cij})∧().當{opi1,opi2,…,opir}?ci時,對于?opip,opiq(1≤p≤r,1≤q≤r),如果在Cbefore中opip≥opiq,則在Cafter中仍有opip≥opiq.

規則5.重構前,對于?ci∈C(1≤i≤n),{opi1,opi2,…,opir}?ci,?se∈S(1≤e≤m),使得se{⊙ci};重構后,ci={ci1,ci2,…,cik},如果?la∈L(1≤a≤t),有se≡la,且對于?cix,ciy(1≤i≤n,1≤x≤k,1≤y≤k,x≠y),有(la{⊙cix,ciy})∧().對于 ?opip,opiq(1≤p≤r,1≤q≤r),如果{opip}?cix,{opiq}?ciy,opip和opiq訪問同一內存位置并且opip或opiq是寫操作,則不能進行鎖分解.

規則4 和規則5 共同保證了鎖分解重構的一致性.規則4 對鎖分解的重構進行了約束,該規則通過檢查臨界區讀寫語句的Happens-before 關系,確保該關系在重構前后沒有改變.在FLock 工具的重構對象中,重構前后代碼都涉及同步關系,可以在同步關系的基礎上建立Happens-before 關系,進而進行規則判定.規則5 從保持原有臨界區的原子性角度對鎖分解進行了約束,確保原有臨界區的原子性沒有被破壞.如果存在opip和opiq訪問同一內存位置,有可能因為線程交互而改變原有操作語義,在這種情況下,FLock 只推斷一個寫鎖而不進行鎖分解.

4 重構工具實現

FLock 是在Eclipse JDT 框架下設計并以Eclipse 插件的形式實現的,對Eclipse 中的基礎類Refactoring 和UserInputWizardPage 等進行擴展,實現相關的重構邏輯設計和可視化的重構工具界面設計.FLock 重構界面截圖如圖4 所示,展示了重構前后的代碼之間的對比,其中,左側為重構前的代碼,右側為重構后代碼的預覽.

Fig.4 Screenshot of the FLock圖4 FLock 重構工具界面

5 實驗評估

本節對所提出的方法和工具進行了實驗評估.首先對實驗配置和測試程序進行介紹,然后從重構數目、改變的代碼行數和時間等方面給出了實驗結果,并對結果進行了分析[18].

5.1 實驗配置

所有實驗都是在HP Z240 工作站上完成的,該工作站搭載Intel Core i7-7700 處理器,該處理器主頻為3.6GHz,有4 個處理核,均支持超線程技術,可以支持8 個線程同時運行,內存為8GB.軟件上,操作系統使用Ubuntu 16.04,使用Eclipse 4.12.0 作為重構工具的開發平臺,使用JDK 1.8.0_221 和程序分析工具WALA 1.52.

5.2 測試程序

本文選取了11 個實際應用程序來驗證我們重構工具的有效性和適用性,這些應用程序包括HSQLDB[19],Jenkins[20],Cassandra[21],SPECjbb2005[22],JGroups[23],Xalan[24],Fop[25],RxJava[26],Freedomotic[27],Antlr[28],MINA[29].其中,HSQLDB 是一個開源的Java 數據庫,Cassandra 是Apache 公司的開源分布式NoSQL 數據庫系統,Jenkins是一個開源的自動化服務器,JGroups 是群組通信工具,SPECjbb 2005 是Java 應用服務器測試程序,Xalan 和Fop分別是Apache 公司的XSLT 轉換處理器和格式化對象處理器,RxJava 是Netflix 公司的在Java VM 上使用可觀測的序列來組成異步的、基于事件的程序的庫,Freedomotic 是一個開源的物聯網框架,Antlr 是一個解析器生成器,MINA 是Apache 公司的網絡應用框架.這些程序的版本號信息、包含同步方法和同步塊的個數以及源碼行數見表1.

5.3 實驗結果及分析

在實驗中,使用FLock 對11 個測試程序進行自動重構,對重構個數、代碼行數、重構后程序的準確性進行了驗證,并與重構工具Relocker 和CLOCK 進行了對比.

5.3.1 鎖重構個數

我們首先對FLock 重構后的不同類型鎖個數進行了匯總,重構結果見表2.

從實驗結果可以看出:在11 個程序中,共有391 個粗粒度鎖重構為細粒度鎖.內置監視器對象轉換為鎖降級模式的個數有25 個,其中,HSQLDB 中最多,包含6 個,集中分布在org.hsqldb 包里的Session 類和Table 類中,這兩個類分別是用來執行session 和保存數據庫表的數據結構和方法;在RxJava 和MINA 中,由于原程序中包含的內置監視器對象較少,在重構之后沒有監視器對象轉換為鎖降級模式.內置監視器對象轉換為鎖分解模式的個數為127 個,在HSQLDB,Cassandra 和JGroups 測試程序中重構后轉換為鎖分解模式的個數較多;測試程序Fop 中包含32 個內置監視器對象,重構后沒有內置監視器轉換為鎖分解模式.在重構為讀鎖方面,有293 個內置監視器對象轉換為讀鎖,在測試程序HSQLDB 和Cassandra 中,讀鎖的占比相對較高;在程序Antlr 和MINA 中,使用鎖分解模式比使用讀鎖的個數多.

Table 1 Benchmarks and their configuration表1 測試程序及其配置

Table 2 Refactoring results by FLock表2 FLock 重構結果

Table 3 Comparison of Relocker and FLock表3 Relocker 和FLock 重構對比

Table 4 Comparison of CLOCK and FLock表4 CLOCK 和FLock 重構對比

在重構工具FLock 中,加入了對臨界區的一致性規則檢測,表2“違背一致性規則”列展示了不滿足一致性檢測的臨界區數目.對于所有的測試程序,除了MINA 測試程序外,其余10 個程序均存在違背一致性檢測規則的情況發生,共有139 個,其中,HSQLDB 中最多,有41 個.對于這些不滿足一致性規則的臨界區,我們沒有對他們進行鎖分解,而是采用寫鎖作為臨界區的保護模式.

5.3.2 重構前后改變的代碼行數

我們對重構前后改變的代碼行數進行了統計,這些代碼行數的改變在一定程度上反映了程序員在手動重構時所需要花費的工作量.我們使用SLOCCount(https://dwheeler.com/sloccount/)工具對代碼行數進行統計,該工具是由David A.Wheeler 開發的用于精確統計代碼行數的工具,不僅適用于多個操作系統平臺,而且適合于多種語言.

11 個測試程序共包含1 429 775 行代碼,重構后代碼行數為1 439 779 行,增加了10 004 行代碼.由于重構前使用的是同步鎖,重構后使用的讀寫鎖需要顯示的加鎖和解鎖,并且需要使用try-finally 語句塊,所以重構后會增加代碼行數.對于HSQLDB 測試程序,由于其包含的同步鎖數目最多,重構前后改變的代碼行數也最多,達到 3 756 行;對于Jenkins,Cassandra,SPECjbb2005 和JGroups 測試程序,由于它們包含的同步鎖數目在100 到300之間,代碼改變的行數也較多,分別增加了1 762 行、1 420 行、782 行和1 241 行;對于RxJava,Freedomotic,Antlr和MINA 測試程序,由于包含的同步鎖較少,代碼行數的改變也較少,分別有171 行、274 行、59 行和67 行.

這些代碼行數在一定程度上體現了程序開發人員重構程序時的工作量,如果使用手動重構的方式,開發人員需要首先在程序中找到同步鎖出現的位置,然后進行修改.例如:在手動重構HSQLDB 測試程序時,需要在17萬行的代碼中尋找684 個同步鎖并進行重構,最終結果會增加3 756 行代碼,這種手動重構耗時較長并且容易給程序引入新的錯誤,對于該測試程序,我們發現同步鎖大部分分布在org.hsqldb 包中,分布相對比較集中;在FOP中,32 個內置監視器對象在重構后只增加235 行代碼,但32 個監視器對象分布在2 034 個java 文件中,分布非常稀疏,遍歷過程十分耗時.在使用我們開發的自動重構工具重構HSQLDB 和FOP 時,分別僅需要18s 和15s 即可完成,可以大大節省程序員的工作量.

5.3.3 重構時間

11 個測試程序重構的總耗時為192s,每個程序平均耗時17.5s,見表2.HSQLDB 中監視器對象較多,有684個監視器對象,重構耗時為18s;程序Cassandra 規模相對較大,源碼行數為431 022 行,重構耗時為73s;JGroups和Xalan 重構耗時分別為24s 和19s;SPECjbb2005,RxJava,Freedomotic,Antlr 和MINA 的程序規模相對較小,重構耗時約為2s~8s.通過對這些程序的重構時間進行分析,我們發現:重構工具在重構時的時間消耗主要是用于程序的靜態分析上,程序越大,靜態分析時間越長,造成總的重構時間也越長.對于FOP 測試程序中,源碼行數為198 555 行,雖然其與HSQLDB 程序的代碼規模相當,但其中包含同步鎖個數非常少,分布相對比較稀疏,通過手動的方式進行重構會花費大量的時間在搜索代碼上;而FLock 可以自動地完成重構,用時也僅僅為15s,大大減少重構耗時,有效提高開發效率.

5.3.4 重構的正確性

為了對重構后測試程序的正確性進行驗證,我們主要從以下3 個方面進行了驗證,包括驗證推斷鎖的類型是否正確、加鎖和解鎖的位置是否正確、鎖結構的使用是否正確.由于目前沒有相關的自動驗證工具,我們主要采用了手工檢查的方式.

在驗證推斷鎖類型的準確性方面,我們手動地檢查每一個測試程序中每一個臨界區的代碼,我們發現:推斷出來的每一個鎖都符合我們的推斷規則,都是正確的類型.此外,我們發現:在Cassandra 測試程序中,部分代碼在重構前就使用了讀寫鎖.我們將這些讀寫鎖重構為同步鎖,然后使用Flock再對其進行重構,結果發現:Flock推斷的鎖類型和原有的鎖類型基本相同,只有一處存在不同之處.該處發生在CompactionStrategyManager 類的maybeReload 方法中,該方法原本使用寫鎖,但是Flock 將其推斷為鎖分解的方式,經過手工檢查發現:使用鎖分解的方式并未改變程序原邏輯,是正確的細粒度加鎖方式.

在判斷加鎖和解鎖位置以及鎖的使用方面,我們主要檢查了:(1) 每種鎖的加鎖操作是否對應一個解鎖操作;(2) 解鎖操作是否被放入finally 語句塊中;(3) 細粒度鎖的結構是否正確.經過檢查,我們并未發現相關錯誤.我們也通過運行程序的方式檢查了程序的正確性,發現這些程序在執行過程中并沒有報錯,都可以正確運行.

5.3.5 重構前后性能對比

本節選取HSQLDB,Jenkins,Cassandra,JGroups 和SPECjbb2005 進行性能測試.之所以選擇這5 個程序,是因為它們在發布的版本中都提供了相應的基準測試程序.

HSQLDB 提供了JDBCBench 測試程序,該程序的測試結果如圖5 所示,其中:橫坐標為處理事務數,分別給出了事務數為100k,200k,300k 和400k 的情況;縱坐標為事務處理率.從圖中可以看出:該測試程序在處理100k個事務時,程序重構后使用細粒度讀寫鎖的事務率比重構前使用同步鎖的事務率略有提升,但不明顯;在處理事務量達到200k,300k 和400k 時,重構后比重構前的程序在事務率上的提升大約有15%,19%和22%,提升較為明顯.總的來說,HSQLDB 使用細粒度的讀寫鎖在事務率方面重構后比重構前平均提升了18%,說明使用細粒度鎖有助于提升HSQLDB 的性能,而我們設計的工具可以幫助更快地轉換為細粒度鎖.

對于Jenkins,我們選取了其中的單元測試程序UpdateCenterTest,FunctionsTest 和FilePathTest 進行了測試.圖6 給出了3 個單元測試的執行時間,可以看出:單元測試UpdateCenterTest 在重構前后程序的執行時間基本沒有變化,而FunctionsTest 在重構后執行時間縮短了17.3%,FilePathTest 在重構后執行時間縮短了20.9%.

Fig.5 Performance comparison of the HSQLDB benchmark before and after refactoring圖5 HSQLDB 重構前后的性能比較

Fig.6 Performance comparison of the Jenkins benchmark before and after refactoring圖6 Jenkins 重構前后的性能比較

對于JGroups,我們選取了測試程序RoundTrip,RoundTripRpc,UnicastTest 和UnicastTestRpc 進行測試,這4個測試程序都是測試兩個群組之間消息的發送與接收能力.實驗結果如圖7 所示,其中,橫坐標為測試程序,縱坐標為請求處理率.從結果中可以看出:4 個測試在重構后請求處理率都有所提升,分別提升了15.5%,7%,5%和9%.

對于測試程序Cassandra,我們選取了其中的單元測試程序BatchTests,SimpleQueryTest 和ManyRowsTest進行性能測試,圖8 給出了3 個單元測試程序重構前后的執行時間.對于單元測試程序BatchTests,Cassandra 重構后程序的執行時間與重構前程序的執行時間基本相同;對于SimpleQueryTest 和ManyRowsTest 這兩個單元測試程序,執行時間都有不同程度的下降,都較重構前的執行時間大約縮短了7%.

Fig.7 Performance comparison of the Jgroups benchmark before and after refactoring圖7 JGroups 重構前后的性能比較

Fig.8 Performance comparison of the Cassandra benchmark before and after refactoring 圖8 Cassandra 重構前后的性能比較

圖9 給出了SPECjbb 2005 運行結果,其中,圖9(a)給出了吞吐量隨線程數變化的情況,圖9(b)給出了堆內存使用的百分比隨著線程數變化的情況.從圖9(a)可以看出:當吞吐量達到峰值之后,使用同步鎖的吞吐量要比使用細粒度讀寫鎖的吞吐量稍微高一些.這也說明并不是所有情況下,使用細粒度讀寫鎖性能都比使用同步鎖要好.圖9(b)給出了在不同線程執行情況下使用的堆內存占總內存的百分比,在線程數為8 時,程序重構前的堆內存使用占比高于程序重構后;而在線程數為12 時,程序重構后的堆內存使用占比高于程序重構前.這說明在不同鎖模式和不同線程數下堆內存的使用情況各有不同,而我們設計的重構工具為開發人員提供一種快速的細粒度鎖和粗粒度鎖重構的方式,開發人員可以通過測試來找到程序堆內存使用最合適的情況.

Fig.9 Performance comparison of the SPECjbb2005 benchmark before and after refactoring圖9 SPECjbb2005 重構前后的性能比較

5.3.6 工具對比

我們將FLock 和已有的重構工具Relocker[5]進行了對比.Relocker 是Schafer 等人設計實現的一個自動重構工具,可以把同步鎖重構為可重入鎖或讀寫鎖.該工具是一種粗粒度鎖的推斷模式,不能實現細粒度的加鎖模式.由于Relocker 工具開發較早,不支持高版本的JDK,因此在該實驗中使用的JDK 版本為1.6.測試程序選擇了HSQLDB 和Cassandra,版本分別為1.8.0.10 和0.4.0(比表1 的版本低),這兩個程序中包含的同步鎖的數量也較之前實驗選取的版本有所不同:HSQLDB 總共包含266 個同步鎖,Cassandra 總共包含57 個同步鎖.我們也嘗試使用Relocker 對其他測試程序進行重構,但由于Relocker 開發較早,均不支持對這些版本進行重構.

表3 給出了Relocker 和FLock 重構結果的對比,可以看出:Relocker 只使用讀鎖或寫鎖進行同步保護,而且還存在不能重構的問題;FLock 不僅可以推斷讀鎖和寫鎖,而且可以實現更為細粒度的鎖重構.在讀鎖的推斷上,FLock 比Relocker 推斷出了更多的讀鎖,經人工驗證,使用FLock 進行重構后的讀鎖使用正確.Relocker 的推斷結果不準確的原因可能與分析深度有關,這里的分析深度使用的是Relocker 的默認值.在重構時間上,Relocker重構HSQLDB 耗時7s,FLock 耗時6s;Cassandra 程序規模較大,Relocker 重構耗時50s,FLock 重構耗時42s.總體來看,FLock 在重構效率上有所提升.

我們還將FLock 與重構工具CLOCK[7]進行了對比,CLOCK 是一個面向郵戳鎖的自動重構工具.這里選取了本文實驗中監視器對象相對較多的7 個測試程序進行重構對比,實驗結果見表4.由于郵戳鎖是不可重入鎖,所以CLOCK 對部分臨界區不能執行重構,其中,HSQLDB 和SPECjbb 2005 包含較多不能重構的鎖,分別為61和75 個;由于CLOCK 在鎖推斷上和FLock 不同,所以在鎖降級重構數量上也有所差異.兩個工具在重構效率上,CLOCK 在重構HSQLDB,Cassandra 和Fop 時比FLock 慢1s~2s,其他程序在重構時間上基本一致.

關于重構后程序性能方面,我們對HSQLDB 和SPECjbb2005 這兩個程序使用不同重構工具重構后,使用3種鎖的性能進行了對比.HSQLDB 的實驗結果如圖10 所示,結果表明,粗粒度的讀寫鎖和郵戳鎖在事務率上要低于使用細粒度讀寫鎖的程序.SPECjbb2005 的實驗結果如圖11 所示,由于JDK 版本原因,Relocker 不能對SPECjbb2005 進行重構,這里只對比了CLOCK 和FLock 的重構結果.可以看出:程序在使用細粒度讀寫鎖時,相較于使用粗粒度讀寫鎖和郵戳鎖的程序,事務率有明顯提升.

Fig.10 Performance comparison of the HSQLDB benchmark after refactoring圖10 HSQLDB 重構后的性能比較

Fig.11 Performance comparison of the SPECjbb2005 benchmark after refactoring圖11 SPECjbb2005 重構后的性能比較

5.3.7 有效性威脅

實驗中有幾個可能威脅有效性的因素.

1) 由于并發程序執行的不確定性,不排除性能測試實驗結果可能存在細微的偏差.為了避免誤差,我們所有實驗結果都是在10 次運行的基礎上取平均值得到的;

2) 在實驗中,我們采用手工檢查的方式對重構后程序的正確性進行驗證.手動的檢查方式存在著一些不足之處,可能會出現人為驗證不準確等問題.為了減少不準確情況的發生概率,我們選取了兩組學生分別進行兩次檢查的方式,盡可能避免出現問題;

3) 本實驗只選取了11 個應用程序對FLock 進行了評估,它們并不能代表所有程序,不能完全證明FLock在所有的應用程序中可以成功完成重構.但是我們選取的應用程序涉及數據庫、群組通信、物聯網等多個領域,具有很好的代表性.未來的工作中,我們也將使用更多應用程序對FLock 進行測試.

6 相關工作

本文實現了面向細粒度讀寫鎖的自動重構工具,我們主要關注的相關工作有兩個方面:面向鎖的優化和自動化的重構工具.

6.1 面向鎖的優化

Emmi 等人[3]提出了一種自動鎖分配技術,采用帶有原子性規范的注解對程序進行標記,自動推斷程序中應該獲取鎖的位置.Kawachiya 等人[4]提出一種鎖保留算法,該算法允許鎖被線程保留,當一個線程嘗試獲得鎖操作時,如果線程保留了該鎖,它就不用執行獲取鎖的原子操作;否則,線程使用傳統的方法獲得鎖.Halpert 等人[30]提出了基于組件的鎖分配技術,用于分析數據依賴性,自動將具有可調粒度的鎖對象分配給臨界區.Tamiya Onodera 等人[31]設計了一種基于鎖保留的自旋鎖,并使用這種自旋鎖替換傳統的自旋鎖.Arbel 等人[8]提出了使用樂觀同步替換程序中的一些加鎖代碼,以減少爭用,可以在不犧牲正確性的情況下提高其可擴展性.Bavarsad[9]針對軟件事務性內存,提出了兩種優化技術來克服全局時鐘的開銷:第一種技術是讀寫鎖定分配,它不利用任何中央數據結構來保持事務的一致性,僅當事務成功提交時,此方法才能提高軟件事務性內存的性能;第二種優化技術是一種動態選擇基線方案的自適應技術,用來減小讀寫鎖定分配的成本.Gudka[32]提出了一種針對Java 的鎖定推斷方法,使用鎖定推斷來實現原子塊,該方法可以全面分析Java 庫方法.以上工作的研究目的與我們相似,通過鎖分配、鎖保留、原子塊等技術減少臨界區競爭;而我們使用鎖降級、鎖分解實現對臨界區的細粒度保護方式,從而減少臨界區競爭.

Hofer 等人[33]提出了一種通過跟蹤Java 虛擬機中的鎖定事件來分析Java 應用程序中的鎖爭用的方法,該方法不僅檢測線程在鎖上被阻塞情況,還檢測是哪個其他線程通過持有該鎖來阻止它,并記錄它們的調用鏈.Tallent[34]提出了3 種量化鎖爭用的方法,可以在低開銷的前提下,有效提供鎖爭用檢測精度.Inoue[35]提出了一個基于Java 虛擬機,使用硬件性能計數器來檢測應用程序獲取鎖的位置以及阻塞位置的方法.以上研究是用于揭示鎖爭用的原因以及識別鎖性能瓶頸的分析工具,我們的研究提出的是一個解決鎖爭用問題的重構工具.

6.2 自動化的重構工具

Dig 等人提出了一個軟件并行化重構工具CONCURRENCER[36],該工具可以將串行的Java 代碼進行并行化重構,以及面向循環并行化重構的重構工具Relooper[37].Wloka 等人[38]提出了一個用于把串行程序轉變為可重入的程序的自動重構工具Reentrancer,從而使程序更易并行化實現.Brown 等人[39]提出了一個用于生成并行程序的重構工具ParaPhrase,從而增加并行程序的可編程性.以上研究以各種形式實現了重構工具,并很好地實現了工具的自動化,但都是面向并發程序的自動重構工具,而我們的工具是面向鎖的自動重構.

McCloskey[40]提出了悲觀的原子塊,在不犧牲性能或兼容性的情況下,保留了類似事務性內存中樂觀原子塊的許多優點,并實現了自動重構工具Autolocker.Sch?fer 與IBM T.J.Watson 研究中心合作設計了一種面向Java 顯示鎖的重構工具Relocker[5],它能將同步鎖重構為可重入鎖,以及將可重入鎖重構為讀寫鎖.與Relocker相比,我們的重構方法引入了鎖降級、鎖分解模式,使重構的適用性更廣.Zhang 等人[6]提出了一種用于在字節碼級別鎖重構方法,由于在字節碼層實現,可視性較差一些;我們的重構工作直接在源代碼層實現,轉換過程更直觀.Zhang 等人[7]提出了一個面向郵戳鎖的自動重構工具CLOCK,該重構工具支持優化讀鎖和鎖升級等操作,但是受限于郵戳鎖的非可重入性,適用范圍有限.我們的研究面向細粒度鎖的重構則不受該限制.

Tao 等人[1]提出了針對Java 程序、根據類屬性域劃分鎖保護域的自動鎖分解重構方法,并以Eclipse 插件形式實現了自動重構工具.Yu 等人[2]在進行優化同步瓶頸的研究中提出了一種鎖分解方法,該方法重新構造鎖的依賴關系,使用細粒度的鎖來保護不相交的共享變量集,并實現了工具SyncProf.Greenhouse 等人[41]根據類的功能將對象的狀態劃分為多個子區域,然后通過不同的鎖來保護每個分區鎖分解方法.在工業界,得到廣泛應用的重構工具包括集成在IntelliJ IDEA 上的重構插件LockSmith[10]以及一個基于Eclipse JDT 的并發重構插件[11],這兩個插件都可以實現鎖分解、鎖合并等重構.以上研究均是通過不同鎖對象對類中的方法實現鎖分解,我們的研究是通過讀寫鎖的分離在方法內實現鎖分解.

7 總 結

本文提出了一種面向細粒度鎖的自動重構方法,該方法結合借助訪問者模式分析、別名分析、負面效應分析等多種程序分析技術對讀寫模式進行分析,并設計了基于下推自動機的鎖模式識別方法.以Eclipse 插件的形式實現了自動重構工具FLock,在HSQLDB,Jenkins 和Cassandra 等11 個開源項目中使用該重構工具,對本文提出的方法進行了驗證.實驗中總計重構了1 757 個監視器對象,每個程序重構平均用時17.5s.與手動重構相比,可以有效提升重構效率.實驗結果表明,該重構工具可以有效地實現粗粒度鎖到細粒度鎖的轉換.我們下一步的工作包括:1) 探索更多的細粒度鎖的重構模式,嘗試發現更多的可以使用細粒度鎖的場景;2) 使用更多實際應用程序對FLock 進行測試;3) 完善重構工具FLock,通過比較使用粗粒度鎖和細粒度鎖的程序性能,在重構算法中加入性能權衡,幫助程序員在粗粒度鎖和細粒度鎖之間做出選擇,進而決定是否進行重構.