問題タブ [lock-free]

私は自分に適したconcurrnetHashtableを作成していて、concurrentHashMapとは少し異なり、AtomicReferenceFieldUpdaterを使用してCASNext操作を行っています（通常はCASがサポートされていますが、これによってCASNextも実行できます）。通常、このconcurrentHashTableでは、ハッシュテーブルをロックするよりも優れたパフォーマンスが得られますが、うまくいかない場合もあります。
だから私は次の結論に達しました：
使用可能なプロセッサの数がハッシュテーブルで使用可能なバケットの数よりも多い場合、ロックの競合が発生する可能性が高くなります。したがって、この場合、concurrentHashTableはロックのアプローチよりもうまく機能します。もちろん、読み取りが多い場合（ジャーナルによると85- 90％の読み取り操作）、それならそれは使用に適しています..だから私に提案してください、私は正しい道を進んでいますか、そして物事を正しく仮定していますか？
時間があれば、このページのコードを参照してください 。このハッシュテーブルでは、要素がまだ存在しない場合に挿入を行っています...これが正しいロックフリーアプローチであるかどうかを教えてください。

また、私はc実装を行っており、現在キューの構造を持っています:

しかし、キューとデキュー機能を使用して続行する方法がわかりません...

• コードはどのようになりますか？

集約的なネットワーク アプリケーション用に、ロックフリーのシングル プロデューサー、シングル コンシューマー キューを実装しています。独自の個別のキューで作業を受け取る多数のワーカー スレッドがあり、それらはキューから取り出されて処理されます。

これらのキューからロックを削除すると、高負荷時のパフォーマンスが大幅に向上しましたが、キューが空のときにブロックされなくなり、CPU 使用率が急上昇しました。

何かを正常にデキューできるか、強制終了/中断されるまで、スレッドを効率的にブロックするにはどうすればよいですか?

このロックフリーキューの擬似コードをどのように実装できますCか？

アトミックメモリアクセスに組み込み関数をどのように使用しますか

私は現在持っています

現在の実装では、コード内でロックフリー キューを使用して、単一のプロデューサーとコンシューマーの間のロックの競合を減らすことを検討してきました。キューの実装はたくさんありますが、ノードのメモリ管理を最適に管理する方法についてはあまり明確ではありませんでした。

たとえば、プロデューサーは次のようになります。

そして、消費者は次のようになります。

現在、メモリ プールを割り当てに使用しています。プロデューサがメモリを割り当て、コンシューマがそれを削除することに気付くでしょう。プールを使用しているため、適切に保護するためにメモリ プールに別のロックを追加する必要があります。これは、そもそもロックフリー キューのパフォーマンス上の利点を無効にしているようです。

これまでのところ、私たちの選択肢は次のとおりだと思います。

• ロックのないメモリ プールを実装します。
• メモリ プールをダンプし、スレッドセーフ アロケータに依存します。

他に検討できるオプションはありますか? ロックフリー メモリ プールの実装を回避しようとしていますが、その道をたどる可能性があります。

ありがとう。

私はネットワーク制御機能を書いているので、アルゴリズムは

1. 現在の転送速度を読み取る

2. 必要な転送レートよりも低い場合は続行し、そうでない場合は数 x 秒間スリープしてからステップ 1 に進みます。

3. x は、必要な転送速度と現在の転送速度に基づいて計算されます。

このアルゴリズムをスレッドセーフにする方法を教えてください

(C++ ではなく) C で記述されたロックフリー アルゴリズム (キュー、リンク リストなど) を実装するライブラリはありますか? Intel のようないくつかのライブラリを調べましたが、少なくとも Intel のライブラリよりも汎用的な汎用ライブラリを使用したいと考えています。

go がオーディオ/ビデオ アプリケーションの可能なオプションであるかどうかを評価するために、go でのメッセージ パッシングが、ブロックされない進行の保証 (障害がない、ロックがない、または待機がない) を満たしているかどうかを知りたいです。特に、次のシナリオが該当します。

シングル プロデューサー シングル コンシューマー:

2 つのスレッドが共有チャネルを使用して通信します。スレッド A は非同期送信のみを行い、スレッド B は非同期受信のみを行います。OS スケジューラーがスレッド A を「考えられる最悪の瞬間」に無期限に中断することを決定したとします。スレッド B は、制限された数の CPU サイクルで受信操作を完了することが保証されていますか、それともスレッド A が OS がスレッド A を再開するのを待つ必要がある状態にスレッド A がチャネルを入れることができる (理論的な) 可能性はありますか?

複数のプロデューサー:

いくつかのスレッド A1、A2、A3、... は、共有チャネルを使用して 1 つ以上の他のスレッドと通信します。スレッド Ai は非同期送信のみを行います。A2、A3、... が OS スケジューラによって「考えられる最悪の瞬間」に無期限に中断されたとします。スレッド A1 は、限られた数の CPU サイクルで送信操作を完了することが保証されていますか? さらに、各スレッドが 1 つの送信だけを行いたいとします。プログラムが十分に長く実行された場合 (一部のスレッドを枯渇させる可能性があるか、「最悪の瞬間」にスレッドを中断して再開する「悪意のある」スケジューラを使用)、少なくとも 1 つの送信が成功することが保証されますか?

ここでは、典型的なシナリオにはあまり関心がありませんが、最悪の場合の保証には関心があります。障害、ロック、待機のないアルゴリズムの詳細については、ノンブロッキング アルゴリズム (ウィキペディア) を参照してください。

Intel Threading Building Blocks (TBB)parallel_forのオーバーヘッドが大きいのはなぜですか? セクション 3.2.2 によると、その約 0.5 ミリ秒の自動チャンク。Tutorial.pdfこれはチュートリアルからの特技です:

注意: 通常、ループのパフォーマンスを向上させるには、parallel_for に少なくとも 100 万クロック サイクルかかる必要があります。たとえば、2 GHz プロセッサで少なくとも 500 マイクロ秒かかるループは、parallel_for の恩恵を受ける可能性があります。

私がこれまでに読んだことによると、TBB はスレッドプール (ワーカー スレッドのプール) パターンを内部で使用し、ワーカー スレッドを最初に 1 回だけ生成することで、このような悪いオーバーヘッドを防ぎます (数百マイクロ秒のコストがかかります)。

では、何が時間を取っているのでしょうか。ミューテックスを使ったデータ同期ってそんなに遅くないですか？また、TBB はロックフリーのデータ構造を同期に利用していませんか?

ほとんどの条件下で、ローカル読み取りで問題なく動作するロックフリー コードをいくつか書きました。

メモリ読み取りでのローカル スピンは、スピン読み取りの前に常にメモリ バリアを挿入する必要があることを意味しますか?

（これを検証するために、特定の非常に特定の条件下で、リーダーが書き込まれた値をまったく見ないという結果になるリーダー/ライターの組み合わせを作成することに成功しました。ループ内で実行されるため、矢印はその方向を指していますが、メモリバリアを通過するコストについては完全にはわかりません.)

キャッシュのストア バッファにフラッシュするものが何もない場合、メモリ バリアを介してスピンするコストはいくらですか? つまり、すべてのプロセスが (C で) 行っているのは、

それは無料であり、メモリバスにトラフィックを邪魔しないと仮定するのは正しいですか?

別の言い方をすれば、次のように質問することです: メモリ バリアは、ストア バッファーをフラッシュし、無効化を適用し、コンパイラーがその場所全体で読み取り/書き込みを並べ替えないようにする以上のことを行いますか?

逆アセンブルすると、__sync_synchronize() は次のように変換されます。

Intelのマニュアルから（同様に、初心者にとっては漠然としています）：

私の翻訳: 「ロックと言うと、これはコストがかかりますが、必要な場合にのみ行っています。」

@BlankXavier：

ライターがストア バッファーから書き込みを明示的にプッシュアウトせず、それがその CPU で実行されている唯一のプロセスである場合、リーダーはライターの効果を確認できない可能性があることをテストしました (テスト プログラムで再現できますが、上で述べたように、特定のコンパイルオプションと専用のコア割り当てを使用した特定のテストでのみ発生します-私のアルゴリズムは正常に機能します。将来の問題）。

デフォルトでは、単純な書き込みはWB書き込み（ライトバック）であると思います。つまり、すぐにはフラッシュされませんが、読み取りは最新の値になります（「ストア転送」と呼ばれると思います）。そこで、ライタには CAS 命令を使用します。Intelのマニュアルで、これらすべての異なるタイプの書き込み実装（UC、WC、WT、WB、WP）、Intel vol 3A chap 11-10を発見し、まだそれらについて学んでいます。

私の不確実性は読者の側にあります.McKenneyの論文から、バスからキャッシュへの受信無効化のキューである無効化キューもあることがわかりました。この部分がどのように機能するかわかりません。特に、通常の読み取りをループする（つまり、ロックされていない、バリアなしで、揮発性を使用して、コンパイル後にオプティマイザーが読み取りを確実に残すようにする）と、毎回「無効化キュー」にチェックインすることを暗示しているようです。 （そのようなものが存在する場合）。単純な読み取りでは不十分な場合 (つまり、キューに入れられた無効化が保留されている間はまだ有効に見える古いキャッシュ ラインを読み取ることができます (これは私にも少し矛盾しているように聞こえますが、無効化キューはどのように機能するのでしょうか?))、アトミック読み取りは次のようになります。私の質問は次のとおりです。この場合、これはバスに影響を与えますか? （多分無いと思います。）

私はまだ Intel のマニュアルを読んでいますが、ストア フォワーディングについては素晴らしい議論が見られますが、無効化キューについては適切な議論が見つかりませんでした。C コードを ASM に変換して実験することにしました。これがどのように機能するかを実際に理解するには、これが最善の方法だと思います。