問題タブ [transactional-memory]

バックグラウンド

質問に答えて、私はbounded-tchanを作成してアップロードしました（ jnbのバージョンをアップロードするのは適切ではなかったでしょう）。名前が十分でない場合、bounded-tchan（BTChan）は、最大容量を持つSTMチャネルです（チャネルが容量に達した場合はブロックを書き込みます）。

最近、通常のTChanのようにdup機能を追加するようリクエストがありました。そして、このように問題が始まります。

BTChanの外観

BTChanの簡略化された（実際には機能しない）ビューを以下に示します。

チャネルに書き込むたびnrDupsに、タプルに重複の数（）を含めます。これは、この要素を取得したリーダーの数を示す「個別要素カウンター」です。

すべてのリーダーは、読み取る要素のカウンターをデクリメントしてから、その読み取りポインターをリスト内の次の要素に移動します。リーダーがカウンターをゼロにcountデクリメントすると、チャネルで使用可能な容量を適切に反映するためにの値がデクリメントされます。

必要なセマンティクスを明確にするために：チャネル容量は、チャネルでキューに入れられる要素の最大数を示します。各dupのリーダーが要素を受信するまで、任意の要素がキューに入れられます。GCed dupのキューに入れられたままの要素はありません（これが主な問題です）。

たとえば、容量が2のチャネル（c1、c2、c3）の重複が3つあるとします。ここで、2つのアイテムがチャネルに書き込まれ、次にすべてのアイテムがから読み取られc1ますc2。コピーを消費していないため、チャネルはまだいっぱいです（残りの容量は0） 。c3へのすべての参照c3が削除された場合（c3GCも削除された場合）、いつでも容量を解放する必要があります（この場合は2に復元します）。

ここに問題があります： 私が次のコードを持っているとしましょう

BTChanを次のように見せます：

最後に、の読み取りカウント"hello"がまだ残っていることに注意して1ください。つまり、メッセージは（実際の実装ではGCされますが）なくなったとは見なされず、countデクリメントされることはありません。チャネルは容量（最大1要素）にあるため、ライターは常にブロックします。

dupBTChanが呼び出されるたびにファイナライザーを作成してほしい。複製された（または元の）チャネルが収集されると、そのチャネルで読み取られる残りのすべての要素が要素ごとのカウントをデクリメントし、nrDups変数もデクリメントされます。その結果、将来の書き込みは正しくなりますcount（countGCされたチャネルによって読み取られない変数用のスペースを予約しません）。

解決策1-手動のリソース管理（避けたいこと）

このため、JNBのbounded-tchanには実際には手動のリソース管理があります。を参照してくださいcancelBTChan。私は、ユーザーが間違えるのが難しいことを考えています（多くの場合、手動管理が正しい方法ではないというわけではありません）。

解決策2-TVarでブロックして例外を使用します（GHCはこれを希望どおりに実行できません）

このソリューションを編集すると、単なるスピンオフであるソリューション3は機能しません。バグ5055 （ WONTFIX ）が原因で、GHCコンパイラはブロックされた両方のスレッドに例外を送信します（理論的には決定可能ですが、GHC GCでは実用的ではありません）。

aを取得するすべての方法BTChanがIOである場合forkIO、指定されたに固有の追加の（ダミーの）TVarフィールドで読み取り/再試行するスレッドを作成できますBTChan。nrDups新しいスレッドは、TVarへの他のすべての参照が削除されたときに例外をキャッチするため、および個々の要素カウンターをいつデクリメントするかを認識します。これは機能するはずですが、すべてのユーザーにIOを使用してBTChansを取得するように強制します。

編集：はい、これは貧弱なファイナライザーであり、使用を避ける特別な理由はありませんaddFinalizer。それは同じ解決策であり、それでもIOafaictの使用を強制します。

解決策3：解決策2よりもクリーンなAPIですが、GHCはまだそれをサポートしていません

ユーザーは、を呼び出すことでマネージャースレッドを開始します。これによりinitBTChanCollector、これらのダミーTVarのセット（ソリューション2から）が監視され、必要なクリーンアップが実行されます。unsafePerformIO基本的に、グローバル（ ed）を介して何をすべきかを知っている別のスレッドにIOを押し込みますTVar。基本的にソリューション2と同じように機能しますが、BTChanの作成は引き続きSTMにすることができます。実行に失敗するinitBTChanCollectorと、プロセスの実行中にタスクのリストが増え続けます（スペースリーク）。

BTChan解決策4： sの破棄を許可しない

これは、問題を無視することに似ています。ユーザーがダッピングをドロップしない場合BTChan、問題は解消されます。

解決策 5ezyangの答え（完全に有効でありがたい）がわかりましたが、実際には「dup」関数だけで現在のAPIを維持したいと考えています。

**解決策6**より良いオプションがあることを教えてください。

編集：私はソリューション3（完全にテストされていないアルファリリース）を実装し、グローバル自体をaにすることで潜在的なスペースリークを処理しましたBTChan-そのchanはおそらく1の容量を持つはずなので、実行を忘れるとinitすぐに表示されますが、それは小さな変更です。これはGHCi（7.0.3）で機能しますが、これは偶発的なもののようです。GHCは、ブロックされた両方のスレッド（BTChanを読み取る有効なスレッドと監視スレッド）に例外をスローするため、別のスレッドが参照を破棄したときにBTChanの読み取りがブロックされた場合、あなたは死にます。

常に言及されるソフトウェアトランザクショナルメモリの主な利点の1つは、構成可能性とモジュール性です。さまざまなフラグメントを組み合わせて、より大きなコンポーネントを作成できます。ロックベースのプログラムでは、これは当てはまらないことがよくあります。

これを実際のコードで説明する簡単な例を探しています。Clojureの例をお勧めしますが、Haskellも問題ありません。例が簡単に作成できないロックベースのコードも示している場合のボーナスポイント。

私は 2 つの MVar (MVar と Chan) を持っています。Chan から何かを取り出して、他の MVar が空でなくなるまで処理する必要があります。私の理想的な解決策は、(おそらく空の) MVar とスレッド ブロックのリストを渡す UNIX 関数のようなものselectで、そのうちの 1 つがいっぱいになると、完全な MVar が返されます。false になるまで、isEmptyMVar を使用して各 MVar を繰り返しポーリングする以外に、これを行う方法は考えられません。これは効率が悪いようです。

別の考えでは、throwTo を使用することでしたが、それはスレッドで起こっていることを中断し、Chan からアトミックな方法でジョブの処理を完了する必要があります。

私が入力している最後の考えは、MVar を読み取ろうとする各 MVar に対して新しい forkIO を作成し、新しく作成された MVar を独自のインスタンスで埋めようとすることです。その後、元のスレッドはその MVar でブロックできます。Haskell スレッドはそれほど多く実行できるほど安価ですか?

wikiページを読むと、ロードとストア用のcheckValidateとコミットシステムがあるように見えるので、私は混乱しています。同期の問題を解決することが目的ですか? それは現在のハードウェアの上に構築されたソフトウェア プログラミングですか、それとも ISA を介したハードウェア実装ですか? 各 (HW/SW) 実装の違いは何ですか?

ありがとう。

JAVA で pi-calculus を実装したいと考えています。同時実行のために、Deuce STM ライブラリを使用しています。JAVA 構文を変更するのは難しいので、注釈付き変数と汎用関数/クラスを使用する予定です。

たとえば。

したがって、チャネルはこのクラスのインスタンスになります。

これらのチャネルを介してプロセス間の相互作用を可能にするためにプロセスをモデル化する方法について混乱しています。

ヘルプ/提案はありますか?

ありがとうございました。

'Haswell TSX' (トランザクション メモリ バリア) に関する Anandtech を読んだ後、CLR/JVM がこれらを C#/Java/Scala/F# で高度な並列アプリケーション (C# Rx/TPL/TFD) で利用できるかどうかすぐに疑問に思いました。

JVM STMフレームワークの分析の一環として、オープンソースライブラリのロックメカニズムを再設計して、代わりにSTMを使用することを検討しています。次に、パフォーマンス、コーディングの容易さなどを比較するためにいくつかのテストを実行します。

明らかに、パフォーマンステストはSTMの楽観的ロックを優先する必要がありますが、後でそのセマンティクスを理解することができます。

しかし、今のところ、私はオープンソースライブラリの候補に興味があります。頭に浮かぶのは、内部ロック手段を備えたEhCacheです。

他に適切な候補は何ですか？

私は現在、C++ STL コンテナーを使用してスレッドセーフの問題に頭を悩ませようとしています。最近、メンバー変数として std::mutex を使用してスレッド セーフな std::vector を実装しようとしましたが、ロックをロックすることでメンバー関数をスレッド セーフにすることはできましたが、lib 関数を作成することはできませんでした。 std::sort スレッドセーフのように、begin()/end() イテレータのみを取得するためです。これは、一般的な STL のコンテナとアルゴリズムの間の基本的な分割の結果です。

では、ロックを使用できない場合は、ソフトウェア トランザクショナル メモリ (STM) はどうでしょうか。

だから今、私はこれにこだわっています：

私がコンパイルするもの：

g++ 4.8.2 を使用すると、次のエラーが表示されます。

push_back や sort などは transaction_safe と宣言されていないため、これはちょっとわかりますが、次の質問が残ります。

a) どうすればそのエラーを修正できますか?

b) そのエラーを修正できない場合、これらのトランザクション ブロックは通常何に使用されますか?

c) ロックフリーのスレッドセーフなベクトルをどのように実装しますか?!

前もって感謝します！

編集： これまでの回答に感謝しますが、私のかゆみを実際に掻くことはありません. 例を挙げましょう。グローバル ベクトルがあり、このベクトルへのアクセスが複数のスレッド間で共有されるとします。すべてのスレッドはソートされた挿入を試みるため、乱数を生成し、この番号をソートされた方法でベクトルに挿入しようとするため、ベクトルは常にソートされたままになります (c の複製を含む)。ソートされた挿入を行うには、 std::lower_bound を使用して挿入する「インデックス」を見つけ、次に vector.insert() を使用して挿入を行います。

メンバーとして std::mutex を含む std::vector のラッパーを作成すると、ラッパー関数を作成できます。たとえば、std::lock_guard を使用してミューテックスをロックし、実際の std::vector を実行する insert などです。 insert() 呼び出し。しかし、 std::lower_bound はメンバーミューテックスについて気にしません。これは機能であり、バグではありません。

これにより、誰かが lower_bound を実行している間に他のスレッドがベクトルを変更できるため、私のスレッドはかなり厄介なままになります。

私が考えることができる唯一の修正: ラッパーを忘れて、代わりにベクトルのグローバル ミューテックスを持っています。誰かがこのベクトルに対して/これを使って何かをしたいときはいつでも、そのロックが必要です。

それが問題です。このグローバルミューテックスを使用するための代替手段は何ですか? ソフトウェアトランザクションメモリが頭に浮かんだのはそれです。

それでは、STL コンテナーで STM を使用する方法を教えてください。(および a)、b)、c) 上から)。

Fortran (できれば gFortran) でトランザクション メモリを使用したいと考えています。C 関数でトランザクショナル メモリを使用し、Fortran からこれを呼び出すという回避策があると思いますが、(可能であれば) Fortran で直接実行することをお勧めします。

私が見つけた唯一の関連情報は、Blue Gene の IBM コンパイラーでの実装に関するものでしたが、私は Blue Gene を使用していません。