Lecture 15: Implementing Synchronization + Memory Consistency（实现同步 + 内存一致性）（日期：2025-11-13, Thursday）

目录 · ← l14 · l16 →

Lecture 15: Implementing Synchronization + Memory Consistency（实现同步 + 内存一致性）（日期：2025-11-13, Thursday）

概述：本讲先回顾 Lecture 14 的缓存一致性与 MSI/MESI 协议（slides 1–20），然后切入新主题：内存一致性（memory consistency）。Coherence 只约束”同一地址”的操作顺序，而 consistency 定义”不同地址”上的读写以何种顺序对其他线程可见。幻灯片讲清四个问题：(1) 顺序一致性（sequential consistency，Lamport 1976）是什么、为什么”00/10”输出不该出现；(2) 为什么需要放松一致性（relaxed consistency）——写缓冲与乱序执行为了隐藏内存延迟，会重排内存操作（TSO/PC/PSO/WO/RC）；(3) 同步如何”拯救”这一切——fence、acquire/release、read-modify-write（如 CAS）等原语恢复排序保证；(4) 语言层内存模型：C11/C++11 与 Java 5 承诺 “SC for DRF”（无数据竞争的程序获得顺序一致性）。本讲代码示例覆盖自旋锁、票锁、CAS 与 acquire/release 等同步原语的实现，展示”同步原语如何在放松的硬件上强制出 SC 行为”。

注意：本讲与 Assignment 2（任务图调度）中你使用的 mutex / condition variable / barrier 直接对应——这些库原语内部正是用自旋、CAS、acquire/release 与 fence 实现的；理解本讲能帮你判断”我的同步写对了吗”。另外第 15 讲（Nov 13）当天是 Assignment 4 截止日（Trainium2 Fused Conv+MaxPool），下周二是期中考试（覆盖 Lectures 1–14）。

一、核心概念与定义

1. Memory Coherence vs Memory Consistency（一致性 vs 一致性模型）

定义（slides 24-25）：coherence 定义同一内存位置上读写的观察行为——所有处理器必须对”对 X 的读写顺序”达成一致（能把涉及 X 的所有操作放到一条时间线上）。consistency 定义不同位置（如 X 与 Y）上读写的可见顺序——coherence 只保证”对 X 的写最终会传播”，consistency 决定”对 X 的写何时传播（相对于对其他地址的读写）”。
现实类比：coherence 像”会议室白板上内容的唯一性”（同一块白板只有一个内容）；consistency 像”你先后说出的两句话，听众听到的先后顺序”（不同句子 = 不同地址）。
金句（slide 25）：coherence 的目标是让并行机的内存系统表现得好像缓存不存在；而 consistency 定义的是有没有缓存都要遵守的、不同地址读写行为的规范。

2. Sequential Consistency（顺序一致性，SC）

定义（slide 30，Lamport 1976，图灵奖 2013）：所有内存操作按照某个全局串行顺序执行，就像操作单一共享内存；且每个线程的操作保持程序序（program order）。SC 系统维持全部四种内存操作排序：W→R、R→R、R→W、W→W（写 X 必须先于后续读 Y 提交，依此类推）。
现实类比（slide 31 的”开关隐喻”）：所有处理器按程序序发出 load/store，内存端有一个开关：随机选中某个处理器，把它的一条内存操作完整执行完，再选下一个……同一时刻只有一条操作在内存上执行。

图示：

    处理器0         处理器1
   A = 1           B = 1
   r1 = B          r2 = A
        \            /
         ▼          ▼
      ┌────────────────────┐
      │   Memory（开关轮流执行）│
      │   A = 0, B = 0      │
      └────────────────────┘
 每次"开关"选中一个处理器，完整执行其下一条内存操作

3. Program Order 与四种内存操作排序（Memory Operation Orderings）

定义（slide 27）：程序定义了一串 load/store（即这些操作的 program order）。四种排序约束：
- W_X→R_Y：对 X 的写必须先”提交”（结果可见）于后续对 Y 的读；
- R_X→R_Y：对 X 的读必须先提交于后续对 Y 的读；
- R_X→W_Y：对 X 的读必须先提交于后续对 Y 的写；
- W_X→W_Y：对 X 的写必须先提交于后续对 Y 的写。
现实类比：做饭时”放盐（写 A）必须在尝味（读 B）之前完成”这类工序约束；”先烧水再下面”是 W→W 约束。
注意：这里”提交”（commit）指结果对其他处理器可见，而不仅仅是执行单元执行完。

4. 经典例子：A/B 程序（”00”为什么不该出现）

定义（slide 28-29）：初始 A = B = 0；处理器 0 执行 A = 1; print B;，处理器 1 执行 B = 1; print A;。可能输出 “01”、”10”、”11”，但不应输出 “00” 或 “10”。
happens-before 图：把”必须发生的事件顺序”画成有向图；若某输出导致图中出现环（一个事件必须发生在它自己之前），则该输出不可能。
现实类比：两位同学各写一道题并互改——如果”甲必须先改到乙的答案、乙又必须先改到甲的答案”，这就是环，物理上不可能。

图示（”10” 为什么不可能：r1=0 要求 (2) 先于 (1)，r2=1 要求 (3) 先于 (4)，而程序序要求 (1) 先于 (2)、(3) 先于 (4)……构成环）：

要打印 "10"：r1 = B 得 0 → (2) 必须先于 (1) 完成
            r2 = A 得 1 → (3) 必须先于 (4) 完成
程序序：(1) → (2)，(3) → (4)
综合：(2)→(1)→…→(3)→(4)→… 需要 (2) 先于 (4) 且 (4) 先于 (2) → 环 → 不可能

5. Relaxed Consistency（放松一致性）

定义（slide 37）：放松模型允许违反某些内存操作排序约束，以换取性能——具体放松哪几条，决定了模型名称：TSO（放松 W→R）、PC（Processor Consistency，放松 W→R 且允许他人提前读新值）、PSO（Partial Store Order，再放松 W→W）、WO/RC（Weak Ordering / Release Consistency，几乎全部可重排）。
现实类比：快递可以”先送近的再送远的”（重排）以省时间——只要不违反”必须亲自签收的件不能让别人代签”这类关键约束；放松得越多，省的时间越多，但你需要自己加”加急件标记”（fence）来保证关键件顺序。
动机（slide 38-39）：内存访问在一致性系统中可能要做很多事（找数据、发失效等），写操作要几百个 cycle；若两条操作互不冲突（如 A=1 与 r1=B），没必要等第一条完成——重排/重叠它们能隐藏延迟。

6. Write Buffer（写缓冲）与 TSO

定义（slide 40-43）：处理器把写放入写缓冲（write buffer）后即可继续执行后续指令，不必等写真正到达缓存/内存；读时先查自己的写缓冲。代价：处理器自己的读可以”越过”自己的写（W→R 被放松）→ 出现 SC 下不可能的行为：r1 = r2 = 0。
现实类比：先记账后付款——你（处理器）在账本上记”已付”（写缓冲）就继续忙别的，供应商（其他处理器）要等钱真的汇出才看到”已付”。
关键事实（slide 43）：每个现代处理器都有写缓冲（Intel x86、ARM、RISC-V 皆是）；x86 用的是一种未完全定义的 TSO（Total Store Order）。TSO 只放松 W→R，W→W 仍保持（同一线程的写不重排）。

图示：

处理器0                    处理器1
A = 1 ──► [写缓冲]         B = 1 ──► [写缓冲]
r1 = B ──► (读自己的缓冲？)  r2 = A ──► (读自己的缓冲？)
      │                          │
      ▼                          ▼
      └──────────► Memory ◄──────┘
两个处理器的写都还"堵"在缓冲里，对方读不到 → r1 = r2 = 0 可能！

7. Fence（内存屏障 / 内存围栏）

定义（slide 50）：fence（memory barrier） 指令阻止重排：fence 之前的所有内存操作必须全部完成，fence 之后的任何内存操作才能开始。它是恢复排序保证的”万能工具”，但很昂贵（付出的是放松模型想省下的那部分性能）。
现实类比：工地上的”验收关卡”——所有已完工的工序必须验收完毕（之前的操作全部可见），才能开始下一批工序。
实例（slide 51）：x86 提供 _mm_lfence（等所有 load 完成）、_mm_sfence（等所有 store 完成）、_mm_mfence（等所有内存操作完成）；ARM 的一致性模型非常放松，需要更多显式屏障。

图示：

可重排的读和写……
═══════ MEMORY FENCE ═══════     ← 之前的操作全部完成、全部可见
可重排的读和写……
═══════ MEMORY FENCE ═══════

8. Acquire / Release 语义（同步原语的内存序）

定义：release（释放）：释放操作之前的所有内存操作，在释放之后对其他线程可见（”发布”出去）；acquire（获取）：获取操作之后的所有内存操作，必须能看到获取之前已被 release 发布的所有内容（”领取”回来）。二者成对出现，构成单向屏障：release 是”下行屏障”（前面的不许越过我），acquire 是”上行屏障”（后面的不许越过我）。比全量 fence 便宜，因为它只约束一个方向。
现实类比：发布朋友圈（release）：发之前发生的事，朋友都能看到；刷到朋友圈（acquire）：你接下来看到的（之后的操作）以这条朋友圈为基准。
要点：这是 C++11 std::atomic 中 memory_order_release / memory_order_acquire 的语义，也是锁（lock/unlock）、屏障（barrier）等库原语的内部基石。

9. Data Race（数据竞争）与 DRF

定义（slide 52-53）：两个处理器对同一内存位置的访问构成冲突，如果至少一个是写；若冲突访问没有被同步操作排序（如 fence、release/acquire、barrier），程序就是 unsynchronized 的，包含 data race——输出取决于处理器相对速度（非确定）。
现实类比：两个人同时改同一份 Word 文档（冲突写），且没有任何”审阅锁定”（同步），最后谁存盘谁赢——结果不可预测。
关键定理（slide 54）：同步化程序（data-race-free，DRF）在非 SC 系统上也得到 SC 结果——”If there are no data races, reordering behavior doesn’t matter”：访问被同步排序，同步强制出顺序一致性。实践中绝大多数程序通过锁、屏障等同步库写成 DRF 程序，而不是靠临时读写共享变量。

10. 语言级内存模型：SC for DRF

定义（slide 59）：现代语言 C11/C++11 与 Java 5 保证：无数据竞争的程序（DRF）获得顺序一致性（SC）——编译器负责针对目标硬件插入必要的同步（fence 等）来兑现这一承诺。如果你的程序有数据竞争，语言不提供任何保证（绝大多数程序员会认为有 race 的程序就是 buggy 的）。
现实类比：航空公司承诺”准时到达”（SC for DRF），但前提是你按规则托运（不用同步就乱写共享变量 = 不按规则）；违规者后果自负。
实践建议：用同步库（std::mutex、std::atomic 等），不要手工裸写内存序。

11. 同步原语：Spinlock / Test-and-Set / CAS / Ticket Lock（本讲代码部分的概念）

定义：这些都是”把放松的硬件拉回 SC 行为”的实现手段：
- test-and-set（TAS）：原子指令，读取并置位某内存单元，返回旧值（如 std::atomic_flag::test_and_set）；xchg 在 x86 上加 lock 前缀即原子。
- spinlock（自旋锁）：等待者用 TAS 循环”自旋”抢锁，直到成功；忙等（busy-wait）浪费 CPU，且高竞争下产生大量一致性通信。
- test-and-test-and-set（TTAS）：先普通读（test）看锁是否空闲，空闲才 TAS——把”每轮测试都写”降为”仅在锁释放时发一次失效”，一致性通信从 O(P)/次释放降到 O(P)/释放。
- CAS（compare-and-swap）：原子地”若当前值等于期望值则写入新值，返回旧值/是否成功”（std::atomic::compare_exchange_strong）；是构建无锁数据结构与各种同步的万能积木。
- ticket lock（票锁）：取号（fetch_add 自己的 ticket）→ 等待叫号（读 now_serving 直到等于自己的号）；获取锁只需读，每释放一次锁只产生一条失效（O(P) 通信总量），且先来先得（公平）。
现实类比：TAS 锁像”进门就抢把手”（乱抢、拥堵）；TTAS 像”先隔着玻璃看门开没开，开了才去抢”；票锁像银行取号——先取号（原子加一），然后坐着等叫号（只读显示屏）。

二、代码示例与详细解说（本讲重点）

示例 1：自旋锁（Spinlock）——`std::atomic_flag::test_and_set`

代码（C++11）：

#include <atomic>

class SpinLock {
    std::atomic_flag flag = ATOMIC_FLAG_INIT;   // 初始为 clear（未锁定）
public:
    void lock() {
        // 反复"测试并置位"：若返回 false，说明之前是 clear（我们抢到了锁）
        while (flag.test_and_set(std::memory_order_acquire)) {
            // 抢锁失败：忙等（自旋）——可加 pause/yield 降低功耗与总线压力
        }
    }
    void unlock() {
        flag.clear(std::memory_order_release);  // 释放：置回 clear
    }
};

// 使用示例：用自旋锁保护一个计数器
#include <thread>
#include <vector>
#include <cstdio>

int main() {
    SpinLock lock;
    int counter = 0;
    std::vector<std::thread> threads;
    for (int t = 0; t < 4; t++) {
        threads.emplace_back([&] {
            for (int i = 0; i < 100000; i++) {
                lock.lock();      // acquire：保证拿到锁后能看到锁保护的数据
                counter++;        // 临界区：互斥访问
                lock.unlock();    // release：保证临界区的写对其他线程可见
            }
        });
    }
    for (auto& th : threads) th.join();
    std::printf("counter = %d (期望 400000)\n", counter);
    return 0;
}

【代码做了什么？】

lock()：flag.test_and_set() 是原子指令——读出旧值并把 flag 置 1。若旧值为 0（锁空闲），我们抢锁成功；若旧值为 1（已被持有），返回 true，进入 while 循环忙等（spinning），不断重试直到抢到。
unlock()：flag.clear() 原子地把 flag 置 0，释放锁。
主程序用 4 个线程各加 10 万次计数器，靠自旋锁保证互斥，最终 counter 应恰为 400000（无数据竞争）。

【并行机制解说】

硬件如何支持原子性：test_and_set 对应硬件的 read-modify-write（RMW）原子指令——在 x86 上是 lock xchg 之类（原子前缀保证”读+写”不可分割）；原子性是同步的根基：若”读旧值”和”写新值”之间插进别的线程，抢锁逻辑就崩了。
为什么这里要 acquire/release：在放松的硬件（如 ARM）上，unlock() 用 release 保证”临界区内的所有写（如 counter++）在锁释放时对下一个持锁线程可见”；lock() 用 acquire 保证”拿到锁之后的操作能看到前一个持锁线程 release 的所有内容”。正是这对 acquire/release 把放松模型”拉回” SC 行为——这对应 slide 54 的论点：同步化的（DRF）程序在非 SC 系统上得到 SC 结果。
代价：高竞争时自旋锁产生大量一致性通信（每次 test_and_set 都是一次写，会失效其他缓存中的 flag——即”一锁释放，所有等待者同时抢”，一致性流量大）；且忙等浪费 CPU。这是”同步原语让排序更严格（slide 50）”的代价一面。
对应概念：test-and-set、spinlock、acquire/release、fence 的替代品。

示例 2：票锁（Ticket Lock）——公平且通信高效

代码（C++11，std::atomic）：

#include <atomic>
#include <thread>
#include <vector>
#include <cstdio>

class TicketLock {
    std::atomic<int> next_ticket{0};   // 发号器：下一位客人的号码
    std::atomic<int> now_serving{0};   // 叫号屏：当前服务到几号
public:
    void lock() {
        int my_ticket = next_ticket.fetch_add(1, std::memory_order_relaxed);
        // 取号：原子地把 next_ticket 加一并取回自己的号
        while (now_serving.load(std::memory_order_acquire) != my_ticket) {
            // 等待叫号：只读（没有写！）——直到 now_serving 变成自己的号
        }
    }
    void unlock() {
        // 叫下一个号：把 now_serving 加一
        now_serving.fetch_add(1, std::memory_order_release);
    }
};

int main() {
    TicketLock lock;
    int counter = 0;
    std::vector<std::thread> threads;
    for (int t = 0; t < 8; t++) {
        threads.emplace_back([&] {
            for (int i = 0; i < 50000; i++) {
                lock.lock();
                counter++;
                lock.unlock();
            }
        });
    }
    for (auto& th : threads) th.join();
    std::printf("counter = %d (期望 400000)\n", counter);
    return 0;
}

【代码做了什么？】

lock()：第一步取号——fetch_add 原子地把 next_ticket 加 1，并返回自己的号码 my_ticket；第二步等待——循环只读 now_serving，直到它等于自己的号码。
unlock()：把 now_serving 加 1（”叫下一个号”）。
与自旋锁的关键区别：等待期间不写任何共享变量（只有 fetch_add 取号时写一次）。

【并行机制解说】

为什么通信少：自旋锁里每个等待者反复 test_and_set（每次都是一次写，触发缓存行失效，抢锁风暴）；票锁等待者只做读 now_serving——读不会失效别人的副本，所有线程可以同时读自己的缓存副本，只有 unlock 的那一次 fetch_add 写会发出一条失效。于是每次释放锁只产生 O(P) 总量的一致性通信（每个等待者至多被失效一次），而自旋锁是每轮测试 O(P)。
公平性：取号顺序 = 获得锁的顺序（FIFO），先来先得——解决了 TAS 锁”释放时所有等待者一拥而上、谁快谁得”的不公平。
acquire/release 的角色：等待者用 acquire 读 now_serving，确保”看到自己的号被叫到”之后，能看到前一持锁者 release 出的临界区数据；unlock 用 release 把临界区写”发布”出去。同样地，这一对 acquire/release 保证整个程序（DRF）呈现 SC 行为。
对应概念：ticket lock、fetch_add、acquire/release、一致性通信开销。

示例 3：CAS（compare-and-swap）——原子更新与自旋 CAS 锁

代码（C++11，std::atomic::compare_exchange_strong）：

#include <atomic>
#include <thread>
#include <vector>
#include <cstdio>

// 用 CAS 实现"原子加一"（无锁的 fetch_add 替代品，教学演示）
void atomic_increment(std::atomic<int>& x) {
    int old = x.load(std::memory_order_relaxed);
    do {
        int expected = old;
        // 若 x 仍等于 expected，则把 x 写成 old+1，返回 true；否则返回 false 且 expected 被更新为当前值
        if (x.compare_exchange_strong(expected, old + 1, std::memory_order_relaxed))
            return;                     // 成功
        old = expected;                 // 失败：有人抢先改过，用最新值重试
    } while (true);                     // CAS 循环（compare-exchange loop）
}

// 用 CAS 实现一个"自旋 CAS 锁"（用 0=空闲、1=占用 表示锁）
class CASLock {
    std::atomic<int> state{0};
public:
    void lock() {
        int expected = 0;               // 期望锁是空闲的
        // 只有"state 从 0 变成 1"成功才代表抢到锁；失败则重试
        while (!state.compare_exchange_strong(expected, 1, std::memory_order_acquire)) {
            expected = 0;               // 恢复期望值，继续自旋
        }
    }
    void unlock() {
        state.store(0, std::memory_order_release);
    }
};

int main() {
    // 场景 A：8 个线程各做 5 万次 CAS 原子加
    std::atomic<int> x{0};
    std::vector<std::thread> threads;
    for (int t = 0; t < 8; t++)
        threads.emplace_back([&] { for (int i = 0; i < 50000; i++) atomic_increment(x); });
    for (auto& th : threads) th.join();
    std::printf("x = %d (期望 400000)\n", x.load());

    // 场景 B：CAS 自旋锁保护计数器
    CASLock lock;
    int counter = 0;
    std::vector<std::thread> threads2;
    for (int t = 0; t < 8; t++)
        threads2.emplace_back([&] { for (int i = 0; i < 50000; i++) { lock.lock(); counter++; lock.unlock(); } });
    for (auto& th : threads2) th.join();
    std::printf("counter = %d (期望 400000)\n", counter);
    return 0;
}

【代码做了什么？】

atomic_increment：标准的 CAS 循环——先读旧值，compare_exchange_strong(expected, old+1) 原子地检查”当前值是否还是 expected”，是则写新值并返回成功；否则 expected 被更新为最新值，循环重试。这等价于硬件提供的 RMW 原子加，但在语义上完全由 CAS 构建。
CASLock：锁状态 0/1；lock() 用 CAS 把 0 换成 1——只有”从 0 变 1”成功者获得锁；失败者恢复 expected 后重试（自旋）。
两个场景都验证最终结果恰为 400000。

【并行机制解说】

CAS 的原子性从哪来：compare_exchange_strong 在硬件上是一条原子 RMW（x86 的 lock cmpxchg）——”比较 + 交换”作为不可分割的一步完成。它是实现所有更高级同步（锁、屏障、无锁队列）的”万能积木”，也正是 slide 50 提到的”per-address 同步原语：read-modify-write / compare-and-swap”。
CAS 锁与 TAS 锁的差别：TAS 每次失败都会写（置位），产生一致性失效；CAS 锁失败时只是比较（读），写只在成功时发生——与 TTAS 类似，减少了竞争时的缓存乒乓。但 CAS 锁仍不公平（释放时所有等待者一起抢）。
为什么需要 acquire/release：与示例 1 同理——unlock 的 release 保证临界区写可见，lock 的 acquire 保证进入临界区后能看到前者的写；在放松硬件上，没有这对语义，counter++ 可能被重排到锁外，DRF 前提被破坏。
对应概念：CAS、RMW 原子指令、自旋锁变体、acquire/release。

示例 4：acquire/release 内存序——生产者-消费者交接

代码（C++11，std::atomic + memory_order）（演示”为什么必须用 acquire/release，relaxed 会出错”）：

#include <atomic>
#include <thread>
#include <cstdio>
#include <cassert>

std::atomic<bool> ready{false};
int payload = 0;                    // 普通（非原子）共享数据

void producer() {
    payload = 42;                          // (1) 先写数据
    ready.store(true, std::memory_order_release);   // (2) release：把 (1) 发布出去
}

void consumer() {
    while (!ready.load(std::memory_order_acquire)) { /* 等待 */ }  // (3) acquire
    // 关键问题：这里读 payload 一定得到 42 吗？
    // 答：一定！release-acquire 形成同步关系：acquire 之后的操作
    //     能看到 release 之前的所有写（包括非原子的 payload）。
    assert(payload == 42);
    std::printf("payload = %d\n", payload);
}

int main() {
    std::thread t1(producer), t2(consumer);
    t1.join(); t2.join();
    return 0;
}

// 对比：如果把 (2)(3) 都改成 memory_order_relaxed，程序就是有数据竞争的——
// 编译器/硬件可以重排 (1) 与 (2)，消费者可能看到 ready==true 但 payload 还是 0。

【代码做了什么？】

生产者先写普通变量 payload = 42，再用 memory_order_release 写 ready；消费者用 memory_order_acquire 自旋读 ready，等到 true 后读 payload 并断言它等于 42。
关键保证：release-acquire 配对形成 happens-before 关系——ready.store(release) 之前的所有写（含非原子 payload），对执行 ready.load(acquire) 的线程可见。因此断言必然成立。
注释中对比：若都用 relaxed，payload=42 与 ready=true 可以被重排（编译器或乱序硬件），消费者可能看到 ready==true 却读到 payload==0——这就是 slide 47 中 PSO 的例子（A=1; flag=1; while(flag==0); print A; 可能打印旧值）的现代 C++ 版本。

【并行机制解说】

为什么这对原语足够：这是”同步原语如何把放松硬件拉回 SC”的最小例子——release/acquire 是单向屏障：release 保证”前面的操作不越过我”（下行），acquire 保证”后面的操作不越过我”（上行）。与全量 fence 相比，它只约束一个方向，因此更便宜；这正是锁、屏障等库原语的内部机制（slide 54：同步库把复杂性封装起来，程序员只需用 lock/unlock、barrier）。
fence 在其中的位置：std::atomic_thread_fence(std::memory_order_seq_cst) 或 x86 的 _mm_mfence 是全量屏障（slide 50：所有内存操作完成前，后面的操作不能开始）；acquire/release 是它的”减配版”。在真正的 x86（TSO）上，普通 store/load 已经隐含部分顺序，但 ARM（非常放松）上必须显式使用这些语义。
数据竞争是禁区：payload 是非原子变量，但它被 release/acquire 排序，所以程序是 DRF 的，语言保证 SC 结果；若改用 relaxed（或干脆不用原子），payload 的读写就成了 data race（slide 52-53），程序输出不确定——语言不再提供任何保证（slide 59 的”SC for DRF”）。
对应概念：acquire、release、fence、happens-before、data race、DRF、SC for DRF。

示例 5：”00/10/11/01”问题——用 happens-before 判断合法输出

代码（C++11 伪代码 + 分析）（对应 slide 28-29 的经典问题）：

#include <atomic>
#include <thread>
#include <cstdio>

// 初始 A = B = 0（在 SC 系统上）
std::atomic<int> A{0}, B{0};

void p0() {
    A.store(1);            // (1)
    printf("%d", B.load()); // (2) 输出 r1
}

void p1() {
    B.store(1);            // (3)
    printf("%d", A.load()); // (4) 输出 r2
}

// 在顺序一致性（SC）系统上，可能的输出：
//   "01"：顺序 (1)(2)(3)(4) 或 (3)(4)(1)(2) 的混合
//   "11"：两线程都先写完再读：如 (1)(3)(2)(4)
//   "10"：？  r1=0 要求 (2) 先于 (1)；r2=1 要求 (3) 先于 (4)
//         程序序又要求 (1) 先于 (2)、(3) 先于 (4)
//         → 需要 (2)→(1)→…→(3)→(4)→…→(2)，成环 → SC 下不可能！
//   "00"：？  两个读都先于两个写 → (2) 先于 (1) 且 (4) 先于 (3)，
//         与程序序 (1)→(2)、(3)→(4) 矛盾 → 成环 → SC 下不可能！
// 结论：SC 下只可能 "01" 或 "11"（取决于开关先执行哪个线程的哪条指令）。
// 但在 TSO（写缓冲）或更放松的模型下，"00" 是可能的：
// 两线程的写都还堵在自己的写缓冲里，对方读不到 → r1 = r2 = 0。

【代码做了什么？】

四个语句按程序序排列：P0 写 A、读 B；P1 写 B、读 A。在 SC（”开关”每次完整执行一条内存操作）下枚举所有交错，只有 “01” 和 “11” 合法。
用 happens-before 图论证：某个输出合法，当且仅当所需的先后关系不构成环；”00” 和 “10” 都会导致环（一个事件必须发生在自己之前），因此不可能。
注释指出：一旦引入写缓冲（TSO），”00” 变成可能——这正是”放松一致性”改变程序可见行为的具体演示（slide 41：Can r1 = r2 = 0? SC: No. Write buffers: Yes!）。

【并行机制解说】

这是 consistency 与 coherence 的对照实验：coherence（Lecture 14）保证每个地址（A 或 B）各自的写串行化，但不保证跨地址的可见顺序；consistency 才决定”P0 写 A 与 P1 读 A 之间的相对时间”。所以 slide 24 说：coherence 是关于同一地址的，consistency 是关于不同地址之间的。
为什么现代硬件允许”00”：性能。写 A 需要几百个 cycle（一致性系统里要定位数据、发失效等），P0 没必要干等；把写放进写缓冲、继续执行读 B（与写 A 无冲突）能隐藏延迟（slide 38-39、42 的性能对比）。代价就是 W→R 排序被放松 → TSO。
程序员怎么办：要么接受”我的程序是 DRF 的，用同步库，SC for DRF 保证正确结果”；要么（只有系统程序员/同步库作者才需要）显式用 fence 或 acquire/release 恢复特定排序（slide 50-51、55）。
对应概念：sequential consistency、happens-before、TSO、write buffer、data race。

三、关键要点

Coherence ≠ Consistency：coherence 管”同一地址”的读写顺序（让系统表现得像没有缓存）；consistency 管”不同地址”之间的可见顺序（有没有缓存都得遵守的规范）。一致性问题是复制（缓存）引起的，放松一致性问题则是重排（内存操作）引起的——与缓存是否存在无关（slide 46）。
SC 是黄金标准，但代价是性能：SC（Lamport 1976）要求所有操作存在一个全局串行顺序且每线程保持程序序（四种排序 W→R / R→R / R→W / W→W 全保留）。但写操作要几百 cycle，为了隐藏延迟，每个现代处理器（x86/ARM/RISC-V）都有写缓冲，实际执行比 SC 更放松（x86 ≈ TSO）。
放松模型 = 选择性放弃排序：TSO 只放松 W→R（PC 还允许别人提前读新值）；PSO 再放松 W→W（A=1; flag=1 可能被看到反序）；WO/RC 几乎全放。放松越多性能越好，程序员需要付出的”补排序”工作越多。
同步是解药，但要 DRF 才免费：fence（全量屏障）、acquire/release（单向屏障）、RMW/CAS 等原语可以恢复排序；但有数据竞争的程序（冲突访问未被同步排序）输出不确定。好消息：同步化的（DRF）程序在非 SC 系统上也得到 SC 结果——所以绝大多数程序员用同步库写正确程序，而不用关心硬件模型。
语言也承诺 SC for DRF：C11/C++11、Java 5 保证 DRF 程序获得顺序一致性，编译器负责插入必要同步；有 race 则无任何保证。实践原则：用同步库，别手工裸写内存序。

四、常见陷阱与注意事项

用普通变量 + 原子标志做”消息传递”却忘掉 acquire/release：flag.store(true, relaxed) + payload = 42 可被重排，消费者可能看到”flag 已置位但 payload 还是旧值”——这是典型的 data race，在 ARM 等放松架构上几乎必然出错（x86 上碰巧常对，形成”在我的机器上能跑”的错觉）。正确做法：release/acquire 配对（示例 4）。
自旋锁的忙等（busy-wait）浪费与缓存乒乓：test-and-set 自旋锁在竞争激烈时，每次测试都是一次写、触发整条缓存行失效，性能骤降；应使用 TTAS（先读后 TAS）、ticket lock（只读等待）或加 pause/yield；在单核系统上自旋锁还可能死锁（持锁线程被抢占，等待者永远自旋）。
把”锁了”等同于”内存序正确”：锁（或任何同步）只有在正确使用时才提供排序保证——临界区内外的共享访问都必须被同一把锁保护；漏保护一次访问就产生数据竞争，整个程序的保证归零（race 是”全有或全无”的）。
用错 memory_order 或过度放松：relaxed 只保证原子性、不保证顺序——只适合计数器等”不需要顺序”的场景；seq_cst 最安全但最贵。常见错误是把 compare_exchange 循环里的 expected 忘了更新（无限循环），或把 memory_order_acquire/release 用反（acquire 配 store、release 配 load 是错的）。
以为”现代 x86 上跑得对”就万事大吉：x86 是（未完全定义的）TSO，很多重排不会发生；但编译器在 O2 下也会重排（语言层内存模型管的是”编译器 + 硬件”总和），换到 ARM/RISC-V（非常放松）或换编译器优化级别，bug 立刻暴露。可移植的正确性必须依赖语言内存模型（SC for DRF），而不是某个硬件的巧合行为。

五、思考题（带答案）

Q1：为什么说”缓存一致性”与”内存一致性（consistency）”是两件不同的事？请用 A/B 程序（A=1; print B / B=1; print A）说明。 A1：coherence 只要求每个地址单独存在一个与所有观察一致的串行顺序（SWMR + 写串行化）：A 上的写和读、B 上的写和读各自有序，但不规定 A 的顺序与 B 的顺序之间的相对关系。consistency 才规定跨地址的相对可见时间：SC 下 P0 的”写 A”必须在其”读 B”之前提交（W→R 约束），所以 r1=0 与 r2=1 不能同时成立（”10”不可能），”00”也不可能。一旦硬件用写缓冲放松 W→R（TSO），”00”就成为合法输出——地址 A、B 各自仍然 coherent，但程序整体不再 SC。这正说明：coherence 是关于”复制的缓存”，consistency 是关于”重排的操作”。

Q2：为什么票锁（ticket lock）在高竞争下的性能优于 test-and-set 自旋锁？它与缓存一致性协议有什么关系？ A2：test-and-set 锁的每个等待者在每一轮自旋中都执行一次写（置位指令），每次写都会通过一致性协议（如 BusRdX）使其他缓存中该锁的副本失效——于是”一锁释放，所有等待者同时抢、互相失效”，产生 O(P) 次失效/轮。票锁的等待者只读 now_serving（读不产生失效，所有线程可同时命中自己的缓存副本），唯一的写是取号时的一次 fetch_add 和释放时的一次 fetch_add——每次释放只产生一条失效（O(P) 总量）。此外票锁按取号顺序放行（FIFO 公平），避免 TAS 锁的”抢锁风暴”。这正是 Lecture 14 的 coherence 通信开销在同步原语设计中的直接体现。

Q3：什么是 “SC for DRF”？它为什么能让绝大多数程序员”忘记”内存一致性模型的存在？ A3：”SC for DRF”是 C11/C++11 与 Java 5 语言内存模型的承诺：只要程序无数据竞争（所有冲突访问都被同步操作排序），程序的行为就与顺序一致性系统上的执行一致——编译器负责针对具体硬件（x86 的 TSO、ARM 的弱序）插入必要的 fence/屏障来兑现该承诺。因为绝大多数程序通过同步库（std::mutex、barrier 等，其内部实现如示例 1-3 所示）写成 DRF 程序，所以应用层程序员只需保证”该同步的地方同步了”，不需要知道底层是 TSO 还是弱序；只有同步库实现者、内核/驱动开发者与无锁数据结构作者才需要直面 memory model（slide 23、55、59）。

本讲笔记基于 Stanford CS149 Fall 2025 Lecture 15 幻灯片（raw/sync_consistency.txt）撰写；同步原语示例（自旋锁、票锁、CAS、acquire/release）为支撑幻灯片第 50/54 页论点的标准实现，其正确性依赖 C++11 原子库的内存序语义。

Share on

Bluesky Facebook LinkedIn Mastodon X (formerly Twitter)

Runguo Li