ソフトウェアトランザクションメモリをどのように実装しますか？

StackOverflow https://stackoverflow.com/questions/1627600

  •  06-07-2019
  •  | 
  •  

質問

実際の低レベルのアトミック命令およびメモリフェンス（使用されていると仮定します）の観点から、STMはどのように実装しますか？

私にとって不思議な部分は、任意のコードチャンクが与えられた場合、後で戻って各ステップで使用された値が有効かどうかを判断する方法が必要なことです。それをどのように行い、どのように効率的に行うのですか？これは、他の「ロック」ソリューションと同様に、（競合の可能性を減らすために）クリティカルセクションをできるだけ小さくしたいことを示唆しているようにも思えます。

また、STMは「計算の実行中にこの領域に入った別のスレッドを検出できるため、計算は無効です」と検出できます。または、上書きされた値が使用されたかどうかを実際に検出できます（したがって、運がよければ、2つのスレッドがロールバックを必要とせずに同じクリティカルセクションを同時に実行することがあります）？

役に立ちましたか？

解決

最も単純な答えは「依存する」です。思いつく限りの方法で機能する根本的に異なる実装がたくさんあります。

  

不思議なのは、任意のコードチャンクが与えられた場合、後で戻って各ステップで使用された値が有効であったかどうかを判断する方法が必要なことです。それをどのように、そしてどのように効率的に行うのですか？

1つの解決策は、バージョニングを使用することです。オブジェクトが変更されるたびに、バージョン番号が更新されます。トランザクションの実行中に、アクセスした各オブジェクトのバージョンを検証し、トランザクションがコミットされると、オブジェクトがまだ有効であることを確認します。 この検証は単純な整数比較（ transaction_start_version＆gt; = object_version の場合、オブジェクトは有効）であるため、かなり効率的に実行できます。

  

これは、他の「ロック」ソリューションと同様に、クリティカルセクションをできるだけ小さく保ちたい（競合の可能性を減らすため）ことを示唆しているように思えますが、正しいですか？

非常に可能性が高い。いくつかの実装がすべてをトランザクションであると想定/要求するルートを行ったと思いますが、はい、ほとんどの実装では、トランザクションは特別にマークされたコードの塊であり、トランザクションの実行時間が長くなるほど、トランザクションのロールバックを引き起こす可能性のある競合の可能性。

  

また、STMは「計算の実行中にこの領域に入った別のスレッドを検出できるため、計算は無効です」と検出できます。または、上書きされた値が使用されたかどうかを実際に検出できます（したがって、運がよければ、2つのスレッドがロールバックを必要とせずに同じクリティカルセクションを同時に実行することがあります）？

後者。 TMの考え方は、コードではなく、データを保護することです。

異なるコードパスは、異なるトランザクションで同じ変数にアクセスできます。これは、TMシステムによって検出される必要があります。 「この領域」の本当の概念はありません。それはデータではなくコードを参照しているからです。 TMシステムは、どのコードが実行されているかを気にしません。どのデータが変更されているかを追跡します。そのように、重要なセクション（データではなくコードを保護する）とはまったく異なります

他のヒント

論文の中には非常に読みにくいものもありますが、非常に明確で簡潔な論文は次の2つです。

トランザクションロックII、Dave Dice、Ori Shalev、Nir Shavit 「TL2」任意の言語の観点からのSTMアルゴリズム。

デュース：Javaの非侵襲的ソフトウェアトランザクションメモリ、Guy Korland、Nir Shavit、Pascal Felber は、通常のJavaクラスを、STMを実行するための追加のバイトコードを持つメモリ内クラスに変換するロード時間クラストランスフォーマーを説明します。この論文は、STMのないコードをどのOO言語でもSTMを実行するコードに機械的に変換する方法を説明しているため、この質問に関連しています。

Deuceフレームワークでは、使用する実際のアルゴリズムをプラグインできます。 TL2アルゴリズムを含む。 DeuceフレームワークはJavaなので、以下の説明ではJavaの用語を使用しますが、OO言語で記述していることを前提としています。

以下でTL2アプローチの概要を説明します。論文には代替アプローチへのリンクがありますが、1つのアルゴリズムを研究すると多くの質問に答えます。

  

STMはどのように実装しますか？私にとって不思議な部分は、任意のコードチャンクが与えられた場合、後で戻って各ステップで使用された値が有効かどうかを判断する方法が必要なことです。

TL2がSTMをどのように行うかについての簡単な答えは、「簿記」です。そして、コミット時にのみ書き込みロックを使用します。詳細については論文を読んでくださいが、ボードブラシの概要は次のとおりです。元のコードで使用できるすべてのプロパティには、ゲッターとセッターがあります。変換されたコードには、プロパティのバージョン番号と、ゲッターとセッターに追加されるコードもあります。トランザクション内で読み取ったすべての属性のバージョンをトランザクション「読み取りセット」として記録する必要があります。これを行うには、すべてのゲッターに、スレッドローカルリンクリストに表示される属性のバージョンを追加させます。また、書き込みを＆quot; write-set＆quot;としてバッファリングする必要があります。コミットするまでスレッドローカルで。 getterメソッドは、指定されたフィールドがある場合、そのフィールドのthreadlocal書き込みセット値をチェックして返す必要があることに注意してください。このようにすると、コミットされていない書き込みが読み取りに表示されますが、コミットするまで他のスレッドはそれらを表示しません。

コミット時に、書き込もうとしているすべての属性に対して書き込みロックを取得します。ロックを取得している間、読み取りセットがまだ有効であることを再確認します。トランザクションで読み取った属性が、別のトランザクションによって上位バージョンに更新されていないこと。その場合、一貫性のない読み取りが発生する可能性があるため、ビジネスロジックが有効ではない可能性があるため、トランザクション全体をロールバックする必要があります。最終チェックに合格したら、書き込みセットをフラッシュしてコミットし、それらの属性のバージョンをバンプし、書き込みロックを解除し、書き込みセットと読み取りセットの両方のスレッドローカルリストをクリアします。

この論文は、txが開始されてから読み取られている属性が書き込まれたことを検出すると、アルゴリズムが早期に中断する可能性があると説明しています。このペーパーには、読み取り専用トランザクションを高速化する巧妙なトリックがいくつかあります。どのブロックが読み取り専用で、どのブロックが読み書き可能であるかを判断するためのトリックもあります。そのようなことに興味を持っている人は、本当に2つの論文を楽しむべきです。

上記の論文のDeuceフレームワークは、ロード時にクラスに新しいJavaバイトコードを挿入することにより、すべてのgetterおよびsetterを変更する方法を示しています。他の言語では、通常のコードからSTM対応コードへの同じ機械的変換を実行する特別なコンパイラまたはプリプロセッサを使用できます。具体的には、Deuceを使用すると、ソースコードオブジェクトは単純なゲッターセッターペアを持つことができますが、実行時に変換されたクラスには、bookwoを実行する豊富なゲッターセッターがあります

GHC のSTM実装については、次のセクション6で説明しています。

構成可能なメモリトランザクション。ティム・ハリス、サイモン・マーロー、サイモン・ペイトン・ジョーンズ、モーリス・ハーリーPPoPP'05：ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming、イリノイ州シカゴ、2005年6月

およびセクション5：

トランザクションメモリデータ不変。ティム・ハリス、サイモン・ペイトン・ジョーンズ。 2006年3月TRANSACT '06

このプレゼンテーションをご覧になることをお勧めします。 http：// www infoq.com/presentations/Value-Identity-State-Rich-Hickey

後半では、値を未定義の状態のままにせずに値を更新する方法について説明します。たとえば、STMスタイルで更新するツリーがある場合、以前のバージョンをまったく変更しません。 tree がツリーのルートへのポインターであるとしましょう。作成するのは、変更されたノードのみです（ただし、ツリーの元のスナップショットのノードを参照できます。

次に、 tree ポインターで比較とスワップを行います。成功した場合、誰もが新しいツリーを見ることができ、古いツリーはガベージコレクションできます。そうでない場合は、プロセスを繰り返し、構築したばかりのツリーがガベージコレクションされます。

大きなアイデアは、新しい値と古い値を実際に交換するまで、他の誰かが tree を変更したかどうかを検出する必要がないため、「競合」が発生しないことです。または「上書きされた値」典型的なマルチスレッドプログラミングから。

.NETフレームワークを使用している場合、

この試験運用版をご覧ください

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top