プロンプトと適用コンテキスト
送金サービスが時折フリーズします。スレッドAは口座42のロックを保持して口座84を待機し、スレッドBは口座84を保持して口座42を待機しています。どちらのスレッドも最初のロックを解放しません。これはデッドロックですか？4つの必要条件を説明し、防止、検知、復旧、検証を設計してください。
これは、並行処理コードを記述するバックエンド、システム、インフラ、SRE、その他の役割を対象とした、ソフトウェアエンジニアリングおよびオペレーティングシステムの一般的な質問です。2026年時点の英語および中国語の面接資料でも、定義、4つの必要条件、対処戦略について個別に問われ続けています。本記事は特定の企業への帰属を行わず、根拠のない面接頻度を主張することもありません。
口座42と84は架空の識別子です。この課題は単に4つの名前を暗記して暗唱するだけにとどまりません。優れた回答は、長時間の待機と解消不可能な待機サイクルを区別し、理論をロックプロトコル、ランタイム証拠、障害復旧、テストへと結びつけます。主な対象範囲は単一インスタンスのミューテックスとデータベースの行ロックです。分散リース、ネットワーク分断、コンセンサスアルゴリズムは最初の回答の範囲外とします。
面接官が評価するポイント
第一の評価基準は、診断に待機関係を用いているかどうかです。CPU使用率の低下、リクエストのタイムアウト、あるいは2つのブロックされたスレッドは進捗がないことを示しますが、それ単体ではデッドロックの証明にはなりません。優れた回答では、ノードをスレッドまたはトランザクション、エッジを「〜が所有するリソースを待機している」とする待機グラフ（wait-for graph）を構築し、サイクルを探します。
第二の評価基準は、4つの必要条件（相互排他、保持と待機、非横取り、循環待機）の正確な適用です。これらはデッドロックが発生し得る理由を説明します。各条件を送金処理のパスに対応付けずに列挙するだけでは、単なる丸暗記の回答にとどまります。
第三の評価基準は、証明可能なグローバル不変条件を持つ防止戦略です。実践的な選択肢は、多くの場合、すべてのエントリーポイントで強制される、あらゆるロックに対する安定した全順序付けです。1つの関数内で2行を入れ替えるだけでは不十分です。バッチジョブ、返金処理、修復ツール、将来追加されるパスのいずれかが逆順でロックを取得すれば、サイクルが再生成される可能性があります。
最後に、面接官は復旧の境界を評価します。データベースはサイクルを検知してトランザクションをロールバックできます。一方、プロセス内ミューテックスは、中断されたコードが不変条件の半分しか変更していない可能性があるため、通常は安全に奪取して実行を再開することができません。優れた回答は、防止、回避、検知、復旧を区別し、タイムアウトのコストを明確にし、ストレステストで偶然発生するのを期待するのではなく、そのインターリーブを再現します。
回答前に確認すべき明確化のための質問
- すべてのリソースは単一インスタンスのミューテックスですか？ 単一インスタンスリソースの待機グラフにおけるサイクルは、そのグループが進捗できないことを証明します。あるリソースタイプに複数のインスタンスがある場合、リソース割り当てグラフ内のサイクルは可能性を示すに過ぎず、利用可能なインスタンスと残りの要求量も考慮する必要があります。
- ロックはリエントラント（再入可能）ですか？ 同一スレッドで非リエントラントロックを再取得すると、セルフデッドロックが発生する可能性があります。送金元と送金先が同一口座の場合、ソートによって重複が処理されると仮定せず、ロック取得前に重複を排除してください。
- 両方の口座変更はロールバック可能な単一のトランザクション内で行われますか？ トランザクション境界があれば、被害者（victim）を中断して再試行できます。外部への支払い送信やメール送信をすでに行ったフローでは、盲目的な再試行ではなく、冪等性キーやコミット後のアウトボックスパターンが必要です。
- すべての取得パスで1つの順序付けルールを共有できますか？ 共有できる場合は、グローバルな順序付けを優先します。サードパーティ製コンポーネントやクロスサービスのリソースがそのプロトコルに参加できない場合は、同時所有を減らすか、所有権の設計を見直すか、安全な境界の周囲に検知とロールバックを配置します。
- リクエストはどのくらい待機可能で、タイムアウトは何を意味しますか？ ロックのタイムアウトはテールレイテンシを抑えますが、正当な遅いリクエストを終了させてしまう可能性があります。呼び出し元は、その操作が再試行可能なのか、確定的なのか、結果が不明なのかを知る必要があります。
- ランタイムはどのような診断機能を公開していますか？ JVMのスレッド管理、データベースの待機ビュー、カーネルのロックバリデータは、それぞれ異なるロッククラスをカバーします。あるツールで報告がないからといって、非同期待機、仮想スレッド、または外部リソースが潔白であるとは限りません。
- クリティカルセクションはネットワーク、ディスク、またはユーザー制御の操作を呼び出していますか？ 境界のない依存関係は所有期間を延ばし、ブロッキングを増幅させます。整合性プロトコルが明示的に待機を要求し、その障害を処理する場合を除き、それらを外に移動してください。
30秒の回答フレームワーク
「これはデッドロックです。AはBが84を解放するのを待ち、BはAが42を解放するのを待っているため、待機グラフには A → B → A が含まれます。このケースには、相互排他、保持と待機、非横取り、循環待機の4つすべてが存在します。口座IDの重複を排除し、すべての口座ロックを昇順の安定した順序で取得し、逆順で解放することで、プロトコルによって循環待機を排除します。本番環境では、スレッドやデータベースの待機データからサイクルを確認します。データベースの被害者はロールバックして制限付きで再試行し、プロセス内デッドロックの場合は診断情報を保存した上で、安全な状態境界でのみ復旧します。バリアテストを用いて従来のインターリーブを決定論的に再現し、順序付けされたバージョンが残高の不変条件を維持することを検証します。」
完全な回答には、順序付けがサイクルを排除する理由、タイムアウトが証明にならない理由、検知器がカバーする待機の範囲、復旧によって外部の副作用が重複しないかどうかも追加する必要があります。
ステップバイステップの詳細な回答
ステップ1: 症状から診断するのではなく待機サイクルを証明する
ランタイムの状態を待機グラフとして表現します。スレッドAはロック42を保持し、Bが所有する84を要求しているため、A → B を追加します。スレッドBは84を保持し、Aが所有する42を要求しているため、B → A を追加します。各スレッドは2つ目のロックを取得した後にのみ最初のロックを解放します。サイクル内のどのノードも最初に完了することができないため、このグループは自力で進捗することができません。
本番環境の診断には、ほぼ同一時刻における所有者、待機者、スタックトレースが必要です。単一のスレッドダンプでは無害な競合を捉えてしまう可能性があります。同一のスタックとエッジを持つスナップショットが繰り返し取得されることで、より強力な証拠となります。通常の長い待機には戻りエッジがありません。AがBを待機していても、Bが実行中で最終的にリソースを解放する可能性があります。遅いロックをすべてデッドロックと呼ぶと、キャパシティや依存関係のレイテンシをロックプロトコルのバグと誤診することになります。
グラフによる結論にはモデルの境界があります。各ミューテックスの所有者が1人である場合、待機サイクルはそれらのスレッド間におけるデッドロックの十分条件となります。リソースカテゴリに複数のインスタンスがある場合、リソース割り当てグラフ内のサイクルは証明ではなくリスクを示します。外部のインスタンスが解放され、参加者が続行できる可能性があるためです。その場合、利用可能量、割り当て済み量、最大残余需要の分析が必要になります。
ステップ2: 4つの必要条件をコードに対応付ける
この送金処理において、4つの条件は具体的に次の通りです。
- 相互排他（Mutual exclusion）: 一度に1つのスレッドのみが口座の書き込みロックを所有する。
- 保持と待機（Hold and wait）: Aは42を保持しながら84を要求し、Bは84を保持しながら42を要求する。
- 非横取り（No preemption）: ランタイムは所有者から口座ロックを安全に奪取せず、所有者自身が解放する。
- 循環待機（Circular wait）: AがBを待ち、BがAを待つ。
このデッドロックが発生するとき、すべての条件が存在しており、いずれか1つを破ることでこのクラスのデッドロックを防止できます。「システムがミューテックスを使用している」または「コードがロックをネストしている」ことを、アクティブなデッドロックの証明として扱わないでください。必要条件はデッドロックを許容する要因を説明するものであり、ランタイム状態には依然として解消不能なサイクルが必要です。
相互排他は残高の不変条件を保護している可能性があるため、それを排除して共有状態を競合させることは解決策になりません。安全な横取り（プリエンプション）も、通常のインメモリクリティカルセクションでは困難です。エンジニアリングシステムでは、循環待機を排除するか、ロールバック可能な境界において1つのトランザクションを検知して中止することが多くなります。
ステップ3: グローバルなロック順序により循環待機を排除する
一緒に保持される可能性のあるすべてのロックに対して、リソースタイプのランクに続いてリソースIDを指定するなど、全順序を定義します。口座ロックのみが関係する場合は、口座IDでソートします。送金元と送金先が同一である送金を処理するため、最初に重複を排除します。順序通りに取得し、クリティカルセクション内では検証と状態変更のみを実行し、逆順で解放します。
言語非依存の疑似コード：
transfer(fromid, toid, amount): ids = unique(sortascending([fromid, to_id])) acquired = [] try: for id in ids: acquired.append(lock_account(id)) validateandapplytransfer(fromid, to_id, amount) finally: for lock in reverse(acquired): unlock(lock)
正当性の論証は簡潔です。低いランクのロックを保持するスレッドが、より高いランクのロックのみを待機できる場合、待機サイクルにはランクが厳密に増加することが必要になります。
r1 < r2 < … < rn < r1
厳密な順序付けでは開始点に戻ることはできないため、循環待機は不可能です。この証明は、すべてのパスが同一の順序に従うことに依存します。ある副次的なパスで、リクエスト順、リストの反復順、またはデータベースの返却順に取得すると、不変条件が無効になります。
逆順での解放はネストされた所有権の把握を容易にしますが、サイクルを防ぐ要因そのものではありません。より重要なルールは、ロックを保持している間にリモート呼び出し、ユーザー入力、境界のないI/Oを避けることです。長いクリティカルセクションはデッドロックしなくても、競合、タイムアウト、復旧コストを増大させます。
ステップ4: 他の戦略が適するタイミングを把握する
処理を行う前にすべてのリソースを要求することで「保持と待機」を破ることができますが、呼び出し元は事前に完全なセットを把握している必要があります。また、セットが大きいと所有期間が長くなり、並行性が低下します。これは既知の小さなロックセットには適していますが、探索によってリソースが段階的に発見される場合には適していません。
デッドロック回避（Deadlock avoidance）は、要求の許可が安全な状態を維持するかどうかを問いかけます。銀行家アルゴリズム（Banker's algorithm）は事前に最大需要を把握している必要があり、利用可能、最大、割り当て済み、残余のリソースを追跡します。動的なWebリクエストが後でアクセスするすべてのオブジェクトを事前に把握していることは稀であるため、このアルゴリズムは安全な状態を説明するには有用ですが、通常はアプリケーションコードに組み込まれません。安全な状態は完了シーケンスを保証します。安全でない状態はデッドロックにつながる可能性がありますが、すでにデッドロックしているわけではありません。
共有ミュータブル状態を減らす、単一の所有者を割り当てる、または実績のある並行コンテナを使用することで、手動のロックパスを排除できます。ただし、これによって「メッセージングならデッドロックしない」とは言えません。2つの有界キューが互いの容量を待機する可能性があり、単一のエグゼキュータ内のタスクが結果を循環的に待機する可能性もあります。代替手段でも依然として待機グラフの考慮が必要です。
try-lockとタイムアウトは損失を伴う脱出メカニズムであり、非巡回プロトコルの証明ではありません。タイムアウトパスが部分的な状態をロールバックし、保持されているすべてのロックを解放すれば、閾値後に「保持と待機」を破り、このサイクルを解消します。しかし、閾値に達するまでリクエストは停滞し、短い閾値は正当な処理を中止してしまいます。双方が同時にタイムアウトして再試行するとライブロックが発生する可能性があります。最大試行回数、ランダムなバックオフ、冪等性セマンティクス、および終端エラーを使用してください。
ステップ5: 各検知器が実際にカバーする範囲を把握する
JVMのThreadMXBeanは、オブジェクトモニターまたは所有可能なシンクロナイザを待機しているプラットフォームスレッド間のサイクルを検出し、そのIDを返すことができます。Java SE 25のドキュメントには、仮想スレッドを含むサイクルはこのメソッドでは検出されないこと、およびこの操作は同期の制御ではなくトラブルシューティングを目的としていることが明記されています。結果がnullであっても、それは検知器のカバー範囲内に問題がないことを意味するに過ぎません。
Linuxカーネルのlockdepは、ロッククラス間で観測された取得依存関係を記録します。実行によって L1 → L2 および L2 → L1 が露呈した場合、その実行で偶然フリーズしなかったとしても、潜在的な逆転を報告できます。これは、開発環境やテスト環境で順序付けプロトコルを検証する方法を示しています。アプリケーションコードは、すべてのランタイムが同じバリデータを提供していると仮定することはできません。
PostgreSQLはトランザクションのデッドロックを自動的に検知し、他のトランザクションが続行できるように関係するトランザクションの1つを中止します。そのドキュメントには、どのトランザクションが被害者になるかを予測するのは困難であると記載されているため、ビジネスロジックは「新しいリクエストが常に負ける」という前提に依存してはなりません。またPostgreSQLは、アプリケーション全体で一貫した取得順序を採用すること、および完全な防止が不可能な場合は中止されたトランザクションを再試行することを推奨しています。
本番環境のシグナルには、ロック待機時間、ロック保持時間、デッドロック数、ロールバックされたトランザクション数、再試行回数、終端障害を含める必要があります。診断レコードは、完全な口座データ、クエリパラメータ、機密ペイロードをログに出力することなく、待機者、所有者、ロッククラス、スタックトレースを関連付ける必要があります。
ステップ6: リソースの整合性境界で復旧する
データベースが被害者を選択した後、トランザクション全体をロールバックし、状態を再読み込みして、再度実行します。「最初のロックの後」から再開してはなりません。再試行回数を制限し、ランダムな遅延を追加します。重複リクエストが届く可能性がある場合は、ビジネス冪等性キーを使用します。データベースのロールバックはすでに発行された副作用を取り消せないため、コミット後に冪等なアウトボックスなどのパスを介してメール、メッセージング、または外部決済をトリガーします。
プロセス内スレッドがミューテックスで停止している場合、1つのスレッドを強制終了すると、インメモリの不変条件が中途半端に更新されたままになる可能性があります。一般的な復旧パスでは、スレッドダンプと主要なメトリクスを取得し、監視機構によって、状態を安全に再構築できるプロセスまたはインスタンスを再起動させます。プロセスが復元不可能な独自の固有状態を所有している場合、再起動も安全ではありません。永続化と復旧の再設計が必要になります。
被害者の選択では、すでに実行された作業、ロールバックコスト、優先度、再試行履歴を考慮できますが、正当性が最優先されます。復旧は進捗を回復させるものであり、原因を取り除くものではありません。ロック順序を修正しなければ、同一のトラフィックで再びデッドロックが発生します。
ステップ7: 決定論的なインターリーブで修正を検証する
高並行テストの偶然に頼るだけではいけません。従来のロジックにテスト用バリアを追加します。Aは42をロックした後にバリアに到達し、Bは84をロックした後にバリアに到達します。両方を解放して2つ目のロックを要求させます。ウォッチドッグは、テストの期限内に両方の待機エッジをキャプチャし、テストマシンが単に遅いだけでなく、A → B → A が発生していることを証明する必要があります。
修正後のロジックに対して、同一の逆順入力を実行します。AとBは両方とも、最初により小さいID 42を試行します。一方は84を所有せずに待機し、勝者は84を取得して完了・解放し、その後もう一方が進行します。両方のリクエストが契約上有効な結果を受け取り、合計残高が変化せず、送金が2回実行されないことを検証します。
以下もカバーしてください。
- 同一の送金元・送金先ID。重複排除により非リエントラントロックの2回目の取得が回避されることを証明する。
- 3つ以上の口座および複数のリソースタイプ。順序付けキーがパス間で同一であることを証明する。
- 残高不足、例外、キャンセル、部分的な取得失敗。finallyブロックが取得したすべてのロックを解放することを証明する。
- オンライン送金と並行するバッチ、返金、修復パス。迂回による逆転を検出する。
- データベースの検知と被害者のロールバック。完全な再試行、冪等な副作用、再試行の上限を検証する。
- 残高、ロック待機、デッドロック、飢餓（starvation）を継続的にチェックする、ランダム化された高競合ソークテスト。
決定論的テストは既知の反例を塞ぎます。ソークテストはモデル化されていないパスを探索します。プロトコルが検証されたと主張するには、両方が必要です。
質の高い模範解答
「まず、これが単なる遅い待機以上のものであることを証明します。Aは42を所有してBの84を待機しているため A → B、Bは84を所有してAの42を待機しているため B → A となります。各単一インスタンスミューテックスは、その所有者が2つ目を取得した後にのみ解放されるため、このサイクルはデッドロックです。
4つの必要条件がすべて揃っています。口座の書き込みロックは相互排他的であり、両スレッドは1つを保持しながらもう1つを待機しており、ロックを安全に横取りすることはできず、待機はサイクルを形成しています。残高を保護するために相互排他は排除しません。口座ロックの全順序を1つ定義し、IDの重複を排除し、昇順で取得して逆順で解放することにより、循環待機を排除します。すべてのパスが低いランクから高いランクへのみ待機する場合、サイクルにはランクが増加した後に低い開始点に戻ることが必要になりますが、これは不可能です。
このルールは、オンライン送金、返金、バッチ処理、修復ツールをカバーする必要があります。クリティカルセクションには検証と状態変更のみを含め、リモート呼び出しは含めません。タイムアウトは完全な解放後にこの待機を解消できますが、ロックプロトコルが非巡回であることを証明するものではありません。タイムアウトと再試行が同時に起こるとライブロックになる可能性があるため、タイムアウトパスには試行回数の制限、ランダムなバックオフ、冪等性キーが必要です。
本番環境では、各検知器のカバー範囲を考慮しながら、スレッドダンプやデータベース待機データから待機者-所有者グラフを構築します。PostgreSQLがトランザクションのデッドロックを検知した場合、1つのトランザクションを中止します。どのリクエストが被害者になるかを仮定せず、トランザクション全体をロールバックして制限付きで再試行し、外部メッセージは冪等なコミット後パスを介してのみ発行します。
検証では、バリアを使用して、両方が2つ目のロックを要求する前にAが42をロックし、Bが84をロックするようにして、従来の挙動を確実に再現します。順序付けされたバージョンは同じ逆順の入力を受け取り、完了前に非巡回待機のみを示すはずです。また、同一口座、3口座間の操作、例外時のクリーンアップ、迂回ジョブ、データベースのロールバックもテストし、合計残高、重複する副作用、デッドロック数、終端障害を確認します。」
この回答は、定義、証明、エンジニアリングの選択、復旧、検証を結びつけています。面接官が4つの条件のみを尋ねた場合は、第2段落の後に停止してください。本番環境での処理がフォローアップとなった際に、ツールや再試行の境界へと展開します。
よくある間違い
- スレッドがブロックされるたびにデッドロックと断定する → ロックを長く保持している側がまだ進行中である可能性があります → 待機者から所有者へのエッジを描き、正しいリソースインスタンスモデルのもとでサイクルを確認してください。
- 4つの条件を暗記して列挙するだけ → 回答がコードと対応しておらず、解決策も選択されていません → 各条件をシナリオに対応付け、設計によってどれを打破するかを述べてください。
- 各関数内で独立してソートする → モジュール間でキーやリソースタイプのランクについての認識が一致しない可能性があります → リポジトリ全体のロック階層を定義し、すべてのエントリーポイントを検査してください。
- 重複するリソースIDを無視する → 1つのスレッドが同一の非リエントラントロックを2回取得する可能性があります → ソート前に重複を排除し、同一口座間の送金セマンティクスを定義してください。
- タイムアウトを非巡回設計として扱う → 逆順のまま残り、タイムアウトが正当な待機を中止させる可能性があります → 保持しているすべてのロックを解放し、制限付きバックオフ、冪等性、終端エラーを追加してください。
- サイクル検知後に中途半端な位置から再開する → 部分的な状態が古くなっている可能性があり、副作用が繰り返される恐れがあります → トランザクション全体をロールバックして再実行し、冪等なコミット後パスを使用してください。
- すべてのリソースグラフサイクルがデッドロックを証明すると仮定する → 外部インスタンスが複数インスタンスリソースを解放する可能性があります → 単一インスタンスの待機グラフと、複数インスタンスの割り当て分析を区別してください。
- ロック所有者を強制終了する → インメモリの不変条件が中途半端に更新されたままになる可能性があります → 証拠を収集し、状態が再構築可能な境界でのみ再起動してください。
- ランダム化されたストレステストのみを実行する → 再現に失敗したとしても、逆順の存在を否定することはできません → バリアを用いてインターリーブを固定し、その上で未知のパス向けにソークテストを追加してください。
フォローアップの質問と回答
フォローアップ1: 送金で3つの口座をロックする場合でも順序付けは機能しますか？
はい。取得前に完全で重複のないロックセットが判明しており、同一の安定したキーでソートされていれば機能します。実行時に動的に口座が判明する場合は、ロックなしで候補セットを読み取り、まとめて取得してバージョンを再検証します。セットを事前に知ることができない場合は、トランザクションを分割するか、局所的な順序で段階的に取得するのではなく、ロールバック可能な境界の周りで検知を使用します。
フォローアップ2: 異なるリソースタイプはどのように順序付けしますか？
顧客、口座、台帳シャードの順など、複合ランクを作成し、各タイプ内で安定したIDを用います。共有ロックプロトコルがルールを規定し、レビューとテストによってタイプを跨ぐエッジを検証します。ある操作が逆順で入らなければならない場合は、例外を個別に追加するのではなく、呼び出し方向を再設計するか、境界を越える前に下位レベルのリソースを解放します。
フォローアップ3: 100ミリ秒のタイムアウト付きtryLockはデッドロックを解決しましたか？
この試行の待機時間を設定されたウィンドウに制限しますが、非巡回プロトコルを証明するものではありません。100ミリ秒は正当なクリティカルセクションのテールを下回り、誤った障害を引き起こす可能性もあります。取得済みロックの解放、部分的な状態のロールバック、制限付きランダムバックオフ、冪等性、終端エラーを定義してください。そうでなければ、デッドロックが再試行によるライブロックに変わる可能性があります。
フォローアップ4: 読み取りロックから書き込みロックへのアップグレードが危険なのはなぜですか？
2つのスレッドが両方とも共有読み取りロックを所有し、両方が排他書き込みへのアップグレードを待機している場合、各読み取りロックが相手のアップグレードをブロックしてサイクルを形成します。ライブラリが提供する明示的なアップグレードプロトコルを優先してください。それがない場合は、読み取りロックを解放し、書き込みロックを競合して取得した上で、その隙間に状態が変化している可能性があるため条件を再検証します。
フォローアップ5: PostgreSQLが自動的にデッドロックを検知する場合、アプリケーション側には何が残されていますか？
発生を減らすために一貫した複数オブジェクト順序を使用し、デッドロックエラーをトランザクション全体の失敗として扱います。状態を再読み込みして制限付きで再試行し、リクエストを冪等にし、再試行と終端障害を記録します。特定のトランザクションが常に負けると仮定したり、ロールバック後に元に戻せない外部アクションを繰り返したりしないでください。
フォローアップ6: デッドロック、ライブロック、飢餓（starvation）はどう異なりますか？
デッドロックの参加者は待機サイクルのために進捗できません。ライブロックの参加者は実行されて状態を変更しますが、完了することなく譲り合いや再試行を繰り返します。飢餓とは、他の参加者が完了できる一方で、ある参加者が無期限にリソースを拒否されることを意味します。それぞれの証拠は異なります。待機サイクル、完了を伴わない継続的な状態変更、そして持続的な不公平な待機です。