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

この章でわかること:

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

並べ替えの原因: ストアバッファ

3章でCPUは命令をアウトオブオーダーで実行すると学びました。これに加えて、メモリへの書き込みに関わる専用の機構が、もう1つの並べ替えの要因になります。

書き込みは、まずストアバッファ(store buffer)というコア内の待ち行列に置かれ、L1キャッシュには直接行われません。 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)
    );
}

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

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

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

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

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

	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では差が出ます)。 x86で「orderingを弱めたが差がない」という計測結果が出る理由です。

ロックか、アトミックか

機構がわかったところで、実務での選択を検討します。最も基本的な比較として、共有カウンタを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());
}

筆者の実測(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;
        }
        // 他のスレッドが先に更新した。読み直してやり直し
    }
}

しかし、実用的なロックフリー構造には、さらに2つの難しい問題があります。

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では、これらを前提として、アロケータ、async、unsafe、ビルド、データ構造というRust固有の深層を扱います。