← OSと低レイヤのしくみ コース
15. アトミック命令 — なぜCASが同期の土台になるのか
compare-and-swap(CAS)が「比べて、一致したときだけ書き換える」を不可分に行う仕組みを図で追っていきましょう。
① 「1行の足し算」は本当は3手順に分かれている
counter++ソース上は1行
不可分に見えるコンパイル後は3命令になる
1. loadメモリ → レジスタ
2. addレジスタ内で +1
3. storeレジスタ → メモリ
- ・load と store は別々のメモリアクセスで、その間にレジスタ上の計算が挟まります
- ・命令と命令の境目では、別のハート(ハードウェアスレッド)が同じアドレスに触れられます
ソース上の1行が不可分だという保証はどこにもありません。読み・計算・書き戻しが分かれている以上、その隙間が問題になります。
② 隙間に他CPUが入ると更新が消える(lost update)
counter = 5メモリ上の初期値
両者がまだ書き戻す前に読む
CPU-A: load → 5レジスタに 5
CPU-B: load → 5レジスタにも 5
それぞれ自分のレジスタで +1
CPU-A: 5+1 = 6
CPU-B: 5+1 = 6
順に書き戻す
counter = 62回足したのに 6
期待値は 7- ・2回の加算のうち片方の結果が上書きされて消えます
- ・これが lost update です。ロックもCASも、この隙間を無くすために存在します
どちらのCPUも正しく動いているのに結果が壊れます。原因は「読んでから書くまでの間に値が変わりうる」ことです。
③ CASは「期待値と一致したときだけ書く」を不可分に行う
CAS(addr, old, new)この全体が不可分
メモリの現在値と old を比較
現在値 == old誰も触っていない
現在値 != old誰かが書き換えた
結果
new を書き込む成功を返す
書き込まない失敗を返す
- ・比較と書き込みの間に他CPUが割り込めない点が本質です
- ・old は「自分が読んだときの値」。一致は『読んでから今まで誰も変えていない』証拠になります
CASは値を守るのではなく「自分が見た前提がまだ成立しているか」を検査します。前提が崩れていれば書かずに失敗を返します。
④ 失敗したらやり直す — リトライループ
old = load(counter)現在値を読む
新しい値を計算
new = old + 1
不可分に検査して書く
CAS(counter, old, new)
結果で分岐
成功 → 完了更新が確定
失敗 → 先頭へ戻る読み直してやり直す
- ・失敗は異常ではなく、他CPUが先に成功したという通常の合図です
- ・失敗した側がやり直すので lost update は起きません
CAS単体は1回の検査にすぎず、ループと組み合わせて初めて更新処理になります。ロックを取らずに進むので lock-free と呼ばれます。
⑤ 実現方式(1) x86 の lock cmpxchg
lock cmpxchg [mem], src期待値は EAX / RAX 側
TEMP := DEST してから比較
accumulator == TEMP
accumulator != TEMP
仕様上の結果
ZF := 1, DEST := SRC書き込み成功
ZF := 0, accumulator := TEMP現在値がEAXに返る
- ・比較対象は AL / AX / EAX / RAX。幅はオペランドサイズで決まります
- ・成功・失敗は ZF フラグで判定します
- ・LOCK プレフィクスで不可分になります。宛先がメモリオペランドでない場合 LOCK は #UD 例外です
- ・失敗時は現在値がアキュムレータに入るため、次の試行の期待値としてそのまま使えます
x86は1命令で比較と交換を完結させます。失敗時に現在値が返るので、リトライで読み直す必要がありません。
⑥ 実現方式(2) RISC-V の LR/SC
lr.w rd, (rs1)符号拡張して rd へ
reservation set を登録この間に他CPUが書くと予約が無効化される
新値を計算読んだ値から書きたい値を作る
sc.w rd, rs2, (rs1)
予約が有効 → 成功rs2 を書き、rd = 0
予約が無効 → 失敗書かず、rd に非ゼロ
- ・SC の成否は rd で返ります。成功で 0、失敗で非ゼロです
- ・LR は値そのものではなく『このバイト範囲を見張る』という予約を登録します
- ・値を比較しないため、同じ値に戻っていても書き換えを検知できます(ABA問題の回避)
- ・SC は直前の LR と同じアドレス・同じデータ幅を対象にする必要があります
CASを1命令にせず、予約(LR)と条件付きストア(SC)の2命令に分けたのがRISC-Vの方式です。値の一致ではなく予約の生存で判定するのが特徴です。
⑦ 命令エンコーディングと、なぜ2命令に分けたのか
inst[31:27] = funct5LR.W=00010 / SC.W=00011
inst[26] = aqacquire
inst[25] = rlrelease
残りは通常のR形式と同じ並び
inst[24:20] = rs2LR.W では 0 固定
inst[19:15] = rs1アドレス
inst[14:12] = funct3.w は 010
inst[11:7] = rdSC は成否を返す
- ・LR.W は書き込む値を持たないため rs2 フィールドは 0 と定められています
- ・aq / rl はメモリ順序付けのためのビットで、AMO 形式の命令に用意されています
- ・constrained LR/SC ループは、命令列がメモリ上に連続して並び最大16命令であることなどが条件です
- ・LR と SC の間には基本I命令セットのみを置け、ロード・ストア・後方ジャンプ・成立する後方分岐・JALR・FENCE・SYSTEM は置けません
- ・条件を満たすループなら、他が無条件ストアやAMOを行わない限り、いずれかのハートが必ずループを抜けられると保証されます
設計理由はここにあります。2命令に分ければ計算を普通の命令で書けるため、CAS専用の複雑な命令を作らずに済みます。代わりに『予約が壊れうる』ため、前進保証を制約付きループという形で規定しています。