問題タブ [lockless]

一部のデータ構造をロックフリーにする方法が本当にわかりません。たとえば、リンクされたリストがある場合、操作をミューテックスで囲むか、新しいノードを再リンクするのに忙しい間に別のスレッドが実行されると、競合状態になる可能性があります。

「ロックフリー」の概念（「ロックなし」という意味ではなく、他のスレッドが終了するのを待たずにスレッドが進行できることを意味します）は意味がありません。

別のスレッドの生産性を妨げずに競合状態を防ぐ方法を理解できないため、「ロックフリー」として実装されているスタック、キュー、またはリンクされたリストなどを使用した簡単な例を教えてください。この二つの目的は相反するのではないでしょうか？

シナリオを想像してみてください: 2 つのコアが同時に CaS を実行する場合。プロセッサは古い値を読み取り、新しい値を配置する必要があります。古い値は同じです。彼らが同時に読むとどうなりますか？それとも、他のコアが読み取れないように変数に何らかのロックがかけられていますか?

これは私がこれまでに持っているものです。正しい方向に進んでいますか? あるスレッドが他のスレッドよりも頻繁にシングルトンにアクセスする必要があるシナリオでこれを使用することを目的としているため、ロックのないコードが望ましいため、練習のためにアトミック変数を使用したいと考えました。

私は、ロックフリーの複数のプロデューサーと複数のコンシューマーのリングバッファーで (私の試み) 頭を悩ませてきました。アイデアの基本は、unsigned char 型と unsigned short 型の固有のオーバーフローを使用し、要素バッファーをこれらの型のいずれかに固定してから、リング バッファーの先頭に自由にループバックすることです。

問題は、私のソリューションが複数のプロデューサーに対して機能しないことです (ただし、N 個のコンシューマー、および単一のプロデューサー、単一のコンシューマーに対しては機能します)。

書き込みの主なアイデアは、疑似ロックとして機能する一時インデックス「scratchIndex」を使用して、writeIndex を更新し、他のプロデューサーが進行できるようにする前に、一度に 1 つのプロデューサーのみが要素バッファーにコピー構築できるようにすることでした。 . 私のアプローチが「ロックフリー」であることをほのめかして異教徒と呼ばれる前に、このアプローチが完全にロックフリーではないことを認識していますが、実際には (うまくいけば!) 通常のミューテックスを使用するよりもはるかに高速です!

私はここで（より複雑な）MPMCリングバッファソリューションを認識しています http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue、しかし私は実際に自分の考えを実験して比較していますそのアプローチに対して、それぞれが優れている場所を見つけます (または、実際に私のアプローチが完全に失敗するかどうか!)。

私が試したこと。

• compare_exchange_weak の使用
• 私が望む動作に一致するより正確な std::memory_order を使用する
• 私が持っているさまざまなインデックス間にキャッシュライン パッドを追加する
• Element 配列だけでなく要素を std::atomic にする

これは、アトミック アクセスを使用してミューテックスを使用する方法に関する私の頭の中の根本的なセグメンテーション違反に要約されると確信しています。私の頭の中でどのニューロンが大幅に失火しているかを指摘できる人には、心から感謝します! :)

私は C++11 アトミック プリミティブを試して、ある種のアトミックな「スレッド カウンター」を実装しています。基本的に、コードのクリティカル セクションは 1 つだけです。このコード ブロック内では、任意のスレッドがメモリから自由に読み取ることができます。ただし、すべての共有メモリをデフォルトの初期値にリセットするリセットまたはクリア操作を実行したい場合があります。

これは、読み取り/書き込みロックを使用する絶好の機会のようです。C++11 には、すぐに使用できる読み取り/書き込みミューテックスは含まれていませんが、もっと単純なものがあればよいでしょう。この問題は、C++11 のアトミック プリミティブに慣れる絶好の機会になると思いました。

それで、私はこの問題をしばらく考えました。私がしなければならないことは、

1. スレッドがクリティカル セクションに入るたびに、アトミック カウンター変数をインクリメントします

2. スレッドがクリティカル セクションを離れるたびに、アトミック カウンター変数をデクリメントします。

3. スレッドがすべての変数をデフォルト値にリセットしたい場合、カウンターが 0 になるのをアトミックに待機し、アトミックに特別な「クリア フラグ」値に設定し、クリアを実行してから、カウンターを 0 にリセットする必要があります。

4. もちろん、カウンターをインクリメントおよびデクリメントしたいスレッドは、クリアフラグもチェックする必要があります。

したがって、今説明したアルゴリズムは 3 つの関数で実装できます。最初の関数はincrement_thread_counter()、クリティカル セクションに入る前に必ず呼び出す必要があります。2 番目の関数 はdecrement_thread_counter()、必ずクリティカル セクションを出る直前に呼び出す必要があります。最後に、この関数は、スレッド カウンター == 0 の場合にのみclear()、クリティカル セクションの外から呼び出すことができます。

これは私が思いついたものです：

与えられた:

1. スレッドカウンター変数、std::atomic<std::size_t> thread_counter
2. clearing_flagに設定された定数std::numeric_limits<std::size_t>::max()

...

私が推論できる限り、これはスレッドセーフであるべきです。この関数は、常に前に呼び出されるdecrement_thread_counterものであるため、同期ロジックを必要としないことに注意してください。したがって、 に到達すると、thread_counter が 0 または になることはありません。increment()decrement()decrement()clearing_flag

いずれにせよ、THREADING IS HARD™ はロックレス アルゴリズムの専門家ではないため、このアルゴリズムが競合状態にないかどうかは完全にはわかりません。

質問: このコードはスレッドセーフですか? ここで競合状態が発生する可能性はありますか?

Rxやその他のライブラリ（標準の.net 4.5以外）を使用せずに、実装がいかに簡単かを確認するために、バッファリングされた入力の形式を作成しようとしています。そこで、次のクラスを思いつきました。

原則として、タイマーが作動すると、キューが切り替わり、イベントのトリガーが続行されます。これはリストで実行できたことに気づきました...

しばらくすると、おなじみの次の例外が発生します。

次の行で：

宣言とテスト プログラムは次のとおりです。

私の考えでは、Interlocked.Exchange(アトミック操作) への呼び出しが行われた後、_items への呼び出しは新しいコレクションを返します。しかし、作業中のグレムリンがあるようです...

スレッドプールを介して配列内のアイテムを処理するコードを ruby​​ で書きました。その過程で、渡された配列と同じサイズの結果配列を事前に割り当てました。スレッドプール内で、事前に割り当てられた配列にアイテムを割り当てていますが、それらのアイテムのインデックスは一意であることが保証されています。それを念頭に置いて、割り当てを ? で囲む必要がありMutex#synchronizeますか?

例：

(このテスト コードは実行に時間がかかりますが、毎回「成功」を出力しているように見えます。)

安全のために を で囲みたいと思いArray#[]=ますMutex#synchronizeが、私の質問は次のとおりです。

Ruby の仕様では、このコードは安全と定義されていますか?

以下は私のユースケースです

1 つのグローバル変数があり、すべての CPU で複数のスレッドがこれにアクセスしています。

アトミック比較交換あり

スピントライロック付

これは大まかなコードですが、明確であることを願っています。不明な場合はお知らせください。

global_var は int ではなく、構造体です。

だから、私の主な目的はglobal_varを保護することです.atomic_compare_and_swapとspin.trylock（）のどちらが速いですか？

だから、私は本質的に生産者と消費者の問題を解決しようとしていますが、少し異なります.

• 「プロデューサー」スレッドはトークンを作成し、それらをリストに追加します
• 「消費者」スレッドは、トークンのリストをスキャンして処理します。
• 処理の結果、一部のトークンが削除される可能性があり、他のトークンはもう少し長く残る可能性があります。

したがって、主な違いは、必ずしも FIFO ではなく、プロデューサーの出力を任意の順序でリストから削除できることです。

現在、2 つのスレッド間で共有される構造の同期について考えています。ロックレス構造にしたい。ロックレス キューについては知っていますが、上記の理由により、キューはユース ケースにあまり適していません。次のように、これにはまだキューを使用できます。

• トークンをデキューして処理する
• まだ削除しない場合は、キューに戻します

とはいえ、できれば避けたいところです。理想的には、あるスレッドが追加でき、別のスレッドが任意の要素を削除できる、ロックのない単一リンク リストが必要です。それに関するいくつかの実装または論文を教えてもらえますか?