基于下推自動(dòng)機(jī)的細(xì)粒度鎖自動(dòng)重構(gòu)方法*

張 楊,邵 帥,張冬雯

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

鎖是并發(fā)程序中用于保護(hù)程序狀態(tài)和數(shù)據(jù)訪問(wèn)正確性的必備措施,然而鎖競(jìng)爭(zhēng)問(wèn)題是目前多核/眾核時(shí)代影響并發(fā)程序性能的主要問(wèn)題之一.鎖競(jìng)爭(zhēng)是指當(dāng)臨界區(qū)被一個(gè)互斥鎖保護(hù)時(shí),如果一個(gè)線程獲得了該鎖,那么其他請(qǐng)求訪問(wèn)該臨界區(qū)的線程都將被阻塞,直到持有該鎖的線程釋放該鎖.鎖競(jìng)爭(zhēng)問(wèn)題的存在,會(huì)嚴(yán)重降低程序并行度,損害程序的可伸縮性,降低多核/眾核處理器的執(zhí)行效率.

不恰當(dāng)?shù)牟l(fā)控制方式通常會(huì)進(jìn)一步加劇鎖競(jìng)爭(zhēng),程序開(kāi)發(fā)人員有時(shí)習(xí)慣于使用粗粒度鎖,例如在方法的修飾符中加入synchronized 關(guān)鍵字,使整個(gè)方法處于鎖的保護(hù)之中.這種加鎖方式雖然可以降低程序開(kāi)發(fā)的復(fù)雜性,然而由于粗粒度鎖控制的臨界區(qū)代碼較長(zhǎng),導(dǎo)致其他想獲取該鎖的線程等待時(shí)間增加,往往會(huì)加劇鎖競(jìng)爭(zhēng).許多開(kāi)發(fā)人員嘗試使用細(xì)粒度鎖,相比于粗粒度鎖,細(xì)粒度鎖只對(duì)一小部分代碼進(jìn)行加鎖,可以有效減少鎖的持有時(shí)間和線程等待時(shí)間,減少鎖競(jìng)爭(zhēng)問(wèn)題的影響.

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

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

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

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

本文的主要貢獻(xiàn)有3 個(gè)方面.

1) 提出了一種面向細(xì)粒度鎖的自動(dòng)重構(gòu)方法;

2) 以Eclipse 插件的形式實(shí)現(xiàn)了自動(dòng)重構(gòu)工具FLock,可以實(shí)現(xiàn)源碼級(jí)別的重構(gòu),幫助開(kāi)發(fā)者完成從粗粒度鎖到細(xì)粒度讀寫(xiě)鎖的自動(dòng)轉(zhuǎn)換;

3) 使用11 個(gè)大型實(shí)際應(yīng)用程序?qū)Lock 進(jìn)行了評(píng)估,并與現(xiàn)有工具Relocker 和CLOCK 進(jìn)行了對(duì)比.

本文第1 節(jié)介紹本文的研究動(dòng)機(jī).第2 節(jié)介紹面向細(xì)粒度鎖的自動(dòng)重構(gòu)方法.第3 節(jié)展示自動(dòng)重構(gòu)工具FLock 的使用界面.在第4 節(jié)給出對(duì)本文所提出的方法和工具的實(shí)驗(yàn)評(píng)估.第5 節(jié)對(duì)相關(guān)工作進(jìn)行介紹.第6 節(jié)是本文的總結(jié).

1 研究動(dòng)機(jī)

讀寫(xiě)鎖是JDK 1.5 版本中引入的一種鎖機(jī)制,它包含一對(duì)相互關(guān)聯(lián)的鎖:讀鎖和寫(xiě)鎖.寫(xiě)鎖是一個(gè)排它鎖,只能由一個(gè)線程持有;讀鎖是一個(gè)共享鎖,在沒(méi)有線程持有寫(xiě)鎖的情況下,讀鎖可以由多個(gè)線程同時(shí)持有,讀鎖允許在訪問(wèn)共享數(shù)據(jù)時(shí)有更大的并發(fā)性.Pinto 等人[12]通過(guò)研究SourceForge 上的2 227 個(gè)含有并發(fā)結(jié)構(gòu)的Java工程發(fā)現(xiàn):Java 并發(fā)包還沒(méi)有得到良好的應(yīng)用,只有大約23%有并發(fā)編程結(jié)構(gòu)的Java 工程在使用.

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

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

從上面的例子可以看出:使用鎖降級(jí)實(shí)現(xiàn)了對(duì)臨界區(qū)的細(xì)粒度保護(hù),加鎖方式更為合理,并且可以在一定程度上減少了鎖競(jìng)爭(zhēng).由于讀鎖是共享鎖,允許多個(gè)線程同時(shí)訪問(wèn),在不發(fā)生寫(xiě)入時(shí)可以增加程序的并發(fā)性.

2 面向細(xì)粒度讀寫(xiě)鎖的重構(gòu)

本節(jié)首先給出了重構(gòu)的整體框架,之后對(duì)程序分析方法、基于下推自動(dòng)機(jī)的鎖模式推斷以及重構(gòu)算法進(jìn)行了介紹.

2.1 重構(gòu)框架

在重構(gòu)過(guò)程中,首先通過(guò)訪問(wèn)者模式對(duì)源碼對(duì)應(yīng)的抽象語(yǔ)法樹(shù)進(jìn)行遍歷,主要用到的程序靜態(tài)分析方法包括鎖集分析、別名分析和負(fù)面效應(yīng)分析:鎖集分析用來(lái)對(duì)監(jiān)視器對(duì)象進(jìn)行收集,并存儲(chǔ)監(jiān)視器對(duì)象和鎖對(duì)象的對(duì)應(yīng)關(guān)系;別名分析用來(lái)解決鎖集中的別名問(wèn)題;負(fù)面效應(yīng)分析用來(lái)分析臨界區(qū)是否產(chǎn)生負(fù)面效應(yīng),并生成對(duì)應(yīng)的臨界區(qū)讀寫(xiě)模式序列.下推自動(dòng)機(jī)對(duì)臨界區(qū)讀寫(xiě)模式序列進(jìn)行識(shí)別,進(jìn)而進(jìn)行鎖推斷,在讀鎖、寫(xiě)鎖、鎖降級(jí)、鎖分解這4 種加鎖模式中選擇相應(yīng)的加鎖模式并進(jìn)行重構(gòu).在重構(gòu)之后,需要對(duì)重構(gòu)前后的一致性進(jìn)行檢測(cè),以保證重構(gòu)的正確性.面向細(xì)粒度鎖的重構(gòu)框架如圖2 所示.

Fig.2 Refactoring framework圖2 重構(gòu)框架圖

2.2 AST解析

在重構(gòu)框架中,首先對(duì)源程序進(jìn)行解析,生成一個(gè)抽象語(yǔ)法樹(shù)(abstract syntax tree,簡(jiǎn)稱(chēng)AST).在具體的解析過(guò)程中,首先通過(guò)Eclipse JDT[14]獲取用戶在進(jìn)行重構(gòu)操作時(shí)所選擇的對(duì)象,然后將用戶選擇的對(duì)象存放到ICompilationUnit 對(duì)象中,最后將ICompilationUnit 對(duì)象對(duì)應(yīng)的元素解析成AST.AST 節(jié)點(diǎn)的類(lèi)型很多,每個(gè)節(jié)點(diǎn)表示一個(gè)源程序中的一個(gè)語(yǔ)法結(jié)構(gòu),包括類(lèi)型、表達(dá)式、語(yǔ)句、聲明等.使用訪問(wèn)者模式分析對(duì)AST 上的同步方法節(jié)點(diǎn)以及同步塊語(yǔ)句進(jìn)行遍歷,找到同步方法和同步塊.在具體的實(shí)現(xiàn)過(guò)程中,通過(guò)繼承EclipseJDT 中提供的抽象類(lèi)ASTVisitor 實(shí)現(xiàn)了一個(gè)子類(lèi)作為具體訪問(wèn)者,用于具體類(lèi)型節(jié)點(diǎn)的遍歷.

2.3 程序分析方法

2.3.1 鎖集分析

在進(jìn)行重構(gòu)之前,首先通過(guò)訪問(wèn)者模式遍歷程序中所有的方法,并對(duì)監(jiān)視器對(duì)象進(jìn)行收集.在重構(gòu)過(guò)程中,還需要對(duì)監(jiān)視器對(duì)象是否產(chǎn)生別名進(jìn)行判斷,進(jìn)行別名分析.別名是指監(jiān)視器對(duì)象名稱(chēng)不同,但是同時(shí)指向相同的內(nèi)存地址.對(duì)于監(jiān)視器對(duì)象不同的臨界區(qū),需要使用不同的鎖對(duì)象進(jìn)行重構(gòu);對(duì)監(jiān)視器對(duì)象相同的臨界區(qū),則使用相同的鎖對(duì)象進(jìn)行重構(gòu).使用一個(gè)鍵-值對(duì)集合對(duì)監(jiān)視器對(duì)象和讀寫(xiě)鎖鎖對(duì)象的映射關(guān)系進(jìn)行存儲(chǔ),監(jiān)視器對(duì)象作為鍵-值對(duì)集合的鍵,監(jiān)視器對(duì)象對(duì)應(yīng)的讀寫(xiě)鎖對(duì)象為鍵-值對(duì)集合的值.

監(jiān)視器集合定義為MonitorSet={m1,m2,…,mn},其中,mi為監(jiān)視器對(duì)象,i∈{1,2,…,n}.監(jiān)視器mi的指向集定義為PoniterSeti,如果對(duì)于任意的mi和mj,i≠j,存在PoniterSeti∩PoniterSetj≠?,則認(rèn)為mi和mj互為別名,并把mi和mj作為別名對(duì)〈mi,mj〉存儲(chǔ)在可能別名集AliasSet中.在進(jìn)行重構(gòu)之前,首先通過(guò)別名集AliasSet構(gòu)建鎖集LockSet,對(duì)別名對(duì)中的監(jiān)視器對(duì)象對(duì)應(yīng)的鎖對(duì)象進(jìn)行實(shí)例化,并存入鎖集LockSet中.別名對(duì)中兩個(gè)監(jiān)視器對(duì)象應(yīng)對(duì)應(yīng)相同的鎖對(duì)象,例如別名對(duì)〈mi,mj〉在LockSet中表示為兩個(gè)鍵值對(duì)組合〈mi:lockk〉,〈mj:lockk〉,其中,lockk為鎖對(duì)象;而沒(méi)有產(chǎn)生別名問(wèn)題的監(jiān)視器對(duì)象在重構(gòu)過(guò)程中對(duì)鎖對(duì)象進(jìn)行實(shí)例化,并存入鎖集LockSet中.

2.3.2 負(fù)面效應(yīng)分析

負(fù)面效應(yīng)是指對(duì)非本地環(huán)境的修改[15],例如一個(gè)操作、方法或表達(dá)式在執(zhí)行過(guò)程中修改了內(nèi)存單元,則程序?qū)a(chǎn)生負(fù)面效應(yīng).由于本文提出的重構(gòu)方法不僅要重構(gòu)讀鎖和寫(xiě)鎖,而且還要進(jìn)行細(xì)粒度的鎖重構(gòu),因此負(fù)面效應(yīng)分析需要對(duì)整個(gè)臨界區(qū)進(jìn)行分析,并生成一個(gè)臨界區(qū)讀寫(xiě)模式序列來(lái)表示臨界區(qū)的讀寫(xiě)操作.在生成臨界區(qū)對(duì)應(yīng)的讀寫(xiě)模式序列時(shí),使用字符r表示臨界區(qū)的一個(gè)讀操作,使用字符w表示一個(gè)寫(xiě)操作,使用字符c表示一個(gè)if 條件判斷語(yǔ)句的開(kāi)始且條件判斷為讀操作,使用字符e表示一個(gè)if 判斷語(yǔ)句的結(jié)束.

本文的負(fù)面效應(yīng)分析通過(guò)WALA[16]的中間表示IR 對(duì)方法中的指令進(jìn)行遍歷分析,判斷指令是否修改內(nèi)存單元.在對(duì)方法調(diào)用指令進(jìn)行分析時(shí),為了保證重構(gòu)工具的執(zhí)行效率,將方法調(diào)用進(jìn)入的層數(shù)限制為5 層.具體分析算法如算法1 所示.

1) 首先獲得臨界區(qū)所對(duì)應(yīng)的指令集,調(diào)用sideEffectAnalysis方法對(duì)每一條指令進(jìn)行遍歷分析(第1 行~第4 行);

2) 在sideEffectAnalysis方法中,首先對(duì)方法調(diào)用進(jìn)入的層數(shù)限制進(jìn)行判斷(第6 行),如果大于限制層數(shù)5層,為了保證臨界區(qū)安全,將其認(rèn)定為一個(gè)寫(xiě)操作,返回字符w(第23 行);

3) 之后,對(duì)每條指令進(jìn)行分析,如果指令修改了靜態(tài)字段,或修改了實(shí)例字段,或修改了堆內(nèi)存,則當(dāng)前指令產(chǎn)生了負(fù)面效應(yīng),返回字符w(第7 行、第8 行);

4) 如果指令是方法調(diào)用指令,首先對(duì)調(diào)用層數(shù)的計(jì)數(shù)器加1(第11 行),之后,遞歸調(diào)用sideEffectAnalysis方法對(duì)被調(diào)用方法里的指令進(jìn)行分析:若被調(diào)用方法包含寫(xiě)指令,則當(dāng)前方法調(diào)用指令產(chǎn)生了負(fù)面效應(yīng),返回字符w(第11 行~第15 行);如果當(dāng)前被調(diào)用方法沒(méi)有產(chǎn)生負(fù)面效應(yīng),則返回字符r(第16 行);

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

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

算法1.負(fù)面效應(yīng)分析算法.

2.4 鎖推斷

在負(fù)面效應(yīng)分析中,使用字符c表示一個(gè)if 語(yǔ)句的開(kāi)始,e表示一個(gè)if 語(yǔ)句的結(jié)束.由于判斷語(yǔ)句每一個(gè)開(kāi)始對(duì)應(yīng)著一個(gè)結(jié)束,負(fù)面效應(yīng)分析會(huì)產(chǎn)生類(lèi)似cnAen(A代表其他操作)的字符序列,其中,n>0.在匹配過(guò)程中,需要記錄c和e的對(duì)應(yīng)關(guān)系,因?yàn)閚的值是不確定的,導(dǎo)致?tīng)顟B(tài)的個(gè)數(shù)也是不確定的,所以我們使用下推自動(dòng)機(jī)對(duì)負(fù)面效應(yīng)分析產(chǎn)生的臨界區(qū)讀寫(xiě)模式序列進(jìn)行模式匹配,以確定程序重構(gòu)后的加鎖模式.

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

?Q={q0,q1,…,q7}是一個(gè)有窮狀態(tài)集;

? Σ={r,w,c,e}是輸入字母表,其中,r代表一個(gè)讀操作,w代表一個(gè)寫(xiě)操作,c代表一個(gè)if 條件判斷語(yǔ)句的開(kāi)始且條件判斷為讀操作,e為一個(gè)if 條件判斷語(yǔ)句的結(jié)束標(biāo)志;

? Γ={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)符號(hào);x為輸入符號(hào);X和T為棧符號(hào),表示當(dāng)下推自動(dòng)機(jī)處于狀態(tài)q、當(dāng)前輸入字符為x且棧頂符號(hào)為X時(shí),則下推自動(dòng)機(jī)的狀態(tài)變?yōu)閝′,并用符號(hào)串T代替棧頂符號(hào)X.符號(hào)串T有3 種形式,分別為X′,X′X,ρ,其中,X′表示用字符X′替換棧頂元素,X′X表示將X′壓入棧中,ρ表示彈出當(dāng)前棧頂元素;

?q0為初始狀態(tài);

?Z0為初始棧頂符號(hào);

?F={q1,q3,q4,…,q7}為終態(tài)集.

下推自動(dòng)機(jī)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 下推自動(dòng)機(jī)Mfg 狀態(tài)轉(zhuǎn)換圖

例如:圖3 中,當(dāng)下推自動(dòng)機(jī)處于狀態(tài)q0、當(dāng)前輸入字符為r且棧頂符號(hào)為Z0時(shí),則下推自動(dòng)機(jī)由狀態(tài)q0轉(zhuǎn)移到q1,并把字符R壓入棧中.

在鎖模式定義之前,為了簡(jiǎn)化表示終態(tài)所識(shí)別的符號(hào)集,首先定義符號(hào)串集合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(寫(xiě)鎖模式的定義).一個(gè)臨界區(qū)被推斷為寫(xiě)鎖,當(dāng)且僅當(dāng)讀寫(xiě)模式序列被終態(tài)q3所接受.

終態(tài)q3所識(shí)別的序列為Sw1={w}+,表示臨界區(qū)只包含寫(xiě)操作,將使用寫(xiě)鎖進(jìn)行同步保護(hù).

定義3(讀鎖模式的定義).一個(gè)臨界區(qū)被推斷為讀鎖,當(dāng)且僅當(dāng)讀寫(xiě)模式序列被終態(tài)q1所接受.

終態(tài)q1所接受的序列集為Sr={SrcSre}+,其中,字符c和字符e的數(shù)量相同.序列集Sr不包含字符w,表示臨界區(qū)沒(méi)有產(chǎn)生負(fù)面效應(yīng),所以使用讀鎖.

定義4(鎖降級(jí)模式的定義).一個(gè)臨界區(qū)被推斷為鎖降級(jí),當(dāng)且僅當(dāng)讀寫(xiě)模式序列被終態(tài)q7所接受.

終態(tài)q7所接受的序列集為Sd={r*cS+er+},表示臨界區(qū)首先包含讀操作或沒(méi)有,之后是一個(gè)if 判斷語(yǔ)句塊,其中,判斷語(yǔ)句為讀操作,語(yǔ)句塊內(nèi)包含其他操作但至少有一個(gè)寫(xiě)操作,if 塊之后包含至少一個(gè)讀操作且只包含讀操作.

定義5(鎖分解模式的定義).一個(gè)臨界區(qū)被推斷為鎖分解,當(dāng)且僅當(dāng)讀寫(xiě)模式序列被終態(tài)q5,q4,q6所接受.

終態(tài)q5識(shí)別的序列集為Ss1={r*cS+e},表示臨界區(qū)首先包含讀操作或沒(méi)有,之后是一個(gè)if 判斷語(yǔ)句塊,判斷語(yǔ)句為讀操作,語(yǔ)句塊內(nèi)包含其他操作但至少有一個(gè)寫(xiě)操作;終態(tài)q4和q6識(shí)別的序列表示讀寫(xiě)操作分離的臨界區(qū),終態(tài)q4所識(shí)別的序列集為Ss2={SrSw1},代表臨界區(qū)前半部分為讀操作后半部分為寫(xiě)操作,終態(tài)q6所識(shí)別的序列集為Ss3={Sw1Sr},代表臨界區(qū)前半部分為寫(xiě)操作后半部分為讀操作.

定義6(下推自動(dòng)機(jī)停機(jī)的定義).當(dāng)輸入讀寫(xiě)模式序列為空,或棧頂符號(hào)為V時(shí),下推自動(dòng)機(jī)停止對(duì)讀寫(xiě)模式序列的識(shí)別.

當(dāng)讀寫(xiě)模式序列為空時(shí),表示臨界區(qū)沒(méi)有操作,則對(duì)臨界區(qū)使用讀鎖;當(dāng)棧頂符號(hào)為V時(shí),所識(shí)別的序列集為Sw2={CS(Sw1∪Sr∪Sd∪Ss1∪Ss2∪Ss3)},表示讀寫(xiě)模式序列不符合細(xì)粒度鎖規(guī)則,臨界區(qū)將使用寫(xiě)鎖進(jìn)行同步保護(hù).

2.5 重構(gòu)算法

本節(jié)給出了重構(gòu)算法的設(shè)計(jì),首先對(duì)相關(guān)代碼建立AST;之后遍歷AST 的所有方法節(jié)點(diǎn),找到同步方法和包含同步塊的方法節(jié)點(diǎn);最后,根據(jù)負(fù)面效應(yīng)分析得到的讀寫(xiě)串對(duì)應(yīng)的鎖模式進(jìn)行重構(gòu).重構(gòu)算法如算法2 所示.具體流程如下.

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

2) 通過(guò)負(fù)面效應(yīng)分析獲得c對(duì)應(yīng)的臨界區(qū)讀寫(xiě)模式序列str(第8 行);

3) 如果c為同步方法或同步塊,則移除synchronized 鎖,并通過(guò)下推自動(dòng)機(jī)識(shí)別臨界區(qū)讀寫(xiě)模式序列str,根據(jù)識(shí)別結(jié)果進(jìn)行重構(gòu)(第9 行~第13 行);

4) 最后對(duì)重構(gòu)前臨界區(qū)c和重構(gòu)后的c_r進(jìn)行一致性檢測(cè)(第17 行):如果符合一致性檢測(cè)規(guī)則,返回重構(gòu)結(jié)果c_r(第15 行);否則,將使用寫(xiě)鎖對(duì)臨界區(qū)c進(jìn)行重構(gòu)(第16 行~第19 行),其中,Consistency 方法基于一致性檢測(cè)規(guī)則進(jìn)行定義(第3 節(jié)給出).

算法2.重構(gòu)算法.

輸入:臨界區(qū)c;

輸出:臨界區(qū)c的重構(gòu)結(jié)果.

3 一致性檢測(cè)

FlexSync[17]是一個(gè)可以通過(guò)施加不同標(biāo)記在不同同步機(jī)制之間進(jìn)行重構(gòu)轉(zhuǎn)換的工具,FlexSync 中定義了一致性檢查規(guī)則,以此來(lái)檢查在不同同步機(jī)制之間轉(zhuǎn)換的一致性.為了盡可能地保證重構(gòu)的正確性,本節(jié)參照FlexSync 的一致性檢測(cè)規(guī)則,給出了FLock 重構(gòu)前后的一致性檢測(cè)規(guī)則.在給出規(guī)則之前,我們首先對(duì)相關(guān)的內(nèi)容進(jìn)行了定義.

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

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

Cbefore和Cafter分別表示重構(gòu)前和重構(gòu)后的臨界區(qū)集合,由于FLock 在重構(gòu)時(shí)需要分割臨界區(qū),因此|Cbefore|< |Cafter|,其中,|C|表示集合C元素個(gè)數(shù).

定義8(重構(gòu)前鎖集合).一個(gè)應(yīng)用程序P中所有用于保護(hù)臨界區(qū)的鎖集合定義為集合S={s1,s2,…,sm}.

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

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

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

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

定義11 說(shuō)明了鎖狀態(tài)的原子性問(wèn)題,舉例來(lái)說(shuō):讀寫(xiě)鎖在由寫(xiě)鎖切換為讀鎖時(shí),可以不用釋放該鎖,在該鎖的內(nèi)部完成鎖狀態(tài)的切換.

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

定義13(Happens-before 關(guān)系).對(duì)于?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ǔ)上的讀寫(xiě)操作發(fā)生序關(guān)系,是Java 語(yǔ)言?xún)?nèi)存一致性的重要準(zhǔn)則.該關(guān)系建立的方式之一是通過(guò)程序中的同步關(guān)系,解鎖操作之前的操作先發(fā)生于解鎖之后獲取該鎖的操作.

基于如上的定義,下面給出了重構(gòu)的一致性檢測(cè)規(guī)則.

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

規(guī)則1 說(shuō)明了重構(gòu)之前處于鎖保護(hù)的臨界區(qū),在重構(gòu)之后仍處于鎖的保護(hù)中.

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

規(guī)則2 說(shuō)明:如果重構(gòu)前臨界區(qū)ci在se的保護(hù)中,即使重構(gòu)后ci被分割為多個(gè)臨界區(qū),保護(hù)這些臨界區(qū)的鎖la和se之間存在一一對(duì)應(yīng)的關(guān)系.如果所有的鎖都可以被重構(gòu),那么重構(gòu)前后的鎖集合應(yīng)滿足|S|=|L|.需要說(shuō)明的是:對(duì)于FLock 重構(gòu)前后鎖的一一對(duì)應(yīng)關(guān)系,通常表現(xiàn)在同步鎖的監(jiān)視器對(duì)象和讀寫(xiě)鎖對(duì)象的一一對(duì)應(yīng)關(guān)系上.

規(guī)則1 和規(guī)則2 從重構(gòu)前后代碼結(jié)構(gòu)上進(jìn)行了一致性說(shuō)明,保證了代碼結(jié)構(gòu)的完整性.

由于FLock 在進(jìn)行面向細(xì)粒度鎖重構(gòu)時(shí)主要采用了降級(jí)鎖和鎖分解兩種方式,下面主要針對(duì)這兩種方式進(jìn)行規(guī)則定義.

規(guī)則3.重構(gòu)前,對(duì)于?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,對(duì)于?cij(1≤i≤n,1≤j≤k),有(la{⊙cij})∧()成立,則鎖降級(jí)重構(gòu)前后可以保證一致性.

規(guī)則3 主要針對(duì)降級(jí)鎖的重構(gòu)進(jìn)行了約束.雖然鎖降級(jí)過(guò)程中會(huì)由寫(xiě)鎖降級(jí)為讀鎖,但該過(guò)程是在鎖的內(nèi)部進(jìn)行轉(zhuǎn)換的,期間并沒(méi)有釋放鎖,可以保證鎖的原子性,所以鎖降級(jí)重構(gòu)前后是一致的.

規(guī)則4.重構(gòu)前,對(duì)于?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,且對(duì)于?cij(1≤i≤n,1≤j≤k),有(la{⊙cij})∧().當(dāng){opi1,opi2,…,opir}?ci時(shí),對(duì)于?opip,opiq(1≤p≤r,1≤q≤r),如果在Cbefore中opip≥opiq,則在Cafter中仍有opip≥opiq.

規(guī)則5.重構(gòu)前,對(duì)于?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,且對(duì)于?cix,ciy(1≤i≤n,1≤x≤k,1≤y≤k,x≠y),有(la{⊙cix,ciy})∧().對(duì)于 ?opip,opiq(1≤p≤r,1≤q≤r),如果{opip}?cix,{opiq}?ciy,opip和opiq訪問(wèn)同一內(nèi)存位置并且opip或opiq是寫(xiě)操作,則不能進(jìn)行鎖分解.

規(guī)則4 和規(guī)則5 共同保證了鎖分解重構(gòu)的一致性.規(guī)則4 對(duì)鎖分解的重構(gòu)進(jìn)行了約束,該規(guī)則通過(guò)檢查臨界區(qū)讀寫(xiě)語(yǔ)句的Happens-before 關(guān)系,確保該關(guān)系在重構(gòu)前后沒(méi)有改變.在FLock 工具的重構(gòu)對(duì)象中,重構(gòu)前后代碼都涉及同步關(guān)系,可以在同步關(guān)系的基礎(chǔ)上建立Happens-before 關(guān)系,進(jìn)而進(jìn)行規(guī)則判定.規(guī)則5 從保持原有臨界區(qū)的原子性角度對(duì)鎖分解進(jìn)行了約束,確保原有臨界區(qū)的原子性沒(méi)有被破壞.如果存在opip和opiq訪問(wèn)同一內(nèi)存位置,有可能因?yàn)榫€程交互而改變?cè)胁僮髡Z(yǔ)義,在這種情況下,FLock 只推斷一個(gè)寫(xiě)鎖而不進(jìn)行鎖分解.

4 重構(gòu)工具實(shí)現(xiàn)

FLock 是在Eclipse JDT 框架下設(shè)計(jì)并以Eclipse 插件的形式實(shí)現(xiàn)的,對(duì)Eclipse 中的基礎(chǔ)類(lèi)Refactoring 和UserInputWizardPage 等進(jìn)行擴(kuò)展,實(shí)現(xiàn)相關(guān)的重構(gòu)邏輯設(shè)計(jì)和可視化的重構(gòu)工具界面設(shè)計(jì).FLock 重構(gòu)界面截圖如圖4 所示,展示了重構(gòu)前后的代碼之間的對(duì)比,其中,左側(cè)為重構(gòu)前的代碼,右側(cè)為重構(gòu)后代碼的預(yù)覽.

Fig.4 Screenshot of the FLock圖4 FLock 重構(gòu)工具界面

5 實(shí)驗(yàn)評(píng)估

本節(jié)對(duì)所提出的方法和工具進(jìn)行了實(shí)驗(yàn)評(píng)估.首先對(duì)實(shí)驗(yàn)配置和測(cè)試程序進(jìn)行介紹,然后從重構(gòu)數(shù)目、改變的代碼行數(shù)和時(shí)間等方面給出了實(shí)驗(yàn)結(jié)果,并對(duì)結(jié)果進(jìn)行了分析[18].

5.1 實(shí)驗(yàn)配置

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

5.2 測(cè)試程序

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

5.3 實(shí)驗(yàn)結(jié)果及分析

在實(shí)驗(yàn)中,使用FLock 對(duì)11 個(gè)測(cè)試程序進(jìn)行自動(dòng)重構(gòu),對(duì)重構(gòu)個(gè)數(shù)、代碼行數(shù)、重構(gòu)后程序的準(zhǔn)確性進(jìn)行了驗(yàn)證,并與重構(gòu)工具Relocker 和CLOCK 進(jìn)行了對(duì)比.

5.3.1 鎖重構(gòu)個(gè)數(shù)

我們首先對(duì)FLock 重構(gòu)后的不同類(lèi)型鎖個(gè)數(shù)進(jìn)行了匯總,重構(gòu)結(jié)果見(jiàn)表2.

從實(shí)驗(yàn)結(jié)果可以看出:在11 個(gè)程序中,共有391 個(gè)粗粒度鎖重構(gòu)為細(xì)粒度鎖.內(nèi)置監(jiān)視器對(duì)象轉(zhuǎn)換為鎖降級(jí)模式的個(gè)數(shù)有25 個(gè),其中,HSQLDB 中最多,包含6 個(gè),集中分布在org.hsqldb 包里的Session 類(lèi)和Table 類(lèi)中,這兩個(gè)類(lèi)分別是用來(lái)執(zhí)行session 和保存數(shù)據(jù)庫(kù)表的數(shù)據(jù)結(jié)構(gòu)和方法;在RxJava 和MINA 中,由于原程序中包含的內(nèi)置監(jiān)視器對(duì)象較少,在重構(gòu)之后沒(méi)有監(jiān)視器對(duì)象轉(zhuǎn)換為鎖降級(jí)模式.內(nèi)置監(jiān)視器對(duì)象轉(zhuǎn)換為鎖分解模式的個(gè)數(shù)為127 個(gè),在HSQLDB,Cassandra 和JGroups 測(cè)試程序中重構(gòu)后轉(zhuǎn)換為鎖分解模式的個(gè)數(shù)較多;測(cè)試程序Fop 中包含32 個(gè)內(nèi)置監(jiān)視器對(duì)象,重構(gòu)后沒(méi)有內(nèi)置監(jiān)視器轉(zhuǎn)換為鎖分解模式.在重構(gòu)為讀鎖方面,有293 個(gè)內(nèi)置監(jiān)視器對(duì)象轉(zhuǎn)換為讀鎖,在測(cè)試程序HSQLDB 和Cassandra 中,讀鎖的占比相對(duì)較高;在程序Antlr 和MINA 中,使用鎖分解模式比使用讀鎖的個(gè)數(shù)多.

Table 1 Benchmarks and their configuration表1 測(cè)試程序及其配置

Table 2 Refactoring results by FLock表2 FLock 重構(gòu)結(jié)果

Table 3 Comparison of Relocker and FLock表3 Relocker 和FLock 重構(gòu)對(duì)比

Table 4 Comparison of CLOCK and FLock表4 CLOCK 和FLock 重構(gòu)對(duì)比

在重構(gòu)工具FLock 中,加入了對(duì)臨界區(qū)的一致性規(guī)則檢測(cè),表2“違背一致性規(guī)則”列展示了不滿足一致性檢測(cè)的臨界區(qū)數(shù)目.對(duì)于所有的測(cè)試程序,除了MINA 測(cè)試程序外,其余10 個(gè)程序均存在違背一致性檢測(cè)規(guī)則的情況發(fā)生,共有139 個(gè),其中,HSQLDB 中最多,有41 個(gè).對(duì)于這些不滿足一致性規(guī)則的臨界區(qū),我們沒(méi)有對(duì)他們進(jìn)行鎖分解,而是采用寫(xiě)鎖作為臨界區(qū)的保護(hù)模式.

5.3.2 重構(gòu)前后改變的代碼行數(shù)

我們對(duì)重構(gòu)前后改變的代碼行數(shù)進(jìn)行了統(tǒng)計(jì),這些代碼行數(shù)的改變?cè)谝欢ǔ潭壬戏从沉顺绦騿T在手動(dòng)重構(gòu)時(shí)所需要花費(fèi)的工作量.我們使用SLOCCount(https://dwheeler.com/sloccount/)工具對(duì)代碼行數(shù)進(jìn)行統(tǒng)計(jì),該工具是由David A.Wheeler 開(kāi)發(fā)的用于精確統(tǒng)計(jì)代碼行數(shù)的工具,不僅適用于多個(gè)操作系統(tǒng)平臺(tái),而且適合于多種語(yǔ)言.

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

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

5.3.3 重構(gòu)時(shí)間

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

5.3.4 重構(gòu)的正確性

為了對(duì)重構(gòu)后測(cè)試程序的正確性進(jìn)行驗(yàn)證,我們主要從以下3 個(gè)方面進(jìn)行了驗(yàn)證,包括驗(yàn)證推斷鎖的類(lèi)型是否正確、加鎖和解鎖的位置是否正確、鎖結(jié)構(gòu)的使用是否正確.由于目前沒(méi)有相關(guān)的自動(dòng)驗(yàn)證工具,我們主要采用了手工檢查的方式.

在驗(yàn)證推斷鎖類(lèi)型的準(zhǔn)確性方面,我們手動(dòng)地檢查每一個(gè)測(cè)試程序中每一個(gè)臨界區(qū)的代碼,我們發(fā)現(xiàn):推斷出來(lái)的每一個(gè)鎖都符合我們的推斷規(guī)則,都是正確的類(lèi)型.此外,我們發(fā)現(xiàn):在Cassandra 測(cè)試程序中,部分代碼在重構(gòu)前就使用了讀寫(xiě)鎖.我們將這些讀寫(xiě)鎖重構(gòu)為同步鎖,然后使用Flock再對(duì)其進(jìn)行重構(gòu),結(jié)果發(fā)現(xiàn):Flock推斷的鎖類(lèi)型和原有的鎖類(lèi)型基本相同,只有一處存在不同之處.該處發(fā)生在CompactionStrategyManager 類(lèi)的maybeReload 方法中,該方法原本使用寫(xiě)鎖,但是Flock 將其推斷為鎖分解的方式,經(jīng)過(guò)手工檢查發(fā)現(xiàn):使用鎖分解的方式并未改變程序原邏輯,是正確的細(xì)粒度加鎖方式.

在判斷加鎖和解鎖位置以及鎖的使用方面,我們主要檢查了:(1) 每種鎖的加鎖操作是否對(duì)應(yīng)一個(gè)解鎖操作;(2) 解鎖操作是否被放入finally 語(yǔ)句塊中;(3) 細(xì)粒度鎖的結(jié)構(gòu)是否正確.經(jīng)過(guò)檢查,我們并未發(fā)現(xiàn)相關(guān)錯(cuò)誤.我們也通過(guò)運(yùn)行程序的方式檢查了程序的正確性,發(fā)現(xiàn)這些程序在執(zhí)行過(guò)程中并沒(méi)有報(bào)錯(cuò),都可以正確運(yùn)行.

5.3.5 重構(gòu)前后性能對(duì)比

本節(jié)選取HSQLDB,Jenkins,Cassandra,JGroups 和SPECjbb2005 進(jìn)行性能測(cè)試.之所以選擇這5 個(gè)程序,是因?yàn)樗鼈冊(cè)诎l(fā)布的版本中都提供了相應(yīng)的基準(zhǔn)測(cè)試程序.

HSQLDB 提供了JDBCBench 測(cè)試程序,該程序的測(cè)試結(jié)果如圖5 所示,其中:橫坐標(biāo)為處理事務(wù)數(shù),分別給出了事務(wù)數(shù)為100k,200k,300k 和400k 的情況;縱坐標(biāo)為事務(wù)處理率.從圖中可以看出:該測(cè)試程序在處理100k個(gè)事務(wù)時(shí),程序重構(gòu)后使用細(xì)粒度讀寫(xiě)鎖的事務(wù)率比重構(gòu)前使用同步鎖的事務(wù)率略有提升,但不明顯;在處理事務(wù)量達(dá)到200k,300k 和400k 時(shí),重構(gòu)后比重構(gòu)前的程序在事務(wù)率上的提升大約有15%,19%和22%,提升較為明顯.總的來(lái)說(shuō),HSQLDB 使用細(xì)粒度的讀寫(xiě)鎖在事務(wù)率方面重構(gòu)后比重構(gòu)前平均提升了18%,說(shuō)明使用細(xì)粒度鎖有助于提升HSQLDB 的性能,而我們?cè)O(shè)計(jì)的工具可以幫助更快地轉(zhuǎn)換為細(xì)粒度鎖.

對(duì)于Jenkins,我們選取了其中的單元測(cè)試程序UpdateCenterTest,FunctionsTest 和FilePathTest 進(jìn)行了測(cè)試.圖6 給出了3 個(gè)單元測(cè)試的執(zhí)行時(shí)間,可以看出:單元測(cè)試UpdateCenterTest 在重構(gòu)前后程序的執(zhí)行時(shí)間基本沒(méi)有變化,而FunctionsTest 在重構(gòu)后執(zhí)行時(shí)間縮短了17.3%,FilePathTest 在重構(gòu)后執(zhí)行時(shí)間縮短了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)前后的性能比較

對(duì)于JGroups,我們選取了測(cè)試程序RoundTrip,RoundTripRpc,UnicastTest 和UnicastTestRpc 進(jìn)行測(cè)試,這4個(gè)測(cè)試程序都是測(cè)試兩個(gè)群組之間消息的發(fā)送與接收能力.實(shí)驗(yàn)結(jié)果如圖7 所示,其中,橫坐標(biāo)為測(cè)試程序,縱坐標(biāo)為請(qǐng)求處理率.從結(jié)果中可以看出:4 個(gè)測(cè)試在重構(gòu)后請(qǐng)求處理率都有所提升,分別提升了15.5%,7%,5%和9%.

對(duì)于測(cè)試程序Cassandra,我們選取了其中的單元測(cè)試程序BatchTests,SimpleQueryTest 和ManyRowsTest進(jìn)行性能測(cè)試,圖8 給出了3 個(gè)單元測(cè)試程序重構(gòu)前后的執(zhí)行時(shí)間.對(duì)于單元測(cè)試程序BatchTests,Cassandra 重構(gòu)后程序的執(zhí)行時(shí)間與重構(gòu)前程序的執(zhí)行時(shí)間基本相同;對(duì)于SimpleQueryTest 和ManyRowsTest 這兩個(gè)單元測(cè)試程序,執(zhí)行時(shí)間都有不同程度的下降,都較重構(gòu)前的執(zhí)行時(shí)間大約縮短了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 運(yùn)行結(jié)果,其中,圖9(a)給出了吞吐量隨線程數(shù)變化的情況,圖9(b)給出了堆內(nèi)存使用的百分比隨著線程數(shù)變化的情況.從圖9(a)可以看出:當(dāng)吞吐量達(dá)到峰值之后,使用同步鎖的吞吐量要比使用細(xì)粒度讀寫(xiě)鎖的吞吐量稍微高一些.這也說(shuō)明并不是所有情況下,使用細(xì)粒度讀寫(xiě)鎖性能都比使用同步鎖要好.圖9(b)給出了在不同線程執(zhí)行情況下使用的堆內(nèi)存占總內(nèi)存的百分比,在線程數(shù)為8 時(shí),程序重構(gòu)前的堆內(nèi)存使用占比高于程序重構(gòu)后;而在線程數(shù)為12 時(shí),程序重構(gòu)后的堆內(nèi)存使用占比高于程序重構(gòu)前.這說(shuō)明在不同鎖模式和不同線程數(shù)下堆內(nèi)存的使用情況各有不同,而我們?cè)O(shè)計(jì)的重構(gòu)工具為開(kāi)發(fā)人員提供一種快速的細(xì)粒度鎖和粗粒度鎖重構(gòu)的方式,開(kāi)發(fā)人員可以通過(guò)測(cè)試來(lái)找到程序堆內(nèi)存使用最合適的情況.

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

5.3.6 工具對(duì)比

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

表3 給出了Relocker 和FLock 重構(gòu)結(jié)果的對(duì)比,可以看出:Relocker 只使用讀鎖或?qū)戞i進(jìn)行同步保護(hù),而且還存在不能重構(gòu)的問(wèn)題;FLock 不僅可以推斷讀鎖和寫(xiě)鎖,而且可以實(shí)現(xiàn)更為細(xì)粒度的鎖重構(gòu).在讀鎖的推斷上,FLock 比Relocker 推斷出了更多的讀鎖,經(jīng)人工驗(yàn)證,使用FLock 進(jìn)行重構(gòu)后的讀鎖使用正確.Relocker 的推斷結(jié)果不準(zhǔn)確的原因可能與分析深度有關(guān),這里的分析深度使用的是Relocker 的默認(rèn)值.在重構(gòu)時(shí)間上,Relocker重構(gòu)HSQLDB 耗時(shí)7s,FLock 耗時(shí)6s;Cassandra 程序規(guī)模較大,Relocker 重構(gòu)耗時(shí)50s,FLock 重構(gòu)耗時(shí)42s.總體來(lái)看,FLock 在重構(gòu)效率上有所提升.

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

關(guān)于重構(gòu)后程序性能方面,我們對(duì)HSQLDB 和SPECjbb2005 這兩個(gè)程序使用不同重構(gòu)工具重構(gòu)后,使用3種鎖的性能進(jìn)行了對(duì)比.HSQLDB 的實(shí)驗(yàn)結(jié)果如圖10 所示,結(jié)果表明,粗粒度的讀寫(xiě)鎖和郵戳鎖在事務(wù)率上要低于使用細(xì)粒度讀寫(xiě)鎖的程序.SPECjbb2005 的實(shí)驗(yàn)結(jié)果如圖11 所示,由于JDK 版本原因,Relocker 不能對(duì)SPECjbb2005 進(jìn)行重構(gòu),這里只對(duì)比了CLOCK 和FLock 的重構(gòu)結(jié)果.可以看出:程序在使用細(xì)粒度讀寫(xiě)鎖時(shí),相較于使用粗粒度讀寫(xiě)鎖和郵戳鎖的程序,事務(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 有效性威脅

實(shí)驗(yàn)中有幾個(gè)可能威脅有效性的因素.

1) 由于并發(fā)程序執(zhí)行的不確定性,不排除性能測(cè)試實(shí)驗(yàn)結(jié)果可能存在細(xì)微的偏差.為了避免誤差,我們所有實(shí)驗(yàn)結(jié)果都是在10 次運(yùn)行的基礎(chǔ)上取平均值得到的;

2) 在實(shí)驗(yàn)中,我們采用手工檢查的方式對(duì)重構(gòu)后程序的正確性進(jìn)行驗(yàn)證.手動(dòng)的檢查方式存在著一些不足之處,可能會(huì)出現(xiàn)人為驗(yàn)證不準(zhǔn)確等問(wèn)題.為了減少不準(zhǔn)確情況的發(fā)生概率,我們選取了兩組學(xué)生分別進(jìn)行兩次檢查的方式,盡可能避免出現(xiàn)問(wèn)題;

3) 本實(shí)驗(yàn)只選取了11 個(gè)應(yīng)用程序?qū)Lock 進(jìn)行了評(píng)估,它們并不能代表所有程序,不能完全證明FLock在所有的應(yīng)用程序中可以成功完成重構(gòu).但是我們選取的應(yīng)用程序涉及數(shù)據(jù)庫(kù)、群組通信、物聯(lián)網(wǎng)等多個(gè)領(lǐng)域,具有很好的代表性.未來(lái)的工作中,我們也將使用更多應(yīng)用程序?qū)Lock 進(jìn)行測(cè)試.

6 相關(guān)工作

本文實(shí)現(xiàn)了面向細(xì)粒度讀寫(xiě)鎖的自動(dòng)重構(gòu)工具,我們主要關(guān)注的相關(guān)工作有兩個(gè)方面:面向鎖的優(yōu)化和自動(dòng)化的重構(gòu)工具.

6.1 面向鎖的優(yōu)化

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

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

6.2 自動(dòng)化的重構(gòu)工具

Dig 等人提出了一個(gè)軟件并行化重構(gòu)工具CONCURRENCER[36],該工具可以將串行的Java 代碼進(jìn)行并行化重構(gòu),以及面向循環(huán)并行化重構(gòu)的重構(gòu)工具Relooper[37].Wloka 等人[38]提出了一個(gè)用于把串行程序轉(zhuǎn)變?yōu)榭芍厝氲某绦虻淖詣?dòng)重構(gòu)工具Reentrancer,從而使程序更易并行化實(shí)現(xiàn).Brown 等人[39]提出了一個(gè)用于生成并行程序的重構(gòu)工具ParaPhrase,從而增加并行程序的可編程性.以上研究以各種形式實(shí)現(xiàn)了重構(gòu)工具,并很好地實(shí)現(xiàn)了工具的自動(dòng)化,但都是面向并發(fā)程序的自動(dòng)重構(gòu)工具,而我們的工具是面向鎖的自動(dòng)重構(gòu).

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

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

7 總 結(jié)

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