問題タブ [lock-free]

IList を実装するロックフリーでスレッドセーフなデータ構造はありますか?

当然のことながら、ロックフリーとは、.NET でロック プリミティブを使用せず、インターロック操作/アトミック操作を使用してスレッド セーフを実現する実装を意味します...どうやら並行データ構造の下にはありません...

浮いてるの見たことある人いる？

私は、 LockFreeVector と呼ばれるamino-cbbsに実装されたJavaを見てきましたが、これまでのところ.NET用のものはありません。何か案は？

ロックフリーおよび同時キューに関する Herb Sutter の記事は、ここ SO でかなり言及されています。ただし、私は C++0x コンパイラを持っていません...だから、誰かが自分のコードを変換して、ブースト ライブラリなどを使用して「アトミック」操作を提供したかどうか疑問に思っています。

誰かがミューテックス/条件変数の例を提供できたとしても、私は気にしません...

参考にした記事はこちら…

http://drdobbs.com/cpp/210604448

http://drdobbs.com/cpp/211601363

http://drdobbs.com/high-performance-computing/212201163

ありがとう！

次に、compareAndSet (Java) を使用したロックフリー キューのコードを示します。

(head と tail はキューのメンバーです)

deq 関数と enq 関数の両方で、最初のチェックは不要に思えます。("???" でコメントしたもの) ある種の最適化のためだけにあるのではないかと思います。

ここで何か不足していますか？これらのチェックはコードの正確さに影響しますか?

(コードは「Art of Multi-processor Programming」から取られていますが、コード スタイルをリファクタリングして、ネストされた if と else を減らし、コードを同等に保ちます)

C / c ++用のロックフリーメモリアロケータを使った良い経験はありますか？

Boostとlibcdsを調べましたが、どのライブラリを使用するかわかりません。

背景、私は「ロックフリー、待機フリー、ノンブロッキング、ダイナミックパーフェクトハッシュ、拡張可能、並行ハッシュテーブル」を研究してきました。*はい、それは大げさなように聞こえますが、それはいわゆるものです。

とにかく、私はそれをマルチスレッドテストを開始する準備をしています。新しいノードが追加されたときに、メモリ割り当てを設定するための最良の方法を見つける必要があります。（そして、ポインターの配列を割り当てる必要がある場合）

では、ロックフリーのメモリ割り当てについて良い経験をしている人はいますか？

最近、次のような java-concurrency インタビュー タスクが見つかりました。

プッシュとポップの 2 つのメソッドを使用して、シンプルなロックフリー スタックを作成します。

私は集中しました：

予想されたアプローチに似ていますか？または、「ロックフリースタック」は別の意味ですか? Javaインタビューの初心者を助けてください。

Raymond Chenは、ロックフリーアルゴリズムに関する膨大な 連載 を行っています。関数の単純なケースを超えて、これらすべての一般的なパターンは、独自のロックを実装することです。もちろん、プロセッサ ロックはありませんが、一貫性を確保するために各 CPU で何度もループするという概念は、スピンロックに非常によく似ています。また、スピンロックであるため、他のスレッドを待機している間は量子の制御を譲らないため、オペレーティング システムに付属する一般的なロックよりも効率が低くなります。したがって、誰かが私のところに来て「でも私のアルゴリズムはロックフリーです」と言うときはいつでも、私の一般的な反応は「そうです」でしょうか? InterlockedXxx

興味があります-ロックフリーアルゴリズムがロックフルアルゴリズムよりも優れていることを示すベンチマークはありますか?

x86/x64 での CAS の低レベルの仕組みを理解しようとしていますが、助けや洞察をいただければ幸いです。

私がこれについて考えてきた理由は、指数バックオフについて推論し、バックオフ遅延の正しい単一単位がどうあるべきかを原理的に理解しようとしているからです。

指数関数的バックオフなしでロックフリー フリーリスト ベンチマークを見ると、スレッド数が増えると、パフォーマンスが急速に横ばいになることがわかります。

ご存知のように、各スレッドが他のスレッドの進行を妨げるライブロックが発生する可能性があります。

私の当初の考えは、今では間違っていると思いますが、CAS が CAS に干渉しているというものでした。つまり、CAS 命令自体が別の CAS と破壊的に衝突する可能性があります。どちらも失敗します。(おそらく、イーサネットについて考えていたからです)。

これは「明らかに」結果を説明しています - これらすべての CAS 命令は同時に動作しており、破壊的に中断される前に完全に実行される機会はほとんどありません。

もう少し考えてみると、そんなことはあり得ないと今では思っています。CAS 命令には、実際には障害モードがありません。宛先が比較対象と等しいか等しくないかがわかります。それで全部です。戻ってきて、「ああ、ごめんなさい、他の誰かにぶつかった」とは言いません。

破壊的な干渉は発生していますが、データ構造アルゴリズム自体のより高いレベルで発生しています。フリーリストから/へプッシュまたはポップするとき、実際にはスワップしようとしています。プッシュ/ポップを完了できるように、デスティネーションを読み取り、必要な作業を実行し、変更されていないことを確認できるように、デスティネーションが十分長く安定している必要があります。

他のスレッドが CASing を続けると、destination は安定せず、変化し続け、操作を再試行する必要が生じます。

しかし今、私は混乱しています。

1 つのスレッドが約 3,000 万回のプッシュ/ポップ操作を実行していることがわかります。操作が成功するためには、これらの操作のいずれかが実行されている間、宛先が安定している必要があるため、3,000 万の「スロット」があることがわかります。スレッドが 2 つある場合、理論上の最大パフォーマンスはスレッドあたり 1,500 万回です。各スレッドは半分のスロットを使用します。

では、CAS に戻りましょう。CAS には故障モードがありません。では、別のスレッドが既に CAS を実行しているときに、2 番目のスレッドが CAS を試行するとどうなるでしょうか? スワップが発生しなかったため、2 番目のスレッドはデータ構造レベルで失敗し、スワップを再試行します。

しかし、たくさんのスレッドがあると想像してください。CAS を開始する最初のスレッドは成功します (各 CAS にまったく同じ時間がかかると仮定すると、そうではありませんが、その仮定は基本的なものを何も変更しないため、推論しても問題ありません)。他のすべては失敗します。

ただし、最初のスレッドが終了すると、新しい宛先値を読み取る次のスレッドで CAS が成功します (さらに、まだ CAS を実行しているか、新しい CAS を開始している他のすべてのスレッドは失敗します)。

では、なぜ完全なスケーリングが見られないのでしょうか? すべての「スロット」を使用する必要があるためです。

そのため、私は CAS を正しく理解していないと思います。

Intel の Architecture Software Developer's Manual を読むと、すべてのデータがキャッシュに存在する場合 (私が興味を持っている状況)、キャッシュ コヒーレンシ プロトコルが CAS を処理することがわかりました。

Drepper は、彼のホワイト ペーパーで LL/SC と、MESI を使用してそれがどのように機能するかについて説明しています。

CAS が同様の方法で動作することは、私には理にかなっているように思えます。

2 スレッドの場合を考えてみましょう。最初のスレッドがその CAS を開始します。宛先を含むキャッシュ ラインはそのキャッシュ内にあり、排他的とマークされています。

2 番目のスレッドが CAS に開始されます。最初のコアはそのキャッシュ ラインを 2 番目のコアに送信し、両方のコアがそのキャッシュ ラインを共有とマークします。

最初のスレッドが CAS を完了し、キャッシュ ラインに書き込みます (比較が false であっても、x86/x64 では常に書き込みが発生します。元の値を書き込むだけです)。

書き込み動作は、キャッシュ ラインを変更済みとしてマークします。RFO が発生し、2 番目のコアがそのキャッシュ ラインを無効としてマークします。

2 番目のスレッドが CAS を完了するようになり、そのキャッシュ ラインが無効であることに気付きます。ARM の LL/SC ではアセンブリでこのループを実行する必要があるため、命令が成功するまで内部的にループされる CPU にあるとは信じがたいです。しかし、CAS 命令は宛先の値が変更されたことを認識しているため、その比較の結果は無効です。しかし、CAS でエラーが発生することはありません。比較に対して常に true または false を返します。しかし、命令が完了するまでループしたとしても、完璧なスケーリングが期待できます。各「スロット」は引き続き使用する必要があります。

それでどうなるの？CASに何が起こっているのですか？

私が見ているのは、スレッド数が増えるにつれて、実行される作業がますます少なくなるということです - 利用可能なすべての「スロット」は確実に使用されていません。何かがこれを引き起こしています。CAS命令間の破壊的干渉ですか？それとも、多数の RFO が CPU->ノースブリッジ バスを占有しているのでしょうか?

私が非常に興味深く注目しているのは、同じ物理コア上の 2 つのスレッドが完全にスケーリングされることです。その場合、何か特別で異なることが起こっています。別々の物理コア上の 2 つのスレッドも同様に半分にスケ​​ーリングされます。しかし、すべてを説明するには十分な手がかりではありません。

私は、ブロッキング キューとロックフリー キューを認識しています。これは、スコットらによって提供されている実装の好例です。、しかし、ロックフリーブロッキングキューの実装はありますか?

lock-free-blocking-queue では、dequeue はロックを必要としませんが、キューにアイテムがない場合、コンシューマーをブロックします。そのような獣の実装はありますか? それらが C# 実装であることが望ましいですが、どの実装でも技術的には機能します。

アップデート：

D14.1 行で競合状態になると思います。

http://www.boyet.com/articles/LockfreeQueue.htmlに基づく比較とスワップを使用して、C でロック フリー キューを実装しました。

うまく機能していますが、このキューを実装したロックフリーのスキップリストに統合しようとしています。スキップ リストをプライオリティ キューとして使用しており、プライオリティの競合が発生した場合に複数の値を格納するために、各ノード内のロック フリー キューを使用したいと考えています。ただし、優先順位の競合を検出したときにスキップ リストでノードを管理する方法により、キューが空でない場合にのみ、アイテムをキューに追加できる必要があります。

キューのロックフリーの性質により、この操作を実際に実行する方法がわかりません。

基本的に、アトミックな enqueue_if_not_empty 操作をどのように記述すればよいでしょうか?

やあみんな、
私はこれらのいわゆるノンブロッキングテクニックを読んでいますが、疑問はほとんどありません:

1）ロックフリー操作はアトミック操作を使用して実行されますが、これらのアトミック操作とは何ですか？つまり、特定のレベルでは、ロック権も必要ですか? それで、このロックフリーのアプローチは、より細かい粒度でのみロックを提供しますか?
2) 彼らはノンブロッキング リストと言っています。ノンブロッキング リストとはどうあるべきか : 複数のスレッドが同じ挿入で来る場合、1 つだけが成功し、別のスレッドは他の作業を正しく行いますか?他のスレッドには、ノードを挿入する以外に選択肢がないのに、どうしてノンブロッキングなのですか? 前のものが完了するまでブロックされませんか??
3) Java では、どのようにアトミック操作を行うのですか? 彼らは次のようなことをしませんか synchronized boolean ..... 彼らはロックを取得しているので、ロックフリー、つまり同期セクションはどうですか？4) CAS は通常、アトミック操作の実装に使用されます。cas は、同じオブジェクトに対して 1 つの操作のみを許可し、同じオブジェクトに対して他の操作を停止 (ブロック) するのではないでしょうか? 疑問が多くて申し訳ありません...明確にしてください...

編集 更新する構造があるとどうなりますか? ハードウェアでもサポートされていますか? そうではありません。言語は、これらの構造操作をアトミックにするために、あるレベルでロックを取得しているのではないでしょうか? JAVA
について：オブジェクト（構造またはあらゆる種類のオブジェクト）の更新を提供するAtomicReferenceおよびAtomicReferenceFieldUpdaterクラスがあるため、パフォーマンス、つまり速度の観点からそれらを比較できますか？両方の in tern は、Native クラスを使用する Unsafe クラスを使用します。