事務(wù)存儲結構的實(shí)現

1 引言

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

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

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

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

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

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

2 LogTM的結構

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

圖3 LogTM的硬件結構 (圖中黑框中為其特有結構)

2.1 版本管理(Version Management)

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

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

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

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

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

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