スピンロックの設計（ティケット・MCS・qspinlock）

素朴なスピンロックがスケールしない理由

スピンロックは「取れるまでCPUを手放さずループで待つ」最小の排他制御です。最も素朴な実装は1つのフラグ変数に対する test-and-set（あるいは CAS）で、概念的には次のようになります。

acquire(lock):
  while (atomic_xchg(&lock, 1) == 1)   // 1を書き込み、元が1なら失敗→再試行
    ;                                  // (実機では PAUSE を挟む)
release(lock):
  store(&lock, 0)

正しく動きますが、多コアで深刻に劣化します。原因は 同じキャッシュ行の奪い合い です。atomic_xchg は書き込みを伴うため、実行するコアは MESI でそのキャッシュ行を Modified 状態に引き寄せ、他コアの同じ行を Invalid にします。待っている全コアが xchg を撃ち続けるので、ロック変数のキャッシュ行が コア間を行ったり来たり（キャッシュ行バウンシング）します。

決定的に悪いのは解放の瞬間です。保持者が 0 を書くと、待っていた N 個のコアが一斉に xchg を撃ち、1個だけが成功して残り N-1 個は再び全員のキャッシュを無効化 します。待ち手が増えるほど解放1回あたりのコヒーレンシトラフィックが増え、性能が コア数に対して逆スケール します。さらに次に誰が取れるかは完全に運任せで、公平性がなく 運の悪いコアが飢えます。

ティケットロック──公平性は解くが、バウンシングは残る

第一の改善は公平性です。ティケットロックは銀行の番号札方式で、2つのカウンタ next（次に配る札番号）と owner（いま処理中の札番号、now_serving とも）を使います。多くの実装はこの2つを1ワードの上位/下位16ビットに詰め、取得を 1回のアトミックなインクリメント（fetch_and_add）で済ませます。

acquire(lock):
  my = atomic_fetch_add(&lock.next, 1)   // 自分の札を不可分に確保
  while (load(&lock.owner) != my)         // 自分の番が来るまで待つ
    cpu_relax();

release(lock):
  store(&lock.owner, lock.owner + 1)      // 次の札へ。アトミック不要

これで 取得順＝FIFO が保証され、飢餓が消えます。next の確保が1命令なので、複数コアが同時に来ても札番号は重複せず一意に並びます。

しかしバウンシングは解けていません。全待ち手が 同一の owner を監視するため、保持者が owner を1進めるたびにその行が全待ち手のキャッシュで無効化され、次の保持者だけでなく 無関係な後続の待ち手も巻き込んで 再ロードが走ります。読み込みオンリーになった分は素朴版よりマシですが、競合の本質である「全員が1つの行を見る」構造は残ります。

MCSロック──各コアが「自分のノード」だけを回す

スケーラビリティの本丸を解くのが MCS ロック（Mellor-Crummey と Scott の名による）です。発想は 待ち手を連結リストに並べ、各コアは自分専用のノードのフラグだけをスピンする こと。これにより、スピン対象の変数がコアごとに分かれ、バウンシングの源を断ちます。

各取得者は自分の node（locked フラグと next ポインタを持つ）をスタックやper-CPU領域に確保します。ロック本体は リストの末尾を指す tail ポインタ だけを持ちます。

struct mcs_node { bool locked; mcs_node *next; };

acquire(lock, node):
  node.next = NULL; node.locked = true;
  prev = atomic_xchg(&lock.tail, node)   // 自分を末尾に繋ぎ、直前の待ち手を得る
  if (prev == NULL) return;              // ロックは空いていた→即取得
  prev.next = node                       // 前任者のnextに自分を登録
  while (node.locked) cpu_relax();       // 自分のlockedだけを回す（ローカルスピン）

release(lock, node):
  if (node.next == NULL):                            // 後続がまだ見えない
    if (atomic_cas(&lock.tail, node, NULL)) return;  // 末尾が自分なら解放完了
    while (node.next == NULL) cpu_relax();           // 後続のリンク確定を待つ
  node.next.locked = false;             // 後続のフラグだけを書いて起こす

肝は2点です。第一に、待ち手の while (node.locked) は自コアのキャッシュにある行だけを読む ので、他コアからの書き込みが来ない限りキャッシュミスが起きません。第二に、解放は 現保持者が「次のノードの locked を1回 false に書く」だけ で、書き込みが対象1コアの行に限定されます。結果として、保持者交代1回あたりのコヒーレンシトラフィックが 待ち手の数によらず一定 になり、コア数に対して フラットにスケール します。FIFO公平もリスト順で自然に保たれます。

素朴 spin   : 全コアが同じ flag を spin   → 解放のたび全員のキャッシュ無効化（逆スケール）
ティケット  : 番号札でFIFO公平。だが owner は全員が監視 → バウンシング残る
MCS         : 各コアは自分のノードだけ spin → 書き込みが局所化、ほぼ無効化なし（フラット）

  [保持中:A] → [待ち:B] → [待ち:C]   (B,Cは own.locked を回す)
  A が解放 → A は B.locked=false を書くだけ → B が進む

Linux の qspinlock──三段構えの統合

Linux の spinlock_t は内部的に qspinlock（queued spinlock）で実装されています。これは「未競合は速く、高競合はMCS並みにスケール」を1つの32ビットワードで実現する設計で、状態を3つの領域にパックします。

動作は競合の度合いに応じて段階的にエスカレートします。

• 未競合（fast path）：ワード全体が0なら、locked バイトに1を書くだけで取得完了。tail を読む必要すらなく、素朴なスピンロックと同等の最小コストで済みます。
• 軽い競合（pending）：保持者が1人いるだけなら、2人目は pending ビットを立てて locked が下がるのを待つ。MCSノードもキューも作りません。保持者が解放すると、pending を立てた者が locked を奪って前進します。これで「待ち手が常時1人」という頻出パターンを軽量に捌きます。
• 本格的な競合（MCSキュー）：3人目以降が来て初めてMCSキューに入ります。各CPUは per-CPUのMCSノード配列 を持ち、tail には ポインタではなくCPU番号+ネストインデックスを符号化 して格納します（割り込み等でロック取得がネストしうるため、コンテキスト段ごとにノードを分ける）。これにより32ビットに収めつつ、高競合時は MCSと同じローカルスピン でフラットにスケールします。キューの先頭の待ち手だけが pending/locked を監視し、後続は自分のノードを回す、という役割分担です。

なぜ局所スピンがコヒーレンシを救うのか

各方式の本質的な差は「待ち手が監視するアドレスが共有されているか、局所か」に集約されます。共有変数を全員が監視すると、書き換え1回が全待ち手のキャッシュ行を無効化し、トラフィックが待ち手数に比例します。局所変数を各自が監視すれば、保持者交代の書き込みは「次の1コアの行」だけに当たり、トラフィックが一定になります。この一定化が「コア数に対してフラット」というスケーリング特性の正体です。

なぜ「next の locked を false に書く」だけで相手が確実に前進すると言えるか、には メモリオーダリング が絡みます。解放側のストアと取得側のロードの間に適切な acquire/release 順序がないと、クリティカルセクション内の更新が相手から見えないまま先にロック解放だけが見えてしまう恐れがあります。実装はロック取得を acquire、解放を release セマンティクスで発行し、この可視性を保証しています。

まとめ