プロンプトとコンテキスト
コネクションプールまたはタスクエグゼキューター向けの非同期セマフォを実装してください。容量 N で開始します。許可が利用できない場合、acquire() はキューに並び、release() は許可を1つ返却します。ウェイターはタイムアウトするか、キャンセルされる場合があります。キャンセルによってゴーストキューエントリが残ったり、他のウェイターの進行が妨げられたりしてはなりません。多重解放、クローズ時の挙動、および公平性を定義してください。
この問題は、並行性、ランタイム、およびバックエンドインフラの面接に適しています。Oracleの Semaphore APIは、許可、オプションの公平なFIFO選択、および中断可能な取得を定義しています。Pythonの asyncio のドキュメントでは、acquireで減少しreleaseで増加するカウンターを説明し、通常のセマフォと制限付き（bounded）セマフォを区別しています。公開されている面接の議論では、計数セマフォや並行数制限がオペレーティングシステムの面接トピックとして挙げられています。これらのソースは代表性を裏付けていますが、特定の企業の固定された出題内容や頻度を確定するものではありません。コアスキルが状態の不変条件、キューのクリーンアップ、キャンセルの競合、および検証可能な並行実装であるため、カテゴリーは coding です。
面接官が評価するポイント
第一に、候補者が許可の所有権を定義しているか。取得に成功した場合は、厳密に1回だけ返却できるトークンを作成する必要があります。キャンセルまたはタイムアウトしたリクエストはトークンを持たないため、releaseを呼び出してはなりません。
第二に、公平性が本物であるか。キューが空でない場合、後続のreleaseによって後から来た高速パス（fast path）が先頭を追い越してはなりません。そうでなければ、高負荷時に古いウェイターが飢餓状態（starvation）に陥る可能性があります。FIFOの公平性を保つには、キューの確認、許可の割り当て、およびウェイターの起床を単一の同期境界内で実行する必要があります。
第三に、キャンセルと起床の競合を処理できるか。ウェイターがすでにreleaseによって選択された後にタイムアウトする場合や、releaseがウェイターを削除する前にタイムアウトする場合があります。両方のパスが単一の状態遷移を巡って競合し、ウェイターを最大1回だけ完了させる必要があります。
最後に、テストが単なる順次的なacquire/releaseだけでなく、並行数制限、FIFO順、タイムアウトのクリーンアップ、キャンセル後の進行、多重解放、クローズ、およびタスクの失敗をチェックしているか。
最初に確認すべき明確化のための質問
- 公平性は厳格なFIFOですか、それともベストエフォートですか？ 厳格なFIFOは飢餓を防ぎますが、スループットが犠牲になる可能性があります。
- acquireは何を返しますか？ 解放トークンまたはリース（lease）は、所有権を1回の成功した取得に結び付け、誤った解放を減らします。
- 許可が割り当てられた後にキャンセルが発生した場合はどうなりますか？ 完了の優先順位を定義します。Promiseが解決されると、呼び出し元がリースを所有し、キャンセルはそれ以降の作業にのみ影響します。
- acquireの回数を超えてreleaseすることはエラーですか？ 制限付きセマフォはそれを拒絶または報告すべきです。暗黙にカウントを増やすと容量違反になります。
- closeはウェイターをどのように終了させますか？ closeは新しいリクエストを拒絶し、キューに入っているウェイターを明確なClosedエラーで終了します。保持されているリースは引き続き安全に解放できます。
30秒の回答フレームワーク
「私は available、FIFOウェイターキュー、およびクローズ状態を維持し、すべての変更を単一のクリティカルセクション内で行います。acquireはキューが空の場合にのみ高速パスを利用でき、ウェイターが存在する場合は後続の呼び出し元はキューに入ります。releaseは最初の有効なウェイターを見つけ、1つの許可を譲渡し、それを1回だけ完了させます。有効なウェイターが存在しない場合にのみ、available をインクリメントします。各ウェイターはキャンセル状態と1回限りの完了処理を持ちます。タイムアウトとreleaseはその同じ状態で競合します。取得に成功すると、1回だけ解放できるリースが返されます。テストでは、FIFO、同一境界でのキャンセルとrelease、タイムアウト後の許可の回収、多重解放、クローズ、および並行数制限を強制的に検証します。」
ディープダイブ回答
1. コアとなる不変条件の明示
容量 N に対して、available + held + reserved = N を維持します。available は即時割り当てが可能で、held はリースを通じて呼び出し元に属し、reserved はavailableから、コールバックがまだ完了していない選択されたウェイターに移動した状態です。
各ウェイターは、pending（保留中）、fulfilled（充足済み）、またはcancelled（キャンセル済み）のいずれか1つの終端状態を持ちます。キャンセルされたウェイターは許可を所有せず、充足されたウェイターは必ずリースを生成しなければなりません。クローズしても保持されているリースは回収されませんが、新規の取得は防止されます。
2. 公平な高速パスとキュー
waiters が空でセマフォが開いている場合、acquireは available を直接消費できます。キューが空でない場合は、たとえ available > 0 であっても新しい呼び出し元はキューに並びます。そうしないと、古い呼び出し元を追い越してしまいます。acquireとreleaseは同じ同期境界の下でキューをチェックする必要があります。
キューノードは、ウェイターのPromise、キャンセル状態、タイマーハンドル、および1回限りの完了関数を格納します。完了またはキャンセルされたノードを削除するか、releaseが先頭で遅延スキップするトゥームストーン（tombstone）を保持します。どちらの戦略でも、有効なウェイターが無効なノードの後ろに永久に残されないことの証明が必要です。
3. releaseにおける許可の譲渡
releaseはまずリースがまだ解放されていないことを検証し、次に最初の有効なウェイターに許可を渡します。許可はheldからreservedに変わり、ウェイターの完了処理が呼び出されます。新しいacquireが割り込む可能性があるため、availableをインクリメントして非同期に検索してはなりません。
先頭がキャンセルされている場合は、それをスキップしてクリーンアップし、次のウェイターに進みます。有効なウェイターが存在しない場合にのみ、available += 1 とすべきです。制限付きセマフォはNを超える解放を拒絶し、呼び出し元のバグによってリークや二重返却が隠蔽されないようにします。
4. キャンセルとタイムアウトの競合
キャンセルとreleaseは、両方とも同じウェイターを終了させようとする可能性があります。ワンショットCAS、ロック内の状態チェック、または同等のメカニズムを使用して、どちらか一方のみが勝つようにします。キャンセルが勝った場合は、許可を所有したことがないため、availableを変更せずにウェイターを削除します。releaseがすでに許可を予約している場合、キャンセルがその許可を返却しつつreleaseが同じウェイターを完了させるという両方の処理を行うことはできません。
シンプルなルールは、releaseがPromiseを解決する前に、クリティカルセクション内でウェイターをfulfilledとしてマークすることです。一度fulfilledになると、タイムアウトは呼び出し元が以降の作業を破棄したことのみを記録できます。呼び出し元は受け取ったリースを依然として解放します。より高度な設計では未配信の予約を回収することもありますが、その回収は拒否されたPromiseから推測するのではなく、同じ状態マシンに属させる必要があります。
5. リースと多重解放
released フラグを持つリースを返します。lease.release() はfalseからtrueへ1回だけ遷移できます。重複した呼び出しは冪等な結果または明確なエラーを返します。2つの許可を追加することはできません。APIが呼び出し元所有のカウンティングモデルを明示的に使用していない限り、任意の呼び出し元に単純なreleaseメソッドを公開すると所有権の関連付けが失われます。
6. クローズ、障害、およびバックプレッシャー
クローズ後は、新しいacquireを拒絶し、キューに入っているウェイターをClosedで終了します。リースを保持しているタスクは完了して解放できます。セマフォが閉じているという理由だけでreleaseが許可を破棄してはならず、さもなければheldのカウントが説明できなくなります。タスクが失敗した場合でも、finally で解放されます。
セマフォは並行性を制限するものであり、キューの長さを制限するものではありません。無制限のウェイトキューは、バックプレッシャーをメモリ肥大化へと変化させます。本番コードでは、最大待機数、タイムアウト、または拒絶ポリシーを設定し、待機時間、キャンセル率、およびキューの深さを記録する必要があります。
7. スケジューラによる競合の制御
実際のsleepで競合を証明しようとしないでください。手動クロックと制御可能なスケジューラを使用して、キューイング、releaseによるウェイターの選択、およびタイムアウトコールバックがキューに入ったがまだ実行されていない状態の各ポイントで一時停止します。各ステップで、available、held、有効なウェイター数、およびリースの所有権をアサートします。
無効なN=0の初期化、N=1での厳格なFIFO、複数の許可、先頭および中間のウェイターのキャンセル、同一境界でのタイムアウトとrelease、多重解放、クローズ前後のacquire、タスクの失敗、および長時間待機している呼び出し元の飢餓がないことを網羅します。
質の高い模範解答
「私は許可の所有権をリース内にカプセル化します。セマフォは available、FIFOウェイター、およびクローズ状態を保持し、すべての遷移は1つの同期境界を共有します。acquireはキューが空の場合にのみ高速パスを取り、ウェイターが存在する場合は後続の呼び出しはキューに並びます。
releaseはリースが1回だけ解放されたことを検証し、最初の有効なウェイターを見つけ、heldをそのウェイターの予約に譲渡し、それを1回だけ完了させます。キャンセルされた先頭ノードをスキップしてクリーンアップし、有効なウェイターが存在しない場合にのみavailableを増やします。キャンセルとタイムアウトは同じウェイター状態上でreleaseと競合し、ワンショットの遷移によって勝者が決定されます。acquire前のキャンセルは許可を所有せず、完了したacquireは呼び出し元にリースを付与し、キャンセルがそれを上書きすることはできません。
closeは新しいリクエストを拒絶し、キューに入っているウェイターを終了させますが、保持されているリースは引き続き解放できます。テストでは手動クロックとスケジューラを使用して、FIFO、先頭および中間のキャンセル、タイムアウトとreleaseの同時発生、多重解放、失敗後のfinallyクリーンアップ、および並行数制限を強制的に再現します。カウンターの不変条件により、許可の喪失や不正生成がないことが証明されます。」
よくある間違い
- キューが空でないのに高速パスを取る → 新しい呼び出し元が古い呼び出し元を追い越して飢餓状態にさせる → ウェイターが存在する間はすべての呼び出し元をキューに並べる。
- ウェイターがキャンセルされたときにavailableをインクリメントする → releaseがすでにその許可を予約している可能性がある → キャンセルとreleaseを単一のワンショット状態で競合させる。
- 所有者のないreleaseを公開する → 重複呼び出しによって許可が不正に生成される → 1回だけ解放できるリースを返す。
- 先頭を起床させる前にavailableをインクリメントする → 新しい呼び出し元が割り込む可能性がある → 同じクリティカルセクション内で直接譲渡する。
- タイムアウトを配信済みリースのロールバックとして扱う → タスクがまだ実行中である可能性がある → 待機中のキャンセルと取得済み許可を区別する。
- 無制限のキューを許可する → 並行数制限がメモリリークを引き起こす → キューの上限、タイムアウト、または拒絶ポリシーを設定する。
- 順次呼び出しのみをテストする → キャンセルの競合や多重解放の検証が漏れる → 制御可能なスケジューラでインターリーブを強制する。
- クローズ時に保持されている許可を破棄する → リソース数が収束しなくなる → 保持されているリースをfinallyで解放できるようにする。
フォローアップの質問と回答
FIFOの公平性は常に優れていますか？
いいえ。FIFOは飢餓を防ぎ、説明が容易ですが、実行時間が長い先頭やタイムアウト間近の先頭によってHead-of-Lineブロッキングが発生する可能性があります。スループット優先の実装では非公平な高速パスを許可することもありますが、飢餓、最大待機時間、および優先度は、想定される暗黙の性質ではなく明示的なコントラクトの選択である必要があります。
一度に複数の許可を取得するにはどうすればよいですか？
各ウェイターのリクエスト数を記録し、availableが十分に大きくなった場合にのみ充足します。厳格なFIFOでは、複数許可を待つ先頭の後ろにある1許可のリクエストが待たされる可能性があります。追い越しを許可すると公平性が犠牲になります。1つのポリシーを選択し、不変条件ではウェイターオブジェクトではなく予約された許可数をカウントします。
タスクが処理の途中でキャンセルされた場合はどうなりますか？
セマフォは許可を所有しますが、タスクの中断を制御するわけではありません。呼び出し元はキャンセル時に作業を停止し、finallyでリースを解放する必要があります。作業を中断できない場合は、解放する前に完了しなければなりません。セマフォは、まだ使用中の許可を回収してはなりません。
セマフォとミューテックスの境界線は何ですか？
セマフォは利用可能なリソースの数を表し、異なるアクターが許可を取得および解放できます。ミューテックスは排他的な所有権を表し、通常は所有者がロックを解除する必要があります。値が1のセマフォは排他制御を模倣できますが、所有権チェックや優先順位セマンティクスが失われるため、APIコントラクトに一致するプリミティブを選択してください。