liblfds のマルチプロデューサー/マルチコンシューマー境界キューは本当にロックフリーですか?

ロックフリー キュー アルゴリズムの分析

質問: マルチプロデューサー/マルチコンシューマーの制限付きキュー アルゴリズムですかliblfdsでlock-free?

ロックフリーの定義:

ロックフリー アルゴリズムでは、同時スレッドに関係なく、少なくとも 1 つのスレッドが確実に前進できるようになります。これは、フラグがリセットまたは設定解除されるのを待機するなど、スレッドが別のスレッドに依存して続行するコードを含めることはできないことを意味します。

アルゴリズム分析:

アルゴリズムは、CAS ループを使用してキュー内のスロットを予約し、書き込みインデックスをインクリメントします。次に、ユーザー データを予約スロットにコピーし、シーケンス番号を更新します。ただし、この予約は、POP 操作がシーケンス番号の更新を完了する PUSH スレッドに依存していることを意味します。

進行状況の欠如保証:

「作成」の定義によると、進行中」というメッセージが表示された場合、アルゴリズムはロックフリーの基準を満たしていません。 PUSH または POP 操作が進行中であっても、キューが満杯または空として観察され、他のスレッドがこれらの操作を実行できなくなることがあります。

部分的にブロックされた進行状況:

アルゴリズムにより、POP 操作が進行中の要素まで継続できる場合がありますが、この進行は制限されています。書き込みインデックスの更新とシーケンス番号の書き込みの間のクリティカル領域中にスレッドがコンテキスト スイッチアウトされた場合、すべてのコンシューマ スレッドは空のキューを報告します。

Hidden Mutex:

書き込みインデックスとスロット シーケンス番号の組み合わせは、基本的に要素ごとのミューテックスとして機能します。スレッドが書き込みインデックスを正常にインクリメントすると、元のスレッドが操作を完了するまで、後続のすべてのスレッドはキューへの書き込みを禁止されます。

パフォーマンスの利点:

このアルゴリズムは厳密にロックフリーであるため、次の点でパフォーマンス上の利点があります。

• 競合しないパフォーマンス:高速パスは、単一の CompareAndSwap 操作で構成されます。
• 競合パフォーマンス: 書き込みインデックス変数は競合していますが、適切に最適化された CAS 実装により、動作は妥当です。

結論:

このアルゴリズムはいくつかの有用なパフォーマンス特性を提供しますが、主要な正確性特性が欠けています。予約システムと PUSH 操作と POP 操作間の依存関係により、ロックフリー操作が制限されます。

以上がliblfds のマルチプロデューサー/マルチコンシューマー境界キューは本当にロックフリーですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。