liblfds の循環バッファ キューは本当にロックフリーで、すべてのスレッドの進行を保証しますか?

循環バッファ キューにおけるロックフリーの進行保証

ロックフリー アルゴリズムの概念により、少なくとも 1 つのスレッドの能力が保証されます。他のスレッドのアクションに関係なく、継続的に進歩します。ただし、この定義は、特に liblfds などの同時実行ライブラリのコンテキストにおいて、あいまいさに直面することがあります。

Liblfds は、境界付きキューの実装にカスタム アトミックとメモリ バリアを採用しています。このアルゴリズムは効率的であるように見えますが、そのロックフリーの性質には疑問が残ります。

強制の進行状況:

PUSH アルゴリズムは、ユーザー データ用にキュー内のスロットを予約します。ただし、sequence_number が更新されるまで、スロットは POP 操作でアクセスできないままになります。この PUSH の完了への依存により、他のスレッドがブロックされたり遅延したりする状況が生じ、進行状況が保証されない可能性があります。

アルゴリズムの評価:

アルゴリズム著者が提案したロックフリーの定義を厳密には満たしていません。 m_write_index と s.sequence_number の組み合わせは要素ごとのミューテックスとして機能し、スロットを予約している中断されたスレッドが存在すると潜在的な障害が発生する可能性があります。

パフォーマンスと機能の評価側面:

パフォーマンス:

最小限のアトミック操作により、競合のないパフォーマンスは満足のいくものです。競合パフォーマンスも妥当ですが、複数のリーダーがキューにアクセスしようとすると、m_write_index が競合の原因になる可能性があります。

コンテキスト スイッチに対する耐性:

クリティカル領域中にスレッドがコンテキストスイッチされた場合でも、他のスレッドは引き続き要素をキューにプッシュできるため、部分的な免疫が提供されます。ただし、進行中の要素が影響を受けると、要素のポップが停止する可能性があります。

機能制限:

このアルゴリズムは、非同期スレッドの終了や、割り込みハンドラーやシグナル ハンドラーからのアクセスに対しては安全ではありません。クリティカル領域でスレッドが中断された場合、すべての要素が完全に排出されない可能性があります。

結論:

liblfds キューの実装はパフォーマンス上の利点を提供する可能性がありますが、そのロックは-free の性質は、成功した PUSH 完了に依存しているため、疑わしいです。これは進捗保証の厳密な定義を完全には満たしておらず、特定のエッジケースでは進捗のブロックや失敗につながる可能性があります。

以上がliblfds の循環バッファ キューは本当にロックフリーで、すべてのスレッドの進行を保証しますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。