問題タブ [lockless]

今日は、ロックレス キューを調査してきました。複数のプロデューサー、複数のコンシューマーの状況があります。テストのために、Win32 で Interlocked SList を使用するシステムを実装したところ、スレッド化されたタスク ベースのコードのパフォーマンスが 2 倍になりました。残念ながら、複数のプラットフォームをサポートしたいと考えています。複数のプラットフォームでの連動自体は問題なく、問題なく連動できると考えて間違いありません。しかし、実際の実装は私を失います。

大きな問題は、リストのプッシュ/ポップが 1 つのインターロック呼び出しのみを使用することを保証する必要があることです。そうしないと、別のスレッドが挟み込んで物事を台無しにするためのスペースを残していることになります。Microsoft の実装が内部でどのように機能するのかよくわかりません。詳しく知りたいです。

誰でも有用な情報を教えてもらえますか (プラットフォームと言語はまったく関係ありません)。

それに加えて、ロックレスベクターを実装できるかどうか知りたいです。それは私にとって非常に多くの用途があります:)乾杯！

編集: ハーブの DDJ の記事を読んだ後、私がすでに持っていたものとかなり似た、削減されたロック キューを確認できます。しかし、ダブルコンペアアンドスワップ (DCAS) 操作を使用して真のロックレスキューイングを行うことができる論文が最後にあることに気付きました。cmpxchg8b (または cmpxchg16b) を使用してキューを実装した人はいますか?

私はこの時点で（論文を読んでいない）ただ黙想していますが、このシステムを使用してヘッドポインターとテールポインターを同時に更新し、別のスレッドが2つのアトミック操作の間にジャンプする問題を回避できます。ただし、次のヘッド ポインターを取得してテール ポインターに対してテストし、テールを変更したかどうかを確認する必要があります。他のスレッドがこの情報を変更する準備をしている間に、別のスレッドがこの情報を変更しないようにするにはどうすればよいでしょうか? これはロックレスな方法でどの程度正確に実装されていますか? それとも、研究論文である解読不能性を読んだほうがよいでしょうか? ;)

私はロックレスデータ構造にかなり慣れていないので、演習のために（機能することを望んでいます）制限付きロックレス両端キューを作成しました（サイズ変更はまだありません。基本ケースを機能させたいだけです）。私が正しい考えを持っているかどうか、および/またはこれをどのように改善できるかについて、彼らが何をしているのかを知っている人々から確認を得たいと思います.

単一のスレッドに投稿されて処理される複数のスレッドからの要求を含むリンクリストの形式でCで記述されたロックレスキューがあります。数時間のストレスの後、最後のリクエストの次のポインタがそれ自体を指すようになり、無限ループが作成され、処理スレッドがロックされます。

アプリケーションはLinuxとWindowsの両方で実行されます（そして失敗します）。私はWindowsでデバッグしており、InterlockedCompareExchangePointerCOMPARE_EXCHANGE_PTRにマップしています。

これは、リクエストをリストの先頭にプッシュするコードであり、いくつかのスレッドから呼び出されます。

これは、リストの最後からリクエストを取得するコードであり、それらを処理する単一のスレッドによってのみ呼び出されます。

でテールポインタを処理する必要があるという複雑さを避けたかったので、テールポインタを使用していないことに注意してくださいpush_request。ただし、問題はリストの最後を見つける方法にあるのではないかと思います。

リクエストをキューにプッシュする場所はいくつかありますが、それらはすべて一般的に次のように見えます。

リクエストを処理するコードはそれ以上のことを行っていますが、本質的にはループでこれを行います。

また、各操作の前後で重複がないかリストをチェックする関数を追加しましたが、このチェックによってタイミングが変わるので、失敗することはありません。（これを書いている間、私はそれが壊れるのを待っています。）

ぶら下がっているプログラムを壊すと、ハンドラースレッドpop_requestはマークされた位置でループします。1つ以上のリクエストの有効なリストがあり、最後のリクエストの次のポインタがそれ自体を指しています。リクエストキューは通常短く、10を超えることはありません。また、デバッガーでこの障害を確認できたのは1回と3回だけです。

私はこれをできる限り考え、同じリクエストを2回プッシュしない限り、リスト内でループが発生することは決してないはずだという結論に達しました。私はこれが決して起こらないと確信しています。また、（完全ではありませんが）ABA問題ではないこともかなり確信しています。

同時に複数のリクエストをポップする可能性があることは知っていますが、これはここでは無関係であると信じており、それが発生するのを見たことがありません。（これも修正します）

どうすれば関数を壊すことができるかについて、長く懸命に考えましたが、ループに陥る方法がわかりません。

だから問題は：誰かがこれがどのように壊れることができるかを見ることができますか？誰かがこれができないことを証明できますか？

最終的に私はこれを解決します（おそらくテールポインタまたは他の解決策を使用することによって-ポストするスレッドはロックされるべきではないのでロックは問題になりますが、私は手元にRWロックを持っています）が、それを確認したいと思いますリストを変更すると、実際に私の問題が解決します（タイミングが異なるために問題が発生する可能性が低くなります）。

複数のスレッドが読み取りまたは書き込みを行っているときに、ロックのないキューを持つことは可能ですか? 1 つの読み取りスレッドと 1 つの書き込みスレッドで機能するロックレス キューを使用した実装を見たことがありますが、いずれのスレッドも複数のスレッドで機能することはありませんでした。出来ますか？そうではないと思います。誰かがそれを証明できますか/証明したいですか?

複数のスレッドによって読み取られ、更新されるデータがいくつかあります。読み取りと書き込みの両方がアトミックである必要があります。私はこのようにすることを考えていました：

データは、読み取りと書き込みのたびにデータへのポインタを盗むことで保護されます。これにより、データはスレッドセーフになりますが、アクセスごとに2つのインターロックされた命令が必要です。読み取りと書き込みの両方がたくさんあり、読み取りと書き込みのどちらが増えるかを事前に知ることはできません。

これよりも効果的にできるでしょうか？これは読み取り時にもロックされますが、読み取りよりも書き込みが多い可能性があるため、書き込みにペナルティを課さない限り、読み取りを最適化しても意味がありません。

インターロックされた命令なしで（シーケンス番号とともに）ポインターを取得し、データをコピーしてから、シーケンス番号が変更されたかどうかを確認する方法を考えていました。変更された場合は、再試行する必要があります。ただし、これにはいくつかのメモリバリアが必要であり、速度が向上するかどうかはわかりません。

- - - 編集 - - -

みんなありがとう、素晴らしいコメント！私は実際にこのコードを実行していませんが、現在のメソッドを今日の後半にクリティカルセクションと比較しようとします（時間があれば）。私はまだ最適な解決策を探しているので、後でより高度なコメントに戻ります。再度、感謝します！

シングル プロデューサー スレッド、シングル コンシューマー スレッドのロックレス キューがあり、プロデューサーが長期間にわたってデータを生成しない場合があるとします。キューに何もないときにコンシューマー スレッドをスリープ状態にすることは有益です (電力を節約し、他のプロセス/スレッドのために CPU を解放するため)。キューがロックレスではない場合、この問題を解決する簡単な方法は、生成スレッドにミューテックスをロックさせ、その作業を実行させ、条件変数を通知してロックを解除し、読み取りスレッドがミューテックスをロックするまで条件変数を待機することです。 、その読み取りを行い、ロックを解除します。しかし、ロックレス キューを使用している場合、まったく同じ方法でミューテックスを使用すると、そもそもロックレス キューを使用することで得られるパフォーマンスが失われてしまいます。

単純な解決策は、キューへの挿入ごとにプロデューサーにミューテックスをロックさせ、条件変数を通知してからミューテックスのロックを解除し、実際の作業 (キューへの挿入) を完全にロックの外に保ち、コンシューマーに実行させることです。同じように、ミューテックスをロックし、条件変数を待機し、ロックを解除し、キューからすべてを取り出してから繰り返し、キューの読み取りをロックの外に保ちます。ただし、ここには競合状態があります。リーダーがキューから離れてからスリープ状態になるまでの間に、プロデューサーがアイテムをキューに挿入した可能性があります。これでリーダーはスリープ状態になり、プロデューサーが別のアイテムを挿入して条件変数に再度シグナルを送るまで、無期限にスリープ状態になる可能性があります。これは、特定のアイテムがキューを通過するのに非常に長い時間がかかるように見える場合があることを意味します. キューが常にアクティブである場合、これは問題にならない可能性がありますが、常にアクティブである場合は、条件変数を完全に忘れてしまう可能性があります。

AFAICT解決策は、プロデューサーが通常のニーズロックキューを使用しているかのように動作することです。ミューテックスをロックし、ロックレス キューに挿入し、条件変数を通知し、ロックを解除する必要があります。ただし、消費者は異なる行動を取る必要があります。起動すると、キューが読み取られるまで待機するのではなく、すぐにミューテックスのロックを解除する必要があります。次に、できる限り多くのキューをプルして処理する必要があります。最後に、消費者がスリープ状態になることを考えている場合にのみ、ミューテックスをロックし、データがあるかどうかを確認し、データがある場合はロックを解除して処理するか、そうでない場合は条件変数を待機します。この方法では、ロックフル キューよりもミューテックスの競合が少なくなりますが、キューにデータが残ったままスリープ状態になるリスクはありません。

これが最善の方法ですか？代替手段はありますか？

注: 「最速」とは、実際には「キューを何度もチェックするためにコアを専用にすることなく最速」を意味しますが、それはタイトルには当てはまりません;p

1 つの代替方法: 単純なソリューションを使用しますが、キューを通過するアイテムに対して許容できる最大待機時間に対応するタイムアウトを使用して、コンシューマーを条件変数で待機させます。ただし、必要なタイムアウトがかなり短い場合は、OS の最小待機時間を下回っているか、CPU の消費量が多すぎる可能性があります。

2 つの pthread 間で、ロックのないシングル プロデューサー、シングル コンシューマーの循環キューを実装したいと考えています。ARM Linux の C で。

キューはバイトを保持し、プロデューサーは memcpy() を取り込み、コンシューマーはそれらをファイルに write() します。

頭と尾のオフセットを int に格納でき、すべてがうまくいくと考えるのは単純ですか? コンパイラの最適化など、頭/尾の書き込みがレジスタにあり、他のスレッドからは見えないこと、またはどこかにメモリバリアが必要であることなどについて疑問に思っています。

アトミックまたはアトミックまたはのようなものはあり|=ますか？いいえの場合、スレッドセーフにする必要がある変数にビットを設定するための推奨される手法は何ですか? （私はロックを避けています）

以下の msdn 記事で概説されている原則と、以下の DXUT ロック フリー パイプ コードに基づいて、単純なロックレス キューを作成しました。

• http://msdn.microsoft.com/en-us/library/ee418650(v=vs.85).aspx

• http://code.google.com/p/bullet/source/browse/trunk/Demos/DX11ClothDemo/DXUT/Optional/DXUTLockFreePipe.h?r=2127

したがって、メイン スレッドがレンダリング命令をフィードし、レンダリング スレッドが利用可能なメッセージを消費して、対応する opengl 呼び出しを発行するプロデューサー/コンシューマー モデルのセットアップがあります。メインスレッドを各ループ/反復で十分な時間スリープさせれば問題なく動作しますが、十分な時間スリープさせない (またはまったくスリープさせない) と、アクセス違反の例外が発生します。

私のコールスタックは次のとおりです。

何が問題なのかよくわかりません。ロックレス キューのコードは次のとおりです。

読み取り/書き込みオフセットとバッファ ポインタがウォッチ ウィンドウから正常に見えるため、デバッグに苦労しています。残念ながら、アプリが壊れると、BeginRead 関数から autos/local 変数を監視できません。ロックレス プログラミングを使用した経験がある場合は、この問題に関するヘルプや一般的なアドバイスをいただければ幸いです。

アプリですぐに発生するはずのイベントを待機したいので、スレッドを待機させて後でウェイクアップしたくありません。Sleep(0)ハードウェア一時停止命令の使用との違いは何だろうか。

次のプログラムの CPU 使用率に違いは見られません。私の質問は、省電力の考慮事項に関するものではありません。