事務內存

事務內存（英語：Transactional memory）是一種並行程序設計的方式，其來自於數據庫管理系統（DBMS）中的事務（Transaction）概念。事務內存目前有兩種實現方式，基於軟件的軟件事務內存（STM）和基於硬件的HTM（Hardware Transactional Memory）。

背景

採用任務並行時必須考慮線程間同步的問題：最初步也是最通常的方法是使用鎖，只有獲得了鎖的線程在允許訪問臨界區，但是使用鎖會發生一些問題，諸如優先級反轉(Priority inversion)、死鎖（Deadlock）、護航（Convoying）等問題；於是後來產生了無鎖編程（Lockless programming）的概念，即使用原子操作（Atomic Operations）和同步路障（Memory barrier）來完成線程間同步的功能，這種方法規避了使用鎖時出現的上述問題並極大的提高了並行度，但是面臨着原子操作本身功能局限性和組合性(Compositionality)不佳的問題。原子操作的局限性使得無鎖編程的算法設計很難，組合性則是指數個同步的原子對象組合應該也是一個同步的原子對象。

事務的概念

事務的概念源自於數據庫管理系統（DBMS）中數據庫事務的概念。在數據庫管理系統中，事務必須滿足ACID性質，即原子性，一致性，隔離性和持久性。原子性指的是事務中的動作要麼全部執行，要麼一個都不執行；一致性指的是任何時刻，數據庫必須處於一致性狀態，即必須滿足某些預先設定的條件；隔離性是指一個事務不能看見其他未提交事務所涉及到的內部對象的狀態，而持久性則是指一個已提交的事務對數據庫系統的改變必須是永久的。

事務內存的分類和涉及到的基本術語

事務內存按照更新數據時的機制不同，可分為 延遲更新(deferred-update) 和 直接更新 (direct-update) 兩大類。延遲更新軟件事務內存的基本思想是一個線程僅改變屬於自己的資料副本，如果未與其他線程發生衝突，最終的提交 (Commit) 動作則可順利完成，副本內容抄到正本之上；如果失敗則取消或回溯 (Abort / Rollback)，丟棄副本即可。直接更新則是一個綫程暫時獨佔和直接更新資料正本，提交得到確認，只須解除獨佔設定，容許其他綫程往後存取；直接更新需要資料的原始值作為副本，倘若運算最終無法完成，可作回溯之用。

根據在事務衝突時的處理機制不同，又可以分為 悲觀和樂觀的並發控制(pessimistic & optimistic concurrency control)兩大類。在悲觀的並發控制中，衝突一旦發生就必須要得到偵測並加以解決，而在樂觀的並發控制里，衝突的偵測和解決可以延遲，只要是在事務提交之前進行就可以了。

事務還有粒度(granularity)的概念：最容易讓程序員理解的粒度是對象粒度；在此粒度下，任何衝突發生的判決是在對象範圍內進行的：即使兩個事務修改的內存塊不重合，只要他們是在同一個對象內，那麼就可以判斷這兩個事務衝突。更精細的粒度是字粒度(word granularity)和字節粒度(byte granularity)，在這兩種粒度下，衝突的檢測更精細，更利於事務內存系統性能的提升，但是卻會給程序員帶來不小的麻煩。

軟件事務內存（STM）

軟件事務內存的實現包括原子對象（Atomic object）、衝突判決器（Conflict manager）。其中原子對象的實現是最重要的，它是各事務之間通信同步的媒介。原子對象的實現又分為順序性實現和事務實現：其中事務實現還要要求實現同步和恢復（recovery）功能，同步功能即意味着要求有檢測事務衝突的能力，而恢復功能則意味着需要在事務失敗的時候將對象回滾到事務執行之前的狀態。目前提出的原子對象一般是基於讀/寫衝突(Read/Write conflict)的機制：原子對象提供兩個接口，一個為讀接口，一個為寫接口，通過讀接口可以得到一個可以讀的對象，而通過寫接口則可以得到一個可以寫的對象。為了檢測衝突（即多個事務並發時的同步情況），事務中可以設立兩個集合，一個為讀集（Read set）,一個為寫集（Write set），分別記錄該事務所要處理的讀寫原子對象集。如果一個事務的讀集或寫集與另一個事務的寫集有交叉，則表明兩個事務衝突，需要衝突判決器進一步採取決策。

硬件事務內存（HTM）

昇陽電腦的Rock微處理器將支援硬件事務內存。

Azul Systems在2009年推出的 Vega 2 微處理器支援硬件事務內存。

相關的話題

• 內存一致性模型 （Memory consistency model）
• 無鎖編程（Lockless programming）
• 任務並行
• 事務提升（Transactional boosting）

參考書目

1. Transactional Memory，Synthesis Lectures on Computer Architecture，Mark D. Hill, University of Wisconsin, Madison