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

1 引言

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

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

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

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

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

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

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

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

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

2.1 版本管理(Version Management)

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

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

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

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

為了能更好的理解LogTM版本管理過程，圖4通過一個例子進行了很好的分析。

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