カーネルのロックフリー同期とCAS

なぜロックフリーなのか──ロックの構造的な弱点

ロック（ミューテックス）は正しく安全ですが、構造的な弱点を抱えています。鍵を握ったスレッドが、解放する前に スケジューラに横取り（プリエンプト） されると、その間ほかの全スレッドは何もできずに待たされます。優先度の高いスレッドが、鍵を持つ低優先度スレッドの再実行を待つ 優先度逆転 も起きえます。最悪、鍵を持つスレッドが落ちれば、その鍵は永久に返ってきません。

ロックフリー同期は、この「1スレッドの停止が全体を巻き込む」性質を断ち切る設計です。鍵という共有状態を持たず、CPUのアトミック命令だけで 共有データを更新します。土台となる排他制御の全体像は 排他制御とデッドロック を、横取りが起きる仕組みは コンテキストスイッチ を参照してください。

CAS：ロックフリーの土台となる1命令

ロックフリーの心臓部が CAS（Compare-And-Swap、比較交換） です。「指定アドレスの値が期待値と一致するなら新値に書き換え、一致しなければ何もしない」を、途中で割り込まれない1つの不可分な操作として実行します。

CAS(addr, expected, new) -> bool:
  アトミックに {
    if *addr == expected:
        *addr = new
        return true        # 成功
    else:
        return false       # 失敗（誰かが先に書き換えた）
  }

x86 では LOCK CMPXCHG、ARM では LDXR/STXR（LL/SC）として実装されます。重要なのは、CAS が 失敗を返せる こと。失敗は「自分が値を読んでから書こうとするまでの間に、別スレッドが割り込んで更新した」という事実を意味します。この失敗を起点に 読み直して再試行 するのがロックフリーの基本パターンです。

do {
    old = atomic_load(&counter)      # 現在値を読む
    new = old + 1                    # 望む新値を計算
} while (!CAS(&counter, old, new))   # old のままなら成功、変わっていたらやり直し

楽観的同時実行の原理：read-copy-update のループ

CASループの本質は 「読む→新しい状態を作る→一致を確認して差し替える」 の繰り返しです。共有データに直接手を入れず、自分のローカルで望む結果を組み立て、最後の一瞬だけCASで原子的に公開します。

連結リストの先頭に要素を挿入する例で見ます。

node->next = head             # ① 今の先頭を新ノードの次に繋ぐ（ローカル操作）
while (!CAS(&head, node->next, node)) {
    node->next = head         # ② head が変わっていたら読み直してやり直す
}

ポイントは、CASが守る不変条件です。「自分が node->next に記録した先頭と、いま実際の head が同一なら、その間に誰も head を変えていない」とみなせる。だから安全に差し替えられます。誰かが先に挿入していれば head が変わってCASが失敗し、新しい先頭で組み直す。ロックを取らずに、衝突したスレッドだけがやり直す わけです。

ロックフリーとウェイトフリーは別物

「ロックを使わない＝ロックフリー」ではありません。ノンブロッキングな進行保証は 段階 で定義され、混同は禁物です。

差は 「誰の前進を保証するか」 にあります。ロックフリーが保証するのは「システム全体の前進」だけ。CASループでは、ある不運なスレッドが毎回CASに失敗し続けて 永久に再試行する（飢餓に陥る） ことが原理上ありえます。それでも「誰か」は必ず成功して進むため、全体は止まりません。

ウェイトフリーはさらに踏み込み、「各スレッドが、他の挙動に関わらず決まった上限ステップで必ず完了する」を保証します。飢餓が起きません。実現には、止まりかけた他スレッドの作業を 手伝って肩代わりする（helping） などの工夫が要り、コストも複雑さも跳ね上がります。リアルタイム系で最悪実行時間の上限が要る場面以外では、実務上ロックフリーで十分なことが多いです。

ABA問題：CASが見ているのは「値」だけ

ロックフリー実装で最も悪名高い罠が ABA問題 です。原因は単純で、CASは「値が一致するか」しか見ない こと。値がいったん別物に変わってから元に戻ると、CASは「変化していない」と誤認します。

ロックフリースタックの pop で起きる典型を追います。

スレッド1: top を読む → A（次は B）。CAS(&top, A, B) を出そうとした直前で横取りされる
スレッド2: A を pop（top は B に）→ B も pop（top は C に）→ A を再利用して再び push（top は A に、ただし A->next は今や C）
スレッド1: 再開。CAS(&top, A, B) は「top はまだ A だ」と見て成功してしまう
        → top を B に書き換える。しかし B はすでに解放済み。リストが壊れる

top の値はA→B→…→Aと 一周して戻った ため、CASは中身が入れ替わった事実に気づけません。A->next がもう B を指していないのに、古い前提のまま top=B を書き込み、解放済みメモリへの参照（use-after-free）を生みます。

ABA問題への対策

対策はいずれも「値の一致だけでは『変化なし』と断定しない」ための仕組みです。

最も直接的なのが 世代カウンタ。ポインタの隣に「更新通し番号」を置き、ポインタと世代を一括してCAS します。A→…→Aと値が戻っても世代は必ず進んでいるため、CASが正しく失敗します。x86 の CMPXCHG16B で 16 バイトをまとめて比較交換するのが定石です。

カーネルで広く使われるのが RCU です。読み手はロックもCASも使わずほぼ素通りで読み、書き手は 旧データを書き換えず新しいコピーを作って、ポインタ差し替え1発で公開 します。旧バージョンは「いま読んでいる全スレッドが読み終える（猶予期間＝grace period を抜ける）」のを待ってから解放するため、参照中のメモリが消えずABAやuse-after-freeを避けられます。Linux カーネルがルーティングテーブルや設定の参照で多用する、読み取り偏重に極めて強い手法です。

まとめ──楽観的に進み、確認の瞬間だけ原子的に