プロンプトとコンテキスト
アトミックポインタによってノードが連結された高競合のロックフリースタックがあります。あるスレッドがheadを読み取ってCASで削除する一方で、別のスレッドがそれを解放する可能性があります。スタック全体のグローバルロックなしで並行リーダーを許可し、C++26のhazard_pointerモデルを使用して安全なメモリ回収を設計してください。
面接官がテストしていること
ハザードポインタは現在読み取り中のアドレスを保護しますが、ノードを永久に存続させるわけではありません。リーダーはハザードを公開し、アトミックなheadが依然としてそのノードを指していることを再確認してから、初めてそれをデリファレンスします。削除されたノードはリタイアリスト（retired list）に入り、すべてのハザードをスキャンした後にのみ回収されます。acquire/release、登録と終了処理、スキャンコスト、およびABAには個別の保護が必要である点について説明してください。
最初に確認すべき明確化のための質問
データ構造とプログレス保証
これがTreiberスタック、連結リスト、またはハッシュバケットのいずれであるか、lock-freeまたはwait-freeの進行保証が必要かどうか、そしてスレッドローカルなリタイアリストが許容されるかを確認します。
スレッドのライフタイム
スレッドがハザードスロットをどのように取得し、終了時にどのように保護をクリアしてリタイアノードを転送するかを尋ねます。クラッシュしたスレッドが恒久的に回収不能なレコードを残してはなりません。
ABAとタギングポリシー
アドレスが再利用可能かどうか、またバージョンカウンタやタグ付きポインタが利用可能かどうかを判断します。ハザードポインタは保護されたノードの解放を防ぎますが、それ単体ではABAによってCASが誤って成功することを防ぐことはできません。
30秒の回答フレームワーク
「リーダーはheadをアトミックにロードし、そのアドレスをハザードスロットに公開して、再びheadをロードします。変更されていない値のみがデリファレンス可能です。CASが成功した後、古いノードは削除される代わりにリタイアリストに入ります。スキャンはすべてのハザードアドレスを収集し、そのセットに存在しないリタイアノードのみを回収します。対応するacquire/releaseセマンティクスを使用し、スレッド終了前にスロットをクリアし、ABAはバージョンまたはタグで個別に処理します。」
ステップごとの詳細な回答
ステップ 1: ハザードスロットとリタイアリストの定義
共有ノードをデリファレンスする可能性のある各スレッドは、ハザードスロットを所有します。リタイアリストは、データ構造から削除されたものの、まだ安全に回収できないノードを保持します。一時的な生ポインタが保護を回避できないように、登録とスロットの所有権は明示的でなければなりません。
ステップ 2: 公開と検証のウィンドウの確立
headをロードし、releaseまたは同等の順序付けでハザードスロットに公開してから、acquireでheadをリロードします。両方の値が一致した場合にのみフィールドをデリファレンスします。そうでない場合はスロットをクリアして再試行します。これにより、別のスレッドがノードを削除して回収する隙間を塞ぎます。
ステップ 3: CASと回収の遅延
nextを読み取り、headをcompare-exchangeします。CASが失敗した場合は、ハザードをクリアして再試行します。成功した場合は、古いノードをリタイアリストに追加し、リーダーがそのノードを必要としなくなった後にのみスロットをクリアします。いかなるパスも共有ノードを直接削除してはなりません。
ステップ 4: スキャンと回収
すべてのスレッドのハザードスロットをスキャンして、保護対象アドレスのセットを作成します。リタイアリストを走査し、そのセットに含まれていないノードのみを回収します。スロット数とリタイアリストの長さからスキャンのしきい値を調整します。準拠したリーダーの公開・検証プロトコルにより、スキャンがハザードを確認する前にノードが無保護になることはありません。
ステップ 5: ABAとメモリーオーダリングの処理
回収の遅延はアドレスの再利用を減らしますが、ABAを排除するわけではありません。ノードが素早く削除されて再挿入される可能性がある場合は、バージョンカウンタ、タグ付きポインタ、または別のABA対策を使用します。アトミックなhead、ハザードスロット、およびノードフィールドのhappens-before関係を定義します。証明なしに速度向上のためだけにrelaxed操作を使用してはなりません。
ステップ 6: スレッドの終了と例外の処理
読み取りを停止する前にハザードをクリアし、リタイアノードをアクティブな回収スレッドまたは共有ドメインに転送します。レジストリには、終了を検知して放置されたスロットを回避できる所有者状態が必要です。破棄は、リーダーがそのノードに到達できなくなった後にのみ実行されます。通常のオブジェクトライフタイムの前提では不十分です。
ステップ 7: 安全性とパフォーマンスのテスト
ThreadSanitizer、ランダム化されたスケジューリング、およびCAS失敗、並行スキャン、スレッド終了、再利用、例外に関するストレステストを使用します。use-after-freeを検出するために遅延解放センチネルを追加します。スキャン時間、リタイアリストのピーク、スループット、テールレイテンシを測定し、グローバルロックを追加する代わりにバッチのしきい値を調整します。
高品質な回答例
各リーダーにハザードスロットを割り当てます。popはheadをロードし、ハザードを公開し、headをリロードし、その後にのみnextを読み取ってCASを試行します。値が変更されていた場合はスロットをクリアして再試行します。削除が成功するとリタイアリストに入り、すべてのハザードアドレスのスキャンによって保護されていないノードのみが回収されます。スレッド終了時にはそのスロットがクリアされ転送されます。ABAはバージョンまたはタグ付きポインタを個別に使用します。テストでは、use-after-freeとスキャンコストをチェックしながら、競合、CAS失敗、再利用、終了、および例外をカバーします。
よくある間違い
- 間違い: 最初のロード直後にheadをデリファレンスする。 → なぜ失敗するか: 保護が公開される前にノードが回収される可能性があるため。 → 修正方法: ハザードを公開し、再度headを検証する。
- 間違い: CAS成功後に即座に削除する。 → なぜ失敗するか: 別のリーダーがまだ保護ウィンドウ内にいる可能性があるため。 → 修正方法: まずリタイアさせ、スキャンしてから回収する。
- 間違い: ハザードポインタがABAを解決すると想定する。 → なぜ失敗するか: 遅延解放は論理的なバージョンの安定性を保証しないため。 → 修正方法: バージョンカウンタまたはタグ付きポインタを追加する。
- 間違い: relaxedアトミックのみを使用する。 → なぜ失敗するか: 公開と検証が必要な順序で可視化されない可能性があるため。 → 修正方法: acquire/releaseおよびhappens-before関係を証明する。
フォローアップの質問と回答
フォローアップ 1: 公開後にheadをリロードする理由は何ですか？
最初のロードとハザードの公開の間に、別のスレッドがノードを削除して回収する可能性のあるウィンドウが存在するためです。リロードにより、そのノードが保護下にある現在のheadであることが証明されます。そうでない場合は再試行します。
フォローアップ 2: スキャン中に公開されたハザードをスキャンが見落とすことはありますか？
このプロトコルでは、リーダーが検証前に公開し、検証が失敗した場合には再試行することが義務付けられています。そのプロトコルにより、保護セットに存在しないリタイアノードのみが回収されます。保護されていない生ポインタを使用するリーダーは保証の対象外です。
フォローアップ 3: リタイアリストは無制限に肥大化する可能性がありますか？
リーダーがハザードを長時間保持している場合、スレッドが停止した場合、またはスキャンの頻度が低すぎる場合に肥大化する可能性があります。しきい値を設定し、ピークを監視し、終了時にクリーンアップを行い、必要に応じて回収スレッドが事前にスキャンできるようにします。
フォローアップ 4: エポックベースの回収（EBR）ではなくハザードポインタを選択するのはどのような場合ですか？
ハザードポインタは少数のアドレスを正確に保護し、動的な読み取りパスに適していますが、スロットのスキャンにCPUコストがかかります。エポックベースの回収は効率的にバッチ処理できますが、スレッドの遅延によって処理全体が滞る可能性があります。リーダー数、ストール許容度、メモリ制限を考慮して選択します。