計算機科学において、ソフトウェアトランザクショナルメモリ（, 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 は概念的には非常に単純でマルチスレッドプログラムを理解しやすくするので、オブジェクトやモジュールのような高レベルな抽象化を進めることができ、プログラムをよりメンテナンスしやすくできる。ロックベースのプログラミングは実際にはしばしば非常に良く知られた問題にぶつかる。対照的にメモリトランザクションの考えは大変シンプルである。なぜなら、それぞれのトランザクションはあたかもシングルスレッドで動作しているかのように見えるからである。デッドロックやライブロックはまったく起きないか外部のトランザクションマネージャーによって制御されるので、プログラマはそのような問題について頭を悩ませる必要はまったくない。優先度逆転については課題として残るが、優先度が高いトランザクションはまだトランザクションが完了していない低い優先度のトランザクションとぶつかって処理が中断することはない。他方、トランザクションの振る舞いにおいて、失敗したトランザクションを中止するのにも制限を設けたいこともある。たいていのI/O処理を含む、トランザクションがロールバックできない操作である。このような制限は普通実際にはバッファを作ることでやりくりする。このバッファによって、取り消せない操作をキューに入れたり、それらを他のトランザクションとは別にあとで実行したりする。2005年に、Tim Harris、Simon Marlow、Simon Peyton Jones そして Maurice Herlihy によって STM が Concurrent Haskell 上に構築された。これは任意のアトミックな操作をより大きなアトミックな操作に合成することができる。この役に立つ考えはロックベースプログラミングでは不可能である。以下に筆者の言葉を引用する。STM においては、この問題は単純に解決できる。あるトランザクション中における2つの操作を単にラップしてアトミックな操作としてくっつけてしまえばよいのである。唯一の突っ込み所としてはこの処理を呼び出す側からははっきりしないことがある所である。つまり、コンポーネントが提供する方法の実装の詳細や、もし操作が失敗した場合に、そのトランザクションが再実行を試みるタイミングである。それに対して、筆者は retry コマンドを提案している。これは、トランザクションが失敗したときに生成されるトランザクションログを使って、どのメモリセルが読み出されたかを決定するものである。そして、これらのメモリセルのうちの一つが変更された時に自動的にトランザクションをリトライする。これは、少なくともある一つの値が変化するまでは、トランザクションの振る舞いは変わらないだろうという考えに拠っている。筆者はまた、操作を合成するための代替手段を提案している。これは orElse というキーワードである。これは一つのトランザクションが走っていて、そのトランザクションが "retry" するならば、もう一方が実行されるというものである。もし両方リトライするならば、関連する変更がなされたらすぐに両方ともリトライしようとする。この機能は、POSIXのネットワークで使われる "select()" 呼び出しの特徴と比較される。orElse を使えば、呼び出し側は複数のイベントのうちどれか一つが変化するのを同時に待つことができる。この機能はまたプログラミングインタフェースを単純化できる。例えば、同期操作および非同期操作を相互に変換する機構を単純に作ることができる。STM は概念的に単純なため、プログラマは比較的単純な文法で STM を使うことができる。Tim Harris と Keir Fraser は論文"Language Support for Lightweight Transactions"で、古典的な「条件つき排他領域」("conditional critical region

出典:wikipedia