プロンプトとコンテキスト
1 つのライターと 1 つのリーダーを持つ固定容量キューを実装します。満杯のときは push が失敗し、空のときは pop が失敗します。面接官は、マルチプロデューサーキューを真似るのではなく、SPSC の制約を活用した上で、インデックス、可視性、リソース回収、境界テストについて説明できるかを求めています。
面接官が見ているポイント
核心となるのは並行処理の不変条件とトレードオフです。プロデューサーは自身の tail のみを書き込み、コンシューマーは自身の head のみを書き込む必要があります。双方が相手のインデックスを読み取り、アトミック操作を使用して「データを書き込んでからインデックスを公開する」happens-before 関係を確立します。cppreference には release ストアと acquire ロード間の同期関係が記載されており、Java の VarHandle も同様に acquire、release、および volatile アクセスモードを区別しています。
最初に確認すべき明確化の質問
要素がコピーされるのかムーブされるのか、古いデータの上書きが許可されているか、容量が実行時に決定されるか、ブロッキング API が必要か、プロデューサーとコンシューマーが厳密に 1 つずつか、破棄や例外がどのように処理されるかを確認します。制約が MPSC や MPMC に変わる場合、このアルゴリズムをそのまま再利用することはできません。
30秒で答える回答の枠組み
次のように伝えます：「単調増加する head と tail のカウンターを維持し、剰余演算によってスロットにマッピングします。プロデューサーは自身のローカル tail とコンシューマーが公開した head を読み取り、空き容量を確認してスロットに書き込んだ後、新しい tail を release で公開します。コンシューマーは tail を acquire ロードし、空でないことを確認して要素をムーブし、新しい head を release で公開します。剰余演算により 2 のべき乗以外の容量も処理し、テストではラップアラウンド、満杯/空の境界、および可視性を網羅します。」
ステップごとの詳細分析
1. 不変条件を定義する
十分な幅を持つ符号なしカウンターの自然なラップアラウンドを前提として、tail - head を格納されているエントリ数として使用します。プロデューサーはその差分が容量を超えないようにする必要があり、コンシューマーは head != tail の範囲外を読み取ってはなりません。各スロットは消費される前にプロデューサーによって 1 回だけ書き込まれます。
2. ローカルインデックスと共有インデックスの分離
プロデューサーは頻繁に tail を更新し、コンシューマーは頻繁に head を更新します。それぞれが自身のインデックスを通常のローカル変数として保持できます。スレッドをまたいで相手のインデックスを読み取る際には acquire を使用し、自身の新しいインデックスを公開する際には release を使用することで、同一カウンターに対する書き込み競合を回避します。
3. push の順序で公開する
プロデューサーはコンシューマーの head をロードし、tail - head < capacity を確認します。buffer[tail % capacity] を書き込み、その後新しい tail を release ストアします。コンシューマーは acquire ロードによって新しい tail を観測した後にのみ、そのスロットを読み取ることができます。
4. pop の順序で回収する
コンシューマーはプロデューサーが公開した tail をロードし、head != tail を確認します。スロットの値をムーブした後、新しい head を release ストアします。プロデューサーは acquire ロードによって新しい head を観測した後にのみ、そのスロットを再利用できます。
5. 容量とラップアラウンドの処理
2 のべき乗の容量ではビットマスクを使用できますが、実装ではオーバーフローとビット幅の前提条件を明記する必要があります。通常の容量に対しては、% capacity の方が検証が容易です。長期稼働するカウンターには幅の広い符号なし型を使用し、インデックスを小さな整数に切り詰めるのではなく、差分を比較します。
6. 失敗、ライフタイム、テストの定義
満杯時は false を、空時は empty を返し、スピン待機は行いません。要素の書き込みが失敗した場合は tail を公開してはなりません。要素のムーブや破棄には、明示的な型制約または回復ルールが必要です。容量 1、容量 + 1、繰り返しのラップアラウンド、プロデューサーとコンシューマーの速度差、満杯/空のエッジケース、およびシャットダウン時の残存要素をテストします。
質の高い模範解答
push(x):
t = tail.load(relaxed)
h = head.load(acquire)
if t - h == capacity: return false
buffer[t % capacity] = x
tail.store(t + 1, release)
return true
pop():
h = head.load(relaxed)
t = tail.load(acquire)
if h == t: return empty
x = move(buffer[h % capacity])
head.store(h + 1, release)
return xhead と tail はアトミックカウンターです。プロデューサーは tail のみに書き込み、コンシューマーは head のみに書き込みます。通常のバッファ書き込みは tail の release 公開の前に発生（happens-before）するため、コンシューマーの acquire ロードによって要素が可視化されます。逆方向の head の release により、プロデューサーはスロットを安全に再利用できます。2 のべき乗以外の容量には剰余演算を使用し、マスクは 2 のべき乗とオーバーフローの追加前提がある場合のみ使用します。このバージョンは SPSC であり、一般的なマルチライターまたはマルチリーダーキューではありません。
よくある間違いと改善策
- 両方のスレッドが 1 つのインデックスに書き込む： SPSC の所有権を明示し、制約が変更された場合は専用の MPSC/MPMC アルゴリズムに切り替えます。
- 要素を書き込む前に公開する： 先にスロットへ書き込み、最後にインデックスを release 公開します。
- すべてに relaxed を使用する： Relaxed はアトミック性を保証しますが、通常データの公開は保証しません。スレッド間のインデックスには acquire/release が必要です。
- すべての容量が 2 のべき乗であると決めつける： 未検証のマスクを使うのではなく、通常の容量には剰余演算を使用します。
フォローアップ質問と回答
なぜローカルインデックスの読み取りに relaxed を使用できるのですか？
プロデューサーは自身の tail のみを変更し、コンシューマーは自身の head のみを変更するため、ローカルな読み取りは相手スレッドと同期する必要がありません。相手のインデックスを読み取る場合は、可視性も提供するため依然として acquire が必要です。
参照値のスロットはいつ再利用できますか？
コンシューマーが値のムーブまたは破棄を完了し、新しい head を release 公開した後にのみ再利用できます。プロデューサーはスロットを上書きする前にその値を acquire ロードする必要があります。コンシューマーが処理を開始したのを確認するだけでは不十分です。
複数のプロデューサーに対応するにはどう拡張しますか？
複数のプロデューサーが同じ tail に直接書き込むことはできません。CAS ベースのシーケンス予約、スロットごとのシーケンス番号、またはロックが必要となり、予約、公開、回収の順序を再検証する必要があります。SPSC コードを一般的なキューとして提示してはなりません。
最適化によって高速化されたことをどのように確認しますか？
同一の要素サイズ、スレッドアフィニティ、バッチサイズ、負荷の下で、スループット、p99 レイテンシ、コンテキストスイッチ、キャッシュミスを比較します。プロデューサーが頻繁にコンシューマーに追いつく場合は、メモリ順序付けを弱めることよりも、容量、バッチ処理、またはバックプレッシャーの方が重要になる可能性があります。