問題タブ [lock-free]

Intel x86 ベースのプラットフォーム (特に、Intel コンパイラを使用して MacOSX 10.4 を実行している Intel ベースの Mac) で C でプログラミングする場合、64 ビット書き込みがアトミックであることが保証されるのはいつですか? 例えば：

y への最初の代入の実行が終了した後に別のスレッドが y の値を調べている場合、値 0xfedcba87654321 または値 0x12345678abcdef のいずれかが表示され、それらの混合ではないようにしたいと考えています。ロックせずに、可能であれば余分なコードなしでこれを行いたいと思います。私の希望は、64 ビット コードをサポートできるオペレーティング システム (MacOSX 10.4) で 64 ビット コンパイラ (64 ビット Intel コンパイラ) を使用する場合、これらの 64 ビット書き込みがアトミックになることです。これは常に真実ですか？

私のマルチスレッド アプリケーションでは、ロックの競合が激しく、複数のコアにまたがる優れたスケーラビリティが妨げられています。これを解決するために、ロックフリープログラミングを使用することにしました。

ロックのない構造を書くにはどうすればよいですか?

.netを初めて使用しますが、.netにAtomicInteger、ConcurrentLinkedQueueなどのJava版があるかどうかを知りたいですか？

私は少し検索をしましたが、何も思いつきませんでした。

ロックフリーアルゴリズムには、Javaの文書化されていないUnsafeクラスを通じて提供される、ある種のCAS命令が必要ですが、.netには同等のものがありますか？

こんにちは、ロックレスリストを書き込もうとしています。追加部分が機能していると思いますが、リストからオブジェクトを抽出するコードがうまく機能しません:(

リストは通常​​のリストではありません..私はインターフェースIWorkItemを持っています

そして、私はこれを追加できるリストを持っています:P そして理想は私が Get(); を実行したときです。リストでは、IWorkItem が見つかるまでループする必要があります。

リストから削除して返します..デュアルコアCPUで多くのスレッドを使用してテストを実行しましたが、これまでのところ追加が失敗したことはないようですが、Get関数はいくつかの作業項目を失い、何が悪いのかわかりません.. ...

psこれが機能するようになったら、誰でも自由にコードを使用できます:)まあ、あなたはどうでもいいですが、バグが発生したときのポイントはわかりません:P

コードはhttp://www.easy-share.com/1903474734/LinkedList.zipにあります。実行しようとすると、リスト...

編集: ロックレス リストが動作しています。lock(obj) ステートメントを使用するよりも高速でしたが、Interlocked を使用するロック オブジェクトがあり、ロックレス リストよりもパフォーマンスが優れていました。ここで結果をアップロードするのがうまくいかない場合でも、同じ結果が得られます..

.NET で利用できるロックフリーのコンテナ ライブラリがあるかどうかは誰にもわかりませんか?

できれば、.NET の Synchronized ラッパーよりも高速で機能することが証明されているものを使用してください。

.NET に関する記事をいくつか見つけましたが、いずれも速度のベンチマークを指定しておらず、信頼性にあまり自信を持っていません。

ありがとう

私が非常に不変な型を持っている場合 (すべてのメンバーは読み取り専用であり、それらが参照型のメンバーである場合、それらは非常に不変なオブジェクトも参照します)。

次のように、型に遅延初期化プロパティを実装したいと思います。

私が言えることから：

...スレッドセーフです。両方のスレッドが同時に初期化するために競合することについてはあまり心配していません。これはめったにないためです。論理的な観点からは両方の結果が同じであり、ロックがない場合はロックを使用したくないからです。に。

これは機能しますか？長所と短所は何ですか？

編集： 回答ありがとうございます。おそらくロックを使用して先に進みます。しかし、コンパイラが temp 変数が不要であることを認識し、m_PropName に直接代入する可能性を誰も持ち出さなかったことに驚いています。その場合、読み取りスレッドは、構築が完了していないオブジェクトを読み取る可能性があります。コンパイラはそのような状況を防ぎますか?

(回答は、ランタイムがこれを許可しないことを示しているようです。)

編集:そこで、Joe Duffy によるこの記事に 触発された Interlocked CompareExchange メソッドを使用することにしました。

基本的：

これにより、このオブジェクト インスタンスでこのメソッドを呼び出すすべてのスレッドが同じオブジェクトへの参照を取得するようになるため、== 演算子が機能します。無駄な作業が発生する可能性がありますが、これは問題ありません。楽観的なアルゴリズムになるだけです。

以下のコメントにあるように、これは動作する .NET 2.0 メモリ モデルに依存します。それ以外の場合、m_PropName は volatile と宣言する必要があります。

メモリ内の 2 つの値のアトミック合計が必要な状況に陥っています。私が継承したコードは次のようになります。

a と b の個々の読み取りはアトミックであり、コード内のこれら 2 つのメモリ位置への書き込みもすべてロックレス アトミックです。ただし、問題は、2 つの場所の値が 2 つの読み取り間で変化する可能性があり、実際に変化することです。

では、この操作をアトミックにするにはどうすればよいでしょうか。私は CAS についてすべて知っていますが、読み取り-変更-書き込み操作をアトミックにすることだけが必要になる傾向があり、それは私がここでやりたいことではありません。

それを行う方法はありますか、またはコードをリファクタリングして、1つの値のみを確認する必要があるようにするための最良のオプションはありますか?

編集: ありがとう、最初のリビジョンでこれをロックレスでやりたいとは言いませんでしたが、2 回目のリビジョンの後でそれを理解した人もいました。こういうことを言う人は誰も信じないのはわかっていますが、実際にロックを使うことはできません。アトミックでミューテックスをエミュレートする必要があり、それはコードをリファクタリングして 2 つではなく 1 つの値を追跡するよりも手間がかかります。

今のところ、私の調査方法は、値が連続しているという事実を利用し、64 ビットの読み取りでアトミックにそれらを取得することです。これは、ターゲット プラットフォームではアトミックであることが保証されています。誰かが新しいアイデアを持っている場合は、貢献してください! ありがとう。

標準のユニオン/検索またはディスジョイント セットのO(1)データ構造は、シングル スレッドの場合、(事実上) 実行時間が非常に長くなります。ただし、マルチスレッドの場合の有効性/パフォーマンスはどうですか? ロックやアトミック ポインター サイズの書き込み以外のアトミック操作がなくても、完全に有効だと思います。

次のロジックに問題がある人はいますか?

最初に、ポインター サイズの書き込みはアトミックであると仮定します。findそのことから、発生する唯一の更新はすべて同じ値に設定されるため、関数を複数のスレッドで安全に実行できると主張するのは難しくありません。find関数が呼び出されたとき (返されたときではなく) に true だった答えを返すことを許可する場合、多くfindの s と 1 つの s をunion同時に実行できると主張するのは難しくありません。sの引数findは変更されず、unionのみがルートを更新し、finds はルートを更新しません。

残りのケース（数union秒）については、それもうまくいくと思いますが、よくわかりません。

ところで: ソリューションがシングル スレッド バージョンと同じくらい効率的である必要はありません。(ロック/アトミックを回避するために、グローバルにコヒーレントな状態も喜んで破棄します。)

編集：別の見方をすると、新しいルートではない側が（ルートとしてではなく）他の何かと結合されている場合、2番目の結合の反対側からそれを切り離すことができるため、多結合のケースは機能しません.

これはCASで回避できます:

C＃タグを使用してこの質問をしますが、可能であれば、どの言語でも可能であるはずです。

インターロック操作を使用して二重リンクリストを実装し、待機なしのロックを提供することは可能ですか？挿入、追加、削除、そしてクリアするのを待たずにしたいと思います。