ロックフリー・ウェイトフリーとCAS命令

なぜロックを外したいのか

ミューテックスによる排他は正しさを保証しますが、本質的な弱点を抱えます。ロックを保持したスレッドが停止すると、待っている全員が巻き添えで止まることです。ロック保持中にOSがそのスレッドをプリエンプト（横取り）すれば、ロックを待つ他スレッドは保持者が再スケジュールされるまで進めません。これがデッドロック・優先度逆転・コンボイ現象（一台の遅延が後続を数珠つなぎに滞らせる）の温床です。

ロックフリー・プログラミングは、ロックという「排他の所有権」を捨て、代わりにハードウェアの不可分命令で共有状態を直接更新する設計です。あるスレッドが途中で止まっても、他スレッドは独立して前進できる——これが核心の狙いです。ロックの難しさ全般の地図は並行性モデル（CSP・アクター・STM）に整理してあります。

CAS：すべての土台となる不可分命令

ロックフリーの中心にあるのが CAS（Compare-And-Swap） です。CPUが提供する不可分命令で、概念的には次の三引数を取ります。

CAS(address, expected, new):
  # 以下が「割り込み不能な1ステップ」として実行される
  if *address == expected:
    *address = new
    return true        # 成功：誰にも邪魔されず差し替えた
  else:
    return false       # 失敗：その間に他者が値を変えた

重要なのは、この比較と書き込みの全体が他のコアから見て不可分である点です。x86 では lock cmpxchg、ARM では LDXR/STXR（Load-Exclusive/Store-Exclusive。MIPS等の Load-Linked/Store-Conditional, LL/SC と同じ「読んでから条件付きで書く」方式）が対応します。CASを使う典型は「読んで、計算して、書き戻す」を楽観的に回すループです。

loop:
  old = atomic_load(counter)     # 現在値を読む
  new = old + 1                  # 望む新値を計算
  if CAS(counter, old, new):     # 「読んだときと同じなら」差し替え
    break                        # 成功
  # 失敗＝間に誰かが更新した → 読み直して再試行

ロックなら「区間を占有して直列化」しますが、CASは占有せず、衝突したら再試行する。この差が進行保証の性質を根本から変えます。

進行保証の階層

「ロックを使わない」と「ロックフリーである」は別物です。進行保証（progress guarantee）は、システム内のスレッドが必ず前進すると言えるかを形式的に分類した階層で、強い順に整理できます。

• obstruction-free：もし他スレッドが全員止まれば、残った1スレッドは有限ステップで完了できる。ただし複数が干渉し合うと、互いの再試行を無限に誘発するライブロックが起こり得ます。
• lock-free：どこかのスレッドは必ず有限ステップで前進する、をシステム全体として保証します。CASループは「自分のCASが失敗した」＝「他の誰かのCASが成功して値を変えた」を意味するため、全員が同時に永久に失敗し続けることはありません。ただし特定の1スレッドが運悪く負け続ける飢餓は理論上あり得ます。
• wait-free：最も強く、個々のスレッドが他者の挙動に依存せず、決まった上限ステップ内で完了します。飢餓が原理的に起きません。

ABA問題：CASの最大の落とし穴

CASは「値が expected と一致するか」だけを見ます。ここに致命的な盲点があります。値が A → B → A と変化して元に戻った場合、CASは「変わっていない」と誤認して成功してしまうのです。これが ABA問題 です。

ポインタを差し替えるロックフリー・スタックを考えます。スレッド1が先頭ノード A を読み、A.next（= B）を新しい先頭にしようと準備したところでプリエンプトされたとします。その間に他スレッドが A をpopし、B もpopし、メモリアロケータが同じアドレスを再利用して新ノードを再び A としてpushしたら——。

# スレッド1の意図：先頭が A なら、先頭を「Aのnext」に差し替える
top = A
next = A.next            # この時点の A.next は B
# ← ここで中断。その間に pop A, pop B が起き、A のアドレスが再利用される
CAS(stack.top, A, next)  # top はアドレス的に A と一致 → 成功してしまう！
                         # だが next(=旧B) は既に解放済み。先頭が壊れる

アドレスとしては A に一致するためCASは成功しますが、スレッド1が握っていた next（旧 B）はすでに解放され、リストの整合性が崩壊します。ポインタと参照を直接CASで付け替える設計に特有の罠です。

ABAを封じる：タグとハザードポインタ

ABA問題への対策は、大きく二系統あります。

タグ付きポインタは、ポインタ値に単調増加するバージョン番号を抱き合わせ、両方をまとめてCASします。アドレスが A に戻っても、その間に行われた更新でタグが進んでいるため、(A, version=5) と (A, version=7) は不一致となりCASが正しく失敗します。(ポインタ, タグ) の組をまとめて入れ替えるには、x86 の cmpxchg16b のような**二重幅CAS（DWCAS）**が要ります。

ハザードポインタは、各スレッドが「いま自分が参照中のノード」をグローバルな公示テーブルに掲示する方式です。ノードを解放したいスレッドは、解放前に公示テーブルを走査し、誰かが公示しているなら解放を保留します。これによりABAの根本原因である「使用中アドレスの即時再利用」を断ちます。**RCU（Read-Copy-Update）**やエポックベースの回収も、誰も古い版を見なくなったタイミングまで解放を遅らせる点で同じ思想です。これらは安全な世代管理を「変えないものは共有してよい」というイミュータビリティ（不変性）の発想で支えています。

ロックフリーは万能ではない

ロックフリーは強力ですが、銀の弾丸ではありません。設計判断の勘所を押さえます。

• 高競合下では遅くなり得る：衝突が多いとCAS再試行が空転し、lock cmpxchg のキャッシュコヒーレンシ通信が増えて、よく書かれたロックに性能で負けることがあります。スループットは競合度に強く依存します。
• 正しさの検証が極端に難しい：メモリ順序とABAとメモリ回収が絡み合い、テストで再現しないバグが残りやすい。実績ある定理証明済みアルゴリズム（Treiberスタック、Michael-Scottキュー等）を踏襲するのが定石です。
• メモリ回収が別問題として残る：GCのない言語では「いつ安全に解放できるか」がハザードポインタ等で別途要り、ここが実装の大半を占めます。

まとめ

ロックフリー・プログラミングは、(1) CAS という不可分命令で共有状態を楽観的に更新し、失敗したら読み直して再試行する、(2) その進行保証は lock-free（全体前進）と wait-free（各スレッド有限完了） という階層で精密に語られる、(3) 再試行ループ特有の ABA問題 をタグやハザードポインタで封じる、という三本柱で成り立ちます。「ロックを外せば速くなる」ではなく、「停止したスレッドが全体を止めない進行保証を、競合と検証コストと引き換えに得る」設計だと捉えるのが正確です。並行設計全体の見取り図は並行性モデルと同期処理と非同期処理と合わせて押さえると、いつCASまで踏み込むべきかの判断がつきます。