張 婷，李文敬，黃 帆+

(1.廣西民族大學(xué)相思湖學(xué)院 計算機(jī)科學(xué)與工程系，廣西 南寧 530008；2.南寧師范大學(xué) 物流管理與工程學(xué)院，廣西 南寧 530001)

0 引 言

多核處理機(jī)的不斷普及，為應(yīng)用多處理器、充分發(fā)揮多核機(jī)的潛能、并行解決各領(lǐng)域的實際問題提供了更好的解決方案。而事務(wù)內(nèi)存較鎖機(jī)制具有優(yōu)勢，如：不會導(dǎo)致死鎖；允許事務(wù)并發(fā)執(zhí)行[1]；事務(wù)的復(fù)合或嵌套能更好地實現(xiàn)。事務(wù)內(nèi)存使用的是樂觀的并發(fā)機(jī)制，當(dāng)事務(wù)發(fā)生沖突時，交由競爭管理策略來裁決哪個事務(wù)繼續(xù)執(zhí)行，哪個事務(wù)被撤銷，重新執(zhí)行。當(dāng)系統(tǒng)中事務(wù)之間的沖突較小時，該方法可以維持較好的性能[2]。但是，假設(shè)一個極端的情況，就是事務(wù)之間的沖突極其頻繁，那么這將耗費大量的系統(tǒng)資源來進(jìn)行沖突檢測及競爭管理的操作。沖突規(guī)避就是對事務(wù)的沖突情況進(jìn)行預(yù)測，避免可能發(fā)生大量沖突的事務(wù)進(jìn)入到系統(tǒng)中。沖突規(guī)避是一個新興概念，目前學(xué)術(shù)界對于沖突規(guī)避的研究甚少，文獻(xiàn)[3]提出了基于集群系統(tǒng)的沖突規(guī)避方法，即在事務(wù)啟動之前，根據(jù)歷史發(fā)生沖突的情況預(yù)測其發(fā)生沖突的可能性，并根據(jù)預(yù)測結(jié)果對事務(wù)進(jìn)行調(diào)度，以降低事務(wù)的失敗率[3]。但是沖突規(guī)避的研究空間還很大，例如：如何對歷史沖突情況進(jìn)行收集、如何提高預(yù)測沖突的效率、如何設(shè)計算法將數(shù)據(jù)與預(yù)測集合進(jìn)行快速比較等等，都是需要繼續(xù)研究的課題，因此沖突規(guī)避還有很大的研究空間，具有極大的研究與應(yīng)用價值[4]。

1 沖突規(guī)避思想的提出

首先分析一個傳統(tǒng)事務(wù)內(nèi)存的生存周期，如圖1所示。事務(wù)開始時，底層事務(wù)管理器會給事務(wù)分配一個ID，并記錄下該事務(wù)開始時的指令地址，為防止發(fā)生沖突后，該事務(wù)可以回滾到開始的位置重新執(zhí)行[5]。一個事務(wù)的執(zhí)行過程可分為兩種可能，分別是成功和失敗，成功的執(zhí)行過程為：事務(wù)開始→執(zhí)行階段→事務(wù)提交→結(jié)束；失敗的執(zhí)行過程為：事務(wù)開始→執(zhí)行階段→事務(wù)回滾。在事務(wù)執(zhí)行過程中進(jìn)行讀寫一致性檢驗，當(dāng)檢驗出讀寫地址發(fā)生沖突時，由競爭管理選擇一個事務(wù)回滾[6]。

圖1 傳統(tǒng)事務(wù)生存周期

事務(wù)內(nèi)存使用的是樂觀的并發(fā)機(jī)制，當(dāng)事務(wù)發(fā)生沖突時，交由競爭管理策略來裁決哪個事務(wù)繼續(xù)執(zhí)行，哪個事務(wù)被撤銷，重新執(zhí)行。當(dāng)系統(tǒng)中事務(wù)之間的沖突較小時，該方法可以維持較好的性能。但是，假設(shè)一個極端的情況，就是事務(wù)之間的沖突極其頻繁，那么這將耗費大量的系統(tǒng)資源來進(jìn)行沖突檢測及競爭管理的操作[7]。文獻(xiàn)[3]提出了沖突規(guī)避的思想，即在事務(wù)開始之前，判斷該事務(wù)發(fā)生沖突的可能性，若可能性較大，則暫時不讓該事務(wù)執(zhí)行，避免執(zhí)行后發(fā)生大量沖突影響系統(tǒng)性能。

采用沖突規(guī)避機(jī)制的事務(wù)執(zhí)行流程如圖2所示，與傳統(tǒng)的事務(wù)執(zhí)行流程所不同的是，事務(wù)的開始不再是不受限的，而是在每次新的事務(wù)開始之前，或是經(jīng)過競爭管理被判回滾的事務(wù)重新執(zhí)行之前，都要進(jìn)行一次沖突預(yù)測，若判斷出該事務(wù)發(fā)生沖突的可能性較大，則掛起事務(wù)，反之，放行事務(wù)，開始執(zhí)行[8]。

圖2 事務(wù)內(nèi)存生存周期中加入沖突規(guī)避機(jī)制

如何預(yù)測到?jīng)_突的可能性是該算法的關(guān)鍵，設(shè)計了一個P-RHR(predict-repeat hash by random)，即：基于記錄表的隨機(jī)質(zhì)數(shù)算法，可以在運行時記錄下發(fā)生沖突的讀寫地址集合，作為歷史沖突情況的記錄，保存到本地私有記錄表H(history)中。在事務(wù)開始之前，系統(tǒng)將事務(wù)的元素集合C(current)與H相比較，若集合C中的元素與H中的元素重復(fù)率達(dá)到一個閾值，則要掛起該事務(wù)[9]。為改進(jìn)P-RHR算法耗時長的問題，提出了HLF-RHR(high and low frequency-repeat hash by random)，即：高低頻區(qū)分的隨機(jī)質(zhì)數(shù)算法，高低頻表角色不同，各施其職，可以縮短記錄表的表長，提升查找速度，進(jìn)而提高系統(tǒng)性能。

2 基于記錄表的沖突規(guī)避算法

2.1 P-RHR算法設(shè)計

目前學(xué)術(shù)界對于沖突規(guī)避的研究甚少，文獻(xiàn)[3]提出了基于集群系統(tǒng)的沖突規(guī)避方法，即在事務(wù)啟動之前，根據(jù)歷史發(fā)生沖突的情況預(yù)測其發(fā)生沖突的可能性，對事務(wù)進(jìn)行調(diào)度，以降低事務(wù)的失敗率。但是沖突規(guī)避的研究空間還很大，例如：如何對歷史沖突情況進(jìn)行收集、如何提高預(yù)測沖突的效率、如何設(shè)計算法將數(shù)據(jù)與預(yù)測集合進(jìn)行快速比較等等，都是需要繼續(xù)研究的課題[10]。本文提出了一種基于記錄表的沖突規(guī)避算法，并改進(jìn)記錄表的存儲方式。經(jīng)實驗驗證，該算法能有效減少系統(tǒng)中的沖突，能夠防止高的沖突頻率對系統(tǒng)性能的影響。

首先需要建立一個記錄表，使用Hash算法來檢測讀寫沖突，將Hash沖突檢測出來的地址值記錄在內(nèi)，記錄的方法有多種：編譯時直接生成、運行時隨時記錄[11]。選擇在運行時記錄下歷史發(fā)生沖突的地址值，生成一個動態(tài)的可供參考的記錄表[12]。

記錄表中記錄著地址值以及其對應(yīng)的沖突次數(shù)n，其中，n是隨著沖突次數(shù)的增加而累加的，n的最大值定義為“線程數(shù)-1”。例如：線程數(shù)為16，則記錄的沖突次數(shù)n最大值為15。閾值的確定是本算法中的一個難點，經(jīng)實驗研究，設(shè)定閾值為記錄表中的沖突次數(shù)n，能夠獲得較好的性能。

下面，對沖突規(guī)避算法用數(shù)學(xué)語言進(jìn)行描述和量化。

分配一個隨機(jī)數(shù)p1作為優(yōu)先級，其中，在加入沖突規(guī)避機(jī)制下，事務(wù)啟動的條件是優(yōu)先級p1大于記錄表中的沖突次數(shù)n，即

p1>n

于是事務(wù)啟動的概率

從上面式子可以看出，影響事務(wù)的啟動的因素有線程數(shù)M和歷史沖突次數(shù)n，在線程數(shù)為M既定的情況下，事務(wù)歷史沖突次數(shù)n越大，事務(wù)啟動的概率越低，從而規(guī)避掉大量沖突。

例如：線程數(shù)為16，記錄表中某個地址值的沖突次數(shù)達(dá)到了15，則事務(wù)被分配的優(yōu)先級必須大于15，也就是只能分配到16才能得以開始執(zhí)行，幾率是1/16,所以歷史沖突越多，則事務(wù)越難得以開始執(zhí)行。

在沖突檢測算法中加入沖突規(guī)避機(jī)制，算法描述如下：

輸入、輸出及(1)中定義最大線程數(shù)的過程請參見文獻(xiàn)[13]。

(2)每一個線程都取一個隨機(jī)數(shù)作為關(guān)鍵字，同時會獲得一個以線程數(shù)為上限的隨機(jī)數(shù)作為優(yōu)先級p1，與本地的記錄表進(jìn)行遍歷比對。例如：線程數(shù)為16，某線程得到56478作為關(guān)鍵字地址值，同時獲得一個小于16的隨機(jī)數(shù)5作為優(yōu)先級。

(3)若關(guān)鍵字在記錄表里找不到相同地址值，直接進(jìn)入到(7)。

(4)若關(guān)鍵字與記錄表里有相同的地址值，且該地址值的歷史沖突次數(shù)n小于該事務(wù)的優(yōu)先級p1，則該事務(wù)可以順利開始執(zhí)行，進(jìn)入到(7)。例如，某線程的優(yōu)先級是隨機(jī)數(shù)5，記錄表中相同地址值的歷史沖突次數(shù)是4，則線程可以開始執(zhí)行。

(5)若關(guān)鍵字與記錄表里有相同的地址值，且該地址值的歷史沖突次數(shù)n大于或等于該事務(wù)的優(yōu)先級p1，則該事務(wù)被掛起。

(6)重新給該事務(wù)分配新的隨機(jī)數(shù)作為地址值，重復(fù)(3)、(4)，若出現(xiàn)記錄表里相同地址值的歷史沖突次數(shù)n仍大于或等于事務(wù)的優(yōu)先級p2，則繼續(xù)掛起重試，直到優(yōu)先級pn大于記錄表中的沖突次數(shù)n，進(jìn)入到(7)。

(7)事務(wù)得以順利開始執(zhí)行，進(jìn)行沖突檢測的步驟。若檢測過程中，該事務(wù)發(fā)生地址沖突，則記錄表中該地址值的歷史沖突次數(shù)增加1。

事務(wù)與記錄表進(jìn)行地址值對比的流程如圖3所示。

圖3 事務(wù)與記錄表進(jìn)行地址值對比

2.2 應(yīng)用示例

用火車票網(wǎng)上售票系統(tǒng)來直觀說明該問題，若1000人同時訂購?fù)粡垺氨本虾！钡挠沧保瑒t讀寫地址的沖突情況嚴(yán)重，系統(tǒng)要花大量時間對1000個讀寫地址進(jìn)行一致性檢驗，若同時訪問的人數(shù)更多，系統(tǒng)則更不堪重負(fù)。因此，可以將較為搶手的火車票在系統(tǒng)中的地址值記錄下來，假設(shè)“北京—上?！蹦秤沧钡牡刂分禐?821，“廣州—深圳”某硬座票的地址值為3881，建立成為一個記錄表，并將每個地址值的歷史沖突次數(shù)進(jìn)行累計，假設(shè)某張票的歷史沖突次數(shù)為1000次。當(dāng)購票高峰來臨時，若同時訂購?fù)粡垺?821”火車票的人數(shù)為3000人，系統(tǒng)將會給每個購票者分配一個小于3000的隨機(jī)數(shù)作為優(yōu)先級，若購票者甲的優(yōu)先級是1500，大于歷史沖突次數(shù)1000，則甲可以進(jìn)入到訂票步驟；若購票者乙的優(yōu)先級是800，小于歷史沖突次數(shù)1000，則被提示“很抱歉，無法訂購”。

沖突規(guī)避的思想可以在事務(wù)有可能產(chǎn)生沖突頻率較大的情況下，限制事務(wù)的啟動，對系統(tǒng)進(jìn)行維護(hù)，以免造成不必要的開銷[13]。

2.3 實驗結(jié)果與分析

本地維護(hù)的記錄表使用C++的MAP類實現(xiàn)，MAP是一個關(guān)聯(lián)式容器，自動建立Key-Value對應(yīng)，key和value 可以是自定義的類型，用戶可以對MAP內(nèi)元素進(jìn)行快速的查找、刪除、修改操作，因此可以實現(xiàn)歷史沖突地址值的查找、刪除、沖突次數(shù)增加等操作[14]。

加入沖突規(guī)避機(jī)制的算法與原算法RHR性能對比見表1。

由表1看出，加入了沖突規(guī)避機(jī)制的算法在運行時間上比無沖突規(guī)避算法耗時更多，因為需要在每次事務(wù)開始前進(jìn)行一次調(diào)度，有一定的性能消耗，但是沖突規(guī)避算法的思想是“未雨綢繆”、“以時間為代價換穩(wěn)定”，雖然犧牲了一些時間，但是沖突規(guī)避的好處還是顯而易見的，實驗結(jié)果表明，沖突規(guī)避算法中線程間發(fā)生沖突的次數(shù)明顯少于無沖突規(guī)避算法，能減少一半以上的沖突。隨著線程數(shù)的增加，沖突次數(shù)增加，運行時間減少。

表1 沖突規(guī)避算法與無沖突規(guī)避算法的性能對比

3 高低頻區(qū)分的HLF-RHR沖突規(guī)避算法

用MAP記錄表實現(xiàn)的沖突規(guī)避算法能減少一部分的沖突，但是耗時較多。因此，需要對算法的時間復(fù)雜度進(jìn)行理論上的分析。對于記錄表中元素的查找，使用的是線性查找，在理想的情況下，每個元素依次找到對應(yīng)值，時間復(fù)雜度為O(n)，在不理想的情況下，每一個元素都要經(jīng)過n次查找來遍歷記錄表，則時間復(fù)雜度為O(n2)。n的大小與記錄表的長度有關(guān)，記錄表中的地址值越多，則遍歷的長度n就越大。

記錄表里的沖突地址值是隨著運行的次數(shù)不斷增加，有可能其中存放著大量的只發(fā)生過一次沖突的地址值，這些地址值極少被命中，存儲著這些低頻的地址值，不僅加長了記錄表的長度，還增加了遍歷記錄表的耗時，消耗系統(tǒng)性能，沖突規(guī)避的優(yōu)勢不能很好體現(xiàn)出來。為了進(jìn)一步減少查找的時間復(fù)雜度，對MAP記錄表沖突規(guī)避算法進(jìn)行改進(jìn)，提出高低頻區(qū)分的沖突規(guī)避算法，提高運行效率。

3.1 HLF-RHR沖突規(guī)避算法的機(jī)理

為了提高查找記錄表的效率，本文提出高低頻區(qū)分的沖突規(guī)避算法，HLF(high and low frequency)法，將只發(fā)生過一次地址沖突的地址值先存放到低頻表，當(dāng)該地址值再次發(fā)生沖突，則將其從低頻表轉(zhuǎn)移至高頻表中，每發(fā)生一次沖突，高頻表里的沖突次數(shù)n就累加一次，n的上限為“線程數(shù)-1”。這樣，每次事務(wù)開始執(zhí)行前，先與高頻表中的地址值進(jìn)行比對，高頻表中存放著出現(xiàn)沖突頻率高的地址值，命中率較高。而低頻表則作為一個“過渡區(qū)”，存放著低頻地址，并負(fù)責(zé)將沖突次數(shù)增加的地址“運送”到高頻表。高低頻表角色不同，各施其職，可以縮短表長，提升查找速度，進(jìn)而提高系統(tǒng)性能，工作流程如圖4所示。

圖4 事務(wù)與高低頻區(qū)分的記錄表進(jìn)行比對

為了保持高頻表中的地址值永遠(yuǎn)“高頻”，引入了清理機(jī)制，將一定時間內(nèi)沒有增加沖突次數(shù)的地址值進(jìn)行清理，將其轉(zhuǎn)回低頻表中。在實驗中，設(shè)置為1 s內(nèi)，若記錄表中某地址值沒有被讀取的話，不管其在高頻表還是低頻表，都將沖突次數(shù)依次減1。

3.2 HLF-RHR沖突規(guī)避算法設(shè)計

在沖突檢測算法中加入HLF沖突規(guī)避機(jī)制，維護(hù)兩個記錄表，分別是HIGHMAP和LOWMAP，算法描述如下：

Begin：

輸入、輸出及(1)中定義最大線程數(shù)的過程請參見文獻(xiàn)[14]。

(2)每一個線程都取一個隨機(jī)數(shù)作為關(guān)鍵字，同時會獲得一個以線程數(shù)為上限的隨機(jī)數(shù)作為優(yōu)先級p1，與本地的HIGHMAP高頻記錄表進(jìn)行遍歷比對。

(3)若關(guān)鍵字在高頻表中找不到相同的地址值，直接進(jìn)入到(7)。

(4)若關(guān)鍵字與高頻表里有相同的地址值，且該地址值的歷史沖突次數(shù)n小于該事務(wù)的優(yōu)先級p1，則該事務(wù)可以順利開始執(zhí)行，進(jìn)入到(7)。

(5)若關(guān)鍵字與記錄表里有相同的地址值，且該地址值的歷史沖突次數(shù)n大于或等于該事務(wù)的優(yōu)先級p1，則該事務(wù)被掛起。

(6)重新給該事務(wù)分配新的隨機(jī)數(shù)作為地址值，重復(fù)(3)、(4)，若出現(xiàn)記錄表里相同地址值的歷史沖突次數(shù)n仍大于或等于事務(wù)的優(yōu)先級p2，則繼續(xù)掛起重試，直到優(yōu)先級pn大于記錄表中的沖突次數(shù)n，進(jìn)入到(7)。

(7)事務(wù)得以順利開始執(zhí)行，進(jìn)行沖突檢測的步驟。

(8)若檢測出事務(wù)與其它事務(wù)發(fā)生地址值沖突，如果該事務(wù)的地址值在高頻表中，將高頻表中地址值的沖突次數(shù)增加1；如果地址值在低頻表中，將低頻表的地址值沖突次數(shù)增加1，沖突次數(shù)累加到2次時，將該地址值從低頻表中刪除，添加到高頻表中。

接下來分析高低頻區(qū)分的記錄表是否比單個記錄表更具有效率上的優(yōu)勢。查找單個記錄表中一個元素，理想的時間復(fù)雜度為O(n)，為了減少記錄表的長度，將記錄表分為高頻表和低頻表，假設(shè)高低頻表中的地址值數(shù)量剛好是1∶1,那么每個表的長度是原來的一半，可以用數(shù)據(jù)結(jié)構(gòu)當(dāng)中的折半查找來說明該問題。折半查找將每次事務(wù)查找記錄表的長度縮小二分之一，在理想的情況下，時間復(fù)雜度可以縮短到O(lgn)[15]。

3.3 應(yīng)用示例

繼續(xù)用火車票網(wǎng)上售票系統(tǒng)的實例說明該問題，根據(jù)歷史發(fā)生讀寫地址沖突的情況，將容易發(fā)生沖突的地址值記錄在高頻表中，高頻表中維護(hù)的是一組“高頻詞”序列。而某些路線車票的歷史購買沖突情況不多，則將其放入低頻中。

當(dāng)訂票高峰來臨，購買“北京—上?！被疖嚻钡牡刂分翟谂c高頻表進(jìn)行比對時，由于高頻表的長度比原先的記錄表短，因此能快速查找到相應(yīng)的地址值，相對于將所有產(chǎn)生過沖突的地址值進(jìn)行一一查找，該方法更具針對性，更能節(jié)約時間。

當(dāng)某個路線被開發(fā)成旅游景點，該低頻路線的火車票變得炙手可熱時，其沖突次數(shù)在低頻表中累加，累加到某個值時，該火車票地址值被轉(zhuǎn)移到高頻表中，實行沖突規(guī)避機(jī)制，避免系統(tǒng)中產(chǎn)生大規(guī)模沖突的情況。

3.4 HLF-RHR沖突規(guī)避算法實現(xiàn)

高低頻表使用C++的MAP類實現(xiàn)，分別為HIGHMAP和LOWMAP。事務(wù)啟動前，先查找高頻表的記錄，低頻表中的歷史沖突地址若沖突次數(shù)增加到2次，則將該地址轉(zhuǎn)移到高頻表中。MAP實現(xiàn)的部分代碼如圖5所示。

圖5 MAP實現(xiàn)的高低頻表

實現(xiàn)沖突規(guī)避的部分代碼如圖6所示。

圖6 實現(xiàn)沖突規(guī)避的部分代碼

3.5 實驗結(jié)果與分析

使用了HLF沖突規(guī)避算法的HLF-RHR與原算法P-RHR的性能對比見表2。

表2 HLF-RHR與P-RHR性能對比

實驗結(jié)果表明，HLF-RHR算法在運行速度上比P-RHR算法有提高，因為將“歷史高頻地址”專門用高頻表維護(hù)之后，節(jié)省了“高頻地址”查找記錄表元素的時間，“高頻地址”往往出現(xiàn)的幾率和數(shù)量較多，在數(shù)據(jù)量大的情況下，HLF-RHR算法在效率上的優(yōu)勢更加顯著。隨著線程數(shù)的增加，運行時間減少。

4 結(jié)束語

本文將沖突規(guī)避思想應(yīng)用在基于多核PC的事務(wù)內(nèi)存設(shè)計中。通過在事務(wù)開始執(zhí)行之前，預(yù)測事務(wù)發(fā)生沖突的幾率，控制事務(wù)的發(fā)生和重啟，能夠防止高的沖突頻率對系統(tǒng)性能的影響。實驗結(jié)果表明，引入沖突規(guī)避機(jī)制的并行算法能避免較大的沖突。在算法上改進(jìn)了基于記錄表的沖突規(guī)避算法，使用高低頻區(qū)分的方法，將記錄表的記錄按照沖突頻率分別用高頻表和低頻表維護(hù)，便于事務(wù)地址的查找，實驗結(jié)果表明，該算法相比原算法，在運行速度上有很大提升。

目前學(xué)術(shù)界對于沖突規(guī)避的研究甚少，還有很大的研究空間，沖突規(guī)避是一個新興概念，具有極大的研究與應(yīng)用價值。