PUSH 操作が POP 操作をブロックする可能性がある場合、循環バッファ キューは本当にロックフリーですか?

PUSH 操作が POP 操作をブロックできる場合、キューをロックフリーにすることはできますか?

逸話として、「ロックフリー」はよく誤って使用されます。 「ミューテックスを使用しない同時プログラミング」を意味します。ロックフリー アルゴリズムは、実際には、他のスレッドのアクションに関係なく、進行状況を保証します。これは、あるスレッドが別のスレッドに依存して進行するコードがあってはいけないことを意味します。

明示的なミューテックスを使用せずに同時実行を目的とした liblfds の循環バッファー キューを考えてみましょう。 PUSH アルゴリズムでは、書き込みインデックスを比較し、シーケンス番号を更新することによってスロットを予約します。単一の CAS では効率的ですが、ロックフリー性について疑問が生じます。

一方で、スロットが利用可能な場合、スレッドは常にキューに入れることができます。しかしその一方で、シーケンス番号を更新する前に PUSH 操作が中断された場合、後続の POP 操作は失敗し、キューが空のように見えます。

ロックフリーの定義では、「構造体は次の場合に使用可能」となります。すべてのスレッドは無期限に一時停止されます。」というメッセージが表示された場合、このキューは厳密にはロックフリーではありません。これには隠しミューテックス メカニズム (書き込みインデックスとシーケンス番号) があり、クリティカル領域でライターが一時停止されているため、ライターは要素の挿入に失敗する可能性があります。

ただし、キューは依然としていくつかの有用なプロパティを示す可能性があります。オーバーヘッドが低いため、競合のない適度なパフォーマンスが得られ、競合するパフォーマンスを合理的に処理し、部分的にコンテキストスイッチの影響を受けません。さらに、非同期スレッド終了の処理には制限がありますが、割り込みまたはシグナルからのキュー アクセスもサポートしています。

liblfds キューはロック フリー性の厳密な定義を完全には満たしていない可能性がありますが、特定の用途には依然として有益である可能性があります。アプリケーション。ミューテックスベースのソリューションの複雑さを排除し、部分的な進捗の保証と適切なパフォーマンス特性を提供します。

以上がPUSH 操作が POP 操作をブロックする可能性がある場合、循環バッファ キューは本当にロックフリーですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。