基于多核PC 的事務內存沖突管理算法的改進

張婷，李文敬

（1.廣西民族大學相思湖學院，南寧530008；2.南寧師范大學，南寧530001）

0 引言

軟件事務內存的競爭管理策略在事務發(fā)生沖突時決定是否放棄其中一個事務，Scherer 等人對此進行了專門的分析，但是目前并沒有一個能夠適用于不同環(huán)境的競爭管理策略算法。現有競爭管理策略有：Aggressive 激進算法、Polite 禮讓算法、Randomized 隨機算法、Karma 報應算法、Timestamp 時間戳算法等，本文將對競爭管理算法進行理論分析，并結合Repeat-Hash沖突檢測算法及沖突規(guī)避算法進行實驗，將不同的競爭管理算法的評測結果進行對比，選擇出最優(yōu)的算法，驗證該算法可以在一定程度上提高性能。通過三者的結合所構成的完整沖突管理算法，降低了系統(tǒng)運行時沖突發(fā)生的概率，并且縮短運行時間。

1 競爭管理

并發(fā)的事務之間發(fā)生沖突，在何種條件下，決定哪個事務被中止，是競爭管理來決定的問題。競爭管理發(fā)生在沖突檢測之后，事務申請?zhí)峤恢?，保證每個事務都能在有限時間內完成。文獻[1,2]介紹了一些新穎的競爭管理策略,并評估了它們在各種各樣的基準下的表現,在一個給定的數據結構下，競爭管理所要做的總結為一個問題：當檢測出兩個事務同時訪問同一個內存單元發(fā)生沖突時，我們該怎么做？這些請求交由競爭管理器來解決，競爭管理器的作用是：①判斷事務是否在這個時間可以開始或重新執(zhí)行。②判斷事務是否要中止與之競爭的敵對事務。

假設兩種極端的情況，第一種是當一個事務發(fā)現與別的事務發(fā)生沖突時，總是讓自己中止，讓敵對事務繼續(xù)執(zhí)行，這樣的禮貌行為將導致死鎖或優(yōu)先級反轉的問題。第二種情況是事務總是中止敵對事務，讓自己繼續(xù)執(zhí)行，這樣的激進策略有可能導致活鎖。因此，設計競爭管理方案時，要盡量介于兩種極端情況之間。

目前學術界研究出了一些競爭管理算法，但是競爭管理的設計空間還非常大，仍需繼續(xù)研究與改進。下面，給出幾種常見的競爭管理算法的分析。

Aggressive 侵略算法是當發(fā)生沖突時，總是選擇中止與之競爭的事務，讓自己獲得資源，這使得它非常容易導致活鎖問題，目前，學術界將該策略形成一個有用的基準來跟其他策略進行實驗比較。

與之相反的，是Polite 禮貌算法，為了防止某個事務無休止的禮貌等待，該算法增加了等待期限。當檢測到沖突時，該事務先禮貌地等待一段時間，為2n 的單位時間，當重試的次數n 達到了最大的重試次數8，那么禮貌算法將會毫無條件地中止其競爭的事務。

究竟選擇兩個事務中的哪一個繼續(xù)運行，是算法的關鍵問題。Timestamp 時間戳算法以事務的開始時間作為判斷事務是否被中止的標準，當事務之間發(fā)生沖突時，較早開始的事務得以繼續(xù)執(zhí)行，較晚的事務則被中止掉。這樣可以避免之前做了大量計算工作的事務被中止掉，造成計算資源浪費。但是如果較晚開始的事務一直被中止，不能得以執(zhí)行，將造成死鎖、優(yōu)先級反轉等問題。

為了讓優(yōu)先級低的事務也能夠在有限時間內提交，Karma 工作量算法則給了優(yōu)先級低的事務增加優(yōu)先級的機會。Karma 算法總是企圖根據一個事務迄今為止所做的工作量，來決定是否中止該事務。當一個事務遇到沖突，競爭管理器將會比較該事務與敵對事務之間的優(yōu)先級，如果該事務的優(yōu)先級較高，則對方就要流產。反之，該線程就要等待一段固定的時間，等待敵對事務完成。該算法為了解決短事務因優(yōu)先級低不斷被中止的問題，將成功提交的事務優(yōu)先級置為0，被中止的事務繼續(xù)保留原來的優(yōu)先級，這使得短事務在不斷重試，優(yōu)先級累加之后，能達到超過長事務的優(yōu)先級，從而可以順利提交。但是，有可能會出現敵對事務執(zhí)行時間太久，阻塞其他的競爭線程，影響整體提交的效率。

因此，Polka 算法增加了等待時間的上限，Polka 算法是Polite 算法與Karma 算法的結合，將兩種算法的名稱結合在一起取名，因此稱為“Polka”。該算法結合了Polite 與Karma 的優(yōu)點，各取所長。它保留了Polite算法的一定長度的回退時間，以及Karma 的優(yōu)先級累加的機制。因此，該算法的設計思想為：被中止的事務T 回退進行重試的時間m 等于該事務與其敵對事務的優(yōu)先級之差p，若重試的時間超過m，則競爭管理器讓事務T 繼續(xù)執(zhí)行，中止競爭的事務。該算法在很多的實驗中，獲得了很高的性能。

為了改進松散的解決沖突的規(guī)則，Kindergarten 隊列算法傾向于讓事務有秩序的申請?zhí)峤弧τ诿恳粋€事務,競爭管理器維護一個列表（起初是空的），該列表存儲著事務T 之前中止掉的敵對事務。當沖突發(fā)生時，競爭管理器核對該列表，如果目前的敵對事務在列表中能找到，則中止該敵對事務。若未找到，則將新的敵對事務添加進列表中，事務T 則要回退一小段時間長度。在回退的時間間隔里同時將敵對事務的哈希地址存儲至列表。若在固定的等待時間內，事務T 仍然在等待相同的敵對事務申請?zhí)峤?，則競爭管理器就將事務T 中止。當事務T 重新被一個線程執(zhí)行，并出現相同的敵對事務時，則可以在列表中找到敵對事務，并且中止敵對事務，保證了事務T 可以順利提交。

常用的競爭管理算法還有Greedy、Eruption、Randomize、Published Timestamp 等，根據不同競爭管理算法對于競爭事務的處理方式，我們做出如表1 所示的分類對比。

表1 競爭管理策略分類

文獻[1,2]研究表明，并沒有一種競爭管理算法適用于所有的應用，不同的算法在不同的系統(tǒng)及程序中，有不同的性能表現。

2 競爭管理算法的設計

2.1 Polite和Timestamp算法簡介

為了防止某個事務無休止地等待敵對事務執(zhí)行完成，Polite 禮貌算法增加了等待時間的上限。當檢測到沖突時，該事務先禮貌地等待一段時間，為2n 的單位時間，當重試的次數n 達到了最大的重試次數8，那么Polite 算法將會毫無條件的中止執(zhí)行耗時太久的競爭的事務。但是Polite 算法的缺點是并沒有明確讓哪種事務等待，有可能出現工作量大的事務等待工作量小的事務，最后工作量大的事務被判回滾，浪費了大量計算資源，出現優(yōu)先級反轉問題。

因此，究竟選擇兩個事務中的哪一個繼續(xù)運行，而不導致計算資源浪費，是算法的關鍵問題。Timestamp時間戳算法以事務的開始時間作為判斷事務是否被中止的標準，當事務之間發(fā)生沖突時，較早開始的事務得以繼續(xù)執(zhí)行，較晚的事務則被中止掉。這樣可以避免之前做了大量計算工作的事務被中止掉，造成計算資源浪費。但是Timestamp 的缺點是：如果較晚開始的事務一直被中止，不能得以執(zhí)行，將造成死鎖、優(yōu)先級反轉等問題。

兩種算法各有優(yōu)缺點，Polite 算法沒有優(yōu)先級的比較，但是限制了等待的時間長度；Timestamp 算法對優(yōu)先級進行比較，比較后直接判執(zhí)行和回滾，沒有對優(yōu)先級進行時間的維護。因此，我們嘗試將兩種算法結合，各取所長，構建競爭管理算法“Polti”。

2.2 競爭管理算法Polti的設計

目前已經實現了重復探測的Hash 沖突檢測，以及引入高低頻區(qū)分的記錄表沖突規(guī)避機制，最后需要設計競爭管理算法來實現對沖突事務的管理。本文所設計的完整沖突管理算法包括沖突規(guī)避、沖突檢測以及沖突時調用的競爭管理方案。

競爭管理是對于每一個線程都有作用的，當檢測出事務T1 與事務T2 產生沖突，事務T1 將會請求競爭管理器做出裁決，有三種可能的裁決方式：a、事務T1中止T2；b、事務T1 中止自己；c、事務T1 等待一段時間。

選擇哪個事務中止或等待，都需要慎重考慮，因為有可能將工作量較大的事務中止，導致其之前的所有讀寫操作全部撤銷，浪費大量計算資源。事務等待的時間長度也需要仔細權衡，因為有可能事務占有某數據的時間太長不釋放，而導致其他的事務不能及時獲取數據的所有權。

為了更好地對沖突的事務進行競爭管理，避免死鎖或活鎖的發(fā)生，本文嘗試將“Polite”和“Timestamp”相結合，形成一種簡稱為“Polti”的競爭管理算法，算法簡單，實現容易，性能消耗低。算法的基本思想是沖突的事務T1 和T2 之間，較晚開始的事務T1 要等待一段時間，先進行2^n 個單位時間（毫秒）的等待，其中n 為重試次數，每重試一次就進行一次沖突檢測，檢測寫入的地址是否有其他線程在使用，如果沒有則說明無沖突，事務T1 得以繼續(xù)執(zhí)行。如果仍檢測出有線程使用則說明出現沖突，繼續(xù)進行2^（n+1）個單位時間的等待，n=n+1，當重試次數n 累加到8 時，事務T1 不再等待，而是直接中止與之競爭的事務T,讓其回滾，讓自己占有地址的使用權。首先，我們對Polti 算法進行理論分析：

事務T1 和T2 發(fā)生沖突后，競爭管理算法首先比較兩者的優(yōu)先級p1 和p2。

（1）當p12^7,則T1 不再等T2 申請?zhí)峤?，而是讓自己繼續(xù)執(zhí)行。

（2）當p1>p2 時，事務T1 能最終不被中止，得以申請?zhí)峤坏臈l件為它讓T2 等待的時間m 小于2^7 個單位時間，也就是說T1 要在m 個單位時間之內執(zhí)行完：

m ≤2^n.(n=n+1,n<8) （1）

從上述式子可以看出，較早開始的事務理論上來說應該可以先申請?zhí)峤?，但是實際上卻不能按時申請?zhí)峤唬f明這個事務執(zhí)行所占用的時間太多，計算量太大。因此Polti 算法設計為：執(zhí)行耗時久的事務將被延后執(zhí)行，耗時短的事務優(yōu)先執(zhí)行，從而提高算法的效率。

如圖1 所示，事務T1 開始的時間比與之競爭的事務T2 早，優(yōu)先級p1 大于p2，因此先讓T1 先執(zhí)行，T2等待m 個單位時間，但是有可能出現T1 的計算量較大，執(zhí)行耗時很多，則T2 不能無休止等待，當等待時間大于2^7 個單位時間時，T2 中止T1，讓自己繼續(xù)執(zhí)行，執(zhí)行完成后申請?zhí)峤弧?/p>

接下來，我們對算法的執(zhí)行時間進行分析。在沒有等待時間的情況下，m 個事務最多在運行了m·tmax的時間之后，方可申請?zhí)峤?。tmax 為事務執(zhí)行的最長時間，在沒有引入等待時間上限的情況下，tmax 的長度不受限制，有可能某些競爭事務執(zhí)行了大量的時間，而影響了整體的提交效率。Polti 算法讓優(yōu)先級低的事務等待一個常數時間，達到等待時間上限后，執(zhí)行耗時久的競爭事務將被判中止，tmax 也相應縮短，總體的提交效率提升。

圖1 Polti算法維護事務優(yōu)先級的流程

2.3 沖突管理算法的構建

接下來，我們將融合重復探測Hash 沖突檢測算法和高低頻區(qū)分的沖突規(guī)避算法的優(yōu)勢，結合Polti 競爭管理算法的優(yōu)點，構建基于多核處理器的事務內存沖突管理算法Full-Polti。

Full-Polti 算法描述如下：

Begin：

輸入：定義最大線程數，隨機生成N 個隨機數，維護高低頻記錄表，記錄歷史沖突的地址值與沖突次數n。

輸出：輸出的參數，第一列是線程id，第二列是hash 地址，第三列是發(fā)生沖突的次數，并輸出運行時間（毫秒）。

Step1：使用OMP_NUM_THREADS 定義執(zhí)行中最大的線程數。

Step2：每一個線程都取一個隨機數作為關鍵字，首先在高低頻記錄表中進行尋址，預測該關鍵字出現沖突的可能性，如果可能性不大，則可以開始執(zhí)行質數取余的哈希運算。

Step3：在沖突檢測階段，用重復探測Hash 沖突檢測算法檢測出兩個事務發(fā)生讀寫地址沖突后，交由競爭管理進行裁決。

Step4：首先競爭管理器先讓開始執(zhí)行時間較早的事務繼續(xù)執(zhí)行，開始時間較晚的事務等待2^n 個單位時間，n 為重試次數，n=n+1。

Step5：若n<8，等待的事務檢測到與競爭事務無沖突，則可以繼續(xù)執(zhí)行。

Step6：若n=8,則等待的事務不再等待競爭事務的申請?zhí)峤唬侵苯又兄沟舾偁幨聞?，讓自己繼續(xù)執(zhí)行。

接下來，我們對算法的時間復雜度進行分析。對于P 個線程同時執(zhí)行N 個事務，將質數取余的運算結果映射到哈希地址上，哈希表中的地址空間數量為C，其中C>N,一個事務執(zhí)行任務所需的時間為Tr，一個事務等待的時間為Tw，經推導，得到Polti 算法的時間復雜度為：

為了簡化模型，我們假設事務等待和執(zhí)行的時間比為1：1，上述式子可以寫成：

經計算，該式子是一個收斂的數組，x 的值越大，計算出的值越小，說明該算法能夠在一定的有限時間能將任務執(zhí)行完成。

Polti 算法的設計可以避免事務之間無休止的相互等待，也避免了將開始較早的事務撤銷而導致的計算資源浪費。相比直接中止的激進算法，該算法給事務一定的等待和重試的時間，避免長事務的長時間執(zhí)行，保證了事務的提交時間。

3 算法實現

本文在程序并行域部分使用OpenMP 編譯指導語句，將串行程序并行化，OpenMP 應用編程接口API 是在共享存儲體系結構上的一個編程模型：其中包含編譯制導（Compiler Directive），運行庫例程（Runtime Library）以及環(huán)境變量（Environment Variables）。OpenMP使用Fork-Join 作為基于線程的并行執(zhí)行模型。Fork-Join 將主程序中不能并行執(zhí)行的部分由主線程執(zhí)行，能夠并行執(zhí)行的部分交由若干個線程同時執(zhí)行，最后將執(zhí)行結果進行合并。Fork-Join 結構將其所包含的代碼劃分給線程組的各個線程來執(zhí)行，也可以通過編譯指導語句，設置并行sections，不同的任務給不同的線程執(zhí)行，或者設置single，只由一個線程來執(zhí)行代碼段。本實驗的并行程序流程如圖2 所示。

圖2 多線程并行程序流程

多線程并行程序流程為：隨機生成N 個隨機數，由n 個線程執(zhí)行質數取余的操作，將沖突檢測出的沖突地址和次數記錄到記錄表中，作為沖突規(guī)避的依據。沖突的線程進入到競爭管理階段，根據競爭管理算法，讓其中一個事務繼續(xù)運行，其他事務中止或等待。繼續(xù)運行的線程完成計算后，將數據申請?zhí)峤?。被中止的線程則要回滾，放棄之前所做的所有計算，重新開始執(zhí)行，當N 個隨機數都計算完成后，由JION 把所有的數據收集完整，統(tǒng)一輸出。

本實驗使用的OpenMP 指導語句實現多線程的并行同步與歸并。使用“omp_num_treads”語句設置環(huán)境變量，定義執(zhí)行中最大的線程數。在多線程同時執(zhí)行的可并行程序部分，加入“#pragma omp parallel for”語句，將可并行執(zhí)行的語句自動并行化，緊隨它的循環(huán)語句由線程組并行執(zhí)行。在線程同步的設置上，使用“#pragma omp critical（name）”語句使得并行域中的代碼塊每次只能執(zhí)行多個線程中的一個，其他線程則被阻塞，該語句用于競爭管理部分的線程等待。使用barrier 制導語句用來同步一個線程組中所有的線程，本實驗的barrier 為隱藏的柵障，等并行區(qū)域中所有線程都執(zhí)行完成后，再繼續(xù)執(zhí)行主線程。最后，將執(zhí)行結果進行歸并，使用“reduction（operator：list）”子句在結構尾部對線程中的變量進行歸并，保證最后輸出的結果是正確的。

4 實驗結果與分析

4.1 實驗結果

本實驗的硬件平臺為：英特爾22 納米酷睿i5-3450 4 核處理器，CPU 主頻3.7GHz，內存為8G。軟件平臺為：Microsoft Windows 7 操作系統(tǒng)，Microsoft Visual Studio 2010（OpenMP），使用C++語言編寫程序。

為了制造更多的沖突，以檢驗競爭管理算法的性能，我們將質數表的個數從699 個減少到25 個。編程實現事務內存沖突管理算法，在重復探測Hash 沖突檢測算法中分別加入競爭管理算法Polite、Timestamp 和Polti，并使用高低頻區(qū)分的沖突規(guī)避功能，形成一套“完整polite 沖突管理算法”“完整Timestamp 沖突管理算法”和“完整Polti 沖突管理算法”，分別簡稱為“Full-Polite”、“Full-Timestamp”和“Full-Polti”，當線程數為16 時，實驗結果如圖3 所示。

圖3 Full-Polite、Full-Timestamp、Full-Polti 算法運行時間對比

實驗結果顯示，Full-Polti 沖突管理算法的用時要少于其余兩種算法，因為Full-Polti 定義了優(yōu)先級低的事務所需等待時間的上限，因此能讓等待的事務中止掉耗時多的競爭事務，不至于耗費太多等待時間。

本文經實驗驗證了Full-Polti 算法的優(yōu)勢，接下來，分析沖突管理算法給事務內存系統(tǒng)所帶來的性能提升。為了更直觀的進行實驗對比，我們分別編程實現了以下三種算法：

（1）“完整Polti 沖突管理算法”——即Full-Polti。

（2）“無預測Polti 沖突管理算法”——不使用沖突規(guī)避機制的Polti 沖突管理算法。

（3）“無預測無管理算法”——既無沖突規(guī)避又無競爭管理的算法。

在相同的初始參數下，當線程數為16 時，對三種算法進行測試。測試結果如圖4、圖5 所示

圖4 三種算法運行時間對比結果

圖5 三種算法沖突次數對比結果

4.2 結果分析

從以上實驗結果可以看出，完整的Polti 沖突管理算法“Full-Polti”的表現最為優(yōu)越，在相同的初始參數下，完整算法的運行時間最短，沖突次數最少。因為完整算法使用了沖突預測避免了不必要的沖突發(fā)生，使用Polti 競爭管理算法對沖突的事務進行合理管理，保證事務在有限的時間內得以申請?zhí)峤?，使運行效率得到提高，最終輸出的沖突次數也比無預測無管理的算法減少了將近二分之一。

性能評測結果顯示，融合沖突檢測算法和沖突規(guī)避算法的優(yōu)勢，結合Polite 和Timestamp 兩種策略的優(yōu)點，所構建的基于多核處理器的事務內存沖突管理算法，整體性能基本上可以滿足多核PC 系統(tǒng)的需要，另外，使用沖突規(guī)避機制可以在一定程度上提高系統(tǒng)性能,總體來說，設計合理的沖突管理算法對事務內存系統(tǒng)的性能和效率有著重要影響，可以顯著提高事務內存系統(tǒng)的執(zhí)行性能。

最后，我們對算法的時間復雜度進行理論上和實驗結果的一致性分析。首先我們計算算法理論上的時間復雜度，將N=2500，C=5000，P=4，x=1,2,3,…,8，代入公式（3）中計算，計算得到理論上的時間復雜度為2502.0016，乘上單位時間，我們在實驗中定義RUN_TIME 為17 個單位時間，因此理論上該算法的運行時間為42534.03ms，根據實驗結果，Full-Polti 的平均運行時間為43012ms，與理論上的計算值相近，因為還有其他時間損耗，實際運行時間比理論值稍大。綜上，實驗結果與理論分析的結論是一致的。

5 結語

競爭管理是事務申請?zhí)峤磺暗囊粋€操作，是對沖突檢測的結果進行的，多個事務發(fā)生沖突后，應該如何管理沖突事務，選擇哪個繼續(xù)執(zhí)行，哪個要回滾。本文首先將目前的幾種競爭管理算法進行研究并歸納分析。在實驗中，嘗試將Polite 和Timestamp 兩種算法結合，構建Polti 競爭管理算法，將重復探測Hash 沖突檢測算法與之進行結合，并使用高低頻區(qū)分沖突規(guī)避算法進行沖突預測。實驗結果表明，完整的“三合一”Full-Polti 沖突管理算法融合了沖突檢測算法和沖突規(guī)避算法的優(yōu)勢，結合了Polite 和Timestamp 兩種策略的優(yōu)點，在性能上較為優(yōu)越，在數據規(guī)模大的情況下，更能體現出優(yōu)勢。