软件事务内存

在電腦科學中，**軟體事務記憶體**（英語：Software transactional memory，縮寫為 STM），又譯為**交易記憶體**，**軟體交換式記憶體**，是一種並行控制機制，類比資料庫事務的機制，控制在平行計算時對共享記憶體的存取控制。它是鎖的一種替代機制。在 STM 中，一個事務指的是一段讀、寫共享記憶體的代碼。這些讀寫操作在邏輯上是一個獨立的單元，其中間狀態對於其它的事務而言，是不可見的。

## 效能

與現在許多多執行緒應用程式廣泛使用的鎖機制不同，STM 是一種非常樂觀的並行控制機制：一個執行緒獨立完成對共享記憶體的修改，完全忽略可能會有其它的執行緒存在，但是執行緒在紀錄檔中記錄對共享內容的每一個讀寫動作。其他的並行控制一般是在進行寫操作時來保證與其他事務的一致性（不能修改已經被別的事務修改過的共享資料），STM 在完成一個事務之後，再驗證其它執行緒有沒有並行的對共享記憶體進行或修改，從而保證事務是完整的。因此，STM 事務的最後一個操作是驗證，如果驗證通過，則提交，否則取消，導致所有以前進行的修改動作回滾。如果一個事務不能夠提交，一般的，事務將回滾，並且從入口開始重新執行。

採用這種樂觀策略可以增加並行效能：任何執行緒無需等待一個資源，多個執行緒可以並列而且安全的修改同一資料結構的多個部分（如果採用鎖，它們一般在同一個鎖的保護之下）。除了在事務失敗後需要重試而增加開銷之外，在現實世界中，由於衝突是很罕見的，因此，實際上可以帶來效能的提升。尤其是在多處理器的情況下。

不過，在一些實踐中，在較少 CPU（1-4）的系統上，基於 STM 的應用程式相對於一些精心調節的基於 Lock 的應用程式而言，會有一定的效能損失。主要的原因是在 STM 事務中，需要維持 log，以及額外的花在提交事務上的時間。不過，即使在這種情況下，效能也不會低於 50%。
相對而言，STM 擁護者認為 STM 帶來的優勢更為明顯。

理論上，在最糟糕的情況下，當 n 個並行事務同時執行，他們需要 n 倍的記憶體和處理器，實際的需要取決於具體的實現細節（比如說一個事務可以儘早的失敗以避免後續額外的開銷）。在某些應用場景下，基於 Lock 機制的演算法會比基於 STM 機制的演算法更好。

## 概念上的優勢和劣勢

除了效能上的優勢之外，STM 可以在概念上簡化多執行緒應用的模型，使得程式與一些已知的抽象概念如物件、模組等相處更為融洽，從而變得更易為維護。基於 Lock 的軟體開發在實踐上存在如下的問題：

* 需要將一些相互交錯、局部的操作理解成為一系列的獨立的、關係不密切的代碼，這對程式設計師而言，是一個艱巨而且很容易犯錯的任務。
* 需要程式設計師採用一定的策略來避免死結、活結，以及其他可能的錯誤。這些策略是強制的，且很容易犯錯的，當出現相關的問題時，難以重現、排錯。
* 會導致優先級衝突。經常會出現一個高優先級的執行緒需要等待另外一個低優先級的執行緒。

相反的，STM 的概念要簡單得多，因為每一個事務可以理解為隔離的，就像只有單個執行緒進行操作一般。死結等會完全避免，無需程式設計師擔心這個問題。優先級衝突的問題仍然存在，但一個高優先級的事務可以令得其他低優先級的事務提前終止。

相應的，由於需要提前結束事務，也對 STM 的事務提出了一些限制：在事務中不能夠操作那些不能回滾的動作，例如大部分的 IO 操作。這些限制在實際開發中是通過建立緩衝區，記錄這些不可回滾的操作，然後在事務完成後，在事務之外一次性的執行。在 Haskell 語言中，編譯器會利用類型資訊，做這個強制性檢查。

## 提議的語言支援

STM 在概念上的簡單性使得我們可以簡單的擴充語言來描述這個概念，Tim Harris 和 Keir Fraser 在 "Language Support for Lightweight Transactions"（語言支援的輕量級事務）中提出了 _conditional critical region_（條件關鍵區） (CCR) 來表述一個事務。在最簡單的形式下，使用一個 "atomic block"（原子塊）：一塊代碼必須在一個獨立的時間內完成的。

```
 _// Insert a node into a doubly-linked list atomically_
 **atomic** {
     newNode->prev = node;
     newNode->next = node->next;
     node->next->prev = newNode;
     node->next = newNode;
 }
```

在這個塊結束時，事務會被提交，或者失敗然後重試。CCR 也容許事務等待一定的條件滿足，這樣的話，事務會一直等待，直到條件滿足時，才開始事務。

```
 **atomic** (queueSize > 0) {
     remove item from queue and use it
 }
```

如果條件不滿足，事務管理器將等待，直到另外的一個事務提交，使得當前事務的條件得以滿足。這種鬆耦合相對於需要線上程之間顯式的進行訊號通訊更簡單。「Composable Memory Transaction」（組合記憶體事務）在這個基礎上走得更遠：通過 retry 命令，在事務的任何時候，終止當前事務，並且進行重試。比如：

```
 **atomic** {
     if (queueSize > 0) {
         remove item from queue and use it
     } else {
         **retry**
     }
 }
```

這種在事務過程中終止事務，並且進行重試的方式可以簡化並行開發，並且帶來新的編程視角。

一個存在的問題是如何處理那些傳播出去的異常，在 "Composed Memory Transaction" 中，作者決定在這種情況下，這個事務將失敗。

## 事務的鎖機制

STM 可以通過不使用鎖或者使用鎖來實現。有兩種鎖的模式：遭遇戰模式（encounter-time）下，所有記憶體的寫操作需要首先得到一個存取鎖，而後修改值，而後記錄操作在 undo 紀錄檔中。提交模式下則僅在提交事務時獲得一個存取鎖。

提交模式在 Dice、Shalev 中實現。Shavit 使用了一個全域版本時鐘，每個事務開始時讀到當前的版本號，並且將其作為讀的版本號。然後，在每次讀寫存取時，存取記憶體的版本號會和讀版本號比較，如果記憶體的版本號更大的話，表示這個記憶體已經被其他事務修改過，當前事務將失敗。這就可以保證當前事務執行的所有代碼都工作在一個獨立的記憶體瞬間映像之上。在提交時，所有的寫位址都將鎖住，所有讀寫位址的版本號會重新檢查。最後，全部版本號增加，所有新寫入的記憶體將從紀錄檔中重新寫入到記憶體中，並且更新其新的版本號。

## 參考資料

* Nir Shavit and Dan Touitou. Software Transactional Memory （頁面存檔備份，存於網際網路檔案館）. _Proceedings of the 14th ACM Symposium on Principles of Distributed Computing_, pp. 204–213. August 1995. The paper originating STM.
* Maurice Herlihy, Victor Luchangco, Mark Moir, and William N. Scherer III. Software Transactional Memory for Dynamic-Sized Data Structures. _Proceedings of the Twenty-Second Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing（PODC）_ , 92–101. July 2003.
* Tim Harris and Keir Fraser. Language Support for Lightweight Transactions （頁面存檔備份，存於網際網路檔案館）. _Object-Oriented Programming, Systems, Languages, and Applications_, pp. 388–402. October 2003.
* Tim Harris, Simon Marlow, Simon Peyton Jones, and Maurice Herlihy. Composable Memory Transactions （頁面存檔備份，存於網際網路檔案館）. _ACM Conference on Principles and Practice of Parallel Programming 2005_ (PPoPP'05). 2005.
* Robert Ennals. Software Transactional Memory Should Not Be Obstruction-Free (dead link). Archived: Software Transactional Memory Should Not Be Obstruction-Free.
* Michael L. Scott et al. Lowering the Overhead of Nonblocking Software Transactional Memory （頁面存檔備份，存於網際網路檔案館） gives a good introduction not only to the RSTM but also about existing STM approaches.
* Torvald Riegel and Pascal Felber and Christof Fetzer, A Lazy Snapshot Algorithm with Eager Validation （頁面存檔備份，存於網際網路檔案館） introduces the first time-based STM.
* Dave Dice, Ori Shalev, and Nir Shavit. Transactional Locking II.
* Knight, TF, An architecture for mostly functional languages, ACM Lisp and Functional Programming Conference, August, 1986.
* Knight, TF, System and method for parallel processing with mostly functional languages, US Patent 4,825,360, April, 1989.
* Ali-Reza Adl-Tabatabai, Christos Kozyrakis, Bratin Saha, Unlocking concurrency, ACM Queue 4, 10 (December 2006), pp 24–33. Ties multicore processors and the research/interest in STM together.
* James R Larus, Ravi Rajwar, Transactional Memory, （頁面存檔備份，存於網際網路檔案館） Morgan and Claypool Publishers, 2006.

## 外部連結

* Cambridge lock-free group （頁面存檔備份，存於網際網路檔案館）
* Software transactional memory Description; Derrick Coetzee （頁面存檔備份，存於網際網路檔案館）
* Transactional Memory Bibliography （頁面存檔備份，存於網際網路檔案館）
* Introduction to STM by Cyprien NOEL （頁面存檔備份，存於網際網路檔案館） If you like it, there is a more detailed explanation in this free eBook (pdf).