事務(wù)存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)

1 引言

隨著多核處理器技術(shù)的不斷更新和發(fā)展，傳統(tǒng)的串行程序不論在效率上還是性能上都已經(jīng)跟不上信息高速發(fā)展的腳步了，程序員不得不開(kāi)發(fā)線程級(jí)并行以提高片上計(jì)算資源的使用效率，但也帶來(lái)了新的挑戰(zhàn)和問(wèn)題。目前不同線程間的同步、對(duì)共享資源的訪問(wèn)等都是通過(guò)鎖和信號(hào)量機(jī)制完成的。然而，這種傳統(tǒng)的基于鎖和信號(hào)量的并發(fā)系統(tǒng)存在明顯的局限性。粗粒度的鎖對(duì)大量的共享數(shù)據(jù)做了保護(hù)，但是可擴(kuò)展性不好，因?yàn)榧词乖诰€程間不存在對(duì)共享數(shù)據(jù)的訪問(wèn)的情況下也可能會(huì)出現(xiàn)沖突阻塞現(xiàn)象；細(xì)粒度的鎖雖然比粗粒度的鎖擴(kuò)展性能好，但由于算法設(shè)計(jì)的復(fù)雜性，普通程序員很難借助細(xì)力度的鎖實(shí)現(xiàn)高效的應(yīng)用。同時(shí)使用鎖機(jī)制還會(huì)帶來(lái)諸多問(wèn)題，比如：死鎖、優(yōu)先級(jí)反轉(zhuǎn)等，極大地影響了并行應(yīng)用的效率和性能。

事務(wù)存儲(chǔ)(Transactional Memory，TM)的使用是解決上述存在問(wèn)題一個(gè)很好的辦法[1]。通過(guò)將不同并行執(zhí)行的線程事務(wù)化，用事務(wù)操作來(lái)代替鎖機(jī)制能降低編程的復(fù)雜性。事務(wù)是被單線程執(zhí)行的對(duì)內(nèi)存進(jìn)行讀寫(xiě)的有序操作序列，其特性包括：原子性、隔離性、一致性和持久性。通常事務(wù)的執(zhí)行過(guò)程為：調(diào)用事務(wù)入口函數(shù)(begin_transaction)開(kāi)始執(zhí)行事務(wù)，當(dāng)事務(wù)執(zhí)行完畢后調(diào)用提交函數(shù)(commit_transaction)開(kāi)始提交工作，提交過(guò)程分為三個(gè)階段(請(qǐng)求提交、開(kāi)始提交和完成提交)，執(zhí)行完提交后此事務(wù)也就執(zhí)行完畢，從而繼續(xù)執(zhí)行下面的事務(wù)。但如果事務(wù)在執(zhí)行或提交過(guò)程中發(fā)生沖突或者錯(cuò)誤，則通過(guò)其特有的回滾機(jī)制 (rollback)返回到此事務(wù)入口繼續(xù)執(zhí)行。事務(wù)的執(zhí)行流程圖如圖 1所示。

圖 1 事務(wù)執(zhí)行流程

為了實(shí)現(xiàn)事務(wù)的這些特性，需有一個(gè)很好的TM系統(tǒng)來(lái)支持事務(wù)數(shù)據(jù)的版本管理(Version Management)和事務(wù)的沖突管理(Contention Management)。版本管理同時(shí)對(duì)新值(事務(wù)提交后可見(jiàn))和原始的舊值(事務(wù)執(zhí)行過(guò)程中發(fā)生了回滾的恢復(fù)數(shù)據(jù))進(jìn)行管理。根據(jù)數(shù)據(jù)存放方式的不同TM系統(tǒng)區(qū)分版本管理為：積極版本管理(Eager Version Management)和懶惰版本管理(Lazy Version Management)。積極版本管理是將新值置于目標(biāo)存儲(chǔ)區(qū)中，這樣在提交時(shí)新值能夠很快的得到執(zhí)行，極大地降低了提交的時(shí)延；而懶惰版本管理是將原始的舊值置于目標(biāo)存儲(chǔ)區(qū)，雖然會(huì)增加提交的延時(shí)但是降低了當(dāng)事務(wù)發(fā)生回滾后執(zhí)行的延時(shí)。沖突管理是不同事務(wù)執(zhí)行過(guò)程中對(duì)共享資源訪問(wèn)引發(fā)沖突而進(jìn)行的沖突檢測(cè)以及管理的機(jī)制。沖突管理有積極的(Eager)和懶惰的(Lazy)兩種策略，如果沖突在讀數(shù)據(jù)或?qū)憯?shù)據(jù)時(shí)立刻被發(fā)現(xiàn)而進(jìn)行仲裁，這種沖突檢測(cè)是積極的；如果沖突是在事務(wù)進(jìn)行提交時(shí)才發(fā)現(xiàn)并仲裁的，這種沖突檢測(cè)則是懶惰的。

目前，基于TM的硬件結(jié)構(gòu)有很多種，圖2中列出了目前幾種流行的硬件結(jié)構(gòu)根據(jù)版本管理和沖突管理而進(jìn)行的分類(lèi)。本文將介紹其中的一種結(jié)構(gòu)——LogTM(日志事務(wù)存儲(chǔ))，通過(guò)對(duì)其硬件結(jié)構(gòu)（參見(jiàn)圖3）、版本管理、沖突管理的實(shí)現(xiàn)，展現(xiàn)了此結(jié)構(gòu)的優(yōu)越性，并給后續(xù)研究提供參考和幫助。

圖2 TM系統(tǒng)分類(lèi)

2 LogTM的結(jié)構(gòu)

LogTM是建立在多機(jī)系統(tǒng)中基于日志的TM實(shí)現(xiàn)，每個(gè)核都有獨(dú)自的私有cache，并通過(guò)目錄協(xié)議來(lái)維持?jǐn)?shù)據(jù)的一致性。它采用的是積極的版本管理策略和積極的沖突管理策略。圖3給出了LogTM的硬件結(jié)構(gòu)，它通過(guò)增加一些寄存器和cache中的讀/寫(xiě)位很好地完成了對(duì)事務(wù)的操作。

圖3 LogTM的硬件結(jié)構(gòu) (圖中黑框中為其特有結(jié)構(gòu))

2.1 版本管理(Version Management)

LogTM使用積極的版本管理，將新的執(zhí)行數(shù)據(jù)存儲(chǔ)在目標(biāo)區(qū)域(目標(biāo)地址)中，而將舊的數(shù)據(jù)存儲(chǔ)在其它緩沖區(qū)。它通過(guò)在內(nèi)存中開(kāi)辟一塊事務(wù)日志區(qū)域存儲(chǔ)事務(wù)執(zhí)行過(guò)程中被修改的數(shù)據(jù)(上文中提到的原始數(shù)據(jù))和這些數(shù)據(jù)所對(duì)應(yīng)的地址，新的執(zhí)行數(shù)據(jù)則被保存在目標(biāo)存儲(chǔ)區(qū)(目標(biāo)地址)，當(dāng)執(zhí)行完成提交時(shí)，這些新數(shù)據(jù)將會(huì)立即生效；當(dāng)事務(wù)執(zhí)行過(guò)程中或提交時(shí)發(fā)生沖突或錯(cuò)誤需要回滾時(shí)，則通過(guò)事務(wù)日志中記錄的信息恢復(fù)出事務(wù)執(zhí)行前的初始狀態(tài)。

剛開(kāi)始創(chuàng)建線程時(shí)，每一個(gè)線程對(duì)應(yīng)著一個(gè)日志而且為日志分配一塊虛擬存儲(chǔ)區(qū)域，并將該日志基地址寫(xiě)入Log Base寄存器，當(dāng)舊數(shù)據(jù)需要存儲(chǔ)到日志時(shí)，LogTM通過(guò)Log Base寄存器中的值定位到日志的入口然后將舊數(shù)據(jù)的虛擬地址和值一同保存在日志中以便恢復(fù)時(shí)使用。為了減少冗余日志，LogTM為每一個(gè)cache塊添加了對(duì)應(yīng)的寫(xiě)(W)位，用此來(lái)標(biāo)識(shí)該cache塊在日志中的記錄情況。當(dāng)事務(wù)提交成功后，LogTM將對(duì)應(yīng)cache塊的寫(xiě)(W)標(biāo)志位清0并將Log Pointer(日志指針)重新指向日志的入口處，以便處理后續(xù)事務(wù)。

LogTM也為每個(gè)cache塊設(shè)置了一個(gè)讀(R)標(biāo)志位，就像上面我們討論的寫(xiě)(W)標(biāo)志位一樣。在每個(gè)事務(wù)操作過(guò)程中LogTM同樣將讀標(biāo)志位設(shè)置用于表示讀操作的執(zhí)行(如圖4所示)，而且在事務(wù)結(jié)束后，讀標(biāo)志位也清0。

這種積極的版本管理模式的缺點(diǎn)就是在事務(wù)發(fā)生沖突或錯(cuò)誤需要回滾時(shí)執(zhí)行比較慢，在回滾時(shí)，LogTM為了完成恢復(fù)必須將原始數(shù)據(jù)從日志中讀到合適的目標(biāo)地址中然后重置寫(xiě)(W)位，同時(shí)因?yàn)橛泻芏鄶?shù)據(jù)記錄在日志中，所以恢復(fù)過(guò)程必須按照由后向前(后進(jìn)先出)的順序進(jìn)行。但在事務(wù)沖突比較少的情況下，這種模式能夠帶來(lái)高效的執(zhí)行效率。

為了能更好的理解LogTM版本管理過(guò)程，圖4通過(guò)一個(gè)例子進(jìn)行了很好的分析。

(1)事務(wù)執(zhí)行開(kāi)始前的狀態(tài)——cache數(shù)據(jù)塊中存放著原始數(shù)據(jù)，每塊的讀(R)、寫(xiě)(W)位置0，LogBase(日志基址寄存器)指向日志入口地址，LogPtr(日志偏移指針)指向日志入口地址同時(shí)TMcount(事務(wù)計(jì)數(shù)器)置1代表正準(zhǔn)備執(zhí)行一個(gè)事務(wù)。