ソフトウェアトランザクショナルメモリ

計算機科学において、ソフトウェアトランザクショナルメモリ（英: software transactional memory, STM）は、データベーストランザクションに似た並行性制御機構であり、並列計算を行う際の共有メモリへのアクセス法である。この機構はロックベースの同期を用いた並行性制御の代替手段として機能し、ノンブロッキングな方法で実装される物もある。ここでいうトランザクションとは、共有メモリに対する一連の読み出しと書き込みを実行するコードを意味する。論理的にはこれらの読み出しと書き込みは、時間的なある一点で行われ、他のトランザクションからはその間の状態は見えない。トランザクションを行うためにハードウェアにサポートさせるアイデア(ハードウェアトランザクショナルメモリ)は、1986年に Tom Knight により論文と特許として出された。そのアイデアを普及させたのが Maurice Herlihy と J.Eliot B. Moss である。1995年、Nir Shavit と Dan Touitou がこのアイデアをソフトウェアのみで行うトランザクショナルメモリ (STM) に拡張した。STM は近年非常に研究が進み、実用的な実装も進展している。

パフォーマンス

現在のたいていのマルチスレッドアプリケーションでロック技術が使われているのとは異なり、STMは楽観的で、実行中の読み書きを逐一記録し、あるスレッドは他のスレッドが行っていることを考慮せずに、共有メモリに対しての変更を完了する。他の進行中の操作に悪影響を与えない責任を書き込み側に負わせる代わりに、その責任を読み込み側に負わせ、全体のトランザクションが完了した後、読み込み側にアクセス対象のメモリが並行して過去に他のスレッドから変更されていないかを検証させる。この最後の処理、つまりトランザクション中に起きた変更を検証させる処理であるが、この検証により正しいものと確認されたならば、変更は永久なものとして反映される。この処理はコミット (commit) と呼ばれる。また、トランザクションはいつでも中止されることがある（アボートと呼ぶ）。アボートされると、そのトランザクションがそれまでに行った（共有データへの）変更は取り消される（ロールバックされる）。もし、トランザクションが変更が競合したためにコミットできなかったならば、普通トランザクションはアボートされ、成功するまで最初からやり直しする。
この楽観的なアプローチの利点は並列性が向上することである。どのスレッドもリソースにアクセスするために待つ必要がなく、普通は同じロックを使って保護されているひとかたまりのデータ構造に対して、異なるスレッド同士が安全かつ同時にデータ構造内の要素に対してばらばらに変更が可能である。読み出しや変更のたびに複製を作るオーバーヘッドや、トランザクションが失敗した場合にやり直すオーバーヘッドがあるにもかかわらず、たいていの現実にあるプログラムではリソースのコンフリクトはめったに起こらないので、多数のコアを搭載した環境ではロックベースの仕組みで行う以上の良好なパフォーマンスを得られる。
しかし実際には、STM システムも少ないプロセッサ（アプリケーションにもよるが1個から4個）上では細粒度ロックベースのシステムと比較して余分な負荷を受ける。これは主にログ管理に関連するオーバーヘッドとトランザクションを完了する時にかかる時間によるものである。この様な場合でも通常2倍以上遅いわけではないので、STM の概念から得られる利益からするとこのペナルティは正当なものだと、STM 提唱者は考えている。
理論的に（最悪値では）、n個の並列で同時に動作するトランザクションが存在した場合、O(n) のメモリ及びプロセッサ時間を必要とする。実際にはこれらは実装の詳細（オーバーヘッドを避けるのに十分早くトランザクションが失敗するように作られる）によって変化する。しかし、ソフトウェアトランザクショナルメモリよりもロックベースアルゴリズムのほうが理論的に処理時間が短いことがある。

提案されている言語側のサポート

STM は概念的に単純なため、プログラマは比較的単純な文法で STM を使うことができる。Tim Harris と Keir Fraser は論文"Language Support for Lightweight Transactions"で、古典的な「条件つき排他領域」(conditional critical region, CCR) を使ってトランザクションを表現するアイデアを提示した。CCR の最も単純な形式は、「アトミック・ブロック」というものである。これは論理的には"一瞬"に実行されるコードブロックと考えることができる。
 // 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 Transcations" では、retryコマンドを導入してこれをさらに一歩押し進めている。このコマンドは、トランザクションを（その途中の任意の箇所で）アボートし、その時点までにそのトランザクションによってリードされたいずれかの共有データが変更されるまで待ってから再実行（リトライ）するというものである。例えば...
 atomic {
     if (queueSize > 0) {
         remove item from queue and use it
     } else {
         retry
     }
 }
このように、トランザクション中のあとの段階で動的にリトライできるようにすることで、プログラミングモデルが単純になり、また新しい可能性がひらかれる。
課題の一つとして、例外がトランザクションの内から外へ伝播しようとするときにどのように振舞うべきかという点がある。"Composable Memory Transactions" では、筆者らは Concurrent Haskell では例外は予期せぬエラーを示すのが普通であり、この場合はトランザクションをアボートするのがよいと判断した。その際、例外はトランザクションの中で（リードや領域確保により）得られた情報を持ち出せるとした。これは例外の発生理由の診断に役立つ。ただし、著者らは、他の問題設定（例えば他の言語）においては他に妥当な設計判断がありうることを強調している。