実際の低レベルのアトミック命令とメモリ フェンス (使用されていると思います) に関して、STM をどのように実装しますか?
私にとって不可解な部分は、コードの任意のチャンクが与えられた場合、後で戻って各ステップで使用された値が有効かどうかを判断する方法が必要だということです。それをどのように行い、どのように効率的に行うのですか? これは、他の「ロック」ソリューションと同様に、(競合の可能性を減らすために) クリティカル セクションをできるだけ小さくしたいことを示唆しているようにも思えますが、そうですか?
また、STM は「計算の実行中に別のスレッドがこの領域に入ったため、計算は無効です」を単純に検出できますか、それとも破壊された値が使用されたかどうかを実際に検出できますか (したがって、運が良ければ、2 つのスレッドが同じクリティカル セクションを実行せずに同時に実行される場合があります)。ロールバックの必要性)？
一部の論文は非常に読みにくい場合がありますが、非常に明確で簡潔な論文は次の 2 つです。
Transactional Locking II、Dave Dice、Ori Shalev、Nir Shavitで、「TL2」STM アルゴリズムを任意の言語で説明しています。
Deuce: 非侵襲的ソフトウェア トランザクション メモリ in Java、Guy Korland、Nir Shavit、Pascal Felberでは、通常の Java クラスを、STM を実行するための追加のバイトコードを持つメモリ内クラスに変換するロード時間クラス トランスフォーマーについて説明しています。この論文では、STM のないコードを任意の OO 言語で STM を実行するコードに機械的に変換する方法が説明されているため、これは質問に関連しています。
Deuce フレームワークでは、使用したい実際のアルゴリズムをプラグインできます。TL2アルゴリズムを含みます。Deuce フレームワークは Java であるため、以下の説明では Java 用語を使用しますが、OO 言語で記述していることを前提としています。
以下に、TL2 アプローチの概要を示します。論文には代替アプローチへのリンクがありますが、1 つのアルゴリズムを研究することで多くの疑問が解決されます。
どのように STM を実装しますか? 私にとって不可解な部分は、コードの任意のチャンクが与えられた場合、後で戻って各ステップで使用された値が有効かどうかを判断する方法が必要だということです。
TL2 が STM をどのように行うかについての簡単な答えの 1 つは、「簿記」であり、コミット時にのみ書き込みロックを使用することです。細かいところは紙を読んでくださいが、ボードブラシの概要は次のとおりです。元のコードで使用できるすべてのプロパティには、ゲッターとセッターがあります。変換されたコードには、プロパティのバージョン番号と、ゲッターとセッターに追加された追加コードもあります。トランザクション内で読み取ったすべての属性のバージョンを、トランザクションの「読み取りセット」として記録する必要があります。これを行うには、すべての getter に、見られる属性のバージョンをスレッドローカル リンクリストに追加させます。また、コミットするまで、書き込みをスレッドローカルの「書き込みセット」としてバッファリングする必要があります。getter メソッドは、指定されたフィールドのスレッドローカル書き込みセット値をチェックして返す必要があることに注意してください。
コミット時に、書き込もうとしているすべての属性に対して書き込みロックを取得します。ロックを取得している間、読み取りセットがまだ有効であることを再確認します。トランザクションで読み取った属性が、別のトランザクションによってより高いバージョンに更新されていないこと。その場合、一貫性のない読み取りが発生する可能性があるため、ビジネスロジックが有効ではない可能性があるため、トランザクション全体をロールバックする必要があります。最終チェックに合格したら、書き込みセットをフラッシュしてコミットし、それらの属性のバージョンを増やし、書き込みロックを解放し、最後に書き込みセットと読み取りセットの両方のスレッドローカル リストをクリアします。
この論文では、送信が開始されてから読み取られている属性が書き込まれたことを検出した場合、アルゴリズムが早期に中止される可能性があると説明しています。この論文には、読み取り専用トランザクションを高速化するための巧妙なトリックがいくつかあります。どのブロックが読み取り専用で、どのブロックが読み書き可能かを判断するトリックさえあります。このようなことに関心を示している人は、この 2 つの論文を本当に楽しむべきです。
上記の論文の Deuce フレームワークは、ロード時にクラスに新しい Java バイトコードを挿入することによって、すべてのゲッターとセッターを変更する方法を示しています。他の言語には、通常のコードから STM 対応コードへの同じ機械的変換を実行する特別なコンパイラまたはプリプロセッサがある場合があります。特に Deuce を使用すると、ソース コード オブジェクトは単純なゲッター セッターのペアを持つことができますが、実行時に変換されたクラスには、ブックワークを行う強化されたゲッター セッターがあります。
通常のコードを (特に実行時に) STM コードに変換することは興味深いことですが、STM 対応のデータ構造を実際に作成する必要がある場合は、魔法のソースは必要ありません。代わりに、 aと aを使用してRefクラスを作成し、ハンドルで構成されるデータ構造オブジェクト間のすべての関係を作成します。あなたのクラスの中で、スレッドローカルブックワークを行うことができます。次に、単純なバージョンの「TL2」またはデータ構造と読み取りと書き込みの同時実行性に適した他のアルゴリズムを実装できます。 get()set(x)RefgetsetRef
これは、他の「ロック」ソリューションと同様に、(競合の可能性を減らすために) クリティカル セクションをできるだけ小さくしておくことを示唆しているようにも思えますが、そうですか?
TL2 には、書き込みロックを保持してから最終チェックと書き込みを行う重要な期間があります。これは、アプリケーションのビジネス ロジックを理解していなくても、簡単に理解して最適化できます。各番号に一意のプロパティを割り当てると、ロックを昇順で取得することでデッドロックを自明に回避できます。すべてのビジネス ロジックは、コミット チェックに合格することを前提として投機的に実行されることに注意してください。任意の遅いビジネス ロジックを実行している間は、ロックを保持しません。複数の Web サービス ルックアップや遅いデータベース呼び出しを行うことができ、コミットまでロックを取得しません。明らかに、専門家は一般的なクリティカル セクションから完全に調整しようとしています。
この論文は、特定のビジネス ロジックが必要とするよりも頻繁にアルゴリズムが中止される可能性があることを明らかにしています。一般的なアルゴリズムでは、特定のダーティ リードが実際の書き込み結果に影響しないかどうかはわかりません。実際のビジネス ロジックを理解する手書きのロジックは、特定の一連のダーティ リードに対してロールバックが必要ない特殊なケースを認識できます。ただし、記述するコードが多く、ロールバックの可能性が非常に低いアプリケーションがある場合は、一般的な機械的 STM アプローチがバグの減少につながり、パフォーマンスが向上する可能性があります。
また、STM は「計算の実行中に別のスレッドがこの領域に入ったため、計算は無効です」を単純に検出できますか、それとも、破壊された値が使用されたかどうかを実際に検出できますか (したがって、運が良ければ、2 つのスレッドが同じクリティカル セクションを実行せずに同時に実行される場合があります)。ロールバックの必要性)？
TL2アプローチは、それを行うコードではなく、読み書きされるデータに関するすべてのものです。それはあなたが取得して設定するものであり、重要です。そして、すべての書き込みをフラッシュする前に、他のスレッドがつま先を踏んだかどうか。コードに必要なのはbegin()、commit()ビジネスrollback()ロジック内にトランザクションを開始、終了、中止するための , があることだけです。それでもコードを生成できます。Java では、メソッドに @Transactional アノテーションを付けてメソッドをマークし、慣用的な Java として begin/commit/rollback を実行する try/catch/finally でメソッド呼び出しをラップするコードを生成できます。Deuce は、クラスのロード時にそのようなロジックを挿入します。
繰り返しますが、独自の STM 対応データ構造で開始/コミット/ロールバックするために、そのような魔法のソースは必要ありません。明示的にデータ構造のロジック コードにすべてを組み込むことで、任意の OO 言語で明示的に STM 対応の独自のクラスを作成できます。
最も簡単な答えは「状況によって異なります」です。想像できるほとんどすべての方法で機能する根本的に異なる実装がたくさんあります。
私にとって不思議なのは、コードの任意のチャンクが与えられた場合、後で戻って、各ステップで使用された値が有効かどうかを判断する方法が必要なことです。それをどのように行い、どのように効率的に行いますか？
1つの解決策は、バージョン管理を使用することです。オブジェクトが変更されるたびに、そのバージョン番号が更新されます。トランザクションの実行中に、アクセスされた各オブジェクトのバージョンを検証し、トランザクションがコミットされたときに、オブジェクトがまだ有効であることを確認します。この検証は単純な整数比較（transaction_start_version >= object_versionオブジェクトが有効な場合）である可能性があるため、かなり効率的に実行できます。
これは、他の「ロック」ソリューションと同様に、クリティカルセクションをできるだけ小さくしたい（競合の可能性を減らすため）ことを示唆しているように思われますが、私は正しいですか？
可能性が非常に高い。いくつかの実装は、すべてをトランザクションと見なす/要求するルートをたどったと思いますが、はい、ほとんどの実装では、トランザクションは特別にマークされたコードのチャンクであり、トランザクションが長く実行されるほど、競合が発生する可能性が高くなりますトランザクションをロールバックさせます。
また、STMは、「計算の実行中に別のスレッドがこの領域に入ったため、計算が無効である」ことを単純に検出できますか、または実際に不正な値が使用されたかどうかを検出できます（したがって、運が良ければ、2つのスレッドが同じクリティカルセクションを同時に実行することがあります。ロールバックの必要性）？
後者。TMの考え方は、コードではなくデータを保護することであることに注意してください。
異なるコードパスは、異なるトランザクションで同じ変数にアクセスする可能性があります。これは、TMシステムによって検出される必要があります。「この領域」の実際の概念はありません。これは、データではなくコードを参照しているためです。TMシステムは、実行中のコードを気にせず、変更されているデータを追跡します。このように、クリティカルセクション（データではなくコードを保護する）とは完全に異なります。
GHCの STM 実装は、次のセクション 6 で説明されています。
コンポーザブル メモリ トランザクション。ティム・ハリス、サイモン・マーロウ、サイモン・ペイトン・ジョーンズ、モーリス・ハーリー。PPoPP'05: 並列プログラミングの原則と実践に関する ACM SIGPLAN シンポジウム、イリノイ州シカゴ、2005 年 6 月
そしてセクション5：
データ不変条件によるトランザクション メモリ。ティム・ハリス、サイモン・ペイトン・ジョーンズ。2006年3月 TRANSACT '06
このプレゼンテーションを見ることをお勧めします: http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey
後半では、値を未定義のままにせずに更新する方法を説明します。たとえば、STM スタイルで更新したいツリーがある場合、以前のバージョンはまったく変更しません。treeそれがツリーのルートへのポインタだとしましょう。作成するのは変更されたノードのみです (ただし、ツリーの元のスナップショット内のノードを参照できます。
tree次に、ポインターで比較と交換を行います。成功した場合は、新しいツリーが全員に表示され、古いツリーをガベージ コレクションできます。そうでない場合は、プロセスを繰り返して、構築したばかりのツリーがガベージ コレクションされます。
大きなアイデアは、新しい値と古い値を実際に交換するまで、他の誰かが を変更したかどうかを検出する必要がないtreeため、典型的なマルチスレッド プログラミングからの「競合」や「破壊された値」がないということです。
.NET フレームワークを使用する場合は、
あなたはこの実験をチェックすることができます