アトミック命令と同期プリミティブのハード実装

なぜ命令1つの「不可分性」が問題になるのか

counter = counter + 1 は高級言語では1行でも、機械語では「ロード→加算→ストア」の3段です。2つのコアが同時に実行すると、両方が同じ古い値をロードし、それぞれ加算してストアし、結果として加算が1回ぶん消える(ロストアップデート)。これを防ぐのがアトミック命令で、read-modify-write(RMW)の全体を、途中を誰にも観測・割り込みさせない不可分操作として実行します。ソフトのロックも突き詰めれば、こうしたハードのアトミック命令1個の上に組み上がっています。

不可分性は「実行中ずっと値を独占する」ことを意味します。鍵は、その独占をどの粒度で確保するかです。歴史的にはメモリバス全体を、現代では1本のキャッシュラインだけを占有します。

バスロックからキャッシュロックへ

初期の x86 では、lock 接頭辞付き命令はメモリバスにロック信号(LOCK#)を張り、RMW が終わるまで他のすべてのバスマスタのアクセスを止めていました。これがバスロックです。確実ですが、無関係なアドレスへのアクセスまで巻き添えで止まるため、コア数が増えるほど致命的なボトルネックになります。

現代の実装は**キャッシュロック(cache locking)**へ進化しました。RMW 対象のデータが1本のキャッシュラインに収まり、そのコアがラインをコヒーレンスプロトコルの M(Modified) または E(Exclusive) 状態で保持できるなら、バスを止める必要はありません。

1. RMW 開始時、対象ラインを Read-For-Ownership(RFO) で要求し、他コアの全コピーを Invalid にする(排他取得)。
2. ラインを M/E で握っている間に、ロード・演算・ストアを完了する。
3. その間に来る他コアのスヌープ要求は、RMW が終わるまで応答を保留(または完了後に処理)し、外からは中間状態が一切見えないようにする。

つまりロックの単位がバス全体から「1ライン」へ縮み、無関係なメモリアクセスは並行して進めます。MESI などキャッシュコヒーレンスの「書き込み前に他コピーを無効化する」性質が、そのままアトミック性の土台になっている点が要です。バスロックは消滅したわけではなく、対象がラインをまたぐ(アラインメント違反)など、キャッシュロックで完結できない場合のフォールバックとして残ります。

主要プリミティブ：CAS・fetch-and-add・LL/SC

ハードが提供する RMW は大きく2系統あります。

compare-and-swap(CAS) は「メモリの現在値が期待値と等しければ新値に差し替え、結果(成否や旧値)を返す」操作です。ロックフリーなデータ構造の中核ですが、値が A → B → A と戻ると変化を見逃す ABA 問題 を持ち、バージョンカウンタ併用などで対処します。x86 の lock cmpxchg が代表で、CAS の詳細なループ構成はロックフリーと CASが扱います。

fetch-and-add は「加算して加算前の値を返す」操作で、チケットロックや参照カウンタに向きます。CAS と違い競合下でも必ず一度で成功するため、後述のフォワードプログレスの観点で優れます。

LL/SC(load-linked / store-conditional) は RISC 系の手法です。load-linked で読むと同時にそのアドレスを**予約(reservation)**し、store-conditional は「予約が破られていなければ書いて成功、破られていれば書かずに失敗」を返します。予約はコヒーレンスと連動し、他コアがそのラインへ書き込む(無効化が届く)と予約が外れます。

// LL/SC で fetch-and-add を合成する典型形
retry:
    ll   r1, [addr]      // 予約しつつロード
    add  r2, r1, #1
    sc   r3, r2, [addr]  // 予約が生きていれば書いて r3=成功
    beqz r3, retry       // 失敗(他コアが割り込んだ)なら再試行

LL/SC は単一プリミティブで CAS・fetch-and-add・任意の RMW を表現できる柔軟さが強みですが、「失敗したら再試行」という楽観的な構造ゆえに、競合時はループが回り続けるリスクを抱えます。

競合時のフォワードプログレスとライブロック

複数コアが同じアトミック変数を激しく叩くと、キャッシュラインが M 状態のまま各コアの間を往復し続けます(キャッシュライン・バウンシング)。各 RFO は他コアの無効化とライン転送を伴うため、コア数に対してスループットが伸びず、むしろ悪化します。これは正しさの問題ではなく性能の問題ですが、LL/SC ではさらにライブロックという正しさに近い危険があります。

CAS ベースのループ(do { 旧値読む; 新値計算; } while(!CAS))もロックフリーではあります。これは「全体として少なくとも1スレッドは必ず前進する」保証で、システムが止まらないことを意味します。一方 fetch-and-add 系は個々のスレッドが有限ステップで完了する**待機自由(wait-free)**で、より強い公平性を持ちます。フォワードプログレスの強さは 待機自由 > ロックフリー > 障害なし(obstruction-free) の順で、ハードプリミティブの選択がこの保証レベルを直接左右します。

リモートアトミック：演算をメモリ近傍へ送る

ラインバウンシングの根本原因は「演算するためにデータをコアまで引き寄せる」ことです。そこで近年は発想を逆転させ、演算をデータの近くへ送るリモートアトミック(near-memory atomic)が広がりました。

ARMv8.1 の LDADD/SWP などの命令は、競合が激しいと判断されればコアでラインを取得せず、演算要求そのものを共有キャッシュ(LLC)やメモリコントローラ、相互接続のホームノードへ送り、そこで RMW を実行して結果だけ返せます。データはホーム側に居続けるため、コア間でラインを奪い合うバウンシングが起きません。x86 系でも xadd を LLC 側で処理する最適化が見られます。

この考え方は単一チップを超え、CXL のようなコヒーレント相互接続の世界へも延びます。デバイスやメモリプールに対するアトミックを、データの所在地(ホーム)で実行することで、長い往復遅延を避けつつ整合性を保ちます。near-memory アトミックは、高競合カウンタやヒストグラム集計のように「多数のコアが少数の変数を更新する」ワークロードで特に効きます。

まとめ

• アトミック命令は read-modify-write を不可分に実行し、ソフトのロックや lock-free 構造の最下層を支える。
• 実装はバスロックからキャッシュロックへ進化し、対象ラインを M/E 状態で排他確保してコヒーレンスのスヌープを退けることで、1ライン粒度の独占を実現する。
• CAS と fetch-and-add は専用命令、LL/SC は予約付きで汎用 RMW を楽観的に合成する。フォワードプログレスは待機自由＞ロックフリーの順で強く、LL/SC はライブロック対策が要る。
• 高競合では near-memory のリモートアトミックが演算をデータ側へ送り、ラインバウンシングを回避する。

命令の並列実行の文脈はアウトオブオーダー実行が、ライン無効化の土台はキャッシュメモリの原理が掘り下げます。