カーネルのロック機構（spinlock・mutex・seqlock）

待ち方の二択──眠るか、回すか

カーネルのロックを理解する第一の軸は、ロックが取れなかったとき何をするか です。選択肢は2つしかありません。

• 眠る（sleep / block）：自スレッドを実行可能列から外し、CPUを別タスクに譲る。再びロックが空いたら起こしてもらう。
• 回す（spin / busy-wait）：CPUを手放さず、取れるまでループで確認し続ける。

眠るほうはCPUを無駄にしませんが、コンテキストスイッチ 2回ぶん（眠るとき・起きるとき）のコストがかかります。回すほうは切り替えコストがゼロな代わり、待っている間ずっとCPUを焼き続けます。

この差から原則が決まります。ロックを保持する時間が「コンテキストスイッチ2回より短い」と見込めるなら回す（spinlock）、長くなりうるなら眠る（mutex）。クリティカルセクションが数命令で終わるなら spinlock、I/O待ちやメモリ確保を含むなら mutex、が大づかみの基準です。

割り込みコンテキストでは眠れない

カーネルのコードが走る文脈は大きく2つ。プロセスコンテキスト（システムコールなどタスクの延長で走る）と 割り込みコンテキスト（ハードウェア割り込みで叩き起こされて走る）です。決定的な違いは次の点にあります。

割り込みコンテキストには「眠って後で戻ってくる先」のタスクが存在しません。 割り込みは特定のタスクに紐づかず割り込んできただけなので、ここでスケジュールを呼んで眠ると、何を起こせばいいか分からなくなり、システムが壊れます。だから割り込みコンテキストでは 眠る系のロック（mutex / semaphore）は禁止。使えるのは spinlock だけです。

さらに厄介なのがデッドロックの一種です。あるコアがプロセスコンテキストで spinlock を保持したまま、同じコアに割り込みが入り、割り込みハンドラが同じロックを取りに行く と、ハンドラはロックが空くのを spin で待ち、しかしロックを持つ本体は割り込みが終わるまで再開できない——自分自身を永久に待つ 状態に陥ります。

コアX: spin_lock(L)        ← プロセス文脈でLを保持
       ┊（クリティカルセクション中）
       割り込み発生 ───► ハンドラ: spin_lock(L)  ← 同じLを取りに来る
                          本体は割り込み終了まで進めない
                          ハンドラは本体がLを離すまで spin
                          → 同一コアで自己デッドロック

これを防ぐため、割り込みハンドラと共有する spinlock は、ローカル割り込みを無効化してから取得 します。Linux の spin_lock_irqsave() が典型で、ロック取得前に当該コアの割り込みを止め、解放時に元へ戻します。

読み多寡で選ぶ──rwlock・seqlock・RCU

共有データが 圧倒的に読まれ、たまにしか書かれない 場合、読み手どうしまで排他するのは無駄です。そこで読みの並行度を上げる道具が段階的に用意されています。

• rwlock（リーダー/ライターロック）：読み手は複数同時に入れ、書き手だけが排他。ただし読み手も内部カウンタの更新でキャッシュ行を共有するため、コア数が増えると読み手間でも競合します。書き手が来ると読み手は締め出されます。
• seqlock（シーケンスロック）：書き手を最優先にする発想。書き手は書き込みの開始時にシーケンス番号を偶数→奇数へ、終了時に奇数→偶数へと2回進めるだけで（＝書き込み中は番号が奇数）、読み手を一切ブロックしません。読み手はロックを取らず、読む前後でシーケンス番号を確認し、途中で書き手が入った（番号が変わった/奇数だった）ら読み直す 楽観的な方式です。
• RCU（Read-Copy-Update）：読み手側のコストをほぼゼロにする究極形。読み手はロックもアトミック操作もせず、ただポインタを辿るだけ。更新側は 既存データを書き換えず、コピーを作って差し替え、旧データは「全ての既存読み手が読み終えた」ことを保証してから解放します。

seqlock の読み手（リトライする楽観読み）:
  do {
    s = read_seqbegin(&sl)   // 開始時のシーケンス番号
    ... 共有データを読む ...
  } while (read_seqretry(&sl, s))  // 途中で書かれていたら最初からやり直し

spinlock はなぜスケールしないか──ティケットとMCS

最後に、spinlock そのものの性能問題です。最も素朴な spinlock は、1つのフラグ変数に対し全コアが CAS を撃ち続けます。これが多コアで深刻に劣化します。

原因は キャッシュ行の奪い合い です。複数コアが同じフラグに書き込もうとすると、そのキャッシュ行が コア間を行ったり来たり（キャッシュコヒーレンシのバウンシング）します。待ち手が増えるほどこのトラフィックが増え、コア数に対して逆スケール し、しかも誰が次に取れるか不定で 公平性もありません（運の悪いコアが飢える）。

これを2段階で改善します。

• ティケットロック：銀行の番号札方式。取得時に next を atomic に1増やして自分の番号（札）を受け取り、now_serving が自分の番号になるまで待ちます。FIFO順で公平 になり、飢餓が消えます。ただし全コアが同じ now_serving を読むため、解放のたびに全待ち手のキャッシュが無効化 され、バウンシング自体は残ります。
• MCSロック：待ち手を 連結リスト に並べ、各コアは 自分専用のローカル変数だけを spin します。解放時は、現保持者がリスト上の次のコアのローカル変数だけを1つ書き換えて起こします。書き込みが1コアの行に限定されるため コア間バウンシングがほぼ消え、FIFO公平も保ったまま コア数に対してフラットにスケール します。

素朴な spinlock : 全コアが同じ flag を spin → 解放のたび全員のキャッシュ無効化
ティケットロック : 番号札でFIFO公平。だが now_serving は全員が見る → 無効化は残る
MCSロック        : 各コアは自分のノードだけ spin → 書き込みが局所化、ほぼ無効化なし

MCS のイメージ:
  [保持中:A] → [待ち:B] → [待ち:C]   (各々が own.locked を spin)
  A が解放 → A は B.locked を false に書くだけ → B が進む

まとめ