多核結(jié)構(gòu)上軟件事務(wù)存儲(chǔ)的研究.pdf

1、針對(duì)計(jì)算資源日益增加的需求，單純提高處理器主頻的方式，已經(jīng)不再能夠提升計(jì)算機(jī)的性能了。因此，工業(yè)界引入了“多核”的概念，即在一個(gè)芯片上集成兩個(gè)或多個(gè)獨(dú)立的處理器，處理器之間共享內(nèi)存。在多核系統(tǒng)中，同樣的時(shí)鐘頻率，由于片上處理器個(gè)數(shù)的增加，每秒鐘執(zhí)行的指令數(shù)也隨著翻倍，這為解決處理器性能的瓶頸問題提供了新的思路。與此同時(shí)，多核系統(tǒng)也給并行處理提出了新的問題，如何能夠更好地利用多核的資源對(duì)程序進(jìn)行并行處理，成為當(dāng)今并行處理方面研究的一個(gè)熱點(diǎn)

2、方向。
　　事務(wù)的概念來源于數(shù)據(jù)庫，實(shí)踐證明了其是一種有效的并發(fā)控制手段。因此，將事務(wù)引入并行程序設(shè)計(jì)領(lǐng)域，形成了事務(wù)存儲(chǔ)的理論。事務(wù)存儲(chǔ)中的事務(wù)，指的是被某個(gè)線程執(zhí)行的對(duì)內(nèi)存的一系列有序讀寫操作序列。這些序列或者全部被執(zhí)行并提交，或者一個(gè)也不執(zhí)行并恢復(fù)到執(zhí)行該序列之前的狀態(tài)。本文首先對(duì)現(xiàn)有的各類事務(wù)存儲(chǔ)系統(tǒng)進(jìn)行了分析，重點(diǎn)研究了基于Signature數(shù)據(jù)結(jié)構(gòu)的軟件事務(wù)存儲(chǔ)系統(tǒng)。然后針對(duì)軟件事務(wù)存儲(chǔ)系統(tǒng)中的三大基本功能分別進(jìn)行了研

3、究，提出了新的優(yōu)化方案，并對(duì)這些方案進(jìn)行了仿真實(shí)驗(yàn)。最后，將改進(jìn)后的功能整合起來構(gòu)成一個(gè)基于Signature的軟件事務(wù)存儲(chǔ)系統(tǒng)。本文的主要研究成果如下：
　　(1)在研究了沖突檢測算法VHB的基礎(chǔ)之上，提出了一種基于Signature的新的沖突檢測算法VHTB。該算法不但對(duì)Signature的行與行之間進(jìn)行動(dòng)態(tài)變換，而且對(duì)地址數(shù)據(jù)相對(duì)較少的情況采用了尚未使用的存儲(chǔ)空間來存儲(chǔ)哈希函數(shù)的True Bloom映射信息。這種并行實(shí)現(xiàn)的方

4、式既可以對(duì)塊內(nèi)的行與行之間進(jìn)行并行搜索，降低延時(shí)，同時(shí)也可以降低誤判率。經(jīng)實(shí)驗(yàn)測試VHTB算法的誤判率和中止率較VHB算法有了明顯的降低。
　　(2) True Bloom和Hash Bloom是事務(wù)存儲(chǔ)中常用的沖突檢測算法，而這兩種算法各有其特點(diǎn)，在此基礎(chǔ)之上將Signature區(qū)域劃分為兩個(gè)區(qū)域，對(duì)其中一個(gè)區(qū)域進(jìn)行TrueBloom映射，對(duì)另一個(gè)區(qū)域進(jìn)行Hash Bloom映射，由此提出了一種沖突檢測算法MixBloom。實(shí)驗(yàn)

5、證明該算法較Hash Bloom算法有著較低的誤判率和中止率。
　　(3)針對(duì)軟件事務(wù)存儲(chǔ)中數(shù)據(jù)版本管理的問題，提出了一種結(jié)合急切版本管理和惰性版本管理于一身的混合數(shù)據(jù)版本管理機(jī)制。在該機(jī)制中，混合數(shù)據(jù)版本管理器能夠根據(jù)沖突的數(shù)量進(jìn)行動(dòng)態(tài)地雙向切換，從而選取最適合當(dāng)前狀態(tài)的數(shù)據(jù)版本管理策略。實(shí)驗(yàn)證明混合數(shù)據(jù)版本管理策略在整體上取得了較好的性能，達(dá)到了預(yù)期的效果。
　　(4)在現(xiàn)有的沖突解決策略的基礎(chǔ)上，結(jié)合各個(gè)沖突解決策略的

6、優(yōu)點(diǎn)，提出了一種沖突解決策略Synthesized。該策略綜合了若干因素，包括Polite的隨機(jī)指數(shù)回退、Karma的優(yōu)先級(jí)、Eruption的繼承優(yōu)先級(jí)以及Justice的權(quán)重等，形成一個(gè)綜合的沖突解決策略。實(shí)驗(yàn)證明了該沖突解決策略與現(xiàn)有策略相比，有較高的事務(wù)提交數(shù)量。
　　(5) Rochester STM是一種常用的軟件事務(wù)存儲(chǔ)系統(tǒng)，該系統(tǒng)僅采用單一沖突解決策略來處理沖突。為解決這一問題，提出了一種復(fù)合型沖突解決策略Comp

7、rehensive。該策略在兩個(gè)事務(wù)發(fā)生沖突時(shí)根據(jù)兩個(gè)事務(wù)的丟棄成本、嘗試次數(shù)以及起始時(shí)間等因素來決定丟棄哪個(gè)事務(wù)。實(shí)驗(yàn)證明了該沖突解決策略性能較其他沖突解決策略有顯著的提高。
　　(6)設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)支持多種基于Signature的沖突檢測算法的事務(wù)存儲(chǔ)系統(tǒng)RingSS(Ring Support Signature)，并在RingSS中對(duì)本文中提出的改進(jìn)策略進(jìn)行了評(píng)測。結(jié)果表明，在該事務(wù)存儲(chǔ)系統(tǒng)中，通過使用新的策略，使系統(tǒng)的性