摘 要多核處理技術將成為計算機的主流技術，基於多核開發線程級並行已至關重要，事務的引入能夠解決目前線程所不能完成的功能，同時能夠簡化編程模型，事務存儲能很好地實現事務特性。本文首先介紹了TM的基本原理，接著分析了目前主流TM系統LogTM，著重於數據版本管理和衝突管理機制的實現，進而將此系統的優越性展現出來。最後對本文進行了總結和展望。
關鍵詞事務存儲；日誌事務存儲；體系結構；作業系統
1 引言
隨著多核處理器技術的不斷更新和發展，傳統的串行程序不論在效率上還是性能上都已經跟不上信息高速發展的腳步了，程式設計師不得不開發線程級並行以提高片上計算資源的使用效率，但也帶來了新的挑戰和問題。目前不同線程間的同步、對共享資源的訪問等都是通過鎖和信號量機制完成的。然而，這種傳統的基於鎖和信號量的並發系統存在明顯的局限性。粗粒度的鎖對大量的共享數據做了保護，但是可擴展性不好，因為即使在線程間不存在對共享數據的訪問的情況下也可能會出現衝突阻塞現象；細粒度的鎖雖然比粗粒度的鎖擴展性能好，但由於算法設計的複雜性，普通程式設計師很難藉助細力度的鎖實現高效的應用。同時使用鎖機制還會帶來諸多問題，比如：死鎖、優先級反轉等，極大地影響了並行應用的效率和性能。
事務存儲(Transactional Memory，TM)的使用是解決上述存在問題一個很好的辦法[1]。通過將不同並行執行的線程事務化，用事務操作來代替鎖機制能降低編程的複雜性。事務是被單線程執行的對內存進行讀寫的有序操作序列，其特性包括：原子性、隔離性、一致性和持久性。通常事務的執行過程為：調用事務入口函數(begin_transaction)開始執行事務，當事務執行完畢後調用提交函數(commit_transaction)開始提交工作，提交過程分為三個階段(請求提交、開始提交和完成提交)，執行完提交後此事務也就執行完畢，從而繼續執行下面的事務。但如果事務在執行或提交過程中發生衝突或者錯誤，則通過其特有的回滾機制 (rollback)返回到此事務入口繼續執行。事務的執行流程圖如圖 1所示。
圖 1 事務執行流程
為了實現事務的這些特性，需有一個很好的TM系統來支持事務數據的版本管理(Version Management)和事務的衝突管理(Contention Management)。版本管理同時對新值(事務提交後可見)和原始的舊值(事務執行過程中發生了回滾的恢複數據)進行管理。根據數據存放方式的不同TM系統區分版本管理為：積極版本管理(Eager Version Management)和懶惰版本管理(Lazy Version Management)。積極版本管理是將新值置於目標存儲區中，這樣在提交時新值能夠很快的得到執行，極大地降低了提交的時延；而懶惰版本管理是將原始的舊值置於目標存儲區，雖然會增加提交的延時但是降低了當事務發生回滾後執行的延時。衝突管理是不同事務執行過程中對共享資源訪問引發衝突而進行的衝突檢測以及管理的機制。衝突管理有積極的(Eager)和懶惰的(Lazy)兩種策略，如果衝突在讀數據或寫數據時立刻被發現而進行仲裁，這種衝突檢測是積極的；如果衝突是在事務進行提交時才發現並仲裁的，這種衝突檢測則是懶惰的。
目前，基於TM的硬體結構有很多種，圖2中列出了目前幾種流行的硬體結構根據版本管理和衝突管理而進行的分類。本文將介紹其中的一種結構——LogTM(日誌事務存儲)，通過對其硬體結構（參見圖3）、版本管理、衝突管理的實現，展現了此結構的優越性，並給後續研究提供參考和幫助。
圖2 TM系統分類
2 LogTM的結構
LogTM是建立在多機系統中基於日誌的TM實現，每個核都有獨自的私有cache，並通過目錄協議來維持數據的一致性。它採用的是積極的版本管理策略和積極的衝突管理策略。圖3給出了LogTM的硬體結構，它通過增加一些寄存器和cache中的讀/寫位很好地完成了對事務的操作。
圖3 LogTM的硬體結構 (圖中黑框中為其特有結構)
2.1 版本管理(Version Management)
LogTM使用積極的版本管理，將新的執行數據存儲在目標區域(目標地址)中，而將舊的數據存儲在其它緩衝區。它通過在內存中開闢一塊事務日誌區域存儲事務執行過程中被修改的數據(上文中提到的原始數據)和這些數據所對應的地址，新的執行數據則被保存在目標存儲區(目標地址)，當執行完成提交時，這些新數據將會立即生效；當事務執行過程中或提交時發生衝突或錯誤需要回滾時，則通過事務日誌中記錄的信息恢復出事務執行前的初始狀態。
剛開始創建線程時，每一個線程對應著一個日誌而且為日誌分配一塊虛擬存儲區域，並將該日誌基地址寫入Log Base寄存器，當舊數據需要存儲到日誌時，LogTM通過Log Base寄存器中的值定位到日誌的入口然後將舊數據的虛擬地址和值一同保存在日誌中以便恢復時使用。為了減少冗餘日誌，LogTM為每一個cache塊添加了對應的寫(W)位，用此來標識該cache塊在日誌中的記錄情況。當事務提交成功後，LogTM將對應cache塊的寫(W)標誌位清0並將Log Pointer(日誌指針)重新指向日誌的入口處，以便處理後續事務。
LogTM也為每個cache塊設置了一個讀(R)標誌位，就像上面我們討論的寫(W)標誌位一樣。在每個事務操作過程中LogTM同樣將讀標誌位設置用於表示讀操作的執行(如圖4所示)，而且在事務結束後，讀標誌位也清0。
這種積極的版本管理模式的缺點就是在事務發生衝突或錯誤需要回滾時執行比較慢，在回滾時，LogTM為了完成恢復必須將原始數據從日誌中讀到合適的目標地址中然後重置寫(W)位，同時因為有很多數據記錄在日誌中，所以恢復過程必須按照由後向前(後進先出)的順序進行。但在事務衝突比較少的情況下，這種模式能夠帶來高效的執行效率。
為了能更好的理解LogTM版本管理過程，圖4通過一個例子進行了很好的分析。
(1)事務執行開始前的狀態——cache數據塊中存放著原始數據，每塊的讀(R)、寫(W)位置0，LogBase(日誌基址寄存器)指向日誌入口地址，LogPtr(日誌偏移指針)指向日誌入口地址同時TMcount(事務計數器)置1代表正準備執行一個事務。
(2) 讀00地址(十六進制地址)中的數據到寄存器r1中，00地址對應數據塊的讀(R)標誌位置1表示此數據被讀。
(3) 將寄存器r2中數據(這裡假設為56)存入c0地址中，由於c0地址中存在原始數據34，將c0地址和該原始數據一起根據LogBase中的日誌入口地址存入日誌中，並將LogPtr指針後移，指向用於存放下個數據的地址位，同時將c0地址對應塊的寫(W)標誌位置1，代表一次寫操作的完成，其他的狀態不變。
(4) 讀取40地址中數據到寄存器r3中，然後r3中數據加1，並將執行後的r3數據存回40地址中，該操作對40地址對應塊執行了一次讀操作和一次寫操作，將讀(R)和寫(W)標誌位置1，然後將原始40地址對應塊中數據存入日誌中，存入LogPtr指向的地址中，同時將LogPtr指針後移。
(5) 事務提交後狀態——將與本事務相關的各個數據塊對應讀寫標誌位清0，將LogPtr置位到LogBase，TMcount置0。(本例僅針對單事務執行，如果是嵌套事務的執行，LogTM結構會更加複雜，具體支持嵌套事務的LogTM實現，請參考[2])
(6) 事務回滾後狀態——事務在執行或提交過程中如果出錯需要回滾，則將日誌中記錄的原始數據按照地址映射關係重新加載到對應cache數據塊中，同時將各個塊對應讀寫標誌位清0，LogPtr重置並且TMcount置0。
圖 4 事務版本管理過程——成功提交和回滾
轉貼於論文聯盟 http://www.lwlm.com
關鍵詞事務存儲；日誌事務存儲；體系結構；作業系統
1 引言
隨著多核處理器技術的不斷更新和發展，傳統的串行程序不論在效率上還是性能上都已經跟不上信息高速發展的腳步了，程式設計師不得不開發線程級並行以提高片上計算資源的使用效率，但也帶來了新的挑戰和問題。目前不同線程間的同步、對共享資源的訪問等都是通過鎖和信號量機制完成的。然而，這種傳統的基於鎖和信號量的並發系統存在明顯的局限性。粗粒度的鎖對大量的共享數據做了保護，但是可擴展性不好，因為即使在線程間不存在對共享數據的訪問的情況下也可能會出現衝突阻塞現象；細粒度的鎖雖然比粗粒度的鎖擴展性能好，但由於算法設計的複雜性，普通程式設計師很難藉助細力度的鎖實現高效的應用。同時使用鎖機制還會帶來諸多問題，比如：死鎖、優先級反轉等，極大地影響了並行應用的效率和性能。
事務存儲(Transactional Memory，TM)的使用是解決上述存在問題一個很好的辦法[1]。通過將不同並行執行的線程事務化，用事務操作來代替鎖機制能降低編程的複雜性。事務是被單線程執行的對內存進行讀寫的有序操作序列，其特性包括：原子性、隔離性、一致性和持久性。通常事務的執行過程為：調用事務入口函數(begin_transaction)開始執行事務，當事務執行完畢後調用提交函數(commit_transaction)開始提交工作，提交過程分為三個階段(請求提交、開始提交和完成提交)，執行完提交後此事務也就執行完畢，從而繼續執行下面的事務。但如果事務在執行或提交過程中發生衝突或者錯誤，則通過其特有的回滾機制 (rollback)返回到此事務入口繼續執行。事務的執行流程圖如圖 1所示。
圖 1 事務執行流程
為了實現事務的這些特性，需有一個很好的TM系統來支持事務數據的版本管理(Version Management)和事務的衝突管理(Contention Management)。版本管理同時對新值(事務提交後可見)和原始的舊值(事務執行過程中發生了回滾的恢複數據)進行管理。根據數據存放方式的不同TM系統區分版本管理為：積極版本管理(Eager Version Management)和懶惰版本管理(Lazy Version Management)。積極版本管理是將新值置於目標存儲區中，這樣在提交時新值能夠很快的得到執行，極大地降低了提交的時延；而懶惰版本管理是將原始的舊值置於目標存儲區，雖然會增加提交的延時但是降低了當事務發生回滾後執行的延時。衝突管理是不同事務執行過程中對共享資源訪問引發衝突而進行的衝突檢測以及管理的機制。衝突管理有積極的(Eager)和懶惰的(Lazy)兩種策略，如果衝突在讀數據或寫數據時立刻被發現而進行仲裁，這種衝突檢測是積極的；如果衝突是在事務進行提交時才發現並仲裁的，這種衝突檢測則是懶惰的。
目前，基於TM的硬體結構有很多種，圖2中列出了目前幾種流行的硬體結構根據版本管理和衝突管理而進行的分類。本文將介紹其中的一種結構——LogTM(日誌事務存儲)，通過對其硬體結構（參見圖3）、版本管理、衝突管理的實現，展現了此結構的優越性，並給後續研究提供參考和幫助。
圖2 TM系統分類
2 LogTM的結構
LogTM是建立在多機系統中基於日誌的TM實現，每個核都有獨自的私有cache，並通過目錄協議來維持數據的一致性。它採用的是積極的版本管理策略和積極的衝突管理策略。圖3給出了LogTM的硬體結構，它通過增加一些寄存器和cache中的讀/寫位很好地完成了對事務的操作。
圖3 LogTM的硬體結構 (圖中黑框中為其特有結構)
2.1 版本管理(Version Management)
LogTM使用積極的版本管理，將新的執行數據存儲在目標區域(目標地址)中，而將舊的數據存儲在其它緩衝區。它通過在內存中開闢一塊事務日誌區域存儲事務執行過程中被修改的數據(上文中提到的原始數據)和這些數據所對應的地址，新的執行數據則被保存在目標存儲區(目標地址)，當執行完成提交時，這些新數據將會立即生效；當事務執行過程中或提交時發生衝突或錯誤需要回滾時，則通過事務日誌中記錄的信息恢復出事務執行前的初始狀態。
剛開始創建線程時，每一個線程對應著一個日誌而且為日誌分配一塊虛擬存儲區域，並將該日誌基地址寫入Log Base寄存器，當舊數據需要存儲到日誌時，LogTM通過Log Base寄存器中的值定位到日誌的入口然後將舊數據的虛擬地址和值一同保存在日誌中以便恢復時使用。為了減少冗餘日誌，LogTM為每一個cache塊添加了對應的寫(W)位，用此來標識該cache塊在日誌中的記錄情況。當事務提交成功後，LogTM將對應cache塊的寫(W)標誌位清0並將Log Pointer(日誌指針)重新指向日誌的入口處，以便處理後續事務。
LogTM也為每個cache塊設置了一個讀(R)標誌位，就像上面我們討論的寫(W)標誌位一樣。在每個事務操作過程中LogTM同樣將讀標誌位設置用於表示讀操作的執行(如圖4所示)，而且在事務結束後，讀標誌位也清0。
這種積極的版本管理模式的缺點就是在事務發生衝突或錯誤需要回滾時執行比較慢，在回滾時，LogTM為了完成恢復必須將原始數據從日誌中讀到合適的目標地址中然後重置寫(W)位，同時因為有很多數據記錄在日誌中，所以恢復過程必須按照由後向前(後進先出)的順序進行。但在事務衝突比較少的情況下，這種模式能夠帶來高效的執行效率。
為了能更好的理解LogTM版本管理過程，圖4通過一個例子進行了很好的分析。
(1)事務執行開始前的狀態——cache數據塊中存放著原始數據，每塊的讀(R)、寫(W)位置0，LogBase(日誌基址寄存器)指向日誌入口地址，LogPtr(日誌偏移指針)指向日誌入口地址同時TMcount(事務計數器)置1代表正準備執行一個事務。
(2) 讀00地址(十六進制地址)中的數據到寄存器r1中，00地址對應數據塊的讀(R)標誌位置1表示此數據被讀。
(3) 將寄存器r2中數據(這裡假設為56)存入c0地址中，由於c0地址中存在原始數據34，將c0地址和該原始數據一起根據LogBase中的日誌入口地址存入日誌中，並將LogPtr指針後移，指向用於存放下個數據的地址位，同時將c0地址對應塊的寫(W)標誌位置1，代表一次寫操作的完成，其他的狀態不變。
(4) 讀取40地址中數據到寄存器r3中，然後r3中數據加1，並將執行後的r3數據存回40地址中，該操作對40地址對應塊執行了一次讀操作和一次寫操作，將讀(R)和寫(W)標誌位置1，然後將原始40地址對應塊中數據存入日誌中，存入LogPtr指向的地址中，同時將LogPtr指針後移。
(5) 事務提交後狀態——將與本事務相關的各個數據塊對應讀寫標誌位清0，將LogPtr置位到LogBase，TMcount置0。(本例僅針對單事務執行，如果是嵌套事務的執行，LogTM結構會更加複雜，具體支持嵌套事務的LogTM實現，請參考[2])
(6) 事務回滾後狀態——事務在執行或提交過程中如果出錯需要回滾，則將日誌中記錄的原始數據按照地址映射關係重新加載到對應cache數據塊中，同時將各個塊對應讀寫標誌位清0，LogPtr重置並且TMcount置0。
圖 4 事務版本管理過程——成功提交和回滾
轉貼於論文聯盟 http://www.lwlm.com
收藏