内存模型
02 运行时 回答「下一步轮到哪个线程」,这一部分回答另一半:轮到的线程做一次原子读,能读到哪些值,以及读到之后线程之间多了什么因果关系。代码集中在 rt/atomic.rs(931 行)、rt/vv.rs(86 行)和 rt/synchronize.rs(63 行)三个文件,另有 rt/thread.rs 里每个线程的时钟和全局的 seq_cst_causality。
flowchart TB op["AtomicUsize::load / store / fetch_add / fence"] --> br["branch:调度点(fence 除外)"] br --> sy["synchronize:本线程时钟自增"] sy --> st["State:最近 7 次写的环形数组"] st --> m["match_load_to_stores / match_rmw_to_stores:列出候选写"] m --> path["Path 的 Load 分支:这一轮取第几个候选"] path --> ld["State::load / rmw:coherence、first_seen、Synchronize"] ld --> vv["线程的 causality 时钟(happens-before)"] vv --> chk["04 检测器:UnsafeCell、with_mut 用同一套时钟判竞争"]
五章:
- 向量时钟与同步点:
VersionVec的三个操作;每线程causality、released、dpor_vv三套时钟;synchronize()只在原子操作、fence、单元格访问前自增;Synchronize怎样实现 Release / Acquire;spawn 与 unpark 带来的 happens-before。 - 写历史与 coherence:
State与Store的字段;修改顺序用向量时钟表示的偏序;四条 coherence 规则各在哪几行;文件头那张 CDSChecker 规则清单里哪些是空的;7 次写的窗口(E6:连写 7 次后初值不再是候选)。 - load 的候选:主线 2 的核心。
match_load_to_stores的三条排除规则逐条配实验;yield_now之后不再给旧值(新实验:同一个模型加一次yield_now,「对方已写、仍读到 0」这一种结果消失);CoRR 的六种结果(E5);unsync_load不建分支。 - RMW 与释放序列:
match_rmw_to_stores只给修改顺序上最新的写;成功的 RMW 继承所读写的Synchronize形成释放序列(实验:RMW 续上、普通写断开);失败的 CAS 也只读最新写;compare_exchange_weak不会伪失败(E16);与 tokio #1788 的fetch_add(0)。 - fence 与 SeqCst:四种 fence 的实现与
Relaxedfence 的 panic;fence(SeqCst)是对全局时钟的双向 join;SeqCst 访问的seq_cst()是空函数,只剩 load 匹配里的一条规则;SB、RWC、IRIW 三个 litmus 的实测结果;这段实现的历史(#108、#111、#220)。
不重讲的部分
- 五类
Ordering的用法与配对:crossbeam 卷的本库里的内存序。本部分只讲 loom 怎么模拟这些语义。 - 「为什么 x86 上测不出、要靠 loom / Miri / TSan」:crossbeam 卷的怎么验证并发代码。
dpor_vv与回溯点:02 DPOR。它和本部分的causality是两套独立的时钟,只在 向量时钟与同步点 里并列介绍一次。- SB / LB 两个 litmus 在 loom 能力边界里的位置:07 SeqCst 与 load buffering。本部分讲机制,那一章讲「这意味着什么」。
文档与代码的出入
| 出处的说法 | 代码 | 在哪章 |
|---|---|---|
rt/atomic.rs 文件头按 CDSChecker 图 7 / 9 / 10 列出规则 | 「Seq-cst/MO Consistency」「Seq-cst Write-Read Coherence」「RMW Atomicity」以及图 9 的六条 SC fence 规则后面都是空的(atomic.rs:32-55);其中 RMW 原子性实际由 match_rmw_to_stores 实现 | 写历史与 coherence |
Mutex 构造时传 seq_cst = true,解锁处注释「Establish sequential consistency between the lock's operations」 | 调用的 threads.seq_cst() 是空函数(thread.rs:336-341) | fence 与 SeqCst |
assert_ne!(mo_i, mo_j) 旁的注释「TODO: this sometimes fails」 | 断言仍在,同样的断言在 match_rmw_to_stores 里没有这条注释 | load 的候选 |
README「SeqCst accesses … are regarded as AcqRel」 | 与代码一致;唯一多出来的是 SeqCst load 在两个 SeqCst 写之间不读旧的那一条(atomic.rs:766-769) | fence 与 SeqCst |
演进
只列 git log -S 可查的事实;0.5.3、0.5.4 两个版本在 CHANGELOG 里有、仓库里没有对应 tag,版本号以 CHANGELOG 为准。
| 时间 | 提交 | 版本 | 变化 |
|---|---|---|---|
| 2018-12-21 | a2dcce6「Refine atomic history w.r.t yielding」 | 0.1.0 | is_seen_before_yield:yield 之后不再给已读过的旧值 |
| 2019-09-20 | f8ef5e1「Add initial atomic::fence support」(#57) | 0.2.6 | 只支持 fence(Acquire),其余序 assert_eq! 失败 |
| 2020-02-16 | fd8680c「Relax how SeqCst is modelled」(#108) | 0.2.15 | 原先 SeqCst 访问对全局时钟双向 join(全局 happens-before),被改成空函数 |
| 2020-03-23 | 88e4225「Overhaul internals to support faster execution」(#111) | 0.3.0 | 写历史改成 7 格环形数组,修改顺序改用向量时钟,新增 match_load_to_stores / match_rmw_to_stores |
| 2021-09-22 | ffb2672「Implement Release, AcqRel, and SeqCst fences」(#220) | 0.5.2 | 线程多一个 released 时钟;seq_cst_fence 把 #108 删掉的双向 join 只用在 fence(SeqCst) 上;README 新增「Unsupported features」 |
本部分的实验
机器 M2 Max(8P + 4E),macOS,rustc 1.99.1,loom =0.7.2,RUSTFLAGS="--cfg loom" cargo test --release --offline,每个实验目录单独的 CARGO_TARGET_DIR。loom 在一个 OS 线程上跑完所有模型线程,交错数是确定的,重跑结果相同;本部分只报告交错数和结果集合,不报告耗时。
| # | 目录 | 看什么 | 章 |
|---|---|---|---|
| E1 | exp-loom/survey/tests/mp.rs | 消息传递:Release / Acquire 6 个交错通过,Relaxed 第 3 个交错被抓到 | 向量时钟与同步点 |
| E5 | exp-loom/survey/tests/litmus.rs、exp-loom/memory-model/tests/fences.rs | SB 的四种写法、CoRR;单侧 fence、RWC、IRIW、fence 版消息传递 | load 的候选、fence 与 SeqCst |
| E6 | exp-loom/memory-model/tests/history.rs | 7 次写的窗口,n = 5 … 9 | 写历史与 coherence |
| — | exp-loom/memory-model/tests/yield_.rs | yield_now 前后同一个线程能读到的值 | load 的候选 |
| E16 | exp-loom/memory-model/tests/rmw.rs | RMW 读最新写、释放序列、失败的 CAS、fetch_add(0) 版 SB、compare_exchange_weak | RMW 与释放序列 |
💬 关联讨论
发起讨论加载中...