ロックが止まるとき — 誰も間違えていないのに進まない — OSとカーネルの土台

アプリと DB の下に何が積まれているか(左が下、右が上)

物理機リージョン/AZ
ハイパーバイザVM exit で捕まえる
VMゲストOS
コンテナnamespace / cgroup
プロセスアプリ / DB今ここ

前回、1行の `+=` が読む・変える・書くに分かれるせいで値が壊れることを見ました。その手当てのロックが、今度は別の止まり方を生みます。

まず結論

デッドロックは、待ちの関係に**輪**ができた状態です。どのスレッドも規則どおりにロックを取っているのに、全員が止まります。

そして **pthread のミューテックスは、既定ではこれを検知しません。ただ止まります。** `PTHREAD_MUTEX_ERRORCHECK` に変えても同じでした(実測)。`EDEADLK` が対象にするのは「自分がすでに持っているロックをもう一度取った」場合だけで、逆順に取る形は射程の外です。

? 読む前に予測

2つのスレッドが2つのミューテックスを逆の順序で取り合って止まりました。種類を `PTHREAD_MUTEX_ERRORCHECK` に変えるとどうなるでしょうか。

当てることが目的ではありません。外した予測ほど記憶に残るので、直感で選んでください。

抽象原理

止まるのは、待ちの関係に輪ができたとき

前回、counter = counter + 1 が読む・変える・書くに分かれるせいで値が失われることを見ました。手当てはミューテックス——鍵を取ってから触り、終わったら返す。ところが鍵が2つ以上になると、別の止まり方が生まれます。

Linux カーネルのロック順序検証機構 lockdep の設計文書が、この形をそのまま書いています。

Furthermore, two locks can not be taken in inverse order::

<L1> -> <L2> <L2> -> <L1>

because this could lead to a deadlock - referred to as lock inversion deadlock - as attempts to acquire the two locks form a circle which could lead to the two contexts waiting for each other permanently.

"form a circle" と "waiting for each other permanently"。「依存」の定義も同文書にあります。

lock dependency can be understood as lock order, where L1 -> L2 suggests that a task is attempting to acquire L2 while holding L1

L1 を持ったまま L2 を取りにいく——これが1本の辺です。辺が輪を閉じたら、誰も先へ進めません。

どのスレッドも規則は破っていません。 それぞれ「鍵を取ってから触る」正しい手順を踏んでいます。順序が揃っていないことだけが原因で、その順序はどこにも書かれていません。

2つのロックを逆順に取ると、待ちが輪になる

スレッド1A を保持

スレッド2B を保持

次の鍵を要求する

B を待つB はスレッド2が保持

A を待つA はスレッド1が保持

待ちの辺が閉じる

輪waiting for each other permanently

誰も進めない

・輪ができるかは順序だけで決まり、どちらも単体では正しい

具体実物

実測 — 既定でも ERRORCHECK でも、ただ止まる

動かしました。スレッド1は A → 1秒待つ → B、スレッド2は B → 1秒待つ → A の順に取ります。放置すると戻らないので、必ず timeout 10 で包んでいます。

timeout 10 ./dl / timeout 10 ./dl e(Linux 6.10.14-linuxkit, aarch64, gcc 13)コマンド出力

### RUN 1: default mutex, AB/BA order, wrapped in timeout 10 ###
== mutex type: DEFAULT ==
T1: got A
T2: got B
T2: want A ...
T1: want B ...
exit code = 124 (124 = timed out = still deadlocked)
 
### RUN 2: ERRORCHECK mutex, same order ###
== mutex type: ERRORCHECK ==
T1: got A
T2: got B
T2: want A ...
T1: want B ...
exit code = 124 (124 = timed out)

T1: got B も T2: got A も一度も出ていません。 「取りにいく」までは出て、そこで止まる。エラーも警告も出ません。10秒後に timeout が殺して exit 124。

そして本題です。ERRORCHECK に変えても、まったく同じ exit 124 でした。 EDEADLK は返っていません。

man-page の記述と正確に噛み合います。pthread_mutex_lock(3) の ERRORS はこうです。

EDEADLK The mutex is already locked by the calling thread ("error checking" mutexes only).

"already locked by the calling thread" ——対象は呼び出したスレッド自身がすでに持っているロックです。DESCRIPTION 側も同じ状況を扱います。

If the mutex is already locked by the calling thread, the behavior of pthread_mutex_lock() depends on the kind of the mutex. ... If the mutex is of the "error checking" kind, pthread_mutex_lock() returns immediately with the error code EDEADLK.

上の実測は別のスレッドが持っているロックを待つ状態で、この射程に入りません。ERRORCHECK は嘘をついていません。対象範囲が最初から違うだけです。

✓ ここまでの確認

`PTHREAD_MUTEX_ERRORCHECK` の `EDEADLK` は、どの状況を検出しますか。

抽象原理

検知する仕組みがあるかどうかが、現れ方を分ける

一段引き上げます。現象は同じでも、どう見えるかは「検知する仕組みが備わっているか」で決まります。

pthread のミューテックスには既定でそれがなく、誰も輪を見張らないので待ちは続きます。プロセスは生きていて、CPU も使わず、ログにも何も出ない。「静かに止まっている」という最も気づきにくい形です。

一方、カーネル内部には lockdep があります。ただし pthread の代わりにはなりません。lockdep が見るのは起こりうる順序です。

the validator will still find whether these locks can be acquired in a circular fashion

実際に起きていなくても順序の矛盾を見つける。これはカーネル開発者向けのデバッグ機構(CONFIG で有効化)で、ユーザ空間の pthread_mutex_t には効きません。「Linux にはデッドロック検出機構がある」を「自分のアプリのロックも見てもらえる」と読むと間違えます。

なお、成立条件を古典的に4つとして整理したものが知られています(Coffman らの1971年の論文が出典として挙げられます)。ただし本教材はその論文の本文を確認できていませんので、4条件を原文の引用としては扱いません。

具体実物

対比例 — スピンロックだと、止まり方まで変わる

鍵の種類を変えると、同じ止まり方が別の顔を見せます。違いは待つ間に何をするかです。

If the mutex is already locked by another thread, pthread_mutex_lock() suspends the calling thread until the mutex is unlocked.

If the spin lock is currently locked by another thread, the calling thread spins, testing the lock until it becomes available, at which point the calling thread acquires the lock.

"suspends the calling thread" と "spins, testing the lock"。デッドロック時の帰結が pthread_spin_init(3) の NOTES にあります。

If threads create a deadlock situation while employing spin locks, those threads will spin forever consuming CPU time.

同じ輪でも、ミューテックスなら静かに止まり、スピンロックなら CPU を使い続けます。

では「速さのために回り続ける」のは得か。測りました。

同じプログラムで mutex と spin を比較(--cpus=2 で CPU 割り当てを制限)コマンド出力

### SHORT critical section, 2 threads (spinlock often wins) ###
mutex   threads=2   crit_work=0           5.7 ms
spin    threads=2   crit_work=0           4.4 ms
mutex   threads=2   crit_work=0           5.6 ms
spin    threads=2   crit_work=0           2.3 ms
 
### LONGER critical section + OVERSUBSCRIBED (8 threads on 2 cpus) ###
mutex   threads=8   crit_work=200       242.8 ms
spin    threads=8   crit_work=200       366.8 ms
mutex   threads=8   crit_work=200       245.7 ms
spin    threads=8   crit_work=200       284.6 ms

逆転しています。 短い区間・2スレッドではスピンロックが速く、長い区間・スレッド数が CPU の割り当てを超えるとミューテックスが速い。理由も NOTES にあります。

The problem is that if a thread operating under such a policy is scheduled off the CPU while it holds a spin lock, then other threads will waste time spinning on the lock until the lock holder is once more rescheduled and releases the lock.

鍵を持つスレッドが CPU を降ろされると、他は "waste time spinning" するだけです。だから同じ文書の冒頭はこう始まります。

General note: Most programs should use mutexes instead of spin locks. Spin locks are primarily useful in conjunction with real-time scheduling policies. See NOTES.

✓ ここまでの確認

「スピンロックはミューテックスより速い」という説明を、実測に照らして評価してください。

⇄ 2つを見比べる

具体例 A

InnoDB — 検知して片方を巻き戻す

DB編『デッドロックは異常ではない — "Just try again."』で見たとおり、InnoDB は待ちの輪を自分で見つけて片方を巻き戻します——“When deadlock detection is enabled (the default), InnoDB automatically detects transaction deadlocks and rolls back a transaction or transactions to break the deadlock.” **既定で有効**という条件付きです。アプリにはエラーが返ります。詳細はそちらに譲ります。

具体例 B

pthread のミューテックス — 既定では検知せず、ただ止まる

待ちの輪を見張る仕組みが既定では無く、両方のスレッドが止まったままになります。エラーも返らずログにも出ず、実測では `timeout 10` に打ち切られ exit 124。気づく手がかりがありません。

同じ「待ちの輪」なのに、片方は片方を殺して解け、もう片方は解けません。この差はどこから来ているでしょうか。

殺された側に何が起きるかを、両方で考えてみてください。DB では殺されたトランザクションはどうなりますか。

実務の場面エージェントが出した「ロックを足して直しました」という差分を見る

前回の「値が壊れる」問題に対し、エージェントがロックを追加した差分を出してきたとします。テストは通り、値も合っています。

差分を見ると、ロックが2つ足されていました。残高を守る account_lock と、監査ログを守る audit_lock。送金処理は account_lock → audit_lock の順に取り、残高照会の一部の経路は audit_lock → account_lock の順でした。

判定の問いは1つです——「この2つのロックを取る順序は、全ての経路で同じか」。 違っていれば、それが lockdep の言う L1 -> L2 と L2 -> L1 であり、輪の材料です。

厄介なのは、この差分がテストでは落ちないことです。両方の経路が同時に走らなければ何も起きません。起きたときも例外は投げられず、ただ応答が返らなくなるだけです。実測がまさにそうでした。

「ロックを増やせば安全になる」は成り立ちません。1つなら輪はできませんが、2つ目からは順序という取り決めが要ります。差分を受け取ったら、足されたロックの数と、取得順序が書かれている場所を確認してください。どこにも書かれていないなら、それは誰も守れない取り決めです。

この章のまとめ

デッドロックは待ちの関係に輪ができた状態。lockdep は “attempts to acquire the two locks form a circle” “waiting for each other permanently” と述べる。
pthread のミューテックスは既定では検知しない。ただ止まる。 実測では timeout 10 に打ち切られ exit 124、エラーもログも出なかった。
PTHREAD_MUTEX_ERRORCHECK にしても同じ exit 124。 EDEADLK の対象は “already locked by the calling thread”(自己再ロック)だけ。POSIX の “A deadlock condition was detected.” は may fail(任意)で、義務ではない。
スピンロックが速いとは限らない。 短い区間・2スレッドでは速かったが、スレッド数が CPU の割り当てを超えると逆転した(各条件2回の測定。倍率は言えない)。pthread_spin_init(3) は “Most programs should use mutexes instead of spin locks.” と述べる。
デッドロック時、ミューテックスは静かに止まるが、スピンロックは “spin forever consuming CPU time”。
InnoDB が検知して巻き戻せるのは巻き戻す手段があるから。ミューテックスが守るメモリ操作は戻せないので、殺す設計になっていない。順序を揃えるしかない。
lockdep はカーネル内部の検証機構で、pthread ミューテックスには効かない。

自分の現場で確かめる

読んだだけでは身につきません。手元の環境で実際に見てみてください。

環境:

2つ以上のロックを同時に保持している箇所を探し、**取る順序が全ての経路で同じか**を呼び出し元までたどって確認する。順序の取り決めがどこかに書かれているかも探す
止まっているプロセスが何を待っているかを見る(実行中のプロセスが必要)Windowsでは確認できません。この項目はLinux/WSLで試してください。

理解度チェック

読んだ直後は「分かった」と感じやすいものです。実際に解いて確かめてください。

問題 1 / 3正解: 0

AI が「ロックが競合して止まるので、ミューテックスを ERRORCHECK にすればデッドロックを検出できます」と提案しました。評価はどれですか。

用語集(3語)

ミューテックス / スピンロック: どちらも同時に1つのスレッドだけが持てる鍵。待ち方が違う——“pthread_mutex_lock() suspends the calling thread until the mutex is unlocked.” に対し “the calling thread spins, testing the lock until it becomes available.” `pthread_spin_init(3)` は “Most programs should use mutexes instead of spin locks.” と述べている。
EDEADLK: `pthread_mutex_lock` が返しうるエラー。“The mutex is already locked by the calling thread ("error checking" mutexes only).” 対象は自己再ロックのみ。POSIX.1-2024 には別項として “may fail … A deadlock condition was detected.” もあるが、**may fail**(任意)。
lockdep / dependency circle: Linux カーネル内部のロック順序検証機構(CONFIG で有効化)。依存は “lock dependency can be understood as lock order, where L1 -> L2 suggests that a task is attempting to acquire L2 while holding L1”。輪ができると “waiting for each other permanently”。**ユーザ空間の pthread ミューテックスは対象外**。