張婷，李文敬

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

0 引言

軟件事務(wù)內(nèi)存的競爭管理策略在事務(wù)發(fā)生沖突時決定是否放棄其中一個事務(wù)，Scherer 等人對此進(jìn)行了專門的分析，但是目前并沒有一個能夠適用于不同環(huán)境的競爭管理策略算法?，F(xiàn)有競爭管理策略有：Aggressive 激進(jìn)算法、Polite 禮讓算法、Randomized 隨機(jī)算法、Karma 報應(yīng)算法、Timestamp 時間戳算法等，本文將對競爭管理算法進(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)行時沖突發(fā)生的概率，并且縮短運(yùn)行時間。

1 競爭管理

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

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

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

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

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

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

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

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

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

2.1 Polite和Timestamp算法簡介

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

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

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

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

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

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

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

為了更好地對沖突的事務(wù)進(jìn)行競爭管理，避免死鎖或活鎖的發(fā)生，本文嘗試將“Polite”和“Timestamp”相結(jié)合，形成一種簡稱為“Polti”的競爭管理算法，算法簡單，實(shí)現(xiàn)容易，性能消耗低。算法的基本思想是沖突的事務(wù)T1 和T2 之間，較晚開始的事務(wù)T1 要等待一段時間，先進(jìn)行2^n 個單位時間（毫秒）的等待，其中n 為重試次數(shù)，每重試一次就進(jìn)行一次沖突檢測，檢測寫入的地址是否有其他線程在使用，如果沒有則說明無沖突，事務(wù)T1 得以繼續(xù)執(zhí)行。如果仍檢測出有線程使用則說明出現(xiàn)沖突，繼續(xù)進(jìn)行2^（n+1）個單位時間的等待，n=n+1，當(dāng)重試次數(shù)n 累加到8 時，事務(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 時，事務(wù)T1 能最終不被中止，得以申請?zhí)峤坏臈l件為它讓T2 等待的時間m 小于2^7 個單位時間，也就是說T1 要在m 個單位時間之內(nèi)執(zhí)行完：

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

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

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

接下來，我們對算法的執(zhí)行時間進(jìn)行分析。在沒有等待時間的情況下，m 個事務(wù)最多在運(yùn)行了m·tmax的時間之后，方可申請?zhí)峤?。tmax 為事務(wù)執(zhí)行的最長時間，在沒有引入等待時間上限的情況下，tmax 的長度不受限制，有可能某些競爭事務(wù)執(zhí)行了大量的時間，而影響了整體的提交效率。Polti 算法讓優(yōu)先級低的事務(wù)等待一個常數(shù)時間，達(dá)到等待時間上限后，執(zhí)行耗時久的競爭事務(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 個隨機(jī)數(shù)，維護(hù)高低頻記錄表，記錄歷史沖突的地址值與沖突次數(shù)n。

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 多線程并行程序流程

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

本實(shí)驗(yàn)使用的OpenMP 指導(dǎo)語句實(shí)現(xiàn)多線程的并行同步與歸并。使用“omp_num_treads”語句設(shè)置環(huán)境變量，定義執(zhí)行中最大的線程數(shù)。在多線程同時執(zhí)行的可并行程序部分，加入“#pragma omp parallel for”語句，將可并行執(zhí)行的語句自動并行化，緊隨它的循環(huán)語句由線程組并行執(zhí)行。在線程同步的設(shè)置上，使用“#pragma omp critical（name）”語句使得并行域中的代碼塊每次只能執(zhí)行多個線程中的一個，其他線程則被阻塞，該語句用于競爭管理部分的線程等待。使用barrier 制導(dǎo)語句用來同步一個線程組中所有的線程，本實(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ù)表的個數(shù)從699 個減少到25 個。編程實(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í)驗(yàn)結(jié)果如圖3 所示。

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

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

本文經(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 時，對三種算法進(jìn)行測試。測試結(jié)果如圖4、圖5 所示

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

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

4.2 結(jié)果分析

從以上實(shí)驗(yàn)結(jié)果可以看出，完整的Polti 沖突管理算法“Full-Polti”的表現(xiàn)最為優(yōu)越，在相同的初始參數(shù)下，完整算法的運(yùn)行時間最短，沖突次數(shù)最少。因?yàn)橥暾惴ㄊ褂昧藳_突預(yù)測避免了不必要的沖突發(fā)生，使用Polti 競爭管理算法對沖突的事務(wù)進(jìn)行合理管理，保證事務(wù)在有限的時間內(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è)計合理的沖突管理算法對事務(wù)內(nèi)存系統(tǒng)的性能和效率有著重要影響，可以顯著提高事務(wù)內(nèi)存系統(tǒng)的執(zhí)行性能。

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

5 結(jié)語

競爭管理是事務(wù)申請?zhí)峤磺暗囊粋€操作，是對沖突檢測的結(jié)果進(jìn)行的，多個事務(wù)發(fā)生沖突后，應(yīng)該如何管理沖突事務(wù)，選擇哪個繼續(xù)執(zhí)行，哪個要回滾。本文首先將目前的幾種競爭管理算法進(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)勢。