跳至內容

軟件事務主記憶體

本頁使用了標題或全文手工轉換
維基百科，自由的百科全書

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

效能

[編輯]

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

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

不過，在一些實踐中，在較少CPU（1-4）的系統上，基於STM的應用程式相對於一些精心調節的基於Lock的應用程式而言，會有一定的效能損失。主要的原因是在STM事務中，需要維持log，以及額外的花在提交事務上的時間。不過，即使在這種情況下，效能也不會低於50%。 [1]相對而言，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使用了一個全域版本時鐘，每個事務開始時讀到當前的版本號，並且將其作為讀的版本號。然後，在每次讀寫訪問時，訪問主記憶體的版本號會和讀版本號比較，如果主記憶體的版本號更大的話，表示這個主記憶體已經被其他事務修改過，當前事務將失敗。這就可以保證當前事務執行的所有代碼都工作在一個獨立的主記憶體瞬間映像之上。在提交時，所有的寫地址都將鎖住，所有讀寫地址的版本號會重新檢查。最後，全部版本號增加，所有新寫入的主記憶體將從紀錄檔中重新寫入到主記憶體中，並且更新其新的版本號。

參考資料

[編輯]
  1. ^ Simon Peyton-Jones. Programming in the Age of Concurrency: Software Transactional Memory. Channel 9. [2007-06-09]. （原始內容存檔於2012-09-02）. 

外部連結

[編輯]
取自 "https://zh.wikipedia.org/w/index.php?title=软件事务内存&oldid=85093975"