張 楊,邵 帥,張冬雯
(河北科技大學 信息科學與工程學院,河北 石家莊 050018)
鎖是并發(fā)程序中用于保護程序狀態(tài)和數(shù)據(jù)訪問正確性的必備措施,然而鎖競爭問題是目前多核/眾核時代影響并發(fā)程序性能的主要問題之一.鎖競爭是指當臨界區(qū)被一個互斥鎖保護時,如果一個線程獲得了該鎖,那么其他請求訪問該臨界區(qū)的線程都將被阻塞,直到持有該鎖的線程釋放該鎖.鎖競爭問題的存在,會嚴重降低程序并行度,損害程序的可伸縮性,降低多核/眾核處理器的執(zhí)行效率.
不恰當?shù)牟l(fā)控制方式通常會進一步加劇鎖競爭,程序開發(fā)人員有時習慣于使用粗粒度鎖,例如在方法的修飾符中加入synchronized 關(guān)鍵字,使整個方法處于鎖的保護之中.這種加鎖方式雖然可以降低程序開發(fā)的復雜性,然而由于粗粒度鎖控制的臨界區(qū)代碼較長,導致其他想獲取該鎖的線程等待時間增加,往往會加劇鎖競爭.許多開發(fā)人員嘗試使用細粒度鎖,相比于粗粒度鎖,細粒度鎖只對一小部分代碼進行加鎖,可以有效減少鎖的持有時間和線程等待時間,減少鎖競爭問題的影響.
與粗粒度鎖比較,使用細粒度鎖并非一件容易的事.要想實現(xiàn)細粒度的加鎖方式,通??梢圆捎蒙夋i、降級鎖、優(yōu)化讀鎖等加鎖方式,也可以采用將粗粒度讀寫鎖分解為細粒度讀寫鎖的方式.程序開發(fā)人員不僅需要對代碼模式進行分析以確定使用何種細粒度鎖的加鎖方式,而且還需要在同一種方式的不同實現(xiàn)機制之間進行選擇,例如在JDK 中,讀寫鎖和郵戳鎖分別提供了降級鎖,這兩種鎖提供的降級鎖的實現(xiàn)方法截然不同,程序開發(fā)人員需要在兩種鎖機制之間進行選擇,增加了細粒度鎖的使用難度.在傳統(tǒng)的方法中,為了使用細粒度鎖,開發(fā)人員通常需要手工地對并發(fā)程序中使用粗粒度鎖的代碼進行重構(gòu).然而這種重構(gòu)方式既費時費力,還可能會給代碼引入新的錯誤,因此迫切需要對面向細粒度鎖的重構(gòu)方法進行研究.
目前,針對鎖重構(gòu)的研究有很多:Tao 等人[1]提出了針對Java 程序根據(jù)類屬性域劃分鎖保護域的自動鎖分解重構(gòu)方法;Yu 等人[2]在進行優(yōu)化同步瓶頸的研究中提出了一種鎖分解方式;Emmi 等人[3]提出了一種自動鎖分配技術(shù),推斷獲取鎖的位置并確保加鎖的正確性,避免發(fā)生死鎖;Kawachiya 等人[4]提出一種鎖保留算法,該算法允許鎖被線程保留;Schafer 等人[5]針對重入鎖及讀寫鎖提出了一種自動重構(gòu)算法,并實現(xiàn)了重構(gòu)工具Relocker; Zhang 等人提出了面向可定制鎖[6]和郵戳鎖[7]的自動重構(gòu)方法;Arbel 等人[8]提出了并發(fā)數(shù)據(jù)結(jié)構(gòu)的代碼轉(zhuǎn)換,他們的轉(zhuǎn)換采用基于鎖的代碼,并用樂觀同步替換其中的一些加鎖代碼以減少爭用;Bavarsad[9]針對軟件事務(wù)性內(nèi)存,提出了一種讀寫鎖分配技術(shù)來克服全局時鐘的開銷.在工業(yè)界,集成在IntelliJ IDEA 上的重構(gòu)插件LockSmith[10]和基于Eclipse JDT 的并發(fā)重構(gòu)插件[11]都可以實現(xiàn)鎖重構(gòu).從目前國內(nèi)外的研究現(xiàn)狀來看,許多學者已經(jīng)認識到鎖競爭問題以及并發(fā)控制方式在程序設(shè)計中的重要性,并對鎖粒度問題以及鎖機制相關(guān)的問題進行了研究.但大部分研究是對鎖進行消除和對同步鎖進行分解,對細粒度鎖的重構(gòu)方法還有待深入研究.
要想實現(xiàn)面向細粒度鎖的自動重構(gòu),需要解決以下幾個問題:(1) 代碼分析時需要對臨界區(qū)中的每一條語句進行讀寫操作分析,而不能像Relocker[5]工具那樣將整個臨界區(qū)代碼作為一個整體進行分析;(2) 在獲取讀寫模式分析后,需要研究如何對讀寫操作模式進行識別,進而推斷出使用哪一種細粒度鎖;(3) 需要研究如何構(gòu)建由粗粒度鎖到細粒度鎖的重構(gòu)代碼.
為了解決上述問題,本文提出基于下推自動機的細粒度鎖自動重構(gòu)方法,通過訪問者模式分析、別名分析、鎖集分析、負面效應分析等程序分析方法獲取臨界區(qū)代碼的讀寫模式,然后使用下推自動機構(gòu)建不同鎖模式的識別方法,根據(jù)識別結(jié)果進行代碼重構(gòu).基于此方法,在Eclipse JDT 框架下,以插件的形式實現(xiàn)了一個自動重構(gòu)工具FLock.在實驗中,從重構(gòu)個數(shù)、改變的代碼行數(shù)、重構(gòu)時間、準確性和重構(gòu)后程序性能等方面對FLock進行了評估,并與已有重構(gòu)工具Relocker[5]和CLOCK[7]進行了對比,對HSQLDB,Jenkins 和Cassandra 等11 個大型實際應用程序的重構(gòu)結(jié)果表明:FLock 共重構(gòu)了1 757 個內(nèi)置監(jiān)視器對象,每個程序重構(gòu)平均用時17.5s.該重構(gòu)工具可以有效實現(xiàn)粗粒度鎖到細粒度鎖的轉(zhuǎn)換,與手動重構(gòu)相比,有效提升了細粒度鎖的重構(gòu)效率.
本文的主要貢獻有3 個方面.
1) 提出了一種面向細粒度鎖的自動重構(gòu)方法;
2) 以Eclipse 插件的形式實現(xiàn)了自動重構(gòu)工具FLock,可以實現(xiàn)源碼級別的重構(gòu),幫助開發(fā)者完成從粗粒度鎖到細粒度讀寫鎖的自動轉(zhuǎn)換;
3) 使用11 個大型實際應用程序?qū)Lock 進行了評估,并與現(xiàn)有工具Relocker 和CLOCK 進行了對比.
本文第1 節(jié)介紹本文的研究動機.第2 節(jié)介紹面向細粒度鎖的自動重構(gòu)方法.第3 節(jié)展示自動重構(gòu)工具FLock 的使用界面.在第4 節(jié)給出對本文所提出的方法和工具的實驗評估.第5 節(jié)對相關(guān)工作進行介紹.第6 節(jié)是本文的總結(jié).
讀寫鎖是JDK 1.5 版本中引入的一種鎖機制,它包含一對相互關(guān)聯(lián)的鎖:讀鎖和寫鎖.寫鎖是一個排它鎖,只能由一個線程持有;讀鎖是一個共享鎖,在沒有線程持有寫鎖的情況下,讀鎖可以由多個線程同時持有,讀鎖允許在訪問共享數(shù)據(jù)時有更大的并發(fā)性.Pinto 等人[12]通過研究SourceForge 上的2 227 個含有并發(fā)結(jié)構(gòu)的Java工程發(fā)現(xiàn):Java 并發(fā)包還沒有得到良好的應用,只有大約23%有并發(fā)編程結(jié)構(gòu)的Java 工程在使用.
為了說明細粒度鎖重構(gòu)的必要性,我們在代碼結(jié)構(gòu)上進行了說明.圖1 展示了processCached(·)方法的3 種實現(xiàn)方式,該程序段選自讀寫鎖的Java API 文檔[13],是一種典型的緩存處理操作.方法processCached(·)模擬了對數(shù)據(jù)庫及緩存的操作,首先判斷數(shù)據(jù)是否存在于緩存中:如果存在,則直接從緩存中讀取數(shù)據(jù);如果不存在,則從數(shù)據(jù)庫中把數(shù)據(jù)寫入緩存.在圖1(a)中,該方法使用synchronized 進行同步控制,整個方法都處于該鎖的保護下,是一種粗粒度的保護.圖1(b)為使用Relocker[5]進行重構(gòu)后的代碼,由于該方法中包含對緩存的寫入操作,按照Relocker 的鎖推斷策略,將使用寫鎖對其進行重構(gòu).然而我們發(fā)現(xiàn):寫操作的執(zhí)行僅僅發(fā)生在if 語句的條件成立時,如果條件不成立,寫鎖根本不會執(zhí)行,只需要執(zhí)行讀操作.如果把全部代碼使用寫鎖進行保護,可能會降低程序的性能.如果使用讀鎖,將允許多個線程同時讀,可以提高程序的并發(fā)性.圖1(c)為改進后的代碼,是一種細粒度的加鎖方式.該方式首先獲取讀鎖并判斷cacheValid(第3 行、第4 行):如果if 條件不成立,則直接讀取并釋放讀鎖(第16 行~第20 行);如果成立,則釋放讀鎖獲得寫鎖(第5 行、第6 行).為了保證程序狀態(tài)的一致性,這里需要重新對狀態(tài)進行判斷(第8 行),因為其他線程可能已經(jīng)對緩存進行了修改.當從數(shù)據(jù)庫中寫入緩存之后,獲得讀鎖再釋放寫鎖,完成鎖降級操作(第9 行~第14 行).從圖1(c)可以看到:該方式將一直使用讀鎖,直到寫入的時候再加寫鎖.
Fig.1 Three implementations of the method processCached(·)圖1 processCached(·)方法的3 種實現(xiàn)方式
從上面的例子可以看出:使用鎖降級實現(xiàn)了對臨界區(qū)的細粒度保護,加鎖方式更為合理,并且可以在一定程度上減少了鎖競爭.由于讀鎖是共享鎖,允許多個線程同時訪問,在不發(fā)生寫入時可以增加程序的并發(fā)性.
本節(jié)首先給出了重構(gòu)的整體框架,之后對程序分析方法、基于下推自動機的鎖模式推斷以及重構(gòu)算法進行了介紹.
在重構(gòu)過程中,首先通過訪問者模式對源碼對應的抽象語法樹進行遍歷,主要用到的程序靜態(tài)分析方法包括鎖集分析、別名分析和負面效應分析:鎖集分析用來對監(jiān)視器對象進行收集,并存儲監(jiān)視器對象和鎖對象的對應關(guān)系;別名分析用來解決鎖集中的別名問題;負面效應分析用來分析臨界區(qū)是否產(chǎn)生負面效應,并生成對應的臨界區(qū)讀寫模式序列.下推自動機對臨界區(qū)讀寫模式序列進行識別,進而進行鎖推斷,在讀鎖、寫鎖、鎖降級、鎖分解這4 種加鎖模式中選擇相應的加鎖模式并進行重構(gòu).在重構(gòu)之后,需要對重構(gòu)前后的一致性進行檢測,以保證重構(gòu)的正確性.面向細粒度鎖的重構(gòu)框架如圖2 所示.
Fig.2 Refactoring framework圖2 重構(gòu)框架圖
在重構(gòu)框架中,首先對源程序進行解析,生成一個抽象語法樹(abstract syntax tree,簡稱AST).在具體的解析過程中,首先通過Eclipse JDT[14]獲取用戶在進行重構(gòu)操作時所選擇的對象,然后將用戶選擇的對象存放到ICompilationUnit 對象中,最后將ICompilationUnit 對象對應的元素解析成AST.AST 節(jié)點的類型很多,每個節(jié)點表示一個源程序中的一個語法結(jié)構(gòu),包括類型、表達式、語句、聲明等.使用訪問者模式分析對AST 上的同步方法節(jié)點以及同步塊語句進行遍歷,找到同步方法和同步塊.在具體的實現(xiàn)過程中,通過繼承EclipseJDT 中提供的抽象類ASTVisitor 實現(xiàn)了一個子類作為具體訪問者,用于具體類型節(jié)點的遍歷.
2.3.1 鎖集分析
在進行重構(gòu)之前,首先通過訪問者模式遍歷程序中所有的方法,并對監(jiān)視器對象進行收集.在重構(gòu)過程中,還需要對監(jiān)視器對象是否產(chǎn)生別名進行判斷,進行別名分析.別名是指監(jiān)視器對象名稱不同,但是同時指向相同的內(nèi)存地址.對于監(jiān)視器對象不同的臨界區(qū),需要使用不同的鎖對象進行重構(gòu);對監(jiān)視器對象相同的臨界區(qū),則使用相同的鎖對象進行重構(gòu).使用一個鍵-值對集合對監(jiān)視器對象和讀寫鎖鎖對象的映射關(guān)系進行存儲,監(jiān)視器對象作為鍵-值對集合的鍵,監(jiān)視器對象對應的讀寫鎖對象為鍵-值對集合的值.
監(jiān)視器集合定義為MonitorSet={m1,m2,…,mn},其中,mi為監(jiān)視器對象,i∈{1,2,…,n}.監(jiān)視器mi的指向集定義為PoniterSeti,如果對于任意的mi和mj,i≠j,存在PoniterSeti∩PoniterSetj≠?,則認為mi和mj互為別名,并把mi和mj作為別名對〈mi,mj〉存儲在可能別名集AliasSet中.在進行重構(gòu)之前,首先通過別名集AliasSet構(gòu)建鎖集LockSet,對別名對中的監(jiān)視器對象對應的鎖對象進行實例化,并存入鎖集LockSet中.別名對中兩個監(jiān)視器對象應對應相同的鎖對象,例如別名對〈mi,mj〉在LockSet中表示為兩個鍵值對組合〈mi:lockk〉,〈mj:lockk〉,其中,lockk為鎖對象;而沒有產(chǎn)生別名問題的監(jiān)視器對象在重構(gòu)過程中對鎖對象進行實例化,并存入鎖集LockSet中.
2.3.2 負面效應分析
負面效應是指對非本地環(huán)境的修改[15],例如一個操作、方法或表達式在執(zhí)行過程中修改了內(nèi)存單元,則程序?qū)a(chǎn)生負面效應.由于本文提出的重構(gòu)方法不僅要重構(gòu)讀鎖和寫鎖,而且還要進行細粒度的鎖重構(gòu),因此負面效應分析需要對整個臨界區(qū)進行分析,并生成一個臨界區(qū)讀寫模式序列來表示臨界區(qū)的讀寫操作.在生成臨界區(qū)對應的讀寫模式序列時,使用字符r表示臨界區(qū)的一個讀操作,使用字符w表示一個寫操作,使用字符c表示一個if 條件判斷語句的開始且條件判斷為讀操作,使用字符e表示一個if 判斷語句的結(jié)束.
本文的負面效應分析通過WALA[16]的中間表示IR 對方法中的指令進行遍歷分析,判斷指令是否修改內(nèi)存單元.在對方法調(diào)用指令進行分析時,為了保證重構(gòu)工具的執(zhí)行效率,將方法調(diào)用進入的層數(shù)限制為5 層.具體分析算法如算法1 所示.
1) 首先獲得臨界區(qū)所對應的指令集,調(diào)用sideEffectAnalysis方法對每一條指令進行遍歷分析(第1 行~第4 行);
2) 在sideEffectAnalysis方法中,首先對方法調(diào)用進入的層數(shù)限制進行判斷(第6 行),如果大于限制層數(shù)5層,為了保證臨界區(qū)安全,將其認定為一個寫操作,返回字符w(第23 行);
3) 之后,對每條指令進行分析,如果指令修改了靜態(tài)字段,或修改了實例字段,或修改了堆內(nèi)存,則當前指令產(chǎn)生了負面效應,返回字符w(第7 行、第8 行);
4) 如果指令是方法調(diào)用指令,首先對調(diào)用層數(shù)的計數(shù)器加1(第11 行),之后,遞歸調(diào)用sideEffectAnalysis方法對被調(diào)用方法里的指令進行分析:若被調(diào)用方法包含寫指令,則當前方法調(diào)用指令產(chǎn)生了負面效應,返回字符w(第11 行~第15 行);如果當前被調(diào)用方法沒有產(chǎn)生負面效應,則返回字符r(第16 行);
5) 如果是if 判斷語句且判斷語句為讀操作,返回字符c;如果指令是if 條件判斷結(jié)束指令,則返回字符e(第17 行~第20 行);
6) 其他指令均返回字符r(第21 行).
算法1.負面效應分析算法.
在負面效應分析中,使用字符c表示一個if 語句的開始,e表示一個if 語句的結(jié)束.由于判斷語句每一個開始對應著一個結(jié)束,負面效應分析會產(chǎn)生類似cnAen(A代表其他操作)的字符序列,其中,n>0.在匹配過程中,需要記錄c和e的對應關(guān)系,因為n的值是不確定的,導致狀態(tài)的個數(shù)也是不確定的,所以我們使用下推自動機對負面效應分析產(chǎn)生的臨界區(qū)讀寫模式序列進行模式匹配,以確定程序重構(gòu)后的加鎖模式.
定義1.用于推斷細粒度鎖模式的下推自動機Mfg=(Q,Σ,Γ,δ,q0,Z0,F)是一個七元組模型,其中,
?Q={q0,q1,…,q7}是一個有窮狀態(tài)集;
? Σ={r,w,c,e}是輸入字母表,其中,r代表一個讀操作,w代表一個寫操作,c代表一個if 條件判斷語句的開始且條件判斷為讀操作,e為一個if 條件判斷語句的結(jié)束標志;
? Γ={Z0,C,R,W,D,A,B,V}是有限的堆棧字母表;
? δ=δ(q,x,X)是轉(zhuǎn)移函數(shù),一般使用規(guī)則〈q,x,X,q′,T〉代表轉(zhuǎn)移函數(shù),其中:q為狀態(tài)符號;x為輸入符號;X和T為棧符號,表示當下推自動機處于狀態(tài)q、當前輸入字符為x且棧頂符號為X時,則下推自動機的狀態(tài)變?yōu)閝′,并用符號串T代替棧頂符號X.符號串T有3 種形式,分別為X′,X′X,ρ,其中,X′表示用字符X′替換棧頂元素,X′X表示將X′壓入棧中,ρ表示彈出當前棧頂元素;
?q0為初始狀態(tài);
?Z0為初始棧頂符號;
?F={q1,q3,q4,…,q7}為終態(tài)集.
下推自動機Mfg的狀態(tài)轉(zhuǎn)換圖如圖3 所示,其中,規(guī)則〈q,x,X,q′,T〉在圖中表示為〈x,X/T〉,狀態(tài)q到狀態(tài)q′的轉(zhuǎn)移用直線箭頭表示.
Fig.3 State transition diagram of pushdown automaton Mfg圖3 下推自動機Mfg 狀態(tài)轉(zhuǎn)換圖
例如:圖3 中,當下推自動機處于狀態(tài)q0、當前輸入字符為r且棧頂符號為Z0時,則下推自動機由狀態(tài)q0轉(zhuǎn)移到q1,并把字符R壓入棧中.
在鎖模式定義之前,為了簡化表示終態(tài)所識別的符號集,首先定義符號串集合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數(shù)量相等.
定義2(寫鎖模式的定義).一個臨界區(qū)被推斷為寫鎖,當且僅當讀寫模式序列被終態(tài)q3所接受.
終態(tài)q3所識別的序列為Sw1={w}+,表示臨界區(qū)只包含寫操作,將使用寫鎖進行同步保護.
定義3(讀鎖模式的定義).一個臨界區(qū)被推斷為讀鎖,當且僅當讀寫模式序列被終態(tài)q1所接受.
終態(tài)q1所接受的序列集為Sr={SrcSre}+,其中,字符c和字符e的數(shù)量相同.序列集Sr不包含字符w,表示臨界區(qū)沒有產(chǎn)生負面效應,所以使用讀鎖.
定義4(鎖降級模式的定義).一個臨界區(qū)被推斷為鎖降級,當且僅當讀寫模式序列被終態(tài)q7所接受.
終態(tài)q7所接受的序列集為Sd={r*cS+er+},表示臨界區(qū)首先包含讀操作或沒有,之后是一個if 判斷語句塊,其中,判斷語句為讀操作,語句塊內(nèi)包含其他操作但至少有一個寫操作,if 塊之后包含至少一個讀操作且只包含讀操作.
定義5(鎖分解模式的定義).一個臨界區(qū)被推斷為鎖分解,當且僅當讀寫模式序列被終態(tài)q5,q4,q6所接受.
終態(tài)q5識別的序列集為Ss1={r*cS+e},表示臨界區(qū)首先包含讀操作或沒有,之后是一個if 判斷語句塊,判斷語句為讀操作,語句塊內(nèi)包含其他操作但至少有一個寫操作;終態(tài)q4和q6識別的序列表示讀寫操作分離的臨界區(qū),終態(tài)q4所識別的序列集為Ss2={SrSw1},代表臨界區(qū)前半部分為讀操作后半部分為寫操作,終態(tài)q6所識別的序列集為Ss3={Sw1Sr},代表臨界區(qū)前半部分為寫操作后半部分為讀操作.
定義6(下推自動機停機的定義).當輸入讀寫模式序列為空,或棧頂符號為V時,下推自動機停止對讀寫模式序列的識別.
當讀寫模式序列為空時,表示臨界區(qū)沒有操作,則對臨界區(qū)使用讀鎖;當棧頂符號為V時,所識別的序列集為Sw2={CS(Sw1∪Sr∪Sd∪Ss1∪Ss2∪Ss3)},表示讀寫模式序列不符合細粒度鎖規(guī)則,臨界區(qū)將使用寫鎖進行同步保護.
本節(jié)給出了重構(gòu)算法的設(shè)計,首先對相關(guān)代碼建立AST;之后遍歷AST 的所有方法節(jié)點,找到同步方法和包含同步塊的方法節(jié)點;最后,根據(jù)負面效應分析得到的讀寫串對應的鎖模式進行重構(gòu).重構(gòu)算法如算法2 所示.具體流程如下.
1) 首先獲取當前的監(jiān)視器對象(第1 行),并判斷鎖集LockSet中是否存在監(jiān)視器對象所對應的鎖對象(第2 行):如果存在,則從鎖集LockSet中獲得監(jiān)視器對象對應的鎖對象(第3 行);否則生成一個新的鎖對象,并把監(jiān)視器對象與鎖對象的對應關(guān)系存入鎖集LockSet中(第5 行、第6 行);
2) 通過負面效應分析獲得c對應的臨界區(qū)讀寫模式序列str(第8 行);
3) 如果c為同步方法或同步塊,則移除synchronized 鎖,并通過下推自動機識別臨界區(qū)讀寫模式序列str,根據(jù)識別結(jié)果進行重構(gòu)(第9 行~第13 行);
4) 最后對重構(gòu)前臨界區(qū)c和重構(gòu)后的c_r進行一致性檢測(第17 行):如果符合一致性檢測規(guī)則,返回重構(gòu)結(jié)果c_r(第15 行);否則,將使用寫鎖對臨界區(qū)c進行重構(gòu)(第16 行~第19 行),其中,Consistency 方法基于一致性檢測規(guī)則進行定義(第3 節(jié)給出).
算法2.重構(gòu)算法.
輸入:臨界區(qū)c;
輸出:臨界區(qū)c的重構(gòu)結(jié)果.
FlexSync[17]是一個可以通過施加不同標記在不同同步機制之間進行重構(gòu)轉(zhuǎn)換的工具,FlexSync 中定義了一致性檢查規(guī)則,以此來檢查在不同同步機制之間轉(zhuǎn)換的一致性.為了盡可能地保證重構(gòu)的正確性,本節(jié)參照FlexSync 的一致性檢測規(guī)則,給出了FLock 重構(gòu)前后的一致性檢測規(guī)則.在給出規(guī)則之前,我們首先對相關(guān)的內(nèi)容進行了定義.
定義7(臨界區(qū)集合).一個應用程序P中所有臨界區(qū)的集合定義為C={c1,c2,…,cn}.對于?ci∈C(1≤i≤n),ci={ci1,ci2,…,cik}表示ci被劃分為k個細粒度的臨界區(qū).
由于P中的代碼是有限的,因此C是一個有限集合,對于?ci∈C(1≤i≤n),ci表示某一個臨界區(qū).ci中可以包含若干讀寫操作opi1,opi2,…,opir,表示為{opi1,opi2,…,opir}?ci.
Cbefore和Cafter分別表示重構(gòu)前和重構(gòu)后的臨界區(qū)集合,由于FLock 在重構(gòu)時需要分割臨界區(qū),因此|Cbefore|< |Cafter|,其中,|C|表示集合C元素個數(shù).
定義8(重構(gòu)前鎖集合).一個應用程序P中所有用于保護臨界區(qū)的鎖集合定義為集合S={s1,s2,…,sm}.
由于C是有限集合,所以S也是一個有限集合.由于一個鎖可以保護多個臨界區(qū),故m≤n.對于?se∈S,se表示既包含加鎖操作又包含解鎖操作.
定義9(鎖保護).對于?ci∈C(1≤i≤n),?se∈S(1≤e≤m),如果臨界區(qū)ci處于鎖se的保護中,則定義保護關(guān)系為se⊙{ci}.進一步,一個鎖可以保護多個臨界區(qū),定義為se⊙Ck,其中,Ck是Cbefore的子集,即Ck?Cbefore.
定義10(重構(gòu)后鎖集合).一個應用程序P中重構(gòu)之后所有的鎖集合定義為集合L={l1,l2,…,lt}.對于?la∈L(1≤a≤t),la⊙Cv,Cv是Cafter的子集,即Cv?Cafter.
定義11(鎖狀態(tài)原子性保持).對于?la∈L,如果la在沒有釋放鎖的情況下完成鎖狀態(tài)切換,則說明鎖狀態(tài)原 子性沒有被破壞,定義其為?la,否則定義為.
定義11 說明了鎖狀態(tài)的原子性問題,舉例來說:讀寫鎖在由寫鎖切換為讀鎖時,可以不用釋放該鎖,在該鎖的內(nèi)部完成鎖狀態(tài)的切換.
定義 12(重構(gòu)前后鎖的對應關(guān)系).重構(gòu)前,對于?ck∈C(1≤k≤n),?se∈S(1≤e≤m),se⊙Ck;重構(gòu)后,對于?cv∈C(1≤v≤n),?la∈L(1≤a≤t),la⊙Cv.如果Cv?Ck,則se和la之間存在一一對應關(guān)系,記為se≡la.
定義13(Happens-before 關(guān)系).對于?ci∈C,{opi1,opi2,…,opir}?ci,?u,v(1≤u≤r,1≤v≤r),如果opiu先發(fā)生于opiv,則定義Happens-before 關(guān)系為opiu≥opiv.依據(jù)Happens-before 關(guān)系的傳遞性,如果opiu≥opiv并且opiv≥opiw,則opiu≥opiw.
Happens-before 關(guān)系的定義是建立在Java 內(nèi)存模型基礎(chǔ)上的讀寫操作發(fā)生序關(guān)系,是Java 語言內(nèi)存一致性的重要準則.該關(guān)系建立的方式之一是通過程序中的同步關(guān)系,解鎖操作之前的操作先發(fā)生于解鎖之后獲取該鎖的操作.
基于如上的定義,下面給出了重構(gòu)的一致性檢測規(guī)則.
規(guī)則1.對于重構(gòu)前,?ci∈C(1≤i≤n),?se∈S(1≤e≤m),使得se{⊙ci};重構(gòu)后,ci={ci1,ci2,…,cik},對于?cij(1≤i≤n,1≤j≤k),?la∈L(1≤a≤t),使得la{⊙cij}.
規(guī)則1 說明了重構(gòu)之前處于鎖保護的臨界區(qū),在重構(gòu)之后仍處于鎖的保護中.
規(guī)則2.對于重構(gòu)前,?ci∈C(1≤i≤n),?se∈S(1≤e≤m),使得se{⊙ci};重構(gòu)后,ci={ci1,ci2,…,cik},對于?cij(1≤i≤n,1≤j≤k),?la∈L(1≤a≤t),如果有l(wèi)a{⊙cij},則se≡la.
規(guī)則2 說明:如果重構(gòu)前臨界區(qū)ci在se的保護中,即使重構(gòu)后ci被分割為多個臨界區(qū),保護這些臨界區(qū)的鎖la和se之間存在一一對應的關(guān)系.如果所有的鎖都可以被重構(gòu),那么重構(gòu)前后的鎖集合應滿足|S|=|L|.需要說明的是:對于FLock 重構(gòu)前后鎖的一一對應關(guān)系,通常表現(xiàn)在同步鎖的監(jiān)視器對象和讀寫鎖對象的一一對應關(guān)系上.
規(guī)則1 和規(guī)則2 從重構(gòu)前后代碼結(jié)構(gòu)上進行了一致性說明,保證了代碼結(jié)構(gòu)的完整性.
由于FLock 在進行面向細粒度鎖重構(gòu)時主要采用了降級鎖和鎖分解兩種方式,下面主要針對這兩種方式進行規(guī)則定義.
規(guī)則3.重構(gòu)前,對于?ci∈C(1≤i≤n),?se∈S(1≤e≤m),使得se{⊙ci};重構(gòu)后,ci={ci1,ci2,…,cik},如果?la∈L(1≤a≤t),使得se≡la,對于?cij(1≤i≤n,1≤j≤k),有(la{⊙cij})∧()成立,則鎖降級重構(gòu)前后可以保證一致性.
規(guī)則3 主要針對降級鎖的重構(gòu)進行了約束.雖然鎖降級過程中會由寫鎖降級為讀鎖,但該過程是在鎖的內(nèi)部進行轉(zhuǎn)換的,期間并沒有釋放鎖,可以保證鎖的原子性,所以鎖降級重構(gòu)前后是一致的.
規(guī)則4.重構(gòu)前,對于?ci∈C(1≤i≤n),?se∈S(1≤e≤m),使得se{⊙ci};重構(gòu)后,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.
規(guī)則5.重構(gòu)前,對于?ci∈C(1≤i≤n),{opi1,opi2,…,opir}?ci,?se∈S(1≤e≤m),使得se{⊙ci};重構(gòu)后,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訪問同一內(nèi)存位置并且opip或opiq是寫操作,則不能進行鎖分解.
規(guī)則4 和規(guī)則5 共同保證了鎖分解重構(gòu)的一致性.規(guī)則4 對鎖分解的重構(gòu)進行了約束,該規(guī)則通過檢查臨界區(qū)讀寫語句的Happens-before 關(guān)系,確保該關(guān)系在重構(gòu)前后沒有改變.在FLock 工具的重構(gòu)對象中,重構(gòu)前后代碼都涉及同步關(guān)系,可以在同步關(guān)系的基礎(chǔ)上建立Happens-before 關(guān)系,進而進行規(guī)則判定.規(guī)則5 從保持原有臨界區(qū)的原子性角度對鎖分解進行了約束,確保原有臨界區(qū)的原子性沒有被破壞.如果存在opip和opiq訪問同一內(nèi)存位置,有可能因為線程交互而改變原有操作語義,在這種情況下,FLock 只推斷一個寫鎖而不進行鎖分解.
FLock 是在Eclipse JDT 框架下設(shè)計并以Eclipse 插件的形式實現(xiàn)的,對Eclipse 中的基礎(chǔ)類Refactoring 和UserInputWizardPage 等進行擴展,實現(xiàn)相關(guān)的重構(gòu)邏輯設(shè)計和可視化的重構(gòu)工具界面設(shè)計.FLock 重構(gòu)界面截圖如圖4 所示,展示了重構(gòu)前后的代碼之間的對比,其中,左側(cè)為重構(gòu)前的代碼,右側(cè)為重構(gòu)后代碼的預覽.
Fig.4 Screenshot of the FLock圖4 FLock 重構(gòu)工具界面
本節(jié)對所提出的方法和工具進行了實驗評估.首先對實驗配置和測試程序進行介紹,然后從重構(gòu)數(shù)目、改變的代碼行數(shù)和時間等方面給出了實驗結(jié)果,并對結(jié)果進行了分析[18].
所有實驗都是在HP Z240 工作站上完成的,該工作站搭載Intel Core i7-7700 處理器,該處理器主頻為3.6GHz,有4 個處理核,均支持超線程技術(shù),可以支持8 個線程同時運行,內(nèi)存為8GB.軟件上,操作系統(tǒng)使用Ubuntu 16.04,使用Eclipse 4.12.0 作為重構(gòu)工具的開發(fā)平臺,使用JDK 1.8.0_221 和程序分析工具WALA 1.52.
本文選取了11 個實際應用程序來驗證我們重構(gòu)工具的有效性和適用性,這些應用程序包括HSQLDB[19],Jenkins[20],Cassandra[21],SPECjbb2005[22],JGroups[23],Xalan[24],Fop[25],RxJava[26],Freedomotic[27],Antlr[28],MINA[29].其中,HSQLDB 是一個開源的Java 數(shù)據(jù)庫,Cassandra 是Apache 公司的開源分布式NoSQL 數(shù)據(jù)庫系統(tǒng),Jenkins是一個開源的自動化服務(wù)器,JGroups 是群組通信工具,SPECjbb 2005 是Java 應用服務(wù)器測試程序,Xalan 和Fop分別是Apache 公司的XSLT 轉(zhuǎn)換處理器和格式化對象處理器,RxJava 是Netflix 公司的在Java VM 上使用可觀測的序列來組成異步的、基于事件的程序的庫,Freedomotic 是一個開源的物聯(lián)網(wǎng)框架,Antlr 是一個解析器生成器,MINA 是Apache 公司的網(wǎng)絡(luò)應用框架.這些程序的版本號信息、包含同步方法和同步塊的個數(shù)以及源碼行數(shù)見表1.
在實驗中,使用FLock 對11 個測試程序進行自動重構(gòu),對重構(gòu)個數(shù)、代碼行數(shù)、重構(gòu)后程序的準確性進行了驗證,并與重構(gòu)工具Relocker 和CLOCK 進行了對比.
5.3.1 鎖重構(gòu)個數(shù)
我們首先對FLock 重構(gòu)后的不同類型鎖個數(shù)進行了匯總,重構(gòu)結(jié)果見表2.
從實驗結(jié)果可以看出:在11 個程序中,共有391 個粗粒度鎖重構(gòu)為細粒度鎖.內(nèi)置監(jiān)視器對象轉(zhuǎn)換為鎖降級模式的個數(shù)有25 個,其中,HSQLDB 中最多,包含6 個,集中分布在org.hsqldb 包里的Session 類和Table 類中,這兩個類分別是用來執(zhí)行session 和保存數(shù)據(jù)庫表的數(shù)據(jù)結(jié)構(gòu)和方法;在RxJava 和MINA 中,由于原程序中包含的內(nèi)置監(jiān)視器對象較少,在重構(gòu)之后沒有監(jiān)視器對象轉(zhuǎn)換為鎖降級模式.內(nèi)置監(jiān)視器對象轉(zhuǎn)換為鎖分解模式的個數(shù)為127 個,在HSQLDB,Cassandra 和JGroups 測試程序中重構(gòu)后轉(zhuǎn)換為鎖分解模式的個數(shù)較多;測試程序Fop 中包含32 個內(nèi)置監(jiān)視器對象,重構(gòu)后沒有內(nèi)置監(jiān)視器轉(zhuǎn)換為鎖分解模式.在重構(gòu)為讀鎖方面,有293 個內(nèi)置監(jiān)視器對象轉(zhuǎn)換為讀鎖,在測試程序HSQLDB 和Cassandra 中,讀鎖的占比相對較高;在程序Antlr 和MINA 中,使用鎖分解模式比使用讀鎖的個數(shù)多.
Table 1 Benchmarks and their configuration表1 測試程序及其配置
Table 2 Refactoring results by FLock表2 FLock 重構(gòu)結(jié)果
Table 3 Comparison of Relocker and FLock表3 Relocker 和FLock 重構(gòu)對比
Table 4 Comparison of CLOCK and FLock表4 CLOCK 和FLock 重構(gòu)對比
在重構(gòu)工具FLock 中,加入了對臨界區(qū)的一致性規(guī)則檢測,表2“違背一致性規(guī)則”列展示了不滿足一致性檢測的臨界區(qū)數(shù)目.對于所有的測試程序,除了MINA 測試程序外,其余10 個程序均存在違背一致性檢測規(guī)則的情況發(fā)生,共有139 個,其中,HSQLDB 中最多,有41 個.對于這些不滿足一致性規(guī)則的臨界區(qū),我們沒有對他們進行鎖分解,而是采用寫鎖作為臨界區(qū)的保護模式.
5.3.2 重構(gòu)前后改變的代碼行數(shù)
我們對重構(gòu)前后改變的代碼行數(shù)進行了統(tǒng)計,這些代碼行數(shù)的改變在一定程度上反映了程序員在手動重構(gòu)時所需要花費的工作量.我們使用SLOCCount(https://dwheeler.com/sloccount/)工具對代碼行數(shù)進行統(tǒng)計,該工具是由David A.Wheeler 開發(fā)的用于精確統(tǒng)計代碼行數(shù)的工具,不僅適用于多個操作系統(tǒng)平臺,而且適合于多種語言.
11 個測試程序共包含1 429 775 行代碼,重構(gòu)后代碼行數(shù)為1 439 779 行,增加了10 004 行代碼.由于重構(gòu)前使用的是同步鎖,重構(gòu)后使用的讀寫鎖需要顯示的加鎖和解鎖,并且需要使用try-finally 語句塊,所以重構(gòu)后會增加代碼行數(shù).對于HSQLDB 測試程序,由于其包含的同步鎖數(shù)目最多,重構(gòu)前后改變的代碼行數(shù)也最多,達到 3 756 行;對于Jenkins,Cassandra,SPECjbb2005 和JGroups 測試程序,由于它們包含的同步鎖數(shù)目在100 到300之間,代碼改變的行數(shù)也較多,分別增加了1 762 行、1 420 行、782 行和1 241 行;對于RxJava,Freedomotic,Antlr和MINA 測試程序,由于包含的同步鎖較少,代碼行數(shù)的改變也較少,分別有171 行、274 行、59 行和67 行.
這些代碼行數(shù)在一定程度上體現(xiàn)了程序開發(fā)人員重構(gòu)程序時的工作量,如果使用手動重構(gòu)的方式,開發(fā)人員需要首先在程序中找到同步鎖出現(xiàn)的位置,然后進行修改.例如:在手動重構(gòu)HSQLDB 測試程序時,需要在17萬行的代碼中尋找684 個同步鎖并進行重構(gòu),最終結(jié)果會增加3 756 行代碼,這種手動重構(gòu)耗時較長并且容易給程序引入新的錯誤,對于該測試程序,我們發(fā)現(xiàn)同步鎖大部分分布在org.hsqldb 包中,分布相對比較集中;在FOP中,32 個內(nèi)置監(jiān)視器對象在重構(gòu)后只增加235 行代碼,但32 個監(jiān)視器對象分布在2 034 個java 文件中,分布非常稀疏,遍歷過程十分耗時.在使用我們開發(fā)的自動重構(gòu)工具重構(gòu)HSQLDB 和FOP 時,分別僅需要18s 和15s 即可完成,可以大大節(jié)省程序員的工作量.
5.3.3 重構(gòu)時間
11 個測試程序重構(gòu)的總耗時為192s,每個程序平均耗時17.5s,見表2.HSQLDB 中監(jiān)視器對象較多,有684個監(jiān)視器對象,重構(gòu)耗時為18s;程序Cassandra 規(guī)模相對較大,源碼行數(shù)為431 022 行,重構(gòu)耗時為73s;JGroups和Xalan 重構(gòu)耗時分別為24s 和19s;SPECjbb2005,RxJava,Freedomotic,Antlr 和MINA 的程序規(guī)模相對較小,重構(gòu)耗時約為2s~8s.通過對這些程序的重構(gòu)時間進行分析,我們發(fā)現(xiàn):重構(gòu)工具在重構(gòu)時的時間消耗主要是用于程序的靜態(tài)分析上,程序越大,靜態(tài)分析時間越長,造成總的重構(gòu)時間也越長.對于FOP 測試程序中,源碼行數(shù)為198 555 行,雖然其與HSQLDB 程序的代碼規(guī)模相當,但其中包含同步鎖個數(shù)非常少,分布相對比較稀疏,通過手動的方式進行重構(gòu)會花費大量的時間在搜索代碼上;而FLock 可以自動地完成重構(gòu),用時也僅僅為15s,大大減少重構(gòu)耗時,有效提高開發(fā)效率.
5.3.4 重構(gòu)的正確性
為了對重構(gòu)后測試程序的正確性進行驗證,我們主要從以下3 個方面進行了驗證,包括驗證推斷鎖的類型是否正確、加鎖和解鎖的位置是否正確、鎖結(jié)構(gòu)的使用是否正確.由于目前沒有相關(guān)的自動驗證工具,我們主要采用了手工檢查的方式.
在驗證推斷鎖類型的準確性方面,我們手動地檢查每一個測試程序中每一個臨界區(qū)的代碼,我們發(fā)現(xiàn):推斷出來的每一個鎖都符合我們的推斷規(guī)則,都是正確的類型.此外,我們發(fā)現(xiàn):在Cassandra 測試程序中,部分代碼在重構(gòu)前就使用了讀寫鎖.我們將這些讀寫鎖重構(gòu)為同步鎖,然后使用Flock再對其進行重構(gòu),結(jié)果發(fā)現(xiàn):Flock推斷的鎖類型和原有的鎖類型基本相同,只有一處存在不同之處.該處發(fā)生在CompactionStrategyManager 類的maybeReload 方法中,該方法原本使用寫鎖,但是Flock 將其推斷為鎖分解的方式,經(jīng)過手工檢查發(fā)現(xiàn):使用鎖分解的方式并未改變程序原邏輯,是正確的細粒度加鎖方式.
在判斷加鎖和解鎖位置以及鎖的使用方面,我們主要檢查了:(1) 每種鎖的加鎖操作是否對應一個解鎖操作;(2) 解鎖操作是否被放入finally 語句塊中;(3) 細粒度鎖的結(jié)構(gòu)是否正確.經(jīng)過檢查,我們并未發(fā)現(xiàn)相關(guān)錯誤.我們也通過運行程序的方式檢查了程序的正確性,發(fā)現(xiàn)這些程序在執(zhí)行過程中并沒有報錯,都可以正確運行.
5.3.5 重構(gòu)前后性能對比
本節(jié)選取HSQLDB,Jenkins,Cassandra,JGroups 和SPECjbb2005 進行性能測試.之所以選擇這5 個程序,是因為它們在發(fā)布的版本中都提供了相應的基準測試程序.
HSQLDB 提供了JDBCBench 測試程序,該程序的測試結(jié)果如圖5 所示,其中:橫坐標為處理事務(wù)數(shù),分別給出了事務(wù)數(shù)為100k,200k,300k 和400k 的情況;縱坐標為事務(wù)處理率.從圖中可以看出:該測試程序在處理100k個事務(wù)時,程序重構(gòu)后使用細粒度讀寫鎖的事務(wù)率比重構(gòu)前使用同步鎖的事務(wù)率略有提升,但不明顯;在處理事務(wù)量達到200k,300k 和400k 時,重構(gòu)后比重構(gòu)前的程序在事務(wù)率上的提升大約有15%,19%和22%,提升較為明顯.總的來說,HSQLDB 使用細粒度的讀寫鎖在事務(wù)率方面重構(gòu)后比重構(gòu)前平均提升了18%,說明使用細粒度鎖有助于提升HSQLDB 的性能,而我們設(shè)計的工具可以幫助更快地轉(zhuǎn)換為細粒度鎖.
對于Jenkins,我們選取了其中的單元測試程序UpdateCenterTest,FunctionsTest 和FilePathTest 進行了測試.圖6 給出了3 個單元測試的執(zhí)行時間,可以看出:單元測試UpdateCenterTest 在重構(gòu)前后程序的執(zhí)行時間基本沒有變化,而FunctionsTest 在重構(gòu)后執(zhí)行時間縮短了17.3%,FilePathTest 在重構(gòu)后執(zhí)行時間縮短了20.9%.
Fig.5 Performance comparison of the HSQLDB benchmark before and after refactoring圖5 HSQLDB 重構(gòu)前后的性能比較
Fig.6 Performance comparison of the Jenkins benchmark before and after refactoring圖6 Jenkins 重構(gòu)前后的性能比較
對于JGroups,我們選取了測試程序RoundTrip,RoundTripRpc,UnicastTest 和UnicastTestRpc 進行測試,這4個測試程序都是測試兩個群組之間消息的發(fā)送與接收能力.實驗結(jié)果如圖7 所示,其中,橫坐標為測試程序,縱坐標為請求處理率.從結(jié)果中可以看出:4 個測試在重構(gòu)后請求處理率都有所提升,分別提升了15.5%,7%,5%和9%.
對于測試程序Cassandra,我們選取了其中的單元測試程序BatchTests,SimpleQueryTest 和ManyRowsTest進行性能測試,圖8 給出了3 個單元測試程序重構(gòu)前后的執(zhí)行時間.對于單元測試程序BatchTests,Cassandra 重構(gòu)后程序的執(zhí)行時間與重構(gòu)前程序的執(zhí)行時間基本相同;對于SimpleQueryTest 和ManyRowsTest 這兩個單元測試程序,執(zhí)行時間都有不同程度的下降,都較重構(gòu)前的執(zhí)行時間大約縮短了7%.
Fig.7 Performance comparison of the Jgroups benchmark before and after refactoring圖7 JGroups 重構(gòu)前后的性能比較
Fig.8 Performance comparison of the Cassandra benchmark before and after refactoring 圖8 Cassandra 重構(gòu)前后的性能比較
圖9 給出了SPECjbb 2005 運行結(jié)果,其中,圖9(a)給出了吞吐量隨線程數(shù)變化的情況,圖9(b)給出了堆內(nèi)存使用的百分比隨著線程數(shù)變化的情況.從圖9(a)可以看出:當吞吐量達到峰值之后,使用同步鎖的吞吐量要比使用細粒度讀寫鎖的吞吐量稍微高一些.這也說明并不是所有情況下,使用細粒度讀寫鎖性能都比使用同步鎖要好.圖9(b)給出了在不同線程執(zhí)行情況下使用的堆內(nèi)存占總內(nèi)存的百分比,在線程數(shù)為8 時,程序重構(gòu)前的堆內(nèi)存使用占比高于程序重構(gòu)后;而在線程數(shù)為12 時,程序重構(gòu)后的堆內(nèi)存使用占比高于程序重構(gòu)前.這說明在不同鎖模式和不同線程數(shù)下堆內(nèi)存的使用情況各有不同,而我們設(shè)計的重構(gòu)工具為開發(fā)人員提供一種快速的細粒度鎖和粗粒度鎖重構(gòu)的方式,開發(fā)人員可以通過測試來找到程序堆內(nèi)存使用最合適的情況.
Fig.9 Performance comparison of the SPECjbb2005 benchmark before and after refactoring圖9 SPECjbb2005 重構(gòu)前后的性能比較
5.3.6 工具對比
我們將FLock 和已有的重構(gòu)工具Relocker[5]進行了對比.Relocker 是Schafer 等人設(shè)計實現(xiàn)的一個自動重構(gòu)工具,可以把同步鎖重構(gòu)為可重入鎖或讀寫鎖.該工具是一種粗粒度鎖的推斷模式,不能實現(xiàn)細粒度的加鎖模式.由于Relocker 工具開發(fā)較早,不支持高版本的JDK,因此在該實驗中使用的JDK 版本為1.6.測試程序選擇了HSQLDB 和Cassandra,版本分別為1.8.0.10 和0.4.0(比表1 的版本低),這兩個程序中包含的同步鎖的數(shù)量也較之前實驗選取的版本有所不同:HSQLDB 總共包含266 個同步鎖,Cassandra 總共包含57 個同步鎖.我們也嘗試使用Relocker 對其他測試程序進行重構(gòu),但由于Relocker 開發(fā)較早,均不支持對這些版本進行重構(gòu).
表3 給出了Relocker 和FLock 重構(gòu)結(jié)果的對比,可以看出:Relocker 只使用讀鎖或?qū)戞i進行同步保護,而且還存在不能重構(gòu)的問題;FLock 不僅可以推斷讀鎖和寫鎖,而且可以實現(xiàn)更為細粒度的鎖重構(gòu).在讀鎖的推斷上,FLock 比Relocker 推斷出了更多的讀鎖,經(jīng)人工驗證,使用FLock 進行重構(gòu)后的讀鎖使用正確.Relocker 的推斷結(jié)果不準確的原因可能與分析深度有關(guān),這里的分析深度使用的是Relocker 的默認值.在重構(gòu)時間上,Relocker重構(gòu)HSQLDB 耗時7s,FLock 耗時6s;Cassandra 程序規(guī)模較大,Relocker 重構(gòu)耗時50s,FLock 重構(gòu)耗時42s.總體來看,FLock 在重構(gòu)效率上有所提升.
我們還將FLock 與重構(gòu)工具CLOCK[7]進行了對比,CLOCK 是一個面向郵戳鎖的自動重構(gòu)工具.這里選取了本文實驗中監(jiān)視器對象相對較多的7 個測試程序進行重構(gòu)對比,實驗結(jié)果見表4.由于郵戳鎖是不可重入鎖,所以CLOCK 對部分臨界區(qū)不能執(zhí)行重構(gòu),其中,HSQLDB 和SPECjbb 2005 包含較多不能重構(gòu)的鎖,分別為61和75 個;由于CLOCK 在鎖推斷上和FLock 不同,所以在鎖降級重構(gòu)數(shù)量上也有所差異.兩個工具在重構(gòu)效率上,CLOCK 在重構(gòu)HSQLDB,Cassandra 和Fop 時比FLock 慢1s~2s,其他程序在重構(gòu)時間上基本一致.
關(guān)于重構(gòu)后程序性能方面,我們對HSQLDB 和SPECjbb2005 這兩個程序使用不同重構(gòu)工具重構(gòu)后,使用3種鎖的性能進行了對比.HSQLDB 的實驗結(jié)果如圖10 所示,結(jié)果表明,粗粒度的讀寫鎖和郵戳鎖在事務(wù)率上要低于使用細粒度讀寫鎖的程序.SPECjbb2005 的實驗結(jié)果如圖11 所示,由于JDK 版本原因,Relocker 不能對SPECjbb2005 進行重構(gòu),這里只對比了CLOCK 和FLock 的重構(gòu)結(jié)果.可以看出:程序在使用細粒度讀寫鎖時,相較于使用粗粒度讀寫鎖和郵戳鎖的程序,事務(wù)率有明顯提升.
Fig.10 Performance comparison of the HSQLDB benchmark after refactoring圖10 HSQLDB 重構(gòu)后的性能比較
Fig.11 Performance comparison of the SPECjbb2005 benchmark after refactoring圖11 SPECjbb2005 重構(gòu)后的性能比較
5.3.7 有效性威脅
實驗中有幾個可能威脅有效性的因素.
1) 由于并發(fā)程序執(zhí)行的不確定性,不排除性能測試實驗結(jié)果可能存在細微的偏差.為了避免誤差,我們所有實驗結(jié)果都是在10 次運行的基礎(chǔ)上取平均值得到的;
2) 在實驗中,我們采用手工檢查的方式對重構(gòu)后程序的正確性進行驗證.手動的檢查方式存在著一些不足之處,可能會出現(xiàn)人為驗證不準確等問題.為了減少不準確情況的發(fā)生概率,我們選取了兩組學生分別進行兩次檢查的方式,盡可能避免出現(xiàn)問題;
3) 本實驗只選取了11 個應用程序?qū)Lock 進行了評估,它們并不能代表所有程序,不能完全證明FLock在所有的應用程序中可以成功完成重構(gòu).但是我們選取的應用程序涉及數(shù)據(jù)庫、群組通信、物聯(lián)網(wǎng)等多個領(lǐng)域,具有很好的代表性.未來的工作中,我們也將使用更多應用程序?qū)Lock 進行測試.
本文實現(xiàn)了面向細粒度讀寫鎖的自動重構(gòu)工具,我們主要關(guān)注的相關(guān)工作有兩個方面:面向鎖的優(yōu)化和自動化的重構(gòu)工具.
Emmi 等人[3]提出了一種自動鎖分配技術(shù),采用帶有原子性規(guī)范的注解對程序進行標記,自動推斷程序中應該獲取鎖的位置.Kawachiya 等人[4]提出一種鎖保留算法,該算法允許鎖被線程保留,當一個線程嘗試獲得鎖操作時,如果線程保留了該鎖,它就不用執(zhí)行獲取鎖的原子操作;否則,線程使用傳統(tǒng)的方法獲得鎖.Halpert 等人[30]提出了基于組件的鎖分配技術(shù),用于分析數(shù)據(jù)依賴性,自動將具有可調(diào)粒度的鎖對象分配給臨界區(qū).Tamiya Onodera 等人[31]設(shè)計了一種基于鎖保留的自旋鎖,并使用這種自旋鎖替換傳統(tǒng)的自旋鎖.Arbel 等人[8]提出了使用樂觀同步替換程序中的一些加鎖代碼,以減少爭用,可以在不犧牲正確性的情況下提高其可擴展性.Bavarsad[9]針對軟件事務(wù)性內(nèi)存,提出了兩種優(yōu)化技術(shù)來克服全局時鐘的開銷:第一種技術(shù)是讀寫鎖定分配,它不利用任何中央數(shù)據(jù)結(jié)構(gòu)來保持事務(wù)的一致性,僅當事務(wù)成功提交時,此方法才能提高軟件事務(wù)性內(nèi)存的性能;第二種優(yōu)化技術(shù)是一種動態(tài)選擇基線方案的自適應技術(shù),用來減小讀寫鎖定分配的成本.Gudka[32]提出了一種針對Java 的鎖定推斷方法,使用鎖定推斷來實現(xiàn)原子塊,該方法可以全面分析Java 庫方法.以上工作的研究目的與我們相似,通過鎖分配、鎖保留、原子塊等技術(shù)減少臨界區(qū)競爭;而我們使用鎖降級、鎖分解實現(xiàn)對臨界區(qū)的細粒度保護方式,從而減少臨界區(qū)競爭.
Hofer 等人[33]提出了一種通過跟蹤Java 虛擬機中的鎖定事件來分析Java 應用程序中的鎖爭用的方法,該方法不僅檢測線程在鎖上被阻塞情況,還檢測是哪個其他線程通過持有該鎖來阻止它,并記錄它們的調(diào)用鏈.Tallent[34]提出了3 種量化鎖爭用的方法,可以在低開銷的前提下,有效提供鎖爭用檢測精度.Inoue[35]提出了一個基于Java 虛擬機,使用硬件性能計數(shù)器來檢測應用程序獲取鎖的位置以及阻塞位置的方法.以上研究是用于揭示鎖爭用的原因以及識別鎖性能瓶頸的分析工具,我們的研究提出的是一個解決鎖爭用問題的重構(gòu)工具.
Dig 等人提出了一個軟件并行化重構(gòu)工具CONCURRENCER[36],該工具可以將串行的Java 代碼進行并行化重構(gòu),以及面向循環(huán)并行化重構(gòu)的重構(gòu)工具Relooper[37].Wloka 等人[38]提出了一個用于把串行程序轉(zhuǎn)變?yōu)榭芍厝氲某绦虻淖詣又貥?gòu)工具Reentrancer,從而使程序更易并行化實現(xiàn).Brown 等人[39]提出了一個用于生成并行程序的重構(gòu)工具ParaPhrase,從而增加并行程序的可編程性.以上研究以各種形式實現(xiàn)了重構(gòu)工具,并很好地實現(xiàn)了工具的自動化,但都是面向并發(fā)程序的自動重構(gòu)工具,而我們的工具是面向鎖的自動重構(gòu).
McCloskey[40]提出了悲觀的原子塊,在不犧牲性能或兼容性的情況下,保留了類似事務(wù)性內(nèi)存中樂觀原子塊的許多優(yōu)點,并實現(xiàn)了自動重構(gòu)工具Autolocker.Sch?fer 與IBM T.J.Watson 研究中心合作設(shè)計了一種面向Java 顯示鎖的重構(gòu)工具Relocker[5],它能將同步鎖重構(gòu)為可重入鎖,以及將可重入鎖重構(gòu)為讀寫鎖.與Relocker相比,我們的重構(gòu)方法引入了鎖降級、鎖分解模式,使重構(gòu)的適用性更廣.Zhang 等人[6]提出了一種用于在字節(jié)碼級別鎖重構(gòu)方法,由于在字節(jié)碼層實現(xiàn),可視性較差一些;我們的重構(gòu)工作直接在源代碼層實現(xiàn),轉(zhuǎn)換過程更直觀.Zhang 等人[7]提出了一個面向郵戳鎖的自動重構(gòu)工具CLOCK,該重構(gòu)工具支持優(yōu)化讀鎖和鎖升級等操作,但是受限于郵戳鎖的非可重入性,適用范圍有限.我們的研究面向細粒度鎖的重構(gòu)則不受該限制.
Tao 等人[1]提出了針對Java 程序、根據(jù)類屬性域劃分鎖保護域的自動鎖分解重構(gòu)方法,并以Eclipse 插件形式實現(xiàn)了自動重構(gòu)工具.Yu 等人[2]在進行優(yōu)化同步瓶頸的研究中提出了一種鎖分解方法,該方法重新構(gòu)造鎖的依賴關(guān)系,使用細粒度的鎖來保護不相交的共享變量集,并實現(xiàn)了工具SyncProf.Greenhouse 等人[41]根據(jù)類的功能將對象的狀態(tài)劃分為多個子區(qū)域,然后通過不同的鎖來保護每個分區(qū)鎖分解方法.在工業(yè)界,得到廣泛應用的重構(gòu)工具包括集成在IntelliJ IDEA 上的重構(gòu)插件LockSmith[10]以及一個基于Eclipse JDT 的并發(fā)重構(gòu)插件[11],這兩個插件都可以實現(xiàn)鎖分解、鎖合并等重構(gòu).以上研究均是通過不同鎖對象對類中的方法實現(xiàn)鎖分解,我們的研究是通過讀寫鎖的分離在方法內(nèi)實現(xiàn)鎖分解.
本文提出了一種面向細粒度鎖的自動重構(gòu)方法,該方法結(jié)合借助訪問者模式分析、別名分析、負面效應分析等多種程序分析技術(shù)對讀寫模式進行分析,并設(shè)計了基于下推自動機的鎖模式識別方法.以Eclipse 插件的形式實現(xiàn)了自動重構(gòu)工具FLock,在HSQLDB,Jenkins 和Cassandra 等11 個開源項目中使用該重構(gòu)工具,對本文提出的方法進行了驗證.實驗中總計重構(gòu)了1 757 個監(jiān)視器對象,每個程序重構(gòu)平均用時17.5s.與手動重構(gòu)相比,可以有效提升重構(gòu)效率.實驗結(jié)果表明,該重構(gòu)工具可以有效地實現(xiàn)粗粒度鎖到細粒度鎖的轉(zhuǎn)換.我們下一步的工作包括:1) 探索更多的細粒度鎖的重構(gòu)模式,嘗試發(fā)現(xiàn)更多的可以使用細粒度鎖的場景;2) 使用更多實際應用程序?qū)Lock 進行測試;3) 完善重構(gòu)工具FLock,通過比較使用粗粒度鎖和細粒度鎖的程序性能,在重構(gòu)算法中加入性能權(quán)衡,幫助程序員在粗粒度鎖和細粒度鎖之間做出選擇,進而決定是否進行重構(gòu).