メモリモデルと並行データ構造

この章でわかること:

• CPUが読み書きを並べ替える機構的な理由(ストアバッファ)と、 並べ替えが実際に起きる瞬間の観測(実測: 20万回中1万3千回)
• ハードウェアのメモリモデルの違い(x86-TSOとARM)と、 RustのOrderingが「何からの抽象」なのか
• アトミック命令の実装とCAS(compare-and-swap)
• ロックフリーデータ構造の基礎 — Treiberスタック、ABA問題、メモリ回収
• なぜ体系に必須か — 5章はOrderingの使い方を 示しただけでした。「なぜそれが必要か」の機構を知らないと、 並行コードの正しさを自分で判断できません

並べ替えの犯人 — ストアバッファ

3章でCPUは命令をアウトオブオーダーで実行すると 学びました。しかし話はそこで終わりません。メモリへの書き込みには 専用の仕掛けがもう1つあります。

書き込みは、L1キャッシュに直接行われません。まず ストアバッファ(store buffer)というコア内の待ち行列に置かれ、 CPUは完了を待たずに次の命令へ進みます。バッファの中身は、 その後の都合のよいタイミングでL1へ流し込まれます。 5章で見たとおり、書き込みにはラインの 排他的所有権の獲得(数十サイクル)が必要なので、 この「あとでまとめて」方式はレイテンシ隠蔽として非常に有効です。

自分のコアは、ストアバッファの中身を直接読み戻せます (store-to-load forwarding)。だから1スレッドの世界では 何も壊れません。問題は他のコアです。バッファに滞在中の書き込みは、 他のコアからまだ見えません。ここから奇妙な現象が生まれます。

自分の書き込み(バッファ行き)より、その後の読み出し(L1から即座)が 先に「世界に対して」実行される——ストアとロードの並べ替えです。

実験 — 並べ替えを目撃する

理屈だけでは信じがたいので、観測します。古典的なリトマステストです。

• スレッドA: X = 1 と書いてから、Y を読む
• スレッドB: Y = 1 と書いてから、X を読む

両スレッドが命令どおりの順序で動くなら、両方が0を読むことは 論理的にありえません(先に読んだ側がいるなら、相手の書き込みは その後にあるはずだから…と、あらゆる交互配置を考えても両方0は 作れません)。20万回試します。

「ありえない」結果は何回起きるか

use std::sync::atomic::{AtomicI32, AtomicUsize, Ordering::*};
use std::thread;

// ストア→ロードの並べ替えを観測するリトマステスト。
// 2つのスレッドが同時に「自分の変数に1を書く → 相手の変数を読む」。
// 命令どおりの順序で実行されるなら、両方が0を読むことはありえない。
fn litmus(trials: usize, seqcst: bool) -> usize {
    let x = AtomicI32::new(0);
    let y = AtomicI32::new(0);
    let r2 = AtomicI32::new(0);
    let bar = AtomicUsize::new(0);

    // 2スレッド用のバリア: 両方が到達するまで待つ
    let barrier = |target: usize| {
        bar.fetch_add(1, AcqRel);
        while bar.load(Acquire) < target {
            std::hint::spin_loop();
        }
    };

    let mut both_zero = 0;
    thread::scope(|s| {
        // スレッドB
        s.spawn(|| {
            for t in 0..trials {
                y.store(0, Relaxed);
                barrier(4 * t + 2); // 準備完了を待ち合わせ
                if seqcst {
                    y.store(1, SeqCst);
                    r2.store(x.load(SeqCst), Relaxed);
                } else {
                    y.store(1, Relaxed);
                    r2.store(x.load(Relaxed), Relaxed);
                }
                barrier(4 * t + 4); // 実行完了を待ち合わせ
            }
        });
        // スレッドA(このスレッドが判定も行う)
        for t in 0..trials {
            x.store(0, Relaxed);
            barrier(4 * t + 2);
            let r1 = if seqcst {
                x.store(1, SeqCst);
                y.load(SeqCst)
            } else {
                x.store(1, Relaxed);
                y.load(Relaxed)
            };
            barrier(4 * t + 4);
            if r1 == 0 && r2.load(Relaxed) == 0 {
                both_zero += 1;
            }
        }
    });
    both_zero
}

fn main() {
    let trials = 200_000;
    println!(
        "Relaxed: {trials}回中 {:>6}回、両方が0 (並べ替えを観測)",
        litmus(trials, false)
    );
    println!(
        "SeqCst : {trials}回中 {:>6}回、両方が0",
        litmus(trials, true)
    );
}

use std::sync::atomic::{AtomicI32, AtomicUsize, Ordering::*}; use std::thread; // ストア→ロードの並べ替えを観測するリトマステスト。 // 2つのスレッドが同時に「自分の変数に1を書く → 相手の変数を読む」。 // 命令どおりの順序で実行されるなら、両方が0を読むことはありえない。 fn litmus(trials: usize, seqcst: bool) -> usize { let x = AtomicI32::new(0); let y = AtomicI32::new(0); let r2 = AtomicI32::new(0); let bar = AtomicUsize::new(0); // 2スレッド用のバリア: 両方が到達するまで待つ let barrier = |target: usize| { bar.fetch_add(1, AcqRel); while bar.load(Acquire) < target { std::hint::spin_loop(); } }; let mut both_zero = 0; thread::scope(|s| { // スレッドB s.spawn(|| { for t in 0..trials { y.store(0, Relaxed); barrier(4 * t + 2); // 準備完了を待ち合わせ if seqcst { y.store(1, SeqCst); r2.store(x.load(SeqCst), Relaxed); } else { y.store(1, Relaxed); r2.store(x.load(Relaxed), Relaxed); } barrier(4 * t + 4); // 実行完了を待ち合わせ } }); // スレッドA(このスレッドが判定も行う) for t in 0..trials { x.store(0, Relaxed); barrier(4 * t + 2); let r1 = if seqcst { x.store(1, SeqCst); y.load(SeqCst) } else { x.store(1, Relaxed); y.load(Relaxed) }; barrier(4 * t + 4); if r1 == 0 && r2.load(Relaxed) == 0 { both_zero += 1; } } }); both_zero } fn main() { let trials = 200_000; println!( "Relaxed: {trials}回中 {:>6}回、両方が0 (並べ替えを観測)", litmus(trials, false) ); println!( "SeqCst : {trials}回中 {:>6}回、両方が0", litmus(trials, true) ); }

▶ 実行編集stable / releasePlaygroundで開く ↗

筆者の実測(Playground)では、Relaxedでは20万回中13,122回、 「ありえない」はずの両方0が観測されました。約6.6%です。 SeqCstにすると0回になります。

これがストアバッファの実物です。両スレッドの書き込みがそれぞれの バッファに滞在している間に、両者が相手の(まだ0の)変数を読んだのです。 SeqCstのストアは「バッファが空になるまで待つ」命令 (またはフェンス)にコンパイルされるため、この現象を封じます。

大事な注意を2つ。第一に、これはコンパイラの最適化(6章)の 話ではありません。機械語が命令どおりに並んでいても、 CPU自身が並べ替えます。OrderingはコンパイラとCPUの両方を 制約するための指定です。第二に、この実験はx86で行われています。 「x86は順序に強い」とよく言われますが、ストア→ロードだけは x86ですら並べ替わるのです。

ハードウェアのメモリモデル

CPUが許す並べ替えの範囲をメモリモデル(memory model)と呼びます。 主要な2系統を対比します。

	x86-64 (TSO)	ARM64 (weak)	RISC-V (weak)
ストア→ロード	並べ替わる(実験のとおり)	並べ替わる	並べ替わる
ロード→ロード	保たれる	並べ替わる	並べ替わる
ストア→ストア	保たれる	並べ替わる	並べ替わる
Acquire/Releaseの実装	通常のmov(追加コストなし)	専用命令(ldar/stlr)	フェンス命令や命令注釈

x86のTSO(total store order)は「ストアバッファ由来の並べ替え 以外は許さない」強いモデルです。このためx86では、 Acquire/Release指定は実行時コストゼロ(コンパイラの並べ替え 抑止だけが仕事)で、SeqCstのストアだけが高くつきます。 一方ARMやRISC-Vはずっと弱いモデルで、Acquire/Releaseにも それ用の命令が必要です。

ここでRustのOrderingの正体がはっきりします。それは 「どのCPUのモデルの上でも同じ保証が成り立つように書く」ための 抽象です。x86で動いたからとRelaxedを乱用したコードは、 ARMのスマートフォンやMacで壊れます。逆に、この抽象に従って 書いたコードは、コンパイラが各CPUで必要十分な命令を選んでくれます。

アトミック命令の実装

fetch_addのような読み書き一体の操作(RMW)の実装も アーキテクチャで異なります。x86は命令にlockプレフィックスを 付けて「この1命令の間、対象ラインを占有する」方式です。 ARMは伝統的にLL/SC(load-linked/store-conditional)—— 「読んでから書くまでに誰かが触ったら失敗して再試行」方式で、 近年の世代はこれに加えて専用のアトミック命令群(LSE)も持ちます。 なお、x86ではRelaxedのfetch_addもSeqCstのそれも 同じlock付き命令になります。orderingを弱めても x86のRMWは速くなりません(ARMでは差が出ます)—— 「計測したが差がない」ときの理由がこれです。

ロックか、アトミックか

機構がわかったところで、実務の選択に降ります。 まず、最も基本的な比較——共有カウンタをMutexで守る場合と アトミックにする場合です。

共有カウンタ: Mutex vs AtomicU64

use std::sync::Mutex;
use std::sync::atomic::{AtomicU64, Ordering};
use std::thread;
use std::time::Instant;

fn main() {
    let iters = 5_000_000u64;

    let counter = AtomicU64::new(0);
    let start = Instant::now();
    thread::scope(|s| {
        for _ in 0..2 {
            s.spawn(|| {
                for _ in 0..iters {
                    counter.fetch_add(1, Ordering::Relaxed);
                }
            });
        }
    });
    println!("AtomicU64 : {:>9.3?} (計 {})", start.elapsed(), counter.load(Ordering::Relaxed));

    let counter = Mutex::new(0u64);
    let start = Instant::now();
    thread::scope(|s| {
        for _ in 0..2 {
            s.spawn(|| {
                for _ in 0..iters {
                    *counter.lock().unwrap() += 1;
                }
            });
        }
    });
    println!("Mutex<u64>: {:>9.3?} (計 {})", start.elapsed(), *counter.lock().unwrap());
}

use std::sync::Mutex; use std::sync::atomic::{AtomicU64, Ordering}; use std::thread; use std::time::Instant; fn main() { let iters = 5_000_000u64; let counter = AtomicU64::new(0); let start = Instant::now(); thread::scope(|s| { for _ in 0..2 { s.spawn(|| { for _ in 0..iters { counter.fetch_add(1, Ordering::Relaxed); } }); } }); println!("AtomicU64 : {:>9.3?} (計 {})", start.elapsed(), counter.load(Ordering::Relaxed)); let counter = Mutex::new(0u64); let start = Instant::now(); thread::scope(|s| { for _ in 0..2 { s.spawn(|| { for _ in 0..iters { *counter.lock().unwrap() += 1; } }); } }); println!("Mutex<u64>: {:>9.3?} (計 {})", start.elapsed(), *counter.lock().unwrap()); }

▶ 実行編集stable / releasePlaygroundで開く ↗

筆者の実測(Playground、2スレッド)では、アトミックが約68ミリ秒、 Mutexが約270ミリ秒で4倍差でした。Mutexの各回は 「ロック獲得(アトミック操作)+加算+解放(アトミック操作)」なので、 最低でもアトミック2回分+αを払います。単一の数値やフラグなら アトミック型が有利、という5章の指針の数字的裏付けです。

ただしMutexを過度に恐れないでください。競合が少なければ ロック獲得はアトミック1回とほぼ同じで、守れる対象は任意に複雑に できます。まずMutexで正しく書き、計測で競合が見えたら考えるが 正しい順序です。

ロックフリーの基礎 — CASとその困難

ロックなしで複雑な構造を更新する鍵は CAS(compare-and-swap)です。Rustではcompare_exchange—— 「現在値が期待どおりなら新値に置き換える、違ったら失敗を返す」を 1つのアトミック操作で行います。典型は「読む→計算する→CASする→ 失敗ならやり直す」というリトライループです。

古典のロックフリースタック(Treiberスタック)のpushはこう書けます。 コードには生ポインタとunsafeが登場します——正確な規則は 20章で扱うので、ここでは骨格として 読んでください。

// 概念を示す骨格(そのままでは後述の問題がある)
fn push(head: &AtomicPtr<Node>, new: *mut Node) {
    loop {
        let old = head.load(Ordering::Relaxed);
        unsafe { (*new).next = old; }
        // headがoldのままなら、newに差し替える
        if head.compare_exchange(old, new,
            Ordering::Release, Ordering::Relaxed).is_ok() {
            break;
        }
        // 誰かが先に更新した。読み直してやり直し
    }
}

しかし、ここから先が本当の難所です。

• ABA問題 — popの実装でCASの直前に他スレッドが 「Aをpopし、別のものをpushし、たまたま同じアドレスAが再利用される」 と、値はA→B→Aと変わったのにCASは「変わっていない」と誤認します。 ポインタにバージョン番号を添える(タグ付きポインタ)のが古典的対策です
• メモリ回収問題 — popしたノードをいつ解放してよいか? 他のスレッドがまだそのポインタを読んでいる最中かもしれません。 ロックがないため「誰も見ていない」保証が自明でないのです。 実用解がエポックベース回収(epoch-based reclamation)で、 「全スレッドがある時点を通過したら、それ以前に外したメモリは 解放してよい」と世代管理します

Rustでは、この難所はunsafeの世界です(20章)。 そして実務の答えはほぼ決まっています——自作しない。 crossbeamクレートが エポック回収(crossbeam-epoch)とロックフリーキュー等の既製品を 提供しており、標準のmpscより高速なチャネルも含みます。 自作のロックフリーは、計測がロックの競合を示し、既製品で 足りないと確認できたときの最終手段です。

まとめ

• 書き込みはストアバッファ経由です。このため「ストア→ロード」は x86ですら並べ替わり、実験では20万回中1.3万回観測されました
• ハードウェアのメモリモデルはCPU系統で強さが違います。 RustのOrderingは、その差を吸収して移植可能な保証を書くための 抽象です(x86ではAcquire/Releaseは実質無料)
• 共有カウンタの実測ではアトミックがMutexの4倍速でした。 ただし設計はMutexから始め、計測してから最適化します
• ロックフリーの核心はCASのリトライループですが、ABA問題と メモリ回収問題という難所があります。実務ではcrossbeamの既製品を 使い、自作は最終手段です

Part IVはここまでです。CPUとメモリの「深層」——数の表現、 アドレス変換、キャッシュの内部、命令供給、メモリモデル——が 揃いました。Part Vでは、この土台の上でRust固有の深層—— アロケータ、async、unsafe、ビルド、データ構造——に踏み込みます。