問題タブ [lock-free]

これは、SMPシステムの割り込みハンドラーで実行する必要があるため、ロックフリーである必要があります。鍵が取れません。

いくつかの値を保持する連続した配列があります。この配列の一部のエントリは「フリー」であり、占有されていません。これらのエントリのリストを作成して、すばやく割り当てることができるようにします。ただし、任意のエントリを割り当てる必要がある場合があります。

したがって、次のことが適切な方法であることがわかります。連続する配列は、値だけでなく、左右のポインターも保持するため、両端キューが作成されます。有効な左/右ポインタを持つのは空き値のみです。dequeへの単なるインデックスアクセスであるため、任意のノードにすばやくアクセスできます。

さて、その核心に：比較的効率的で、任意のノードの削除をサポートできる優れたロックフリーの両端キューアルゴリズムはありますか？

MESI などのキャッシュ コヒーレンス プロトコルに関して、CPU レジスタと CPU キャッシュの関係はどのようなものですか? 特定の値が CPU のキャッシュに格納され、レジスタにも格納されている場合、キャッシュ ラインが「ダーティ」としてマークされるとどうなりますか? 私の理解では、キャッシュが更新されたとしても (MESI により)、レジスタがその値を更新するという保証はありません。

このコードをヘンチします。

（コンパイラがループ外で「完全」の負荷を最適化していないと仮定しましょう）
私の理解では、値がレジスタ内に保持されているため、「完全」への更新は2番目のスレッドには表示されません（CPU 2のキャッシュはただし、更新します）。

メモリバリアを配置すると、すべてのレジスタが強制的に「フラッシュ」されますか? レジスタとキャッシュの関係は？レジスタとメモリバリアはどうですか？

メインループ コードと割り込みの間で情報をキューに入れるための FIFO を実装する必要がある TI DSP (TMS320F28235) があります。このキューの高速実行は非常に重要ですが、適切な操作も重要です。明示的な同期を行わずに FIFO を実装してうまくいくかどうか、またはそうでない場合は割り込みを無効にする必要があるかどうかはわかりません。

私はこのページを見つけて、ここの誰かがその適用性についてコメントできるかどうか疑問に思っていました.

スレッドセーフなロガーを設計する必要があります。私のロガーには、ログに記録するテキストを単にキューに入れる Log() メソッドが必要です。また、ロガーはロックフリーである必要があります。これにより、ロガーをロックせずに他のスレッドがメッセージをログに記録できます。何らかの同期イベントを待機し、標準の .NET ログ (スレッドセーフではない) を使用してキューからすべてのメッセージをログに記録する必要があるワーカー スレッドを設計する必要があります。だから私が興味を持っているのは、ワーカースレッドとログ機能の同期です。以下は、私が設計したクラスのスケッチです。ここで Monitor.Wait/Pulse を使用するか、ワーカー スレッドを一時停止して再開するには他の手段を使用する必要があると思います。ロガーのジョブがないときに CPU サイクルを消費したくありません。

別の言い方をすれば、ロガーを使用する呼び出し元スレッドをブロックしないロガーを設計したいと考えています。私は高性能システムを持っています - そしてそれは要件です。

理論的には、少なくともブルートフォースでロックフリーアルゴリズムの検証を行うことができるはずです（交差する関数呼び出しの組み合わせは非常に多くあります）。ロックフリーアルゴリズムが正しいことを実際に証明するために利用できるツールまたは正式な推論プロセスはありますか（理想的には、競合状態やABA問題もチェックできるはずです）？

注：1つのポイントを証明する方法（たとえば、ABA問題から安全であることを証明するだけ）または私が言及していない問題を知っている場合は、とにかく解決策を投稿してください。最悪のシナリオでは、各メソッドを順番に実行して、完全に検証できます。

互いに多くの通信を行っているスレッドがたくさんあります。私はこれがロックフリーであることを望みます。

スレッドごとに、他のスレッドがメッセージを送信できるメールボックスが必要です (ただし、メッセージを削除できるのは所有者だけです)。これは、複数の生産者と単一の消費者の状況です。ロックフリー/ハイパフォーマンスの問題でこれを行うことは可能ですか? (これは、巨大なシミュレーションの内側のループにあります。)

2 つのスレッドを持つプログラムを想像してください。次のコードを実行しています (CAS はCompare and Swapを指します)。

0xdeadbeef が「テスト」に書き込まれないように、スレッド B がスレッド A の CAS を永続的に失敗させる可能性はありますか? それとも、自然なスケジューリングのジッタは、実際にはこれが決して起こらないことを意味するのでしょうか? スレッド A の while ループ内で何らかの作業が行われた場合はどうなるでしょうか。

これらの要件に適合するロックのない設計を探しています。

• 単一のライターが構造体に書き込み、単一のリーダーがこの構造体から読み取ります (この構造体は既に存在し、同時読み取り/書き込みに対して安全です)
• しかし、ある時点で、構造体は writer によって変更される必要があり、初期化、切り替え、および新しい構造体への書き込み (同じ型であるが新しい内容を持つ)
• 次にリーダーが読み取るときに、この新しい構造に切り替えます(ライターが新しいロックフリー構造に複数回切り替えた場合、リーダーはこれらの構造を破棄し、そのデータを無視します)。
• 構造体は再利用する必要があります。つまり、 RT の目的で、書き込み/読み取り/切り替え操作中にヒープ メモリの割り当て/解放は許可されません。

現在、これらの構造の複数のインスタンスを含むリングバッファーを実装しています。しかし、この実装は、ライターがリングバッファーに存在するすべての構造を使用すると、構造から変更する場所がなくなるという事実に悩まされています...しかし、リングバッファーの残りの部分には、読み取る必要のないデータが含まれていますリーダーによって再利用できますが、ライターは再利用できません。結果として、リングバッファはこの目的に適合しません。

ロックフリー設計のアイデア(名前または疑似実装)はありますか? この問題を検討していただきありがとうございます。

スレッド セーフな C++ ウィーク ポインター テンプレート クラスを開発する試みでは、オブジェクトがまだ生きていることを示すフラグをチェックする必要があります。存在する場合は、オブジェクトの参照カウントをインクリメントし、両方の手順をアトミックに実行する必要があります。

_InterlockedCompareExchange() や _InterlockedIncrement() など、コンパイラによって提供される組み込み関数の存在を知っています。しかし、私が欲しいのは interlockedCompareIncrement() 関数です。少なくとも Windows x86 プラットフォームで、他のプリミティブを使用してこの組み込みをシミュレートする効率的な方法はありますか?

私はジョン・スキートが質問に対して出した答えを読んでいて、その中で彼は次のように述べていました：

私に関する限り、ロックフリー マルチスレッディングは真のスレッディング エキスパート向けであり、私はその 1 人ではありません。

これを聞いたのは初めてではありませんが、ロックフリーのマルチスレッド コードの書き方を学ぶことに興味がある場合、実際にどのようにそれを行うかについて話している人はほとんどいません。

だから私の質問は、スレッドなどについてできることをすべて学ぶことに加えて、ロックフリーのマルチスレッドコードを具体的に書くことをどこから学び始めますか、そしていくつかの良いリソースは何ですか.

乾杯