問題タブ [lock-free]

私は、データ フィードの 1 つ以上のストリームに接続し、結果に基づいてイベントをトリガーするよりもデータを分析するシステムを設計中です。典型的なマルチスレッド プロデューサー/コンシューマー セットアップでは、データをキューに入れる複数のプロデューサー スレッドと、データを読み取る複数のコンシューマー スレッドがあり、コンシューマーは最新のデータ ポイントと n 個のポイントのみに関心があります。遅いコンシューマが追いつかない場合、プロデューサ スレッドはブロックする必要があります。もちろん、コンシューマ スレッドは、未処理の更新がない場合にブロックします。リーダー/ライター ロックを備えた典型的な同時キューを使用すると問題なく動作しますが、受信するデータのレートが非常に高くなる可能性があるため、ロッキング オーバーヘッド、特にプロデューサーのライター ロックを削減したいと考えました。私が必要としていたのは循環ロックフリーバッファーだと思います。

今2つの質問：

1. 循環ロックフリーバッファが答えですか?

2. もしそうなら、私が自分自身をロールバックする前に、私のニーズに合った公開実装を知っていますか?

循環ロックフリー バッファを実装するためのヒントはいつでも歓迎します。

ところで、Linux の C++ でこれを行っています。

いくつかの追加情報:

システムにとって応答時間は非常に重要です。理想的には、コンシューマ スレッドは更新ができるだけ早く受信されることを望んでいます。1 ミリ秒の遅延が余分にあると、システムの価値がなくなったり、システムの価値が大幅に低下したりする可能性があるからです。

私が傾倒している設計アイデアは、セミロックフリーの循環バッファーであり、プロデューサースレッドができるだけ早くデータをバッファーに入れます。バッファーがいっぱいでない限り、ブロックせずにバッファー A のヘッドを呼び出しましょう。 A はバッファ Z の末尾に到達します。コンシューマ スレッドはそれぞれ、循環バッファへの 2 つのポインタ P と P _nを保持します。ここで、P はスレッドのローカル バッファ ヘッドであり、P _nは P の後の n 番目の項目です。各コンシューマ スレッドは、その P を進めます。および P _nが現在の P の処理を​​終了し、バッファー ポインター Z の末尾が最も遅い P _{nで進められると、}. P が A に追いつくと、つまり処理する新しい更新がなくなると、コンシューマーはスピンして、A が再び進むのをビジーに待ちます。コンシューマー スレッドのスピンが長すぎる場合は、スリープ状態にして条件変数を待つことができますが、レイテンシーが増加しないため、コンシューマーが更新を待って CPU サイクルを占有しても問題ありません (CPU コアが増えます)。スレッドより)。循環トラックがあり、プロデューサーが多数のコンシューマーの前で実行されていると想像してください。重要なのは、プロデューサーが通常コンシューマーのほんの数歩先を行くようにシステムを調整することです。これらの操作のほとんどは、ロックフリー技術を使用して行われます。実装の詳細を正しく理解するのは簡単ではないことは理解しています...わかりました、非常に難しいです.

複数のスレッドによって読み取られ、1 つのスレッドのみによって書き込まれるインメモリ データ構造があります。現在、クリティカルセクションを使用して、このアクセスをスレッドセーフにしています。残念ながら、これには、別のリーダーだけがアクセスしている場合でも、リーダーをブロックする効果があります。

これを修正するには、次の 2 つのオプションがあります。

1. TMultiReadExclusiveWriteSynchronizer を使用する
2. ロックフリーのアプローチを使用してブロッキングをなくす

2.については、これまでのところ次のとおりです(重要ではないコードは省略されています):

残念ながら、置き換えられた OldData インスタンスを取り除くという小さな問題があります。現在 Read メソッド内に他のスレッドがない場合 (ReaderCount=0)、そのスレッドは安全に破棄できます。しかし、そうでない場合はどうすればよいでしょうか。次の呼び出しまで保存してそこで破棄することもできますが、Windows のスケジューリングでは、理論的には、Read メソッド内にあり、OldData への参照を保持している間、リーダー スレッドをスリープ状態にすることができます。

上記のコードに他の問題が見られる場合は、それについて教えてください。これは複数のコアを持つコンピューターで実行され、上記のメソッドは非常に頻繁に呼び出されます。

これが重要な場合: ビルトイン メモリ マネージャーで Delphi 2007 を使用しています。新しいクラスを作成するときに、メモリマネージャーが何らかのロックを強制する可能性があることは承知していますが、今のところそれを無視したいと思います。

編集: 上記から明らかでない場合があります: TDataManager オブジェクトの完全な有効期間では、データに書き込むスレッドは 1 つだけであり、書き込みアクセスを競合する可能性のある複数のスレッドはありません。したがって、これは MREW の特殊なケースです。

メッセージ パッシングに使用する呼び出しキューのロックフリー バージョンを作成しようとしています。これは深刻なことではなく、スレッドについて学ぶためのものです。

命令が並べ替えられているか、レジスタで実行されている場合を除いて、コードが正しいと比較的確信しています。メモリバリアを使用して並べ替えを停止できることはわかっていますが、値がすぐにメモリに書き込まれるようにするにはどうすればよいですか?

cmpxchg16bなどのアトミック（ダブル）比較およびスワップ命令を使用して、ロックフリーメカニズムを実装しています

私は現在、これをアセンブリで作成してからリンクしています。ただし、コンパイラにこれを自動的に実行させる方法があるかどうか疑問に思いましたか? たとえば、コード ブロックを 'atomically' で囲み、基礎となるプロセッサ アーキテクチャでコードをアトミ​​ック命令として実装する方法を理解させます (または、基礎となるアーキテクチャがサポートしていない場合はコンパイル時にエラーを生成します)。

PS gccにはいくつかの組み込み機能があることを知っています（少なくともCASの場合）

http://gcc.gnu.org/onlinedocs/gcc-4.4.0/gcc/Atomic-Builtins.html#Atomic-Builtins

コンシューマー スレッドとプロデューサー スレッドを使用してプログラムを作成していますが、キューの同期がプログラムの大きなオーバーヘッドになっているようで、ロックフリーのキューの実装をいくつか探しましたが、Lamport のバージョンと PPoPP の改善されたバージョンしか見つかりませんでした。 08:

どちらのバージョンも、データ用に事前に割り当てられた配列を必要とします。私の質問は、malloc() を使用してスペースを動的に割り当てる単一消費者、単一生産者のロックフリー キューの実装があるということです。

もう 1 つの関連する質問は、キューの同期で正確なオーバーヘッドを測定するにはどうすればよいですか? pthread_mutex_lock() にかかる時間など。

Herlihy と Shavit の著書 ( The Art of Multiprocessor Programming ) のメモリ再利用ソリューションでは、Java のAtomicStampedReference<T>;.

x86_64 用に C++ で記述するには、少なくとも 12 バイトのスワップ操作 (64 ビット ポインターの場合は 8、int の場合は 4) が必要だと思います。

これに対する x86 ハードウェアのサポートはありますか? そうでない場合は、それなしでウェイトフリーのメモリ再利用を行う方法についての指針はありますか?

単一のプロデューサー-単一のコンシューマーにはいくつかの実装が見つかりましたが、複数のプロデューサー-単一のコンシューマーには実装がありません。

Delphiには、「複数のプロデューサー-単一のコンシューマー」のロックフリーキューが存在しますか？

私はちょうどこれを見つけました：

http://www.emadar.com/fpc/lockfree.htm

一見、問題ないように見えます。誰か使っていますか？それとも、誰かがすでにそれを見て、それが使用できないことに気づいたのでしょうか？

次の記事を見つけました: GCC 提供のアトミック ロック操作を使用して pthread_mutex_lock 関数を置き換える

GCC Atomic Builtinsを指します。

この記事が示唆しているのは、pthread 同期ツールの代わりに GCC アトミック ビルトインを使用することです。

これは良い考えですか？

PS。mysql の投稿は明らかに誤解を招くものです。Atomic Builtins は、すべての pthread ツールを置き換えることはできません。たとえば、ロックを取得できない場合、スレッドは待機する必要があります。つまり、待機が受動的になるように、OS に待機を要求します。単純な GCC ビルトインではそれができません。