プロンプトとコンテキスト
複数のプロデューサーとコンシューマーが固定容量のインメモリキューを共有します。プロデューサーは未消費のアイテムを上書きしてはならず、コンシューマーは未公開のアイテムを読み取ってはなりません。ファストパスはミューテックスを回避し、フル状態および空状態では待機できるようにする必要があります。スロットのレイアウト、enqueue/dequeueの位置、メモリ順序、およびクローズ時の動作を設計してください。
面接官が評価するポイント
- 空、予約済み、公開済み、消費済みの各状態を区別するために、単調増加する位置とスロットごとのシーケンスを使用しているか。
- CASおよびacquire/releaseによって、非アトミックなペイロードデータが正しく可視化されているか。
- 2の累乗以外の容量、プロデューサーとコンシューマーの競合、および偽共有（false sharing）を適切に処理しているか。
- 待機、タイムアウト、クローズ、メモリ解放（reclamation）、およびABA問題の境界について説明できるか。
明確化のための質問
- 要素は固定サイズオブジェクト、ムーブ可能なオブジェクト、または外部所有権を持つポインタのいずれですか？
- フルおよび空の際、即時復帰、ブロック、タイムアウトのどれを行うべきですか？
closeの後、コンシューマーはエンキュー済みの要素をすべて取り出す（ドレインする）ことができますか？- ランタイムはC++20の
atomic::waitおよびnotifyを提供していますか？ - キューはプロセスローカルですか、それともプロセス間で共有されますか？
30秒での回答
単調増加するenqueueおよびdequeue位置を保持し、各スロットに絶対位置に紐づくシーケンスを持たせます。プロデューサーはCASで位置を予約し、非アトミックなペイロードを書き込み、公開されたシーケンスをreleaseストアします。コンシューマーはそのシーケンスをacquireロードし、ペイロードを読み取ってから、次の書き込み可能シーケンスをreleaseストアします。シーケンスの差によってフル状態と空状態を区別します。ファストパスが失敗した場合はatomic::waitまたは有界バックオフで待機し、クローズ状態は戻り値のコントラクトの一部として扱います。
詳細な回答
ステップ 1: スロットと位置の設計
容量Nに対して、単調増加するenqueuePosとdequeuePosを維持し、剰余演算（modulo）を用いて位置をスロットにマッピングします。各スロットにはsequenceとペイロードが含まれます。シーケンスはスロットの周回（ラウンド）を保持するため、インデックス単体で古いデータと新しいアイテムを取り違えることはありません。2の累乗以外の容量の場合は、ビットマスクではなく安全な剰余演算を使用します。
ステップ 2: プロデューサーの位置予約
プロデューサーは候補位置のシーケンスを読み取ります。それが期待される書き込み可能値と一致する場合、スロットは利用可能であり、プロデューサーはCASを用いてenqueuePosの獲得を競います。CASが失敗した場合は再ロードしてリトライします。シーケンスが期待値より遅れている場合、キューがフルである可能性があるため、将来の位置へ進むのではなく、フルを返すか待機またはタイムアウトします。
ステップ 3: ペイロードの公開
位置を予約した後、プロデューサーはそのスロットを排他的に所有し、ペイロードを書き込みます。その後、「この位置で公開された」ことを意味するシーケンスをreleaseストアします。コンシューマーは非アトミックなペイロードを読み取る前にシーケンスをacquireロードしなければなりません。アトミックなインデックスだけでは、オブジェクトの初期化が可視化されていることを保証できません。
ステップ 4: 消費と解放
コンシューマーも同様にCASでdequeuePosを予約します。スロットのシーケンスが期待される公開値と等しい場合にのみ読み取りが可能です。読み取り後、次の書き込み可能ラウンド用のシーケンスをreleaseストアします。次のプロデューサーは、スロットを上書きする前にその値をacquireロードします。
ステップ 5: メモリ順序と偽共有の定義
位置のCASはアトミックなインデックス更新を提供し、公開シーケンスと解放シーケンスに対するrelease/acquireはペイロードに対するhappens-before関係を構築します。relaxed操作のみでは未公開データが公開されてしまう可能性があります。プロデューサーとコンシューマーの位置、および頻繁にアクセスされるシーケンスを別々のキャッシュラインに配置し、書き込みによる無効化を低減します。
ステップ 6: 待機とクローズの処理
ファストパスが進行できない場合、atomic::waitを使用して位置またはシーケンス上で待機します。enqueueまたはdequeueが成功するとnotify_oneまたはnotify_allが呼び出されます。ループではタイムアウトと偽の起床（spurious wakeup）を処理する必要があります。クローズはアトミックに公開します。プロデューサーは新しいアイテムを拒否し、コンシューマーはコントラクトに従って公開済みスロットをドレインするか、クローズ状態を返します。
ステップ 7: 競合とライフサイクルのテスト
容量1、2の累乗以外の容量、スロット数を超えるプロデューサーやコンシューマー、長期のフル/空の反復、およびランダム化された遅延をテストします。シーケンス番号を使用して、欠落なし、重複なし、FIFOの保証、およびクローズ時のドレインを検証します。データ競合を検出するためにThreadSanitizerとストレステストを実行します。ペイロードがポインタの場合は、所有権と回収のタイミングを明確にします。
模範解答
各スロットはペイロードと単調増加するシーケンスを保持し、キューは単調増加するenqueueおよびdequeue位置を保持します。プロデューサーはシーケンスが現在の書き込み可能値と等しい場合にのみCASで予約し、ペイロードを書き込んだ後、シーケンスをrelease公開します。コンシューマーは公開された値をacquire観測し、ペイロードを読み取ってから、次の書き込み可能値をreleaseストアします。シーケンスのラウンドによって空、フル、再利用されたスロットを区別し、剰余演算により2の累乗以外の容量を処理します。キャッシュラインを分離することで偽共有を抑制します。ファストパスが失敗した場合は、タイムアウトおよび偽の起床対策ループを備えたatomic::waitを使用します。クローズ時は新規プロデューサーを拒絶し、コントラクトに従って公開済みアイテムをドレインします。ストレステスト、ThreadSanitizer、シーケンス検証により、競合とライフサイクルを網羅します。
よくある間違い
- headインデックスとtailインデックスのみを使用し、スロットのラウンドや古いデータを区別できない。
- プロデューサーが予約した後、ペイロードを公開する前にコンシューマーが読み取ってしまうことを許す。
- ペイロードに対するacquire/releaseの可視性を確保せず、relaxed公開を使用する。
- キューがフルになった後も位置の予約を続け、未消費のデータを上書きしてしまう。
atomic::waitループにおける偽の起床、タイムアウト、およびクローズ処理を無視する。- 2の累乗以外の容量、偽共有、またはポインタの回収を考慮し忘れる。
フォローアップの質問
フォローアップ 1: なぜすべてのスロットにシーケンスが必要なのですか？
インデックスはラウンドを越えて再利用されます。シーケンスはスロットを絶対位置に紐づけ、書き込み可能、公開済み、次ラウンドの各状態を区別して、古い値が受け入れられるのを防ぎます。
フォローアップ 2: なぜペイロードのみをアトミックにしないのですか？
ペイロードは複合オブジェクトの場合があります。アトミックなインデックスだけでは初期化が可視化されたことにはなりません。releaseによる公開とacquireによる観測が、非アトミックなペイロード全体の可視性を確立します。
フォローアップ 3: 失敗したCASはどのくらいスピンすべきですか？
普遍的な値はありません。短い競合に対しては少しスピンし、その後yieldするか通知を待ちます。コア数、容量、レイテンシ目標に応じた負荷テストによってポリシーを調整します。
フォローアップ 4: アイテムを失わずにクローズするにはどうすればよいですか？
まず新規プロデューサーを停止し、次に公開済みスロットをacquire観測してドレインします。コンシューマーは、位置が収束し、予約スロットを保持するプロデューサーがいなくなった後にのみクローズを返します。
フォローアップ 5: これは常にロックフリーですか？
ファストパスはミューテックスを回避しますが、atomic::waitはランタイムスレッドをブロックする可能性があります。すべてのパスがロックフリーであると保証するのではなく、オプションのブロッキング待機を備えたロックフリーデータ構造として正確に説明してください。
フォローアップ 6: ABAリスクをどのようにテストしますか？
単調増加する位置と各スロットのラウンドシーケンスを使用し、ラップアラウンド、スレッドの遅延、繰り返されるCASに負荷をかけます。スロットのラウンドが進んだ後に、古い観測値が再び適格と判定されてはなりません。