アトミック命令とリードモディファイライトの原理

なぜ `counter++` は壊れるのか──3手に分かれる更新

counter++ という1行は、CPUにとって1命令ではありません。多くのアーキテクチャで、これは ロード（読む）→演算（足す）→ストア（書く） という3手のリードモディファイライト（RMW、read-modify-write）に分解されます。

mov  eax, [counter]   ; ① counter を読む
add  eax, 1           ; ② +1 する（レジスタ上）
mov  [counter], eax   ; ③ 書き戻す

問題は、この3手の 隙間に別コアが割り込める ことです。2つのコアが同じ瞬間に①で同じ古い値（たとえば 5）を読むと、両者とも②で 6 を作り、③で 6 を書く。本来 7 になるべき値が 6 になり、1回ぶんの更新が消える。これがロストアップデートです。原因は単純で、「読む」と「書く」の間に 観測と更新の窓 が空いているからです。

アトミック命令の役割は、この窓を消すことに尽きます。「読んで・変えて・書く」を、他のコアから見て途中状態が一切観測できない不可分な1手にする。これがアトミックなRMWであり、ロックフリー構造から参照カウント、ミューテックスの内部まで、あらゆる並行プリミティブの土台です。

アトミックの2要件──不可分性と単一全順序

アトミックなRMWが保証するのは2つです。第一に 不可分性：他コアは「ロード前」か「ストア後」の状態しか見えず、途中は見えない。第二に 同じアドレスへのRMWが1本の全順序に並ぶ：複数コアが同時にCASを撃っても、ハードウェアが順番をつけ、ちょうど1つだけが「直前の値」を見て成功します。だから足し合わせが消えません。

RMW命令の3類型：FAA / swap / CAS

ハードウェアが提供するアトミックRMWは、おおむね3つの形に整理できます。

命令	意味	返り値と用途
FAA（fetch-and-add）	アドレスの値に加算し、加算前の値を返す	カウンタ・チケットロックの採番。常に成功し再試行不要
swap（exchange）	新値を書き込み、書く前の古い値を返す	フラグの取得・テールポインタの差し替え。常に成功
CAS（compare-and-swap）	期待値と一致するときだけ新値を書き、成否を返す	条件付き更新の汎用形。失敗したら読み直して再試行

このうち CAS が最も汎用 です。「現在値が期待どおりなら書き換え、違えば何もしない」を不可分に行うため、FAA も swap も CAS ループで模倣できます（逆は一般にできません）。x86 では LOCK XADD が FAA、XCHG が swap、LOCK CMPXCHG が CAS に対応します。XCHG だけは LOCK プレフィックスを書かなくても暗黙にアトミックになる特例です。

// FAA を CAS で模倣する（CAS が万能であることの例）
do {
    old = atomic_load(&v)
    new = old + delta
} while (!CAS(&v, old, new))   // 誰かが先に変えたら old を読み直してやり直す

CAS が失敗を返せることが本質的に重要です。失敗は「読んでから書こうとするまでの間に他コアが割り込んだ」事実そのもので、これを起点に再試行するのがロックフリーの基本形になります。CAS を軸にしたロックフリー設計の詳細はカーネルのロックフリー同期とCAS を参照してください。

x86のLOCKプレフィックス：キャッシュラインを占有して1手にする

x86 でRMWをアトミックにする仕掛けが LOCK プレフィックス です。LOCK ADD [counter], 1 のように付けると、その命令が完了するまで対象のメモリ位置を 他コアから触らせない ことを保証します。

古い実装では、これは文字どおりメモリバスを丸ごとロックする「バスロック」でした。しかし1本のバスを止めると全コアが巻き添えになり遅すぎる。そこで現代のx86は、対象が1本のキャッシュライン（通常64バイト）に収まる場合、キャッシュコヒーレンスプロトコル（MESI）を使ってそのラインだけを排他所有（Modified状態）し続ける ことでロックを実現します。これがキャッシュロックです。

LOCK CMPXCHG の内側で起きること（概念）:
  1. 対象ラインを Exclusive/Modified で自コアに引き込む（他コアの複製を無効化）
  2. その所有を保持したまま 比較→（一致なら）書き込み を実行
  3. 完了まで他コアからの当該ラインへのコヒーレンス要求を待たせる

MESI による無効化と所有権移動の仕組みはキャッシュコヒーレンシとMESIプロトコルが土台です。注意点として、対象がキャッシュライン境界をまたぐ「スプリットロック」になると、ハードウェアは安全のため重いバスロックにフォールバックします。これは数百サイクル規模で全コアを止めるため、近年のカーネルは検出して警告・抑止します。

LOCKは「順序」も連れてくる

x86のLOCK付き命令は、アトミック性に加えて フルバリア（StoreLoad を含む） として働きます。つまりRMWの前後でメモリ順序の並べ替えが止まる。だから多くのコードはアトミック変数を使うだけでメモリオーダリングを別途意識せずに済みます。ただしこれは「重い」ことの裏返しでもあります。順序保証そのものの原理はメモリオーダリングとメモリバリアを参照してください。

ARM/RISC-VのLL/SC：占有ではなく「予約と失敗検知」

ARM や RISC-V、POWER は、x86 とは逆の発想を取ります。ラインを占有し続けるのではなく、予約を張って、横取りされたら書き込みを失敗させる。これが LL/SC（Load-Linked / Store-Conditional） 方式です。

LL（ロードリンク）：値を読むと同時に、そのアドレスに対する 予約（reservation） をコアに記録する。
SC（ストアコンディショナル）：書き込みを試みる。LL 以降に 他コアがそのアドレス（が属するラインの粒度）に書いていなければ成功、書いていれば失敗 する。

; ARM: counter を +1 する典型ループ（擬似）
retry:
  LDXR  w1, [counter]   ; ロードリンク：読みつつ予約を張る
  ADD   w1, w1, #1
  STXR  w2, w1, [counter] ; ストアコンディショナル：w2=0なら成功、1なら失敗
  CBNZ  w2, retry         ; 失敗（横取りされた）なら頭からやり直す

ここが本質的に重要なのですが、LL/SC では CAS のような「比較」はハードウェアがしません。SC が見ているのは「値が同じか」ではなく「予約の間に誰かが触ったか」です。だから値が A→B→A と一周して戻っても、その間に書き込みがあれば予約が壊れて SC は失敗します。つまり LL/SC は本質的に ABA 問題に強い。一方 CAS は値しか見ないため、別途の対策（世代カウンタ等）が要ります。

LL/SCは『成功しすぎない』──偽失敗が原理的に起きる

SC は本当の競合がなくても失敗することがあります（spurious failure、偽失敗）。予約はキャッシュライン粒度で追跡されるため、別の変数への書き込み、割り込み、コンテキストスイッチ、果ては関係ない近傍アクセスでも予約が外れて SC が失敗しうる。だから LL/SC は 必ず再試行ループで囲む のが前提で、ループ内に複雑な処理（メモリアクセスや関数呼び出し）を置くと予約が外れ続けて前進できなくなります。中身は最小限に保つのが鉄則です。

観点	LOCKプレフィックス（x86 TSO）	LL/SC（ARM / RISC-V / POWER）
原理	対象ラインを排他所有して1手に固める	予約を張り、横取りされたらストアを失敗させる
失敗の有無	命令単位では失敗しない（CMPXCHGは比較不一致で更新せず成否を返す）	競合・偽失敗でSCが失敗しうる。必ず再試行ループが要る
ABA問題	CASは値しか見ないため起こりうる	予約方式なので原理的に起きにくい
命令例	LOCK XADD / XCHG / LOCK CMPXCHG	LDXR-STXR / LR-SC / lwarx-stwcx.

キャッシュラインバウンシング：アトミックの本当のコスト

アトミック命令の代償は、命令1個の実行時間ではなく キャッシュコヒーレンスのトラフィック にあります。RMW は対象ラインを自コアに排他所有させる必要があり、別コアがそのラインを持っていれば、まず そのコピーを無効化して所有権を奪い取る 必要があります。

複数コアが同じカウンタを激しく更新すると、その1本のラインが コア間を行ったり来たり します。これが キャッシュラインバウンシング です。所有権の移動はコア間あるいはソケット間の通信を伴い、L1ヒットなら数サイクルの読み書きが、数十〜数百サイクル に膨れ上がります。アトミックがスケールしない主因はここにあり、CPU命令としてのコストよりはるかに大きいのです。NUMA をまたぐと所有権移動がさらに高くつく点は NUMAとメモリ局所性も参照してください。

コア0: lock add [c],1  → ライン所有権をコア0へ（コア1のコピーを無効化）
コア1: lock add [c],1  → ライン所有権をコア1へ（コア0のコピーを無効化）
コア0: lock add [c],1  → また奪い返す……（バウンシング）
  → 1更新ごとにコア間でラインが往復し、スループットが頭打ちになる

フォルスシェアリング：無関係な変数が同じ行に同居する罠

バウンシングが最も理不尽な形で現れるのが フォルスシェアリング（偽共有） です。コヒーレンスは キャッシュライン単位（64バイト） で動くため、論理的に無関係な2つの変数が同じラインに同居 していると、片方を更新しただけでもう片方を持つコアのコピーまで無効化されます。

struct {
    long a;   // コア0がひたすら更新
    long b;   // コア1がひたすら更新（aの直後＝同じ64Bライン上）
}
→ a と b は別変数で共有していないのに、同じラインなので
  コア0のa更新がコア1のbのコピーを無効化し、互いに足を引っ張り合う

排他制御もしていない、競合もしていないはずの2変数が、メモリ配置が近いだけ で深刻に劣化する。これがフォルスシェアリングの怖さです。対策はラインを共有させないこと、すなわち パディングやアライメントで頻繁に書く変数を別ラインへ追い出す ことです。

// 各カウンタを64バイト境界に揃え、1ライン1変数にする
struct alignas(64) PaddedCounter { long v; };
PaddedCounter counters[N];   // コアごとに別ラインを更新 → バウンシングを回避

フォルスシェアリングは計測しないと見えない

フォルスシェアリングはコードを読んでも気づけません。ロジックは正しく、ロックも正しく、それでもコア数を増やすほど遅くなる。perf c2c のようなツールでコヒーレンスの競合を可視化して初めて判明することが多い、典型的な「正しいのに遅い」バグです。カウンタ配列・統計値・スピンロックのフラグなど、コアごとに別の要素を頻繁に書く構造 が要注意箇所です。

試験・面接で問われる要点

counter++ はロード・演算・ストアの3手のRMW。隙間に割り込まれるとロストアップデートが起きる。これを不可分にするのがアトミックRMW。
RMWの3類型は FAA / swap / CAS。CASが最も汎用で、失敗時に再試行するのがロックフリーの基本形。
x86は LOCKプレフィックス でラインを排他所有して1手にする。ARM/RISC-Vは LL/SC（予約と失敗検知）。LL/SCはABA問題に強いが偽失敗があり再試行が必須。
アトミックの真のコストは キャッシュラインバウンシング。無関係な変数の同居で起きる フォルスシェアリング はパディングで回避する。

まとめ──不可分にする原理と、その代償

まとめ

counter++ は ロード・演算・ストア の3手に分かれ、その隙間に他コアが割り込むと更新が消えます。これを不可分な1手にするのが アトミックなRMW で、FAA・swap・CAS の3類型があり、CASが最も汎用です。実現方法はアーキテクチャで分かれ、x86は LOCKプレフィックス で対象キャッシュラインを排他所有して固め、ARM/RISC-Vは LL/SC の予約と失敗検知で同じ効果を出します（後者はABAに強いが偽失敗があり再試行必須）。そして忘れてはならないのが代償です。アトミックの本当のコストは命令時間ではなく キャッシュラインバウンシング にあり、無関係な変数の同居が引き起こす フォルスシェアリング はパディングで断ち切ります。土台となるCASとロックフリー設計はカーネルのロックフリー同期とCAS、ラインの無効化が起きる仕組みはキャッシュコヒーレンシとMESIプロトコルを合わせてどうぞ。