張婷，李文敬

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

0 引言

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

1 競爭管理

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

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

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

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

與之相反的，是Polite 禮貌算法，為了防止某個(gè)事務(wù)無休止的禮貌等待，該算法增加了等待期限。當(dāng)檢測到?jīng)_突時(shí)，該事務(wù)先禮貌地等待一段時(shí)間，為2n 的單位時(shí)間，當(dāng)重試的次數(shù)n 達(dá)到了最大的重試次數(shù)8，那么禮貌算法將會(huì)毫無條件地中止其競爭的事務(wù)。

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

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

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

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

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

表1 競爭管理策略分類

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

2 競爭管理算法的設(shè)計(jì)

2.1 Polite和Timestamp算法簡介

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

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

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

2.2 競爭管理算法Polti的設(shè)計(jì)

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

競爭管理是對于每一個(gè)線程都有作用的，當(dāng)檢測出事務(wù)T1 與事務(wù)T2 產(chǎn)生沖突，事務(wù)T1 將會(huì)請求競爭管理器做出裁決，有三種可能的裁決方式：a、事務(wù)T1中止T2；b、事務(wù)T1 中止自己；c、事務(wù)T1 等待一段時(shí)間。

選擇哪個(gè)事務(wù)中止或等待，都需要慎重考慮，因?yàn)橛锌赡軐⒐ぷ髁枯^大的事務(wù)中止，導(dǎo)致其之前的所有讀寫操作全部撤銷，浪費(fèi)大量計(jì)算資源。事務(wù)等待的時(shí)間長度也需要仔細(xì)權(quán)衡，因?yàn)橛锌赡苁聞?wù)占有某數(shù)據(jù)的時(shí)間太長不釋放，而導(dǎo)致其他的事務(wù)不能及時(shí)獲取數(shù)據(jù)的所有權(quán)。

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

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

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

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

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

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

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

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

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

2.3 沖突管理算法的構(gòu)建

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

Full-Polti 算法描述如下：

Begin：

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

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

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

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

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

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

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

Step6：若n=8,則等待的事務(wù)不再等待競爭事務(wù)的申請?zhí)峤?，而是直接中止掉競爭事?wù)，讓自己繼續(xù)執(zhí)行。

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

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

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

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

3 算法實(shí)現(xiàn)

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

圖2 多線程并行程序流程

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

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

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)結(jié)果

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

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

圖3 Full-Polite、Full-Timestamp、Full-Polti 算法運(yùn)行時(shí)間對比

實(shí)驗(yàn)結(jié)果顯示，F(xiàn)ull-Polti 沖突管理算法的用時(shí)要少于其余兩種算法，因?yàn)镕ull-Polti 定義了優(yōu)先級低的事務(wù)所需等待時(shí)間的上限，因此能讓等待的事務(wù)中止掉耗時(shí)多的競爭事務(wù)，不至于耗費(fèi)太多等待時(shí)間。

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

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

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

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

在相同的初始參數(shù)下，當(dāng)線程數(shù)為16 時(shí)，對三種算法進(jìn)行測試。測試結(jié)果如圖4、圖5 所示

圖4 三種算法運(yùn)行時(shí)間對比結(jié)果

圖5 三種算法沖突次數(shù)對比結(jié)果

4.2 結(jié)果分析

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

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

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

5 結(jié)語

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