問題タブ [lock-free]

Haskellでロックフリープログラミングを行うことが可能かどうか誰かが知っていますか？適切な低レベルのプリミティブが利用可能かどうかの問題と、（利用可能な場合）純粋な機能コンテキストで機能する大規模システムを構築するためにこれらを使用することに関して機能する情報についての両方に興味があります。（私はこれまで純粋関数のコンテキストでロックフリープログラミングを行ったことがありません。）たとえば、私が理解しているように、Control.Concurrent.Chanチャネルは（私が理解しているように）ロックを使用するMVarの上に構築されています-- -原則として、内部でロックされていないバージョンのChanプリミティブをビルドできますか？どのくらいのパフォーマンスの向上を期待できますか？

また、私はTVarの存在に精通しているが、それらの内部実装を理解していないと言うべきです---ほとんどロックフリーであることを理解するように言われましたが、それらがそうであるかどうかはわかりません完全にロックフリー。したがって、TVarの内部実装に関する情報も役立ちます。

（このスレッドはいくつかの議論を提供しますが、もっと最新の/より包括的なものがあるかどうか疑問に思います。）

ロックフリーキューの使用について質問があります。

プロデューサーとコンシューマーが別々のコアにバインドされている、単一プロデューサー、単一コンシューマーのキューがあるとします。キュー要素は共有メモリのバッファであり、最初にプロデューサとコンシューマの両方によって mmap されます。

プロデューサはキュー要素を取得し、バッファにデータを入力してキューに入れ、コンシューマは要素をデキューし、それを読み取り、何らかの方法で処理します。

ロックフリー キューのユーザーとして、プロデューサーによって書き込まれたバッファーがユーザーに表示されることを明示的に確認する必要がありますか? それとも、アルゴリズムの中心にある CAS (または他の同様の) プリミティブが自動的にバリアを提供しますか?

私が見たいくつかの例では、整数をペイロードとして使用しているため、このメモリ同期の問題は発生しません。

ありがとう、

スタックのロックフリーの実装をいくつか見てきました...私の質問は、原子性ではなく可視性に関するものです。たとえば、ロック フリー スタックの要素 (ポインターではない) は最大 64 ビットである必要がありますか? 可視性を保証できないため、そう思います。実際の例: この構造体を安全に挿入し、ロックのないコンテナーから削除できますか

編集：一部の人々は質問に混乱しています。少し説明すると、ライターが人物をスタックにプッシュすると、リーダーはそれを取得します。リーダーが（メモリの可視性）人物の正しいコンテンツを見ることが保証されます。

コレクションのコレクションを作成する必要があります。コレクションは複数のスレッドによって呼び出され、アイテムとルックアップ アイテムを追加します。追加されたアイテムは削除されません。現在、要素を追加している間、コレクション全体をロックする必要があります。ロックフリーにする方法はありますか？または、使用できるより良いデータ構造またはパターンはありますか? これが私のコードの簡略版です：

趣味でマルチスレッド コードを書いていると、次のような状況に陥りました。

スレッドは、メモリ プールから単一のリソース ユニットを要求し、それを処理して、このデータへのポインターを別のスレッドに送信し、循環バッファーを使用してさらに操作を行います (1R / 1W の場合)。

後者は、受信したデータの処理が完了するたびに前者のスレッドに通知する必要があるため、メモリを再利用できます。

この「フリーリスト」を別の循環バッファーとして実装し、空きリソースのアドレスを保持するか、ロックフリースタックの方法 (x86-64 で DCAS を実装する) を選択する方がパフォーマンス的に優れているかどうか疑問に思います。

一般的に言えば、2 つの異なるアプローチの長所と短所は何でしょうか?

私は次の場所でロックフリーキューのサンプルコードを見ていました。

http://drdobbs.com/high-performance-computing/210604448?pgno=2

（ C ++での本番環境対応のロックフリーキューやハッシュ実装はありますかなど、多くのSOの質問でも参照してください）

コードには多くのタイプミスがありますが、これは単一のプロデューサー/コンシューマーで機能するはずです。以下に示すようにコードを更新して読み取りましたが、クラッシュします。誰かがなぜ提案がありますか？

特に、分割して最後に次のように宣言する必要があります。

このマシンにはC++0xをサポートするコンパイラがないので、必要なのはそれだけかもしれません...

これをテストするために、次のコードを作成しました。Main（表示されていません）はTestQ（）を呼び出すだけです。

更新：クラッシュはキュー宣言によって引き起こされていることになります：

これを単純な配列に変更すると、正常に実行されます。（ロック付きのバージョンを実装しましたが、それもクラッシュしていました。）コンストラクタの直後にデストラクタが呼び出され、メモリが二重に解放されていることがわかります。しかし、デストラクタがstd :: vectorですぐに呼び出される理由を誰かが知っていますか？

ロックフリーのデータ構造を開発すると、次の問題が発生します。

ヒープ上にオブジェクトを作成し、それらを参照カウンター付きのスマート ポインターにラップするライター スレッドがあります。また、これらのオブジェクトを操作するリーダー スレッドも多数あります。コードは次のようになります。

スレッドローカルコピーを作成ptrすると、少なくとも

1. アドレスを読み取ります。
2. 参照カウンターをインクリメントします。

これら 2 つの操作をアトミックに実行できないため、リーダーが削除されたオブジェクトを操作することがあります。

問題は、正しいメモリ管理を可能にして複数のスレッドから読み取り/書き込みアクセスを可能にするために、どのような種類のスマート ポインターを使用する必要があるかということです。Java プログラマーはそのような問題を気にすることさえなく、すべてのオブジェクトが参照であり、誰もそれらを使用しない場合にのみ削除されることに単純に依存しているため、解決策が存在するはずです。

PowerPC についてはhttp://drdobbs.com/184401888を見つけました。見栄えは良いのですが、x86 にはない Load-Linked 命令と Store-Conditional 命令を使用しています。

私が理解している限り、ブースト ポインターは、ロックを使用してのみそのような機能を提供します。ロックフリーのソリューションが必要です。

共有メモリを使用して、複数のプロセス間で一部のデータを共有しています。プロセス間ミューテックスを使用して同期を実現します。

私の質問は次のとおりです。2 つのプロセス間でミューテックスを使用せずに、ロックフリーのデータ構造 AND/OR アトミック操作を使用してより高速な同期を実現することは可能ですか?

そうでない場合、これの主な理由は何ですか？

これらは、同じプロセスのスレッドを同期するためにのみ使用されます。これらの概念はプロセスにも移植できますか? そうでない場合、プロセス間でデータを共有/同期するためのより高速な方法を知っていますか?

私がロックフリープログラミングで集めたものから、正しく行うのは信じられないほど難しいです...そして私は同意します。いくつかの問題について考えるだけで頭が痛くなります。しかし、私が疑問に思うのは、なぜ高レベルのラッパーが広く使用されていないのですか（たとえば、ロックフリーキューなど）？たとえば、私が知る限り、ブーストにはロックフリーライブラリがありません。クリティカルセクションが負荷の大部分を占めるという事実を避けられないアプリケーションがたくさんあると思います。それで、理由は何ですか？それは...ですか...

1. 特許-ロックフリープログラミングに関連するいくつかのものが特許を取得していると聞きました。
2. パフォーマンス。
3. グーグルとマイクロソフトはそのような内部ライブラリを持っていますが、それらのどれも公開されていません...
4. 他に何かありますか？

だから私の質問は：なぜ「通常の」マルチスレッドプログラミングが「イン」であるのに、ロックフリープログラミングを深く使用する高レベルの抽象化があまり人気がないのですか？

編集：ブーストはロックフリーライブラリを取得しました:)