問題タブ [lock-free]

アトミック操作 (コンペア アンド スワップまたはアトミック アド/デクリメントのいずれか) のコストはいくらですか? どのくらいのサイクルを消費しますか? SMP または NUMA 上の他のプロセッサを一時停止しますか、それともメモリ アクセスをブロックしますか? 順不同の CPU でリオーダー バッファをフラッシュしますか?

キャッシュにはどのような影響がありますか?

x86、x86_64、PowerPC、SPARC、Itanium などの最新の人気のある CPU に興味があります。

バイト ストリームを転送する必要があり、1 つのプロデューサー スレッドと 1 つのコンシューマー スレッドがあります。ほとんどの場合、プロデューサーの速度はコンシューマーよりも高速であり、アプリケーションの QoS のために十分なバッファー データが必要です。私の問題について読んだところ、共有バッファー、PipeStream .NET クラスなどの解決策があります...このクラスはサーバー上で何度もインスタンス化されるため、最適化された解決策が必要です。ByteArray の Queue を使用するのは良い考えですか?

はいの場合、最適化アルゴリズムを使用してキューのサイズと各 ByteArray の容量を推測し、理論的には私のケースに適合します。

いいえの場合、最善のアプローチは何ですか?

C# または VB での ByteArray Queue のロックフリーでスレッドセーフな実装があれば教えてください。

前もって感謝します

単一のプロデューサーと複数のコンシューマーをサポートするロックフリー キュー データ構造を実装する方法を探しています。Maged Michael と Michael Scott (1996) による古典的な方法を見てきましたが、彼らのバージョンでは連結リストを使用しています。境界のある循環バッファーを利用する実装が欲しいです。アトミック変数を使用するものはありますか?

余談ですが、これらの古典的な方法が、多くの動的メモリ管理を必要とするリンクリスト用に設計されている理由がわかりません。マルチスレッド プログラムでは、すべてのメモリ管理ルーチンがシリアル化されます。動的データ構造と組み合わせて使用​​することにより、ロックフリー メソッドの利点を無効にしていませんか?

Intel 64 ビット アーキテクチャで pthread ライブラリを使用して C/C++ でこれをコーディングしようとしています。

ありがとう、シリッシュ

重複の可能性:
C++ での本番対応のロックフリー キューまたはハッシュの実装はありますか

十分にテストされ、公開されているロック フリー キューの C/C++ 実装を探しています。

少なくとも複数プロデューサー/単一コンシューマー機能が必要です。複数のコンシューマーが存在する場合は、さらに優れています。

私は VC の_Interlocked...組み込み関数をターゲットにしていますが、単純に移植できるものであれば何でも問題ありません。

誰でも何か指針を与えることができますか？

この論文: Lock-Free Data Structures ( pdf ) では、次の「比較と交換」の基本が示されています。

そして、言う

手順全体がアトミックです

しかし、それはどうしてですか？addr他のアクターが と の間での値を変更する可能性はありませんifか? その場合、すべてのコードがこの CAS の基本を使用していると仮定すると、次に何かが特定の方法であると「期待」したときに、そうではなかったことがわかります。ただし、それが発生する可能性があるという事実は変わりません。その場合、それはまだアトミックですか? 変更がこのアクターによって上書きされた場合でも、他のアクターが true を返すのはどうですか? もしそれが起こりえないとしたら、それはなぜですか？

著者を信じたいのですが、ここで何が欠けていますか? 私はそれが明らかでなければならないと考えています。これが些細なことのように思われる場合は、事前にお詫び申し上げます。

std::ifstream を使用して、多数のスレッドから 1 つのファイルを読み取るためのオープンを実行する予定です。私の懸念は、std::ifstream がスレッドセーフでロックフリーかどうかです。

詳細:

1. Ubuntu と Windows XP では g++ 4.4、Leopard では 4.0 を使用しています。
2. 各スレッドは std::ifstream の独自のインスタンスを作成します

前もって感謝します！

2 つのスレッド (T1、T2) が共有する変数 A、B、および C があるとします。
私は次のコードを持っています:

質問:
T1 と T2 で InterlockedExchange (暗黙的なフル フェンス) を呼び出すと、T2 がフェンスの前に T1 によって行われた書き込みを「見る」ことが保証されますか? (A、B、および C 変数)、これらの変数はFooおよびBarと同じキャッシュラインに配置されていませんが?

私は、ロックフリーの単一リンクリストを実装する方法を考えてきました。そして正直なところ、私はそれを行うための多くの防弾方法を見ていません。使用するより堅牢な方法でさえ、CASある程度のABA問題が発生することになります。

それで私は考え始めました。部分的にロックフリーのシステムは、常にロックを使用するよりも優れているのではないでしょうか。一部の操作はアトミックでロックフリーにすることができますか？それができれば、それでもスレッドセーフになるはずです。

だから、質問に。私は単純な単一リンクリストを考えています。2つの主な操作。 pushおよびpop。push常に前面に挿入します。このようなもの：

そして、常に最初の要素を取るポップ。このようなもの：

明らかに、プッシュは自明ではないので、単純なロックフリーのアプローチはおそらく起こらないでしょう。しかし、ポップはおそらく実行可能に見えます。gcc-intrinsicsを使用して、私はこれについて考えました：

機能的に同等ですか？うん。ロックフリー？うん。スレッドセーフ？わからない。私の腸の反応はノーです、そしてここに理由があります。

test_and_setのパラメータの1つがメモリを逆参照する必要があるという事実が心配です。ルートがroot->nextとの間で変更された場合はどうなりますか__sync_lock_test_and_set。

このコードはこれと同等だと思います：

だから、私が言ったように、私はこのコードが正しくないと思います。しかし、私が正しい結論を導き出していることを誰もが確かに言うことができます（うまく機能するものを書き留めるのは嫌です）。私が思うようにそれが実際に壊れている場合。簡単な解決策はありますか？

Joe Duffy、CLR 2.0+メモリモデルを説明する6つのルールを示します（これは実際の実装であり、ECMA標準ではありません）これを理解するための試みを、主にラバーダッキングの方法として書き留めていますが、間違えた場合私の論理では、少なくともここの誰かが私に悲しみを引き起こす前にそれを捕まえることができるでしょう。

• ルール1：ロードとストア間のデータ依存性が侵害されることはありません。
• ルール2：すべてのストアにはリリースセマンティクスがあります。つまり、ロードまたはストアが1つ後に移動することはありません。
• ルール3：すべての揮発性ロードは取得されます。つまり、ロードまたはストアが1つ前に移動することはできません。
• ルール4：ロードとストアがフルバリアを超えることはできません（例：Thread.MemoryBarrier、lockacquire、Interlocked.Exchange、Interlocked.CompareExchangeなど）。
• ルール5：ヒープへのロードとストアは導入されない場合があります。
• ルール6：ロードとストアは、同じ場所から/に隣接するロードとストアを合体する場合にのみ削除できます。

私はこれらのルールを理解しようとしています。

これを見ると、ロード0はロードyの前に移動できるように見えますが、ストアはまったく再注文されない可能性があります。したがって、スレッドがz == 0を認識している場合、x==yも認識します。

yが揮発性の場合、負荷0は負荷yの前に移動できません。そうでない場合は移動できます。揮発性の店舗には特別な特性はないようです。店舗を相互に再注文することはできません（これは非常に強力な保証です！）

完全な障壁は、砂の中の線のようなもので、積み込みや保管を移動することはできません。

ルール5が何を意味するのかわかりません。

ルール6は、次のことを意味すると思います。

次に、CLRがyへのロードとxへの最初のストアの両方を削除することができます。

yが揮発性だった場合はどうなりますか？上記の最適化の実行を禁止するルールはありません。2つの同一条件間のlock（）により、負荷が隣接する位置に移動するのを防ぐため、これはダブルチェックロックに違反しません。ルール6によれば、負荷を排除できるのはこのときだけです。

ですから、ここではルール5以外はすべて理解していると思います。誰かが私を啓発したい（または私を訂正するか、上記のいずれかに何かを追加したいですか？）

「ロックフリー FIFO キューへの楽観的アプローチ」アルゴリズムの C++ 実装 (ソース コード) はありますか?