Loading article…
コンピュータサイエンスにおいて、ソフトウェア トランザクショナル メモリ( STM ) は、並行コンピューティングにおける共有メモリへのアクセスを制御するためのデータベース トランザクションに類似した並行性制御メカニズムです。これは、ロック ベースの同期の代替手段です。STM は、ハードウェア コンポーネントとしてではなく、ソフトウェアで実装される戦略です。この文脈におけるトランザクションは、コードの一部が共有メモリに対して一連の読み取りと書き込みを実行するときに発生します。これらの読み取りと書き込みは、論理的には単一の瞬間に発生し、中間状態は他の (成功した) トランザクションからは見えません。トランザクションのハードウェア サポートを提供するというアイデアは、1986 年のTom Knightの論文に由来します。[ 1 ]このアイデアは、Maurice HerlihyとJ. Eliot B. Mossによって普及しました。[ 2 ] 1995 年に、Nir Shavitと Dan Touitou はこのアイデアをソフトウェアのみのトランザクショナル メモリ (STM) に拡張しました。[ 3 ] 2005 年以降、STM は集中的な研究の対象となっており[ 4 ]、実用的な実装のサポートが拡大しています。
ほとんどの最新のマルチスレッドアプリケーションで使用されるロック技術とは異なり、STMは多くの場合非常に楽観的です。スレッドは、他のスレッドが何をしているかを気にせずに共有メモリへの変更を完了し、実行したすべての読み取りと書き込みをログに記録します。進行中の他の操作に悪影響を与えないようにする責任を書き込み側に負わせるのではなく、読み取り側に負わせます。読み取り側は、トランザクション全体を完了した後、過去にアクセスしたメモリに対して他のスレッドが同時に変更を加えていないことを確認します。トランザクションの変更が検証され、検証が成功した場合は永続化されるこの最終操作は、コミットと呼ばれます。トランザクションはいつでも中止することもでき、その場合、それまでのすべての変更がロールバックまたは取り消されます。競合する変更のためにトランザクションをコミットできない場合、通常は中止され、成功するまで最初から再実行されます。
この楽観的なアプローチの利点は、並行処理能力の向上です。どのスレッドもリソースへのアクセスを待つ必要がなく、異なるスレッドが、通常であれば同じロックで保護されるデータ構造の互いに独立した部分を安全かつ同時に変更できます。
しかし実際には、STM システムは、少数のプロセッサ (アプリケーションに応じて 1 ～ 4 個) 上で動作するきめ細かいロックベースのシステムと比較して、パフォーマンスが低下します。これは主に、ログの維持に伴うオーバーヘッドとトランザクションのコミットに要する時間によるものです。この場合でも、パフォーマンスは通常 2 倍以上遅くなることはありません。[ 5 ] STM の支持者は、このペナルティは STM の概念的な利点によって正当化されると考えています。
理論的には、n 個の同時トランザクションの最悪ケースの空間および時間計算量はO ( n ) です。実際の要件は実装の詳細に依存します (オーバーヘッドを回避するためにトランザクションを十分に早く失敗させることができます) が、まれではありますが、ロックベースのアルゴリズムがソフトウェアのトランザクションメモリよりも優れた時間計算量を持つ場合もあります。
STMはパフォーマンス上の利点に加えて、マルチスレッドプログラムの概念的な理解を大幅に簡素化し、オブジェクトやモジュールなどの既存の高レベル抽象化と調和して動作することで、プログラムの保守性を向上させます。ロックベースのプログラミングには、実際によく発生するいくつかの既知の問題があります。
対照的に、メモリ・トランザクションの概念ははるかに単純です。なぜなら、各トランザクションは独立したシングルスレッドの計算として捉えることができるからです。デッドロックとライブロックは完全に防止されるか、外部トランザクションマネージャによって処理されるため、プログラマはほとんど気にする必要がありません。優先順位の逆転は依然として問題となる可能性がありますが、高優先度トランザクションは、まだコミットされていない競合する低優先度トランザクションを中止することができます。
しかし、トランザクションの再試行と中止の必要性により、その動作は制限されます。トランザクション内で実行される操作は、トランザクションが再試行される可能性があるため、冪等でなければなりません。さらに、操作にトランザクションが中止された場合に元に戻す必要のある副作用がある場合は、対応するロールバック操作を含める必要があります。これにより、トランザクション内で多くの入出力（I/O）操作を実行することが困難または不可能になります。このような制限は、実際には通常、不可逆操作をキューに入れてトランザクションが成功した後に実行するバッファを作成することで克服されます。Haskell では、この制限はコンパイル時に型システムによって強制されます。
2005年、ティム・ハリス、サイモン・マーロウ、サイモン・ペイトン・ジョーンズ、モーリス・ハーリヒーは、Concurrent Haskell上に構築されたSTMシステムについて説明しました。このシステムは、任意のアトミック操作をより大きなアトミック操作に合成することを可能にするもので、ロックベースのプログラミングでは不可能な有用な概念です。著者らの言葉を引用すると次のようになります。
おそらく最も根本的な反論は、ロックベースのプログラムは合成できないということです。正しい断片でも、組み合わせると失敗する可能性があります。たとえば、スレッドセーフな挿入および削除操作を備えたハッシュテーブルを考えてみましょう。ここで、テーブル t1 から項目 A を 1 つ削除し、テーブル t2 に挿入したいとします。ただし、中間状態 (どちらのテーブルにも項目が含まれていない状態) は他のスレッドから見えてはいけません。ハッシュテーブルの実装者がこの必要性を予見していない限り、この要件を満たす方法はありません。[...] 要するに、個別に正しい操作 (挿入、削除) は、より大きな正しい操作に合成することはできません。 — Tim Harris 他、「Composable Memory Transactions」、セクション 2: 背景、pg.2 [ 6 ]
STMでは、この問題は簡単に解決できます。2つの操作をトランザクションでラップするだけで、結合された操作がアトミックになります。唯一の難点は、コンポーネントメソッドの実装の詳細を知らない呼び出し元にとって、トランザクションが失敗した場合にいつ再実行を試みるべきかが不明確であることです。これに対し、著者らは、失敗したトランザクションによって生成されたトランザクションログretryを使用して、どのメモリセルを読み取ったかを判断し、これらのセルのいずれかが変更されたときにトランザクションを自動的に再試行するコマンドを提案しました。これは、少なくとも1つの値が変更されるまでトランザクションの動作が変わらないというロジックに基づいています。
著者らはまた、代替案orElseを構成するためのメカニズムである関数を提案した。この関数は、1 つのトランザクションを実行し、そのトランザクションが再試行を行う場合は、2 番目のトランザクションを実行する。両方のトランザクションが再試行を行う場合は、関連する変更が行われるとすぐに、両方のトランザクションを再度試行する。この機能は、ポータブルオペレーティングシステムインターフェース ( POSIX ) ネットワーク呼び出しなどの機能に匹敵し、呼び出し元が複数のイベントのいずれかを同時に待機することを可能にする。また、ブロッキング操作とノンブロッキング操作間の変換を簡単に行えるメカニズムを提供することで、プログラミングインターフェースを簡素化する。select()
この仕組みはグラスゴーHaskellコンパイラに実装されています。
STMの概念的な単純さにより、比較的単純な言語構文を用いてプログラマーにSTMを提示することが可能になります。ティム・ハリスとキア・フレイザーの「軽量トランザクションのための言語サポート」では、トランザクションを表現するために古典的な条件付きクリティカル領域（CCR）を使用するというアイデアが提案されました。最も単純な形式では、これは単に「アトミックブロック」、つまり論理的に単一の瞬間に発生するコードブロックです。
// 二重リンクリストにノードを挿入する 原子的にアトミック{ newNode->prev = node; newNode->next = node->next; node->next->prev = newNode; node->next = newNode; }ブロックの末尾に達すると、可能であればトランザクションがコミットされ、そうでなければ中止されて再試行されます。（これは概念的な例であり、正しいコードではありません。例えば、トランザクション中にノードがリストから削除された場合、正しく動作しません。）
CCRではガード条件も許可されており、これによりトランザクションは実行すべき作業が発生するまで待機することができます。
atomic (queueSize > 0) { キューからアイテムを削除して使用します }条件が満たされない場合、トランザクションマネージャは、条件に影響を与えるコミットが別のトランザクションによって行われるまで待機してから再試行します。プロデューサーとコンシューマー間のこの疎結合は、スレッド間の明示的なシグナリングと比較してモジュール性を向上させます。「Composable Memory Transactions」[ 6 ]は、再試行コマンド（上記で説明）によってこれをさらに一歩進め、いつでもトランザクションを中止し、トランザクションによって以前に読み取られた値が変更されるまで待機してから再試行することができます。例：
原子{ if (queueSize > 0) { キューからアイテムを削除して使用します } それ以外 { リトライ } }トランザクションの後半で動的に再試行できるこの機能は、プログラミングモデルを簡素化し、新たな可能性を切り開きます。
1つの問題は、例外がトランザクションの外に伝播する場合の挙動です。「Composable Memory Transactions」[ 6 ]では、Concurrent Haskellでは通常、例外は予期しないエラーを示すため、トランザクションを中止すべきであると著者らは決定しましたが、例外は診断目的でトランザクション中に割り当てられた情報や読み取られた情報を保持できるとしています。著者らは、他の設定では別の設計上の決定が妥当である場合もあることを強調しています。
STMはロックフリーアルゴリズムとして実装することも、ロックを使用することもできます。[ 7 ]ロック方式には2種類あります。遭遇時ロック（Ennals、Saha、Harris）では、メモリ書き込みは、まず特定の場所のロックを一時的に取得し、値を直接書き込み、それをアンドゥログに記録することによって行われます。コミット時ロックは、コミットフェーズの間だけメモリ位置をロックします。
Dice、Shalev、およびShavitによって実装された「Transactional Locking II」と呼ばれるコミット時方式は、グローバルバージョンクロックを使用します。すべてのトランザクションは、クロックの現在の値を読み取り、それを読み取りバージョンとして保存することから始まります。次に、読み取りまたは書き込みのたびに、特定のメモリ位置のバージョンが読み取りバージョンと比較され、バージョンが大きい場合はトランザクションが中止されます。これにより、コードが一貫性のあるメモリのスナップショット上で実行されることが保証されます。コミット時には、すべての書き込み位置がロックされ、すべての読み取りおよび書き込み位置のバージョン番号が再チェックされます。最後に、グローバルバージョンクロックがインクリメントされ、ログからの新しい書き込み値がメモリに書き戻され、新しいクロックバージョンが刻印されます。
楽観的読み取りによるソフトウェア・トランザクショナル・メモリの実装における問題点の1つは、不完全なトランザクションが矛盾した状態（つまり、別のトランザクションによって書き込まれた古い値と新しい値が混在した状態）を読み取る可能性があることです。このようなトランザクションはコミットしようとすると必ずアボートされるため、トランザクション・システムによって強制される一貫性条件に違反することはありませんが、この「一時的な」矛盾した状態によって、トランザクションがセグメンテーション違反などの致命的な例外状態を引き起こしたり、無限ループに陥ったりする可能性があります。これは、「軽量トランザクションのための言語サポート」の図4にある以下の人工的な例で示されています。
初期状態でx = yであれば、上記のどちらのトランザクションもこの不変条件を変更しませんが、トランザクション A がトランザクション B の更新後にxを読み取り、トランザクション B の更新前にy を読み取ると、無限ループに陥る可能性があります。これに対処する一般的な戦略は、致命的な例外をインターセプトし、無効なトランザクションを中止することです。
これらの問題に対処する一つの方法は、不正な操作を実行したり、終了に失敗したトランザクションを検出し、それらを正常に中止することです。もう一つのアプローチは、トランザクションロック方式です。
{{cite web}}引用には一般的なタイトルを使用します（ヘルプ）