處理Java程序不確定性問題的技術(shù)研究和綜述

季曉楓 宋昶衡 李 弋

(復(fù)旦大學(xué)軟件學(xué)院 上海 201203) (上海市數(shù)據(jù)科學(xué)重點實驗室(復(fù)旦大學(xué)) 上海 201203)

0 引 言

隨著硬件的發(fā)展，小到個人計算機大到數(shù)百上千核的超級計算機，多核處理器已經(jīng)十分普遍。為了能夠充分利用多核處理器性能，并行程序變得越來越流行，并開始占據(jù)了主流的地位。

然而，與單線程程序不同，并行程序并不能保證每一次的執(zhí)行與之前的執(zhí)行從結(jié)果和性能上都完全相同。在多核處理器上執(zhí)行并行程序的過程中，搶占式的線程切換使得程序在不同的運行過程中，線程的調(diào)度過程都是不確定的行為。而在多核處理器上，對共享變量的訪問更是加劇了程序的不確定性。在不同的執(zhí)行循環(huán)過程中，共享變量訪問的讀寫依賴關(guān)系也是無法確定的。由于每次執(zhí)行時共享變量的放回值都可能變化，這導(dǎo)致程序的運行路徑在多次的執(zhí)行之間也可能是不同的。

而在Java虛擬機上，這一不確定性變得更為顯著。Java語言在過去的十數(shù)年中一直是最受歡迎的語言之一。Java受歡迎的一個非常重要的原因就是Java可運行在虛擬機上，保證了Java程序的可移植性，獨立性以及安全性。然而，在Java虛擬機中的使用的許多機制都會給Java程序的執(zhí)行帶來不確定性，這其中包括了即時編譯器、垃圾收集等。即時編譯器通過對程序的采樣分析決定對哪些方法進行優(yōu)化，垃圾收集機制的觸發(fā)也是在運行時決定的，這些機制在Java虛擬機中都由額外的線程來完成。這使得即使是單線程的Java程序，其不確定性也會比C或者C++程序來的更為顯著。圖1展示了Java的多線程程序測試集DaCapo的性能結(jié)果不確定性。圖中黑色方塊代表了變異系數(shù)的區(qū)間。其中，變異系數(shù)最大的sunflow達到了12.12%，平均變異系數(shù)達到了6.87%。由此可見，不確定性在多線程Java程序中表現(xiàn)得非常明顯。

圖1 DaCapo測試集的不確定性

程序的不確定性會給許多原本看似簡單工作帶來新的問題。并行程序的不確定性主要是由于其本身的路徑不確定性所產(chǎn)生的，而路徑的不確定性會給許多相關(guān)工作帶來問題。首先，這會很大程度上影響性能評估的工作，路徑的不確定性會導(dǎo)致性能的不穩(wěn)定。當研究人員要評估性能結(jié)果的優(yōu)劣時，受到程序不確定性的影響，簡單地取均值的方法就不再適用，簡單的方法難以總結(jié)和描述程序的性能表現(xiàn)。其次，路徑的不確定性會給錯誤調(diào)試帶來很大的挑戰(zhàn)。在進行循環(huán)調(diào)試的時候，如果不能每次都重現(xiàn)錯誤發(fā)生的過程，就會使得調(diào)試變得非常困難。

本文首先分析了Java虛擬機內(nèi)部會給程序帶來不確定性的原因，并對于不確定性在性能評估和錯誤調(diào)試方面造成的問題進行了分析。在此基礎(chǔ)上，本文從處理帶有不確定性的性能數(shù)據(jù)以及控制程序不確定性的技術(shù)兩個方面對處理Java虛擬機性能不確定性的方法進行了總結(jié)。此外，在不確定性程序的錯誤調(diào)試方面，本文對解決這一問題的常見確定性重放技術(shù)進行了分析和總結(jié)。最后，本文對適用于這兩個問題的常見的框架的技術(shù)思路進行了分析和比較，對于處理Java虛擬機不確定性的技術(shù)發(fā)展的未來可能的發(fā)展方向進行了展望。

1 Java程序不確定性造成的問題

Java程序的不確定性問題所帶來的影響主要包含兩個方面：(1) 性能結(jié)果的不確定性對于性能分析的影響；(2) 路徑不確定性對于對錯誤調(diào)試的影響。本節(jié)首先將對產(chǎn)生不確定性的因素進行總結(jié)，然后將分別對這兩個方面影響進行分析。

1.1 多線程程序的不確定性

Java多線程程序本身的多線程執(zhí)行就會給程序帶來不確定性。首先，線程的調(diào)度不能保證在每一次的執(zhí)行中，每個線程的調(diào)度順序都完全一致。其次，在有些多線程程序中，工作并不會均勻地分配到每一個線程中去，比如，在多個線程競爭訪問任務(wù)隊列的時候，每次程序的執(zhí)行，各個線程所完成的工作都是隨機的。最后，線程遷移和訪問共享資源的競爭都會增加多線程程序在執(zhí)行過程中的不確定性。

1.2 Java程序的不確定性

除了多線程執(zhí)行本身的不確定性之外，在Java虛擬機中，也有許多部分會對于程序性能產(chǎn)生影響，大致包括以下幾個部分：即時編譯器、線程調(diào)度、垃圾收集機制以及其他的一些系統(tǒng)因素。

(1) 即時編譯器 Java程序在運行前被保存為字節(jié)碼的形式，Java虛擬機可以解釋執(zhí)行字節(jié)碼狀態(tài)的程序，但是這樣做的效率非常低。于是Java引入了即時編譯器。即時編譯器通常會對程序進行采樣分析，尋找程序中的熱點，當程序中的某個方法成為了熱點之后，即時編譯器會對該方法進行優(yōu)化編譯。由于并行程序本身的不確定性，在多次執(zhí)行中，觸發(fā)即時編譯器的方法的順序并不會是固定的，這就會導(dǎo)致程序在不同執(zhí)行循環(huán)中的性能變化。此外，即時編譯器本身作為Java虛擬機中的一個或多個線程進行工作，同樣會增加程序的不確定性。

(2) 線程調(diào)度 和其他并行程序一樣，Java并行程序的線程調(diào)度也是程序不確定性的來源之一。Java虛擬機會直接對線程進行調(diào)度，或者對線程進行封裝之后交由系統(tǒng)來進行調(diào)度。在不同的執(zhí)行循環(huán)中，程序可能經(jīng)過了完全不同的調(diào)度，導(dǎo)致線程之間不同的交互，最終對性能產(chǎn)生影響。

(3) 垃圾收集 垃圾收集機制在Java虛擬機中同樣由額外的線程實現(xiàn)，大部分垃圾收集器在執(zhí)行過程中還會將Java程序暫停。此外，垃圾收集的過程也會對程序的不確定性造成影響，這取決于使用的垃圾收集機制是確定性的或者是非確定性的。

此外，其他的一些系統(tǒng)因素，比如系統(tǒng)中斷，外部IO也會增加程序的不確定性。

1.3 不確定性對于性能評估的影響

傳統(tǒng)的性能評估方法大致包含了取平均、取中位數(shù)、取最好值、次好值以及最差值等幾種[1]。當研究需要獲得性能測試的平均結(jié)果時，取平均數(shù)和中位數(shù)是比較好的選擇。取最佳值和最差值是兩種比較特殊的方法。取最佳值法通常用于尋找類加載和即時編譯器等虛擬機系統(tǒng)行為對Java程序影響最大的情況下的性能，而與之相對應(yīng)的，取最差值法是用于尋找類加載和即時編譯器對程序運行影響最小的情況下的性能。

以上這些性能評估方法給出的結(jié)果都是單一的數(shù)值表示。但是，由于Java程序的不確定性，多次運行的Java程序的性能結(jié)果會有不同幅度的波動。僅僅用一個數(shù)字來代表程序的性能沒有辦法完整的描述Java程序的性能。比如Java程序性能的波動范圍以及在相應(yīng)范圍上的分布都是一個數(shù)字所無法描述的。這時，就可以使用置信區(qū)間來進行描述。置信區(qū)間可以表示出Java程序性能的波動范圍，給出程序性能落在某個區(qū)間上的概率。假如程序結(jié)果的分布是正態(tài)分布的話，置信區(qū)間配合變異系數(shù)可以很好地描述Java程序的不確定性。然而如果Java程序不是正態(tài)分布的話就需要配合其他的方法來對程序結(jié)果進行描述。

對于程序的性能評估來說，如何在更少的測試時間內(nèi)得到更精確的結(jié)果是這個問題的主要研究方向。

此外，對于Java程序的性能評估來說，不同的階段會有不同的不確定性影響因素。如果在一次啟動Java虛擬機的過程中多次循環(huán)運行一個程序，那么前幾次循環(huán)的性能會受到動態(tài)類裝載和即時編譯器非常大的影響。而在之后的循環(huán)中，程序性能的波動幅度，也就是變異系數(shù)會逐漸穩(wěn)定，在評估Java程序的性能是要將這兩種狀態(tài)下的性能區(qū)分開來評估，分為啟動狀態(tài)和穩(wěn)定狀態(tài)[2-3]。

1.4 路徑不確定性對錯誤調(diào)試的影響

由于并行程序在執(zhí)行過程中的存在路徑不確定性，這對錯誤調(diào)試帶來很大的麻煩。路徑不確定性對于錯誤的影響主要在于線程切換和同步，以及對共享變量訪問的依賴關(guān)系。在不同的執(zhí)行循環(huán)中，搶占式的線程切換以及線程同步都會導(dǎo)致不同的線程調(diào)度結(jié)果。這兩個因素，同共享變量的不同訪問順序一起，造成了程序執(zhí)行路徑的不同。而在并行錯誤調(diào)試的過程中，對于內(nèi)存訪問順序的重現(xiàn)在解決死鎖、數(shù)據(jù)競爭等問題時又是至關(guān)重要的。如果對一個共享變量的訪問順序發(fā)生了變化的話，很可能程序就不會再進入死鎖狀態(tài)。

確定性重放技術(shù)分為兩個階段：(1) 記錄階段，在記錄階段，確定性重放的工具會記錄程序一次運行中的信息，并存放到文件中；(2) 重放階段，工具會讀取記錄到文件中的信息，并按照記錄的運行軌跡重現(xiàn)之前程序的運行路徑。

一般而言，記錄階段需要記錄程序中所有的不確定因素，這樣才能確保在重放階段時的執(zhí)行路徑和記錄的那次運行一模一樣。然而，隨著多線程程序的規(guī)模變得越來越龐大，其中用到的共享變量訪問越來越多，完全記錄所有的不確定性信息變得越來越不現(xiàn)實。所以，現(xiàn)今對于確定性重放的研究主要目標就是降低記錄階段的開銷，減小記錄階段用到的日志文件大小。

此外，對于Java程序而言，錯誤也可能發(fā)生在虛擬機內(nèi)部，比如即時編譯器或者垃圾收集階段，所以也有研究針對Java程序的機制做了確定性重放的工具，比如Ogata[21]等的工作。

2 處理性能不確定性

在對Java程序進行評估的過程中，Java程序的不確定性會帶來很多問題。

首先，在JVM的一次生命周期中運行多次Java程序循環(huán)時，即時編譯器、類裝載等因素會使得初始的多次運行的行為表現(xiàn)與之后的運行截然不同。如何對這兩種狀態(tài)進行劃分并且分別進行性能評估是進行Java程序評估時非常重要的一點。

其次，由于Java多線程程序的不確定性比一般的多線程程序更為復(fù)雜，如何使用更少的運行遍數(shù)進行性能評估也是亟待解決的課題。

1.2.1 細胞培養(yǎng)及分組 將SK-N-SH人神經(jīng)母細胞瘤細胞接種于含10%胎牛血清、100 U/mL青霉素、100 mg/L鏈霉素的RPMI1640培養(yǎng)液中，于37℃、5%CO2的常規(guī)培養(yǎng)箱培養(yǎng)。2～3 d換液，0.25%胰酶消化傳代，觀察細胞生長情況，取對數(shù)生長期細胞用于實驗。實驗分為不同濃度螺內(nèi)酯組和對照組，螺內(nèi)酯組加入配置好的螺內(nèi)酯溶液，終濃度分別為5、10及20 μmol/L，不加藥的為對照組。

2.1 利用統(tǒng)計學(xué)處理性能不確定性

由于即時編譯器以及類加載機制的存在，在利用統(tǒng)計學(xué)處理Java程序的不確定性時首先需要劃分出啟動狀態(tài)下和穩(wěn)定狀態(tài)下的Java程序結(jié)果。其后，可以對這兩種狀態(tài)下的結(jié)果使用統(tǒng)計學(xué)的方法進行相應(yīng)的處理。

Java程序的不確定性會使得程序的結(jié)果分布在一個區(qū)間上。當這些結(jié)果在區(qū)間上的分布呈現(xiàn)正態(tài)的時候，可以簡單地使用置信區(qū)間來描述程序的性能，并使用參數(shù)檢驗來比較兩組數(shù)據(jù)的性能。但是，當程序的性能結(jié)果分布呈現(xiàn)非正態(tài)的時候就需要使用非參數(shù)檢驗來判斷兩組數(shù)據(jù)的性能優(yōu)劣。

(1) 對正態(tài)分布數(shù)據(jù)的處理 正態(tài)分布，又稱高斯分布，以平均數(shù)為中心左右對稱，向兩邊逐漸均勻下降。正態(tài)分布是最常見的分布之一，而且使用很簡單的參數(shù)就能夠?qū)υ摲植歼M行描述。此外，最重要的是，根據(jù)中心極限定理，即使是非正態(tài)分布，大量獨立同分布的隨機變量的平均數(shù)是正態(tài)分布的。這給了研究者使用正態(tài)分布來對多線程程序性能進行描述的機會。

Georges等[1]綜合了一系列的統(tǒng)計學(xué)方法，提出了一種嚴格的統(tǒng)計學(xué)測試框架，用來評估Java程序性能。這種框架針對啟動狀態(tài)和穩(wěn)定狀態(tài)分別做了處理。

首先是啟動狀態(tài)，啟動狀態(tài)的性能會受到類加載，即時編譯器等因素的影響。針對啟動狀態(tài)，Georges等提出的方法如下：測量啟動狀態(tài)的Java程序性能需要多次啟動虛擬機，每次只運行程序一遍，記錄其運行時間。然后根據(jù)指定的置信度計算其置信區(qū)間。對于啟動狀態(tài)性能的比較，可以使用z檢驗或者t檢驗來實現(xiàn)。

其次，是穩(wěn)定狀態(tài)的性能評估。穩(wěn)定狀態(tài)時由于程序已經(jīng)運行過一段時間，受到即時編譯器的影響比較少，也幾乎不會收到類加載的影響。為了測量穩(wěn)定狀態(tài)的性能，首先要確定程序的運行在什么時候進入了穩(wěn)定狀態(tài)。Georges等[1]使用在一次虛擬機的生命周期中多次運行一個比較短的Java程序的方法來模擬長期運行的Java程序。他們提出的方法如下：假設(shè)整個測試同樣要運行p次虛擬機周期。在每個虛擬機的生命周期中，循環(huán)運行Java程序q次。在程序循環(huán)運行了k次之后，計算最后k次運行的變異系數(shù)，當變異系數(shù)小于預(yù)設(shè)的閾值時，則認為該k次運行都達到了穩(wěn)定狀態(tài)，記錄其結(jié)果。計算每次虛擬機生命周期中的k次穩(wěn)定狀態(tài)運行結(jié)果的平均值，那么這q個平均值就構(gòu)造了一個新的性能結(jié)果分布。計算這個新的分布在指定置信水平上的置信區(qū)間，用該置信區(qū)間來評價程序在穩(wěn)定狀態(tài)中的性能。

在評估穩(wěn)定狀態(tài)性能的過程中，之所以需要記錄多次虛擬機運行中的數(shù)據(jù)，而不是在虛擬機的一次運行中就多次循環(huán)把所有數(shù)據(jù)都跑完，是為了保證最終結(jié)果的正態(tài)分布性。在虛擬機每一次的運行中，多次循環(huán)后的k個結(jié)果之間并不是獨立的，但是多次虛擬機的運行之間是互相獨立的，所以基于中心極限定理，取每次虛擬機運行的k個結(jié)果的平均值就能夠得到一個獨立的結(jié)果分布。

隨后Kalibera等[4]為了提高性能評估的效率，針對性能評估的各個階段提出了一系列的建議，用以減少性能評估中的重復(fù)次數(shù)，并在合理的時間內(nèi)完成性能評估。他們提出了一種新的識別穩(wěn)定狀態(tài)的方法。這種方法通過識別程序的運行是否進入“獨立”狀態(tài)來判斷循環(huán)是否已經(jīng)穩(wěn)定。“獨立”狀態(tài)意味著程序這次的運行與之前的循環(huán)無關(guān)。該方法利用了Lag圖、ACF圖和運行序列圖，幫助研究人員根據(jù)這三種圖來進行人工判斷。通過這種方法，可以快速地判斷一個程序是否進入了“獨立”的狀態(tài)。Kalibera等[4]認為，對于沒有在較短的時間內(nèi)進入“獨立”狀態(tài)的程序，建議選取多次虛擬機生命周期中初始化狀態(tài)之后的第一次循環(huán)作為性能評估的對象。而對于每次虛擬機運行中的初始化狀態(tài)，同樣用人工識別的方法，對運行序列圖進行觀察并選取，這個工作也能在數(shù)秒內(nèi)完成。

除此之外，Kalibera等[4]還評估了Java程序在虛擬機運行內(nèi)部循環(huán)時和多次虛擬機運行間的性能波動幅度，并且發(fā)現(xiàn)有一些程序在虛擬機運行間的波動性遠大于內(nèi)部循環(huán)時的波動性。由此提出，對于類似的程序可以減少內(nèi)部循環(huán)的重復(fù)次數(shù)，增加虛擬機的運行次數(shù)，而對于特性相反的程序就可以減少虛擬機運行的次數(shù)，增加內(nèi)部循環(huán)數(shù)，減少由于虛擬機重新啟動所需的熱身時間。

與文獻[1]之前的方法進行比較，之前的方法對于達不到“獨立”狀態(tài)的程序并不適用，而文獻[4]通過對于性能評估中的多個重復(fù)周期加以區(qū)分，在不確定性較小的層次中減少重復(fù)次數(shù)，并且引入了人工的階段識別，提升的性能評估的整體效率。

(2) 對非正態(tài)分布數(shù)據(jù)的處理 多線程程序的運行時間分布大多不符合正態(tài)分布。為了能夠使用置信區(qū)間來表征程序的性能，前文提到的方法利用了中心極限定理使得收集到的數(shù)據(jù)能夠呈現(xiàn)正態(tài)分布，但是中心極限定理要求上百個運行結(jié)果，才能足夠構(gòu)成正態(tài)的平均值分布[5]。

Chen等[5]提出了一種利用非參數(shù)統(tǒng)計方法的框架，用于利用更少的程序運行遍數(shù)來獲取準確的性能比較數(shù)據(jù)。這種方法利用了Wilcoxon秩和檢驗，使用Wilcoxon秩和檢驗可以在給定的置信水平上判斷兩組運行數(shù)據(jù)的性能差距是否顯著。在判定加速比的時候，將一邊的數(shù)據(jù)乘以預(yù)計的加速比，再使用非參數(shù)檢驗的方法就能判斷這個加速比是否成立，最后通過緩慢調(diào)整加速比得到最好的結(jié)論。這種方法既可以用于評估單個程序在兩種架構(gòu)上的性能，也能應(yīng)用于用整個測試程序集評估架構(gòu)的性能。

這種方法的好處是在實驗數(shù)據(jù)有限的情況下也能夠得到一個可能比較保守但是正確的結(jié)論，與簡單的計算平均值相比置信水平和加速比的準確性都有大幅度的提高。

2.2 控制不確定性變量

為了控制Java程序的不確定性在性能評估時的影響，除了利用統(tǒng)計學(xué)方法對性能測試結(jié)果進行處理之外，還有另一種思路，即對程序的運行過程中的變量進行控制。

Charlie等提出了Stabilizer[6]。程序在運行時，堆棧和代碼的分布等因素都會受到架構(gòu)的影響，這些不確定因素使得程序的性能結(jié)果未必會呈現(xiàn)正態(tài)分布。

Stabiilizer對于多個層面的不確定因素都進行了包裝，并且主動進行與結(jié)構(gòu)層面的無關(guān)的隨機化。在堆中，Stabilizer會根據(jù)隨機函數(shù)，給新的動態(tài)內(nèi)存請求分配指定的位置。代碼塊同樣會被隨機地存儲在堆上。在每個函數(shù)內(nèi)部Stabilizer都會插入一個trap指令，在運行到這個指令的時候就會根據(jù)隨機函數(shù)將代碼塊在堆上進行分配。對于棧的隨機化，Stabilizer在每個棧幀之間都會插入一個隨機大小的空白塊，最大不超過4 096比特，用來保證每個函數(shù)的棧都是隨機的。

此外，程序每運行過一段時間，都會對所有層面重新進行一次隨機化。這樣，根據(jù)中心極限定理就能確保這些因素對于程序的影響是符合正態(tài)分布的。在確保了程序結(jié)果的正態(tài)性之后，就可以用方差分析等方法對程序的性能結(jié)果進行分析。

Chen等[7]利用符號執(zhí)行建立了一個Java程序性能分布的概率模型，并將這個模型上的性能結(jié)果分布進行了可視化。

在符號執(zhí)行的過程中，根據(jù)輸入集中的權(quán)值以及相應(yīng)的輸入，計算程序執(zhí)行某一分支路徑的概率。之后通過對這些輸入進行測試執(zhí)行，得到的加權(quán)平均值就是該路徑的性能。在完成符號執(zhí)行的搜索之后，就能獲得該程序的性能分布模型。

這一方法的能夠獲得比較完整的程序性能分布，但是所受的限制也比較多。首先，暫時還不支持不確定性多線程程序，Luckow等[8]正在嘗試實現(xiàn)多線程的版本。其次，該方法的性能模型仍然不夠完備，沒能把太多的體系結(jié)構(gòu)因素考慮進去。

3 處理路徑不確定性

正如前文所提到的，Java程序的不確定性多除了對性能的評估造成了影響之外，對于錯誤調(diào)試也會造成很大的干擾。

程序的錯誤調(diào)試經(jīng)常需要多次循環(huán)執(zhí)行程序并重現(xiàn)錯誤來解決問題。但是多線程程序的不確定性使得程序即使多次循環(huán)也未必能夠重現(xiàn)錯誤執(zhí)行的路徑并將錯誤重現(xiàn)。在JVM虛擬機上執(zhí)行時，不確定性的問題也顯得更為嚴重。本節(jié)將針對Java程序的確定性重放技術(shù)進行總結(jié)和綜述。

早期Java程序的重現(xiàn)方法著重于確保相同的線程切換順序以及相同的程序狀態(tài)。比如DejaVu[9]、JaRec[10]和ReVirt[11]等，這些框架適合用于單核機器上的確定性重現(xiàn)。

DejaVu會記錄并重現(xiàn)每次線程切換，包括同步操作和搶占式的切換。DejaVu確保在重放時能夠切換到正確的線程，并且在切換后程序的狀態(tài)與記錄階段的狀態(tài)相同。此外，為了處理插樁對于程序性能的影響，DejaVu還會記錄框架本身所有對于Java程序有影響的操作，并在重放過程中復(fù)現(xiàn)這些操作，確保重放與記錄的一致性。

JaRec同樣只記錄Java程序中的同步操作，它利用了Lamport邏輯時鐘來記錄每一次線程同步的邏輯順序，在重放的時候只需要讀取記錄文件中的邏輯時鐘就能實現(xiàn)同樣的線程切換和同步的順序。JaRec使用JVMPI實現(xiàn)插樁。重放的程序所需時間是與原程序的1.5倍到39倍不等，這一比率取決于同步操作的數(shù)目。與DejaVu相比，JaRec可以在多核平臺上使用。

此外，Ronnse[12]等和Choi等[13]也實現(xiàn)了利用邏輯時鐘的重放框架。隨著多線程程序變得越來越龐大，僅僅記錄線程的切換行為并不足以完成并行程序的重放，性能也越來越差。如何將對共享內(nèi)存的訪問記錄下來并重現(xiàn)成為了確定性重放技術(shù)的新難題。為了解決這一問題，研究人員提出了許多技術(shù)來對記錄階段進行優(yōu)化，工作主要集中于如何減少記錄的事件數(shù)，這樣既能降低記錄階段的開銷，也能減少記錄文件的大小。

3.1 對記錄階段的優(yōu)化

傳統(tǒng)的確定性重放技術(shù)會記錄程序所有不確定性操作，并記錄下他們的全局順序以便之后的重放。但這會導(dǎo)致在記錄階段需要許多同步操作來確定事件的順序。

Leap[14]對這一現(xiàn)象進行了優(yōu)化。Leap記錄每個共享變量的線程訪問順序，而不是記錄共享內(nèi)存的全局訪問順序。通過這個方法，降低在記錄階段的開銷。Leap首先通過Java程序的靜態(tài)分析框架Soot找出在運行中會產(chǎn)生多個線程訪問的共享變量，然后在運行時記錄每一個共享變量的線程訪問序列。在重放時，重放引擎會強制程序按照記錄的線程訪問隊列執(zhí)行。Leap通過Soot實現(xiàn)，經(jīng)過測試，其記錄階段的性能比傳統(tǒng)的邏輯序列，全局序列要快5～10倍。

其后的Order[15]、CARE[16]、Ditto[17]都對記錄階段的局部性做了優(yōu)化，提升記錄階段的性能。

Order框架同樣記錄了共享變量的線程訪問序列。Order框架的記錄以Java中的對象為單位，將訪問記錄放在對象的頭部，這樣能減少垃圾收集時產(chǎn)生的依賴關(guān)系對記錄的影響。此外，將對共享內(nèi)存的訪問信息存放在對象的頭部，能夠提高記錄階段的局部性。最后，Order還會記錄一些Java獨有的導(dǎo)致不確定性的因素，其中包括了垃圾收集，動態(tài)編譯以及類的初始化等操作的時間點，從而能夠重現(xiàn)Java虛擬機內(nèi)部產(chǎn)生的錯誤。相對于正常運行的程序，基于Apache Harmony實現(xiàn)的Order記錄階段的平均額外開銷為8%，比Leap快1.4～3.2倍。

CARE提出了一種減小記錄階段所需的日志文件大小的技術(shù)。CARE為每個線程都添加了一個的共享變量的軟件緩存，只有當讀操作返回的值與緩存中的值不同時，CARE才會記錄下這次讀操作的讀寫依賴關(guān)系，通過這種方法能減少需要記錄的條目。CARE基于JVMTI進行插樁。相比于LEAP、CARE的記錄開銷是LEAP的38.47%，日志文件是LEAP的20.41%。

此外，Ditto也是一種記錄對共享變量的線程訪問順序的框架，Ditto利用邏輯時鐘來保存不同線程上內(nèi)存訪問的順序，同時利用偏序關(guān)系的傳遞性減少需要記錄時的日志文件大小。Ditto也同樣利用了Soot靜態(tài)分析框架來區(qū)分局部變量和全局變量，對記錄過程進行優(yōu)化。

除了記錄足夠的讀寫順序之外，還有一些方法減少了記錄的信息，并在重放階段對程序的執(zhí)行路徑進行推斷，如ODR[18]、CLAP[19]和 PRES[20]等。這些方法通常只能保證重放階段的部分精度。

Stride[21]將兩種方法進行了融合，這一框架在記錄所有讀寫關(guān)系順序的方法和對程序路徑進行搜索的方法之間進行了權(quán)衡，使用Java Soot實現(xiàn)。Stride不會記錄所有確切的讀寫關(guān)系。對于每次讀操作，它會記錄對于這個變量最近版本的寫操作，這個寫操作在之后確定具體讀寫聯(lián)系的時候就是搜索時的上界。相比傳統(tǒng)的記錄順序的方法，Stride在記錄時能夠減少許多同步操作。與Leap相比，Stride在記錄階段快2.5倍，記錄文件小，是LEAP的25.77%。

3.2 在特殊虛擬機環(huán)境下進行確定性重放

為了一些特殊的目的，比如安全性的要求，或者為了降低確定性重放的難度，一些確定性重放技術(shù)通過定制的虛擬機環(huán)境進行實現(xiàn)，比如ReVirt[11]、SMP-ReVirt[22]和TDR[23]。

ReVirt框架在一個自己實現(xiàn)的虛擬機上進行記錄和重放，這樣能夠移除程序?qū)τ谕獠坎僮飨到y(tǒng)的依賴。ReVirt的重放機制與前文所述的框架類似，只適用于單核上的多線程程序。

SMP-ReVirt基于Xen實現(xiàn)了多核模擬器上的確定性重放。SMP-ReVirt利用了并發(fā)讀、單獨寫(CREW)的協(xié)議來控制虛擬機對于共享變量的訪問，然后通過硬件頁保護來確定讀寫的順序。

TDR為了能夠在進行確定性重放之外，還能確保程序的執(zhí)行時間與原來的運行相同，在虛擬機上實現(xiàn)了確定性重放功能。為了使得記錄和重放的環(huán)境不受干擾，TDR重新實現(xiàn)了一個Java虛擬機，在這個虛擬機上盡可能地排除了系統(tǒng)因素對程序的影響，達到干凈狀態(tài)。除了虛擬機之外，TDR還需要另一個核心來幫助虛擬機執(zhí)行IO和中斷等操作。由于這個虛擬機暫時只支持單核執(zhí)行，TDR所使用的重放方法是傳統(tǒng)的記錄線程切換的方法。在同樣配置的兩臺機器上進行記錄和重放，TDR能夠讓運行時間的誤差保持在1.85%之內(nèi)。TDR的虛擬機并沒有垃圾收集和動態(tài)編譯的功能。

3.3 針對Java具體機制的確定性重放

Java虛擬機中，即時編譯器在每次運行時的行為都是不確定的。為此，Ogata等[24]實現(xiàn)了動態(tài)編譯的重放。這一框架由兩個即時編譯器組成，記錄階段用的編譯器會在每次進行動態(tài)編譯的時候?qū)⒕幾g器收到的所有輸入，包括系統(tǒng)配置、虛擬機狀態(tài)和分析數(shù)據(jù)存儲到日志文件中。這些記錄信息會在系統(tǒng)轉(zhuǎn)儲時寫入其中，重放編譯器工作時會將系統(tǒng)轉(zhuǎn)儲文件載入地址空間，然后讀取日志文件作為編譯器的輸入，進行動態(tài)編譯的重放。這一框架在記錄階段的開銷只有1%，日志文件非常小。

3.4 根據(jù)路徑特征信息進行不確定性分析

VarCatcher[25]通過記錄程序的路徑特征，對齊并進行處理之后得到并行特征向量(PCV)。通過對多次運行的并行特征向量進行聚類處理，可以得到路徑類似的運行結(jié)果。得到運行路徑相似的運行結(jié)果之后可以實現(xiàn)和確定性重放類似的效果。此外，通過對于并行特征向量的處理，可以對程序在不同路徑下的性能結(jié)果進行更深入的分析。利用Intel Processor Trace機制，該框架在記錄階段只有3%的額外開銷。

4 分析與展望

本節(jié)我們將對上文提到的各類不確定性處理機制進行比較和分析，并對未來可能的發(fā)展方向進行了展望。

4.1 分析總結(jié)

(1) 對處理性能不確定性研究的分析 針對性能不確定性的研究主要分為兩大類，一類從性能測試和統(tǒng)計學(xué)的角度出發(fā)，對測試方法和性能分析的方法進行優(yōu)化；另一類，從程序本身出發(fā)，控制運行過程中的不確定性變量，使得對性能不確定的分析更加簡便。

文獻[1]提出的嚴格的統(tǒng)計學(xué)處理方法，也就是表1中的Rigorous，為Java并行程序的性能測試提出了一種完備的框架。文獻[4]的工作，也就是表中的Reasonable，對前者的工作進行了優(yōu)化，將測試的過程分層，在不必要的層上減少重復(fù)次數(shù)。隨后文獻[5]的工作，也就是表中的HPT，使用了一種非參數(shù)檢驗的方法，能夠提升從已知的數(shù)據(jù)從歸納出更精確的結(jié)果。

表1 處理性能不確定性研究的比較

Stabilizer和Distribution，也就是文獻[7]的工作，則將減少性能不確定性的努力放在了程序本身上。Stabilizer能夠使程序運行的結(jié)果呈正態(tài)分布；而Distribution則希望通過符號執(zhí)行建立程序的性能分布模型。值得注意的是，這項技術(shù)還并不完全成熟，并不足以模擬多線程不確定性和系統(tǒng)對程序的影響。

(2) 對Java程序的確定性重放技術(shù)的分析 確定性重放技術(shù)的研究方向大致分為兩種：(1) 致力于對記錄階段進行優(yōu)化，降低重放技術(shù)的額外開銷；(2) 通過特定的虛擬機環(huán)境，實現(xiàn)額外功能的重放技術(shù)。對于前者，表2給出了本文總結(jié)的幾種確定性重放技術(shù)的性能比較。由于這幾篇文獻的性能分析都是以Leap為比較對象，表格中就以Leap為基準進行比較，其中Ditto給出了比較數(shù)據(jù)，但沒有具體的總體性能比較?？梢钥吹?，后面幾篇文獻進行各自的優(yōu)化之后，都取得了比較好的結(jié)果。Order針對Java虛擬機中的編譯器，垃圾收集等做了額外的信息記錄。Ditto在記錄階段利用偏序的傳遞性，減少不必要的信息記錄。CARE通過自己實現(xiàn)的軟件緩存減少需要記錄的讀寫操作。Stride結(jié)合了路徑推斷的技術(shù)，減少記錄階段的同步操作。

表2 各確定性重放相對于Leap框架的性能比較

4.2 展 望

4.2.1 對處理系統(tǒng)不確定性研究的展望

在對數(shù)據(jù)處理的研究上，前文所述的研究已經(jīng)做出了十分顯著的成果，但依然有一些問題得不到解決。比如在對于Java虛擬機內(nèi)部機制和并行程序不確定性之間的關(guān)系，這方面的研究仍然比較缺乏。如果能夠知道即時編譯器和垃圾收集等因素會在多大的程度上，會如何影響Java程序執(zhí)行時的不確定性，對分析Java程序的性能結(jié)果會很有幫助。并行程序結(jié)果的分布形態(tài)與程序本身的關(guān)系也是可以進一步研究的方向，這也有助于將程序的結(jié)果分布正態(tài)化。

此外，通過符號執(zhí)行對程序性能分布建立模型的工作也需要進一步發(fā)展，當這項工作能夠?qū)⑺械囊蛩囟伎紤]到模型中時，該技術(shù)才能得到更廣泛的應(yīng)用。

4.2.2 對Java程序的確定性重放技術(shù)的展望

盡管前文提到的工作對確定性重放技術(shù)有了非常大的提升，但是確定性重放技術(shù)的代價仍然是比較大的，這項技術(shù)還有進一步提升的空間。

目前的大多數(shù)工作致力于減少對共享變量訪問的記錄。如果要在這一方面有所突破，可以進一步對多線程程序訪問共享變量的模式進行優(yōu)化，減少不確定性的共享變量訪問。另外，更多的使用事務(wù)內(nèi)存，也可以簡化對于共享變量的記錄，只在檢查點上對這些訪問記錄進行處理。

另一方面，結(jié)合前文提到的TDR技術(shù)也是一個非常有潛力的方向。隨著大數(shù)據(jù)處理和云計算變得越來越普及，在虛擬機上運行程序?qū)⑹俏磥聿豢杀苊獾内厔荨Ｈ绻鸗DR的虛擬機能夠?qū)崿F(xiàn)更高效的性能，那么將有潛力解決未來在云端的程序確定性重放問題。

此外，TDR的時間確定性重放對于解決并行程序的性能不確定性也是非常有幫助的。如果在兩臺配置相同的機器上能實現(xiàn)一模一樣的性能，那在兩臺配置不同的機器上運行，兩者之間的速度差異就可能是確切的性能差異。若能實現(xiàn)這個效果，將會極大地性能評估的效率，并解決性能不確定性的問題。

5 結(jié) 語

隨著多核處理器的發(fā)展，大規(guī)模并行程序已經(jīng)成為了主流。然而并行程序的不確定性卻給程序的性能評估和錯誤調(diào)試帶來了許多問題。而Java虛擬機由于自身系統(tǒng)存在的不確定性，加劇了程序的不確定性，這使得Java并行程序的性能評估以及確定性重放的錯誤調(diào)試方法變得更加重要。本文針對解決Java并行程序的性能評估方法以及確定性重放技術(shù)分別進行了總結(jié)和分析。Java并行程序的性能評估的難點主要在于提升性能測試的效率以及對程序的性能進行總結(jié)和描述?；贘ava程序的確定性重放技術(shù)的主要難點在于如何提升記錄階段的性能。最后，本文總結(jié)了這兩個方向如今還存在的問題，并對解決不確定性問題的前景進行了展望。