c++ - Fober et alロックフリーFIFOキュー：複数の消費者と生産者？

Question

Fober et alの論文http://nedko.arnaudov.name/soft/L17_Fober.pdfに示されているFIFOキューは、複数のコンシューマーであり、FIFOキューを生成するのではないかと思いました。そうでない場合、文書化された複数のコンシューマーおよびプロデューサーFIFOキューの中で最も適切なものはどれですか？

ありがとう

Answer 1

はい。セクション「3.1線形化可能性」を読んでください。ポップ操作は、同時デキューが発生する可能性があることを前提としています。これは、複数のスレッドがキューを消費できることを意味します。

Answer 2

私はこの論文を読んでいませんが、ここで大きな仮定をしています。この論文は、並行性を実現するためにCAS（コンペアアンドスワップ）手法を使用しています。

ロックフリーはブロックフリーを意味するものではありません。CASを使用すると、他のスレッドが停止しますが、少なくとも1つのスレッドが常に「前進」します。

複数のプロデューサーがすべて同じキューに書き込みます-それは問題ではありません。トリッキーなのは複数の消費者です。すべてのコンシューマーがデータにアクセスする必要がある場合、複数のキューでそれを実装すると、データは1つのキューで処理された後、次のキューにフォールスルーされます。スレッドを介して複数のコンシューマーを意味する場合は、上記の方法で機能します

Answer 3

「Foberキュー」はわかりませんが、ロックフリーFIFOをリングバッファとしてすでに書き込んでいます。比較的簡単に可能なのは「インターロックフリー」キューです。つまり、リーダーはライターをブロックせず、その逆も同様ですが、複数のリーダーをシリアル化する必要があり、複数のライターもシリアル化する必要があります。したがって、完全にロックフリーというわけではありませんが、リーダーとライターの間にロック/ブロッキングはありません。

たぶん、さらに少ないロックを可能にするさらに良いアプローチがありますが、おそらくこれはすでにあなたを助けます。