C ++の非ブロッキングスレッドセーフキュー？

StackOverflow https://stackoverflow.com/questions/1645326

  •  10-07-2019
  •  | 
  •  

質問

C ++にはスレッドセーフな非ブロッキングキュークラスがありますか？

おそらく基本的な質問ですが、私は長い間C ++をやっていない...

編集： STL要件を削除しました。

役に立ちましたか？

解決

CPUにダブルポインター幅の比較とスワップ（486以上のcompxchg8b、ほとんどのamd64マシンのcompxchg16b [Intelの初期モデルにはない]）があると仮定します...アルゴリズムがありますこちら。

更新：少しの作業をすることを恐れないのであれば、これをC ++に翻訳するのは難しくありません。 ：P

このアルゴリズムは、「タグ付きポインタ」を想定しています。このような構造：

// Be aware that copying this structure has to be done atomically...

template <class T>
struct pointer
{
   T *ptr;
   uintptr_t tag;
};

次に、いくつかのインラインasmで命令 lock cmpxchg {8 | 16} b をラップします...

たぶん、次のようにキューノードを書くことができます：

template <class T>
struct queue_node
{
    T value;
    pointer<queue_node<T> > next;
};

残りは多かれ少なかれ私がリンクしたアルゴリズムの転写です...

他のヒント

現在のC ++標準ではスレッドの存在さえ認識されていないため、STLや標準ライブラリの他の部分にはスレッドセーフなものはほとんどありません。

これは、ドブ博士の昨年の人気のテーマだったようです：

自分で実装するか、実装するライブラリを使用する必要があります。自分でそれを行うには、これを見てみたいと思うかもしれません：

スレッドの実装-条件変数を使用したセーフキュー

簡単な答え-いいえ。 STLは（少なくとも仕様レベルでは）並行性に関心がありません。現在のC ++標準はスレッドについては何も述べていません。

ただし、STLとBoostの上にこのようなキューを簡単に構築できます。カスタムクラスで std :: queue と boost :: mutex をラップするだけです。

STLコンテナはスレッドセーフではありません。同時アクセスの処理を実装する必要があります。
同時アクセスを提供することを目的とするこのプロジェクト（C ++）があります： CPH STL
および論文。

もう手遅れかもしれません。将来の参考のために、これはロックフリーキューの適切な実装です（いくつかの注意事項とともにスレッドセーフに組み込まれています）。

マルチプロデューサー-マルチコンシューマー

http：// moodycamel。 com / blog / 2014 / a-fast-general-purpose-lock-free-queue-for-c ++

https://github.com/cameron314/concurrentqueue

単一のプロデューサー-単一のコンシューマー

http://moodycamel.com/blog/ 2013 / a-fast-lock-free-queue-for-c ++

https://github.com/cameron314/readerwriterqueue

現在非公式の Boost.Lockfree は考慮すべきこと。 FIFOとアトミックタイプの両方を使用します。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top