Lecture 23: Distributed Shared Memory — 分布式共享内存
Lecture 23: Distributed Shared Memory — 分布式共享内存
讲义对应：CS 425 FA2026 Lecture 23。本章对应课程 Lecture 25「Distributed Shared Memory」（2026-11-17，Back to Basics 模块），主要素材为课程 Lecture 25-A「Distributed Shared Memory」（原始讲义
L25.A.FA25.pdf，29 页：DSM 的动机、页级虚拟共享内存、页状态 R/W 与所有者 owner、读缺失的 6 种场景与写缺失的 4 种场景、写失效（invalidate）协议的缺陷与假共享（false sharing）、写更新（update）协议、DSM 可用的一致性模型谱系、RDMA/Infiniband 带来的”复兴”）。前置知识取自 Lecture 24-B「Consistency Models」（L24.B.FA25.pdf：一致性谱系、线性一致性、顺序一致性、因果一致性、会话一致性、事件一致性）与 Lecture 16「Multicast」（L16.FA25.pdf：FIFO/因果/全序多播、可靠多播、虚拟同步），因为 DSM 的核心正是”把一致性模型应用到一个用多播传播更新的页数组上”。 教材对应：Coulouris 5th Ed. Sec 6.5（共享内存方法 / DSM 案例），Ch. 6 Indirect Communication；补充：Tanenbaum & van Steen Distributed Systems 2nd Ed. Ch. 5-6（线程/共享内存与协调）、Ghosh Distributed Systems: An Algorithmic Approach 的共享内存章节。 阅读材料：Kai Li & Paul Hudak, Memory Coherence in Shared Virtual Memory Systems, ACM TOCS 1989（IVY 协议原始论文）；John B. Carter, John K. Bennett, Willy Zwaenepoel, Implementation and Performance of Munin, SOSP 1991（入口一致性 / type-specific coherence）；Pete Keleher, Alan Cox, Sandhya Dwarkadas, Willy Zwaenepoel, TreadMarks: Distributed Shared Memory on Standard Workstations and Operating Systems, USENIX Winter 1994（懒惰释放一致性 LRC、孪生页 twin 与 diff、多写者）；V. Protic, M. Tomasevic, V. Milutinovic, Distributed Shared Memory: Concepts and Systems, IEEE Parallel & Distributed Technology 1996（综述，DSM 设计空间四维度的经典归纳）；可选：Bershad et al., The Midway Distributed Shared Memory System, COMPCON 1993；Scales, Gharachorloo, Thekkath, Shasta: A Low Overhead, Software-Only Approach for Supporting Fine-Grain Shared Memory, ASPLOS 1996；Dragojević et al., FaRM: Fast Remote Memory, NSDI 2014（RDMA 时代的”DSM 复兴”）。
23.1 概述
本章回答一个极具诱惑力的问题：既然进程之间通信这么麻烦（要 send、要 receive、要序列化、要处理乱序和失败），能不能干脆让分布在不同机器上的进程”像访问本地变量一样”读写一块共享内存？ 这就是分布式共享内存（Distributed Shared Memory, DSM）：在物理上并不共享内存的消息传递网络之上，用一层软件模拟出一个逻辑上共享的地址空间，让程序员继续用共享内存（shared memory）的编程模型写程序——x = x + 1 就够了，不需要知道 x 究竟躺在哪台机器上。
本讲的定位是整门课”通信原语”支线的收束与反思：前 20 多讲我们一直在教”怎样把消息发出去、怎样定序、怎样保证一致性”（多播 Ch.13、逻辑时钟 Ch.11、一致性模型 Ch.10、RPC Ch.18、复制控制 Ch.20），而 DSM 站在相反的方向追问一句：能不能把这些机制全部藏起来，让程序员看不到”分布式”三个字？ 讲义给出的答案是”技术上可以，工程上代价高昂”：DSM 用一个”页面 + 页错误 + 一致性协议”的软件层把远端内存伪装成本地内存，但伪装是有代价的——每一次伪装的失败（页错误、失效、假共享）都会以毫秒级的停顿砸在程序员看不见的地方。
本章的黄金法则（贯穿全章，在 23.6 再次点题）：
DSM 试图用软件在网络上重建共享内存，但共享内存的真正成本在于一致性维护；粒度决定了通信开销与假共享的权衡，一致性模型的强度决定了同步的频率。DSM 的兴衰史告诉我们：把分布式伪装成本地，往往要把代价藏到程序员看不见的地方。
23.2 核心概念与分布式机制图解
23.2.1 共享内存 vs 消息传递（Shared Memory vs Message Passing）
定义与目的：并行/分布式编程有两大范式。共享内存（shared memory）：多个执行单元（进程/线程）读写同一片地址空间，通过
load/store指令隐式通信，用锁和屏障显式同步。消息传递（message passing）：每个执行单元只有私有地址空间，通过显式的send/receive交换数据，通信与同步是同一个动作（收到消息即同步）。DSM 是第三种：物理上是消息传递，逻辑上是共享内存。- 直观解释（”它是什么？”）：把三个程序员关在同一间办公室写代码。
- 共享内存像一块大黑板：谁想改哪一行，直接走过去改就行，别人抬头就能看见；但如果两个人同时改同一行，写出来的东西就乱了（需要”谁拿粉笔谁写”的锁）。
- 消息传递像发纸条：每个人只盯着自己的笔记本，要把信息告诉别人必须明确撕一张纸条递过去，并且要写清楚”第几号更新”（序列号），否则两张纸条可能倒着到手；麻烦，但每个人完全掌控自己的笔记本。
- DSM 像每个人手里都有一本”看起来一样”的活页笔记本，另有一个复印员在背后跑腿：你想读第 5 页，如果手上没有，复印员就去别人那里复印一份给你（读复制）；你想写第 5 页，复印员必须先把别人手里的第 5 页复印件作废（写失效），否则大家看到的就不一致了。代价是：如果两个人很倒霉地要写同一页的不同角落，复印员就会把整页在两人之间来回搬运——这就是假共享（false sharing）。
- 机制图解：三种编程模型的结构对比。
(A) 物理共享内存 (multiprocessor / 多核) (B) 消息传递 (MPI / socket / RPC)
┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ send(m) ┌──────┐
│ P0 │ │ P1 │ │ P2 │ │ P3 │ │ P0 │ ──────────► │ P1 │
└──┬───┘ └──┬───┘ └──┬───┘ └──┬───┘ │ │ ◄────────── │ │
│ │ │ │ └──────┘ recv(m) └──────┘
┌──┴────────┴────────┴────────┴──┐ 私有内存 私有内存
│ 共享地址空间 (RAM) │ （无共享！通信=显式拷贝）
│ 硬件 cache coherence 保证一致 │
└─────────────────────────────────┘
x = x + 1 就够了（但仍是并行程序，不是分布式的）
(C) DSM：物理上是 (B)，逻辑上是 (A)
┌──────────────┐ ┌──────────────┐ ┌──────────────┐
│ P0 + cache │ │ P1 + cache │ │ P2 + cache │
│ ┌────────┐ │ │ ┌────────┐ │ │ ┌────────┐ │
│ │page 5 │ │ │ │page 5 │ │ │ │ │ │
│ │(R)(O) │ │ │ │(R) │ │ │ │ │ │
│ └────────┘ │ │ └────────┘ │ │ └────────┘ │
└──────┬───────┘ └──────┬───────┘ └──────┬───────┘
│ write to page 5 / read page 5（页错误时经多播联系其他进程）│
└──────────────────────┬───────────────────────┘
▼
逻辑上：Page 0 | Page 1 | Page 2 | ... | Page N-1
物理上：每页只真实存在于某些节点的本地内存中
一致性 由【软件协议】保证，而不是硬件 cache coherence
关键假设与系统模型：DSM 假定（1）节点通过消息传递网络互联（局域网或数据中心网络，延迟远高于本地内存）；（2）每个节点有本地内存 + 本地 cache，本地内存扮演”页缓存”的角色；（3）进程之间不存在共享的物理内存，也没有全局同步时钟；（4）故障模型通常是 crash-stop（经典 DSM 系统几乎不处理拜占庭故障，也常常不处理节点崩溃后的数据恢复——这是它的一个隐患）；（5）一致性不做成”严格一致”，而选择某个更弱的一致性模型（见 23.2.4）。
讲义的一个漂亮的对称性结论：消息传递可以实现在 DSM 之上，DSM 也可以实现在消息传递之上。前者只需”拿一个公共页面当缓冲区，把消息读写进去”；后者则是本章的全部内容。这说明两者在表达能力上等价（都具备图灵完备的通信能力），差别只在编程接口与代价分布：共享内存把代价藏在 load/store 的隐式路径里，消息传递把代价摆在程序员眼前。
23.2.2 DSM 的定义：把远端内存伪装成本地内存（What is DSM?）
定义与目的：DSM 是一个软件层（中间件 / 运行时 / 内核模块），它把分布在多台机器上的本地内存组织成一个逻辑上共享的地址空间，使得不同机器上的进程可以像访问本地内存一样访问共享变量。讲义给出的操作性描述是：进程之间”虚拟地共享页面“（processes virtually share pages），而不是显式地 send/receive 消息。它的直接价值有两个：写程序方便（同一份共享内存代码可以在多处理机上跑，也可以在 DSM 上跑），以及复用已有程序（大量现成的共享内存并行程序不必改写就能拿到集群上跑）。
直观解释（”它是什么？”）：DSM 就像给一群各自租房子的室友配了一本“虚拟合租笔记本”：每个人手上只有自己抄的那几页（本地 cache），需要哪页就打电话让持有人传真过来（页错误 + 读复制），要改哪页就必须先通知所有人”你那页作废了”（写失效）。真正的笔记本并不存在，存在的只是”大家手上的复印件 + 一套让复印件保持一致的规矩”。
机制图解：DSM 的运行时路径——从一次普通的
load/store到一次网络往返。
进程执行 x = x + 1 (x 落在共享页 page 5 上)
│
▼
┌──────────────────────── 本地 cache / 本地内存 ────────────────────────┐
│ page 5 在本地吗？ │
│ 在 -> page hit：直接读写本地副本，一条指令，无任何网络消息 │
│ 不在 -> page fault：CPU 陷入内核 (kernel trap) │
└───────────────────────────────┬───────────────────────────────────────┘
▼
内核的 trap handler 调用 DSM 软件层
│
┌──────────────┴───────────────┐
▼ ▼
读缺失 (read fault) 写缺失 (write fault)
向 owner 索取一份只读副本 向 owner 索取"写权限"：
（可多播定位 owner）， owner 先【多播失效】所有其他副本，
复制到本地，标为 R 再把【所有权 + 唯一副本】交给请求者，
标为 W
└──────────────┬───────────────┘
▼
消息往返：若干次网络 RTT + 一次整页（4 KB）传输
——本地访存 ~100 ns，这一次缺失 ~100 us 起，差 10^3 倍以上
- 关键假设与系统模型：讲义强调两个”缓存层次”的概念——每个进程有一个 cache，cache 里存最近访问过的页；页可以映射到本地内存，命中即本地处理，不命中就发生页错误（page fault，内核陷入 kernel trap），由 trap handler 调用 DSM 软件，DSM 软件再通过多播（multicast）联系 DSM 组内的其他进程（多播的定序与可靠性细节见第 13 章）。这套结构决定了 DSM 的性能上限：命中路径是本地内存速度，缺失路径是网络 RTT + 整页传输速度，两者相差三到五个数量级。
23.2.3 两个层面的 DSM：硬件的物理共享内存 vs 软件的 DSM（Hardware vs Software）
- 定义与目的：DSM 这个词在两个层面上使用，必须分清，否则会混淆”共享内存为什么快”与”DSM 为什么慢”。
| 层面 | 硬件共享内存（multiprocessor / 多核 / NUMA） | 软件 DSM（本章重点） |
|---|---|---|
| 共享的实体 | 真实的物理内存（同一块 RAM / 同一封装） | 逻辑地址空间（真实数据分散在各节点 RAM） |
| 一致性由谁保证 | 硬件 cache coherence 协议（MESI 等，总线/目录，纳秒级） | 软件一致性协议（页错误 + 失效/更新消息，微秒~毫秒级） |
| 粒度 | cache line（64 B） | 页 / 大块（几百字节~几 MB） |
| 失效/更新的代价 | 几条总线事务或片上网络消息 | 一次网络往返（几十到几百微秒） |
| 编程模型 | 线程 + 共享变量 | 进程 + 共享变量（看似相同！） |
| 典型系统 | 多核 CPU、共享内存超级计算机、NUMA 服务器 | IVY、Munin、TreadMarks、Shasta、Cashmere |
直观解释（”它是什么？”）：硬件共享内存像同一张桌子上的几个人共用一叠纸：谁改哪张纸，同桌的人转头就能看到，硬件（总线/目录）负责保证大家不会读到旧内容，代价是纳秒级。软件 DSM 像几个不在同一间办公室的人共用一叠纸的复印件：任何改动都要打电话通知、传真，代价是微秒到毫秒级。两者提供给程序员的接口几乎一样，代价却差 3-5 个数量级——这正是 DSM 全部困难的根源。
机制图解：一致性维护的代价层级（每一层都比上一层慢一个数量级以上）。
存储/通信层级 典型延迟 谁来保证一致性
─────────────────────────────────────────────────────────────────────
CPU 寄存器 / L1 cache ~1 ns 无需（私有）
L2 / L3 cache（多核共享） ~10-40 ns 硬件 cache coherence
本地 NUMA 远端内存节点 ~100-300 ns 硬件（NUMA-aware 一致性）
同一台机器内的 DSM（进程间） ~1-10 us 软件（共享内存映射/消息）
机架内 RDMA 远端内存读写 ~1-2 us 软件（显式读写/原子操作）
局域网 DSM 页错误（本节主角） ~100-500 us 软件（页错误 + 失效协议）
广域网 DSM / 分布式文件系统 ~1-100 ms 软件 + 人工取舍
─────────────────────────────────────────────────────────────────────
关键认知：本地内存访问 ~100 ns；一次 DSM 页错误 = 网络 RTT + 整页传输
+ 内核 trap 开销 ≈ 10^2~10^3 倍。DSM 的性能天花板由此确定。
- 关键假设与系统模型：软件 DSM 的实现通常依赖操作系统的虚拟内存（virtual memory）机制：把共享页用
mmap映射进每个进程的地址空间，把本地没有的页标记为不可访问（PROT_NONE），于是访问它会触发 SIGSEGV / 页错误，DSM 运行时在信号处理函数或内核 trap 中截获，完成”向别的节点取页/发失效”的动作，再用mprotect恢复访问权限。这个实现路径决定了粒度必须是”页”（MMU 的最小保护单位），也就决定了假共享不可避免——这是一条贯穿全章的技术因果链。
23.2.4 DSM 的设计空间：四个维度（The DSM Design Space）
定义与目的：任何 DSM 系统都可以用四个正交的设计决策来刻画：粒度（granularity）、共享内存空间的结构与分布（structure / placement）、一致性模型（consistency model）、替换策略（replacement strategy）。这四个决策共同决定了系统的性能、可扩展性与编程难度；把握了这四维，就把握了 DSM 领域四十年研究的全部脉络。
直观解释（”它是什么？”）：把 DSM 想成一家共享办公空间的设计：粒度=文件柜的抽屉大小（抽屉越小找东西越准，但开柜次数越多）；结构=文件怎么摆放、是否有专门的档案室（集中式）还是各人抽屉都放一点（分布 + 复制）；一致性模型=”什么时刻你必须同步你的文件”（每小时强制同步很安全但很慢，只在开会前同步则快但可能看到旧版本）；替换策略=抽屉满了扔哪份文件（扔错了下次还得再复印一遍，甚至把唯一的一份原件弄丢）。
机制图解：DSM 设计空间四维总览。
┌──────────────── DSM 设计空间 ────────────────┐
│ │
┌──────────────────┴───┐ ┌───────────────┐ ┌───────────────┐ ┌┴──────────────┐
│ ① 粒度 Granularity │ │ ② 结构与分布 │ │ ③ 一致性模型 │ │ ④ 替换策略 │
│ │ │ Structure & │ │ Consistency │ │ Replacement │
│ 字节/字 (fine) │ │ Placement │ │ │ │ │
│ |- 假共享少 │ │ │ │ 严格 strict │ │ 淘汰哪一页？ │
│ '- 协议开销爆炸 │ │ 无结构 字节数组 │ │ 线性/顺序 │ │ |- 唯一副本 │
│ cache line │ │ 有结构 对象/树 │ │ 因果 causal │ │ | -> 必须写回│
│ 页 page (4 KB) ←典型 │ │ │ │ PRAM/FIFO │ │ '- 有副本 │
│ 大块 (coarse) │ │ 集中式 │ │ 弱 weak │ │ -> 可丢弃 │
│ |- 通信被摊薄 │ │ 物理分布 │ │ 释放 release │ │ │
│ '- 假共享严重 │ │ 复制 replicated │ │ 入口 entry │ │ 抖动 thrashing│
│ │ │ │ │ 懒惰释放 LRC │ │ 假共享放大 │
└──────────┬───────────┘ └───────┬────────┘ └───────┬───────┘ └──────┬────────┘
│ │ │ │
▼ ▼ ▼ ▼
通信量 vs 精确性 谁存数据、存几份 同步频率与强度 本地内存不够时
【假共享】的总开关 决定了协议的复杂度 决定了性能下限 决定抖动与否
- 表格 1：DSM 设计空间四维度的选项与权衡
| 维度 | 选项 | 优点 | 代价 / 风险 | 代表系统 |
|---|---|---|---|---|
| ① 粒度 | 字节/字（fine-grained） | 精确传输，无假共享 | 一致性元数据爆炸；每次访存都可能通信；需编译器辅助 | Shasta、SoftFLASH |
| cache line（中细） | 与硬件 cache 对齐，假共享限于 64 B | 需要细粒度失效目录，软件开销大 | Shasta（子页保护） | |
| 页（4-8 KB，典型） | 直接复用 MMU/页错误机制，实现最简单 | 假共享以页为单位；传输量大 | IVY、Munin、TreadMarks | |
| 大块 / 段（coarse） | 协议消息数少，传输效率高 | 假共享与浪费严重；延迟高 | 部分数据并行运行时、分布式数组库 | |
| ② 结构与分布 | 无结构（unstructured） | 就是一片字节数组，通用、语言无关 | 无法利用类型信息做优化（如只读复制） | IVY、TreadMarks |
| 有结构（structured） | 按语言类型/对象组织，可做类型特定优化 | 需要语言/编译器配合 | Orca（对象）、Munin（类型特定一致性）、Linda（元组空间） | |
| 集中式（centralized） | 实现简单，一个”家”节点保存全部数据 | 单点瓶颈：家节点带宽/内存/故障 | 早期集中式 DSM、 centralized lock server | |
| 物理分布（distributed） | 带宽与容量随节点数线性增长 | 需要目录/所有者定位，协议更复杂 | IVY（页所有者）、Munin、TreadMarks | |
| 复制（replicated） | 读操作本地化，读扩展性好 | 写操作要维护多副本一致性 | 几乎所有实际 DSM（读复制 + 写失效/更新） | |
| ③ 一致性模型 | 严格/线性一致性 | 编程最直观（像单机） | 多计算机上不可实现（需全局时钟）或代价不可接受 | 无实用 DSM |
| 顺序一致性 | 有全序，程序顺序被尊重 | 实现代价高，同步频繁 | IVY（目标模型） | |
| 因果 / PRAM(FIFO) | 允许并发写并发读，放宽顺序要求 | 仍要求较频繁的通信 | 部分 DSM 与多播协议 | |
| 释放 / 入口 / 懒惰释放 | 只在与锁/屏障交互时同步，把开销摊薄 | 编程需遵守”无数据竞争 + 正确同步”假设 | Munin（入口）、TreadMarks（LRC） | |
| 事件一致性（eventual） | 最快、可用性最高 | 读到旧值的时间无界，编程困难 | 现代分布式 KV/存储，不是经典 DSM 的选择 | |
| ④ 替换策略 | 淘汰”唯一副本”页 | 无需网络交互即可腾出本地内存 | 必须先写回/保留所有权，否则丢数据 | 需要写回或”所有者迁移”策略 |
| 淘汰”多副本”页 | 直接丢弃即可，最便宜 | 下次访问要重新故障取页 | IVY 的只读副本 | |
| 本地容量不足 → 抖动 | —— | 反复故障、性能崩溃（thrashing） | 所有 DSM 的共有风险 |
- （1）粒度（Granularity）：粒度决定了”一次通信搬多少数据”与”一次一致性动作覆盖多少数据”。
- 细粒度（字节/字）：只有真正被访问的数据会被搬动，没有假共享；但每次访存都要查一致性元数据，且需要编译器插桩或硬件协助（软件难以在字级别拦截访问），协议元数据（目录项数 = 数据量 / 粒度）随粒度减小而爆炸。
- 粗粒度（页/大块）：一次页错误搬一整页，通信开销被”摊薄”（页越大，单位数据的传输效率越高），协议消息数少；但假共享严重（两个无关变量落在一页上就互相打架），且单次传输延迟高。
权衡的数量级估算：设一个节点在两次同步点之间要顺序访问 $D$ 个字（word）的共享数据，页大小为 $g$ 个字，每次页错误的协议延迟为 $P$（主要由网络 RTT 与 trap 决定，与 $g$ 基本无关），网络带宽为 $B$（字节/秒），每字 $w=8$ 字节；又设程序中有 $S$ 个被多个节点反复争用的热点字（假共享的源头），每个热点字每轮引发一次假共享故障，每次要搬 $g$ 个字。则总时间大致为
\[T(g) \approx \underbrace{\frac{D}{g}\cdot P}_{\text{故障次数} \times \text{协议延迟}} + \underbrace{\frac{D\cdot w}{B}}_{\text{必须传的数据（常数）}} + \underbrace{S\cdot g\cdot \frac{w}{B}}_{\text{假共享浪费的带宽}}\]第一项随 $g$ 增大而下降（页大 ⇒ 故障少），第三项随 $g$ 增大而上升（页大一页搬得多、假共享放大）。求极小值：
\[\frac{dT}{dg}=0 \;\Rightarrow\; -\frac{D\cdot P}{g^2} + \frac{S\cdot w}{B}=0 \;\Rightarrow\; \boxed{g^{*}=\sqrt{\frac{D\cdot P\cdot B}{S\cdot w}}}\]代入 1990 年代的量级：$D=2\times10^5$ 字（约 1.6 MB 的工作集，两次同步之间顺序扫描），$P=200\ \mu s$（一次跨机页错误），$B=1.25\times10^6$ B/s（10 Mbps 以太网的实测吞吐），$S=25$ 个热点字，$w=8$ B：
\[g^{*}=\sqrt{\frac{2\times10^5 \times 2\times10^{-4} \times 1.25\times10^6}{25\times 8}}=\sqrt{2.5\times10^5}\approx 500\ \text{字}\approx 4\ \text{KB}\]估算给出的最优粒度恰好是”一页”——这不是巧合，而是 IVY/TreadMarks 都选择硬件页大小的原因：MMU 只能按页保护，而按页保护刚好也在性能最优点附近。
- 一个反直觉的推论：如果延迟与带宽按同样倍数改善（例如都比 1990 年代好 100 倍），则 $P\cdot B$ 不变，$g^$ 不变（最优粒度不变）；但如果延迟改善得比带宽快（RDMA 正是如此：延迟降 ~100 倍、带宽只升 ~10 倍），$P\cdot B$ 下降，$g^$ 变小——即”网络越快，越应该用更细的粒度去消除假共享”。这解释了为什么现代系统（Shasta、分布式共享缓存、RDMA 内存池）重新回到细粒度。
- （2）共享内存空间的结构与分布（Structure & Placement）：
- 无结构 vs 有结构：无结构 DSM 只提供”一片字节数组”（IVY、TreadMarks），实现简单、语言无关，但无法利用语义信息；有结构 DSM 按语言的数据类型（对象、变量、数组、树、图）组织共享空间（Orca 的对象、Munin 的类型特定一致性、Linda 的元组空间），可以做到”只读数据复制到所有节点、生产者-消费者数据用更新协议、累加型结果用归约”等类型特定（type-specific） 的优化，代价是需要语言或编译器配合。
- 数据分布方式：集中式（一个”家”节点存全部数据）简单，但制造单点瓶颈与单点故障；物理分布（数据分散在各节点，按地址范围静态划分或按需动态迁移）让带宽和容量随节点数增长，但需要目录或所有者（owner）来定位数据；复制（同一页在多个节点有副本）让读操作本地化，是几乎所有实际 DSM 的选择，代价是写操作要维护多副本一致性。
- 结论：“分布 + 复制”这两件事的组合，直接决定了一致性协议的复杂度：不复制 ⇒ 协议退化成简单的”取来/送回”（但读扩展性差）；复制 ⇒ 必须回答”写的时候其他副本怎么办”（失效还是更新）与”什么时候告诉别人”（急切还是懒惰），这正是 23.3 里 IVY / Munin / TreadMarks 三种协议的分野。
（3）一致性模型（Consistency Model）——DSM 最核心的设计决策：讲义明确点出：只要多个进程共享数据，一致性问题就必然出现；DSM 系统可以用讲义 Lecture 24-B 讲过的整个一致性谱系来实现：线性一致性（Linearizability）、顺序一致性（Sequential Consistency）、因果一致性（Causal Consistency）、流水线 RAM（PRAM/FIFO）一致性、事件一致性（Eventual Consistency），以及讲义特意补充的释放一致性（Release Consistency）。讲义的关键论断是：
“沿这个顺序往下走，速度上升，一致性变弱。”（As one goes down this order, speed increases while consistency gets weaker.）
这一点与一致性模型的整体谱系完全一致（详见第 10 章「一致性模型」）：一致性是系统与应用程序之间的契约，系统开发者按契约优化系统，应用开发者按契约判断自己的程序是否正确。DSM 的特殊之处在于：它不是”选一个模型去实现”，而是”选一个模型去换取性能”——因为 DSM 的同步动作（页错误、失效、取页）比本地访存慢 3-5 个数量级，同步频率就是性能，所以 DSM 实践几乎一致地选择弱一致性模型。
- 严格一致性（Strict Consistency）：任何读都返回”最近一次写”的值，且这个”最近”是按真实时间定义的。它要求所有节点对”此刻”有完全一致的认知，否则无法判断两个并发的写谁更”近”。在多计算机（消息传递网络）上不可实现：要么需要全局同步时钟，要么需要让每次写都在返回前传播到所有副本（延迟不可接受）。讲义体系里比它略弱的线性一致性（Linearizability） 要求”操作看起来在实时序中的某一瞬间原子生效”，同样把延迟写进了关键路径（它的读通常要一次 quorum 往返）。
- 顺序一致性（Sequential Consistency）：Lamport 的经典定义——”任何执行的结果，都等同于把所有处理器的操作按某个全序依次执行，且每个处理器自身的操作在这个全序中保持其程序顺序“。它比严格一致性弱（允许读到旧值，只要全序合法），但执行代价仍然很高：为了让所有节点对全序有一致认知，通常需要集中定序器或原子多播（详见第 13 章的多播定序）。IVY 追求的就是顺序一致性，它用”写失效 + 唯一写者 + 所有权迁移”这一套机制来保证任何时刻只有一个写者，从而把”并发写”彻底消除，代价是每次写都要广播失效（$O(N)$ 条消息）。
- 因果一致性（Causal Consistency）：只要求有因果关系的写在所有节点以相同顺序被看到（无因果关系的并发写可以不同顺序）。它可以用向量时钟实现（详见第 11 章），允许比顺序一致性更多的并发，代价是元数据（向量）随节点数增长。
- PRAM / FIFO 一致性：最弱的有序模型——只保证同一个进程发出的写按序被所有节点看到，不同进程的写之间没有任何顺序保证。实现简单（每个发送者一个序列号，等价于 FIFO 多播的接收规则），但语义弱到只适合特定模式（例如”每个进程只管自己的写，靠屏障来分隔阶段”）。
- 弱一致性（Weak Consistency）：引入同步操作（synchronization） 来划分一致点：在同步点之间不保证任何顺序，同步操作（如屏障、锁的获取）执行时，系统才把之前所有写传播出去。这是”用程序的同步结构来换取性能”的第一步。
- 释放一致性（Release Consistency）：把同步操作细分为获取（acquire）（如加锁、进入屏障）与释放（release）（如解锁、离开屏障）。规则是：在 release 时把本进程此前的写推送到其他副本；在 acquire 时把其他副本的写拉取过来。于是”一致性维护”只发生在这两类操作上，普通访存完全不产生网络流量。这是最实用的模型，Munin、TreadMarks 都建立在它之上。
- 入口一致性（Entry Consistency，Munin）：把释放一致性进一步放松到”只有在进入临界区/获取某个同步对象（锁、屏障）时，才更新与该同步对象关联的那些变量“。也就是说，程序员要说明”这把锁保护哪些变量”，acquire 时只同步这一组变量，而不是”所有之前写过的页”。更精确 ⇒ 开销更低（典型的 Munin 实验里消息数显著少于整页方案）。
- 懒惰释放一致性（Lazy Release Consistency, LRC，TreadMarks）：再放松一层——release 时不推送任何数据，只发布”哪些页被改过”的写在（write notices）；等到别的节点 acquire 时，才主动去把需要的页拉取回来（pull），而且只拉自己真正访问到的页（懒惰 = lazy）。这避免了”推送了但没人要”的浪费。它用写在 + 版本向量（version timestamp / interval） 记录”我的副本是基于哪个版本”，并用孪生页 + diff 支持多写者（见 23.3.3、23.3.4）。
- 事件一致性（Eventual Consistency）：如果写停止，所有副本最终收敛；读可能读到任意旧值。它是分布式存储（Cassandra/Dynamo，见第 9 章）的常用模型，也可以作为 DSM 的”最弱一致”选项（例如只读的共享数据集、近似计算）。它最便宜，但编程最困难（要处理冲突与旧读）。
- 表格 2：各种一致性模型的强度与 DSM 实现开销（强度自上而下递减，性能开销同样自上而下递减）
| 一致性模型 | 语义强度 | 一个读操作要不要通信？ | 一个写操作要不要通信？ | DSM 中的实现代价 | 代表系统 |
|---|---|---|---|---|---|
| 严格一致性 | 最强（实时全序） | 是（需确认最新） | 是（须在返回前传遍全网） | 在多计算机上不可实现 | 无 |
| 线性一致性 | 极强（实时全序 + 原子） | 通常要（quorum 往返） | 是（quorum 写） | 极高，读延迟不可接受 | 分布式 KV（非 DSM） |
| 顺序一致性 | 强（全序 + 程序序） | 命中时可本地 | 是（失效广播 $O(N)$） | 高：每次写一个失效广播 | IVY |
| 因果一致性 | 中（保因果序） | 命中时可本地 | 是（依赖向量时间戳） | 中高：向量随 $N$ 增长 | 因果多播类 DSM |
| PRAM / FIFO | 中弱（只保同进程序） | 命中时可本地 | 是（序列号，无跨进程序） | 中：实现简单但语义弱 | 阶段式并行程序 |
| 弱一致性 | 弱（同步点之间无序保证） | 命中时可本地 | 仅同步点传播 | 低：同步点边界明确 | 早期弱一致 DSM |
| 释放一致性 | 弱（acquire/release 边界） | 命中时可本地 | 只发生在 release | 低（普通访存零流量） | Munin、TreadMarks |
| 入口一致性 | 更弱（按同步对象逐组更新） | 命中时可本地 | 只发生在 acquire，且只涉及关联变量 | 更低（精确到锁保护的数据） | Munin |
| 懒惰释放一致性 LRC | 更弱（acquire 时才拉、且按需拉） | 命中时可本地 | release 只发写在，acquire 按需拉 diff | 最低（只传改动的字节） | TreadMarks |
| 事件一致性 | 最弱（最终收敛） | 可本地（可能旧） | 异步传播 | 极低，但没有可用的一致读 | Cassandra/Dynamo（存储） |
为什么 DSM 实践中都选择弱一致性模型？ 一句话：在 DSM 里，”一致性”就是”通信”，而通信比本地访存慢 3-5 个数量级。顺序一致性要求每一次写都触发失效广播（$O(N)$ 条消息），而释放一致性要求”每个同步区间只传播一次”——同一个程序，两者的消息量可以差一个数量级以上（第 23.4.3 节的实验实测：在 4 节点、每次同步区间内 20 次共享写的工作负载下，急切失效协议花费 16002 条消息 / 834.9 ms，懒惰释放一致性只用 400 条消息 / 21.6 ms，相差 38.6 倍）。弱一致性不是”更差的设计”，而是”用程序员可见的同步结构，换取系统看不见的通信开销下降”——前提是程序员必须真的把同步写对（详见 23.7 的陷阱 1）。
- （4）替换策略（Replacement Strategy）：本地内存有限，当装不下共享数据时必须替换（evict）某些页。
- 与虚拟内存的关键区别：传统虚拟内存中，被换出的页总是能到磁盘（后备存储）上再找回来；而在 DSM 中，被替换的页可能是全网唯一的一份副本（当该节点是这一页的 owner 且处于 W 状态时）。此时若直接丢弃，数据就丢了——所以 DSM 必须先写回（write back）到某个”家”位置，或把所有权连同数据交给别人。这就是为什么”谁能被替换”本身就是一个协议设计问题。
- 替换决策还与一致性耦合：淘汰一个”多副本的只读页”最便宜（直接丢，下次再取）；淘汰”唯一副本页”最贵（要写回）；而 DSM 通常没有全局的”访问时间/频率”信息（别的节点的访问模式看不见），LRU 这类启发式在这里并不好用。
- 抖动（Thrashing）：当多个节点反复争用同一批页，导致”每次访问都故障”时，系统吞吐量崩塌。经典场景：两个进程交替写同一页（讲义称之为 flip-flopping：一个进程使另一个的副本失效，然后反过来），或者工作集超过本地内存导致页被换出后立刻又被访问。用数字感受一下：一次页错误约 $100\ \mu s$（RTT + 传输），因此单节点每秒最多完成约 $10^4$ 次”有用的”故障访问；而一次本地访存约 $100\ ns$，即每秒 $10^7$ 次。抖动等于把程序的性能从”内存级”降到”网络级”，慢 1000 倍。
- 假共享（False Sharing）是 DSM 最著名的性能杀手——下一节专门讲。
23.2.5 假共享（False Sharing）：DSM 最著名的性能杀手
定义与目的：假共享指两个节点访问同一个”一致性单位”（页/块）中不同的变量，却因为 DSM 以块为单位维护一致性而互相失效、互相搬运整块数据。它不是逻辑错误（程序语义完全正确），而是纯粹的性能灾难：两个毫不相干的变量因为”住在一页里”而被绑成了冤家。
直观解释（”它是什么？”）：两个室友共用一本活页夹（一页 = 一个一致性单位）。A 只往第 5 页左上角记自己的账，B 只往第 5 页右下角记自己的账——两人写的是完全不同的格子，但按照”谁要写谁就必须独占整页”的规矩，A 一动笔，B 手上那页复印件就作废；B 一动笔，A 的复印件又作废。于是这本活页夹被传真机在两人之间来回搬运，两人都在等传真，谁也没多做一件正事。这就是讲义描述的 flip-flopping 行为：”两个进程并发写同一页 —— 一个进程使另一个失效，来回翻转，大量网络传输；当互不相关的变量恰好落在同一页上时就会发生，这被称为 false sharing。”
机制图解：假共享的机制与代价（本章最重要的一张图）。
场景：变量 a 在 page 5 的偏移 0，变量 b 在 page 5 的偏移 4096-8（同一页！）
节点 A 只写 a（例如统计自己的计数器），节点 B 只写 b（自己的计数器）
两者没有共享任何数据 —— 但共享了同一个"一致性单位"
时间 → A 的 cache B 的 cache 网络上的消息 谁在等
─────────────────────────────────────────────────────────────────────────────
t0 page5 (W)(O) — — B 想读 b:
t1 page5 (W)(O) page5 ▲失效 "INVALIDATE page5" A 被剥夺所有权
(请求) "FETCH page5"
t2 page5 (W) page5 (W)(O) ←── 整页 4 KB 传输 A 的下一页访问要再取
t3 page5 ▲失效 page5 (W)(O) "INVALIDATE page5" B 被剥夺所有权
(请求) "FETCH page5"
t4 page5 (W)(O) ←── page5 (W) 整页 4 KB 传输 A 再次等待……
t5 重复 t1-t4 …… 每一次"写一个 8 字节的变量"都变成"一整页 4 KB 的网络往返"
量化（本讲实验实测，2 节点 × 200 次写、页 = 64 B）：
紧凑布局（a、b 同页）: 400 次读缺失 + 400 次写升级 + 399 次失效
= 1998 条消息、63,968 字节、模拟耗时 105.0 ms
填充布局（a、b 分页）: 2 次读缺失 + 2 次写升级 + 0 次失效
= 6 条消息、 256 字节、模拟耗时 0.3 ms
放大倍数 : 333x 消息、250x 字节、328x 时间
（实验为了跑得快把页设成 64 B；若页 = 4 KB，字节放大还要再乘 64）
核心公式：一次假共享 = 一次网络 RTT + 一整块数据传输，而程序员以为那只是一次
8 字节的本地写入。粒度越粗，这个"隐藏的乘法系数"越大。
- 代价的定量分析（为什么要用”整页”作单位来看）：
- 假设页大小 $g$ 字节，两个节点各自每秒写 $f$ 次自己的变量（不同字），每次写都因为假共享触发一次整页往返。每秒的消息数约 $2f\cdot C$（一次失效 + 一次取页，$C$ 为一次往返所需的消息条数），每秒传输的字节数约 $f\cdot g$。
- 代入 $g=4096$ B、$f=1000$ 次/秒：每秒传输约 4 MB（每次写都搬一整页），而这 4 MB 里真正被修改的数据只有每次 8 字节，即每秒约 8 KB——有效载荷比 $8/4096 = 0.2\%$，浪费因子 $g/8 = 512$。换句话说，99.8% 的带宽在搬运没有人需要的数据。
- 更糟的是停顿（stall）而不是带宽：每次假共享都要等一个网络 RTT（$100\ \mu s$ 量级），因此一个每秒想写 1000 次的进程，光等待就要 0.1 秒，等于把 CPU 从”内存速度”直接降到”网络速度”。这就是讲义说的”需要把页大小设置成能捕捉一个进程的局部性“：页太大 ⇒ 假共享；页太小 ⇒ 页错误次数爆炸，同样低效（见 23.2.4 的 $g^*$ 估算与 23.4.1 的粒度扫描实验）。
- 表格 3：缓解假共享的方法
| 方法 | 做法 | 优点 | 代价 / 局限 |
|---|---|---|---|
| 减小粒度 | 用 cache line / 字级一致性单位 | 从根上减少假共享 | 需要编译器插桩或硬件支持；元数据爆炸；每字同步开销高 |
| 数据填充（padding） | 把热点变量各自对齐/填充到独立页或 cache line | 对程序改动小、效果立竿见影（实验实测消除 100% 假共享故障） | 浪费内存；需要程序员/编译器知道哪些是热点；对动态数据结构（链表、哈希表）不适用 |
| 编译器重排数据布局 | 把常被同一节点访问的变量聚在一起，把被不同节点访问的变量分开 | 自动、无需改程序语义 | 需要编译器分析访问模式；可能与 ABI/对齐冲突 |
| 按访问模式动态调整粒度 | 运行时检测共享模式，对热点区域使用更细的粒度 | 自适应 | 实现复杂；模式变化时会抖动 |
| 多写者 + 差异化（TreadMarks） | 允许多个节点同时写同一页的不同部分，用孪生页 + diff 只传改动字节，获取时合并 | 不需要搬整页，直接消灭假共享的搬运成本 | 只对不重叠的写安全；同一字节的并发送写仍是数据竞争（见 23.3.4） |
| 写更新（update）协议 | 写时不失效，而是把新值多播给其他持有者 | 适合”多读少写且写小变量”的共享数据 | 每次写都要广播，写频繁时更差；一般不如失效协议 |
- 关键假设与系统模型：假共享的根源是“一致性单位”与”访问模式单位”不匹配。它要求：（1）DSM 的一致性粒度 > 程序员实际共享的粒度（页 » 变量）；（2）多个节点并发/交替访问同一单位的不同部分。只要二者同时成立，假共享就必然发生。注意：假共享是性能问题而不是正确性问题——程序结果依然正确（一致性协议保证了这一点），只是慢得离谱。这一点非常重要，因为它意味着用测试（检查结果是否正确）无法发现假共享，必须测量通信量。
23.2.6 写失效 vs 写更新（Invalidate vs Update）
定义与目的：解决”多副本怎么写”的两条技术路线。写失效（invalidate）：一个节点要写某页时，先把其他所有副本作废，然后自己成为唯一副本与所有者（owner），之后随便写（讲义：页处于 W 状态 时只有 owner 有副本）。写更新（update）：允许多个进程同时持有 W 状态的副本，一次写就把新写的值（或页的一部分）多播给所有持有者，其他进程可以继续读写该页。
直观解释（”它是什么？”）：失效像会议室的”独占发言权”：谁要发言，先把别人的稿子收走，别人想发言得再要回来；更新像微信群里的”同步广播”：谁改了内容就在群里发一条更新，大家各自更新自己的副本——不用收走别人的东西，但每条改动都要发一次群消息。
机制图解：两种协议的时序对比。
(A) 写失效 Write-Invalidate（讲义：一般更优、更常用）
A: write page5 ──► [INVALIDATE page5] ──► B（副本作废） A 成为 owner(W) 独写
[INVALIDATE page5] ──► C（副本作废）
A: 后续 100 次写 → 全部本地命中，0 条消息 ✔ 写密集时非常划算
B: read page5 ──► 必须重新向 A 取整页（1 次 RTT） ✘ 读被拖慢
(B) 写更新 Write-Update（讲义：共享频繁、写小变量、页大时更好）
A: write page5[off=0] ──► [UPDATE page5, bytes 0..7] ──► B、C（就地打补丁）
B: write page5[off=8] ──► [UPDATE page5, bytes 8..15] ──► A、C
两人交替写 → 每次都发一次（小）更新消息 ✔ 读者永不失效，读延迟低
✘ 写频繁时消息数 = 写次数 × N
讲义结论：当【共享很多、写的是小变量、页很大】时 update 优于 invalidate；
但总体而言【invalidate 更好、更常用】。
关键假设与系统模型：失效协议的隐含假设是”写者会连续写“（一次失效可以摊薄后续多次写）；更新协议的隐含假设是”读者会立刻需要新值，且写很稀疏/很小“。两者都要求底层多播是可靠的（否则有的副本没收到失效/更新就会读到旧值，详见第 13 章的可靠多播与虚拟同步）。
一个重要的观察：失效协议把”写”的代价前置（写时付失效广播的钱），更新协议把”写”的代价广播化（每次写都付一次多播的钱）。因此（1）读多写少的共享数据适合失效；（2）写多且被多方持续读取的共享数据适合更新；（3）粒度越大，失效协议越吃亏（每次失效都要整页回取），更新协议越占优（更新的载荷可以只包含改动的小部分）。
23.2.7 DSM 的同步：锁、屏障与信号量（Beyond Consistency）
定义与目的：一致性协议只保证”内存看起来是一致的”，并行程序还需要互斥与阶段同步：锁（lock / mutex） 保护临界区，屏障（barrier） 让所有进程在阶段边界对齐，信号量（semaphore） 做生产者-消费者协调。DSM 的这些原语必须实现在同一套消息传递基础设施上，而且它们本身也会成为瓶颈（因为每个同步点都是一次全网交互）。
直观解释（”它是什么？”）：屏障像旅行团集合：导游要求”所有人都到齐了才发车”。集中式屏障 = 所有人向导游报到，导游数够人数才宣布出发（导游是瓶颈，但实现最简单）；树形屏障 = 分成小组，组长向上一层报到，逐层汇总（$O(\log N)$ 但层数越多、延迟也越多）。
机制图解：集中式屏障与树形屏障的消息模式。
集中式屏障（Centralized Barrier）：每轮 2N 条消息、2 个 RTT，根节点是瓶颈
P0 ──arrive──►┐
P1 ──arrive──►│ ┌──────────────┐
P2 ──arrive──►├─►│ 协调者 root │ 等 N 个 arrive 到齐
P3 ──arrive──►┘ └──────┬───────┘
└──release──► P0..P3（全部解锁）
树形屏障（Combining Tree Barrier）：每节点 O(1) 条消息，没有单点瓶颈
[根] 阶段1（向上）：每个内部节点等齐 k 个子节点
／ ＼ 阶段2（向下）：根发布"出发"，逐层向下
[内1] [内2]
／ ＼ ／ ＼ 每个节点只发 1 条向上、收 1 条向下
P0 P1 P2 P3 延迟 = 2 × 树高 = 2⌈log_k N⌉ 跳（4 节点 k=2：4 跳）
加上 sense-reversing（翻转"代"标志），避免
跑得快的进程抢跑进入下一轮、与上一轮混淆
屏障的成本与可扩展性：集中式屏障每轮至少需要 2 个 RTT（一个 RTT 收集到达，一个 RTT 发布释放），消息量 $O(N)$（若用多播则是 $O(1)$ 条多播消息但每节点仍要处理）。树形屏障把每节点的消息数降到 $O(\log N)$，但延迟变成 $O(\log N)$ 跳；在低延迟小规模集群上集中式反而更快，在大规模上树形/组合（combining）更优。这对并行程序的可扩展性是致命的：由 Amdahl 定律，若程序中 $s$ 比例的部分必须串行（屏障 + 临界区就是典型），则 $N$ 个节点的加速比上限是 $1/s$——屏障把”串行部分”的成本强加到每一轮，所以”加节点”救不了同步点太多、粒度太细的并行程序（这门课后面讲到的批处理/图计算系统之所以采用”超步（superstep）+ 批量同步”，就是在与屏障成本作斗争，详见第 24 章）。
锁的实现选项（与第 14 章「分布式互斥」的内容相互印证）：
| 锁实现 | 机制 | 消息复杂度（一次加锁+解锁） | 适用与局限 |
|---|---|---|---|
| 集中式锁服务器 | 所有请求发给一个节点，它按 FIFO 发 token | $O(1)$ 每条请求（但服务器是瓶颈） | 最简单；单点瓶颈、单点故障 |
| 基于队列的锁（MCS / 链表锁） | 每个等待者在前驱的本地变量上自旋，形成隐式队列 | $O(1)$ 消息，无惊群 | 需要能”远程写别人的本地变量”（RDMA 友好） |
| 票号锁（ticket lock） | 取号（atomic fetch-add）+ 自旋等号 | 每轮 $O(1)$ 但自旋产生缓存/网络流量 | 简单；高争用时自旋浪费带宽 |
| Ricart-Agrawala / Maekawa（第 14 章） | 全互斥投票 / 投票集 quorum 相交 | $2(N-1)$ / $O(\sqrt{N})$ 条消息 | 无中心节点；实现复杂，需处理失败 |
| RDMA 原子操作（CAS / fetch-add） | 直接对远端内存做原子操作，跳过远端 CPU 与内核 | $O(1)$ 个 RDMA 往返（~1-2 μs） | 现代集群的首选（FaRM、DrTM 等） |
- 关键假设与系统模型：DSM 同步原语必须满足（1）互斥（同一时刻至多一个持有者）；（2）无饥饿（每个请求最终被满足）；（3）与一致性协议配合——
acquire/release同时充当一致性同步点（这正是释放一致性的定义）。实现时还要考虑故障：持有锁的节点崩溃怎么办？经典 DSM 系统大多不处理（这是它未能进入生产环境的原因之一），而第 17 章的 Paxos/Raft 才是”崩溃也能正确释放锁”的正解。
23.2.8 经典 DSM 系统谱系与对比
定义与目的：DSM 在 1986-1996 年经历了一段密集的研究期，留下了一批经典系统。它们基本可以按”粒度 / 一致性模型 / 谁做检查“三个问题分成几支。
系统清单：
| 系统 | 年代 | 粒度 | 一致性模型 | 特色机制与贡献 |
|---|---|---|---|---|
| IVY（Li & Hudak） | 1986-1989 | 页（4 KB） | 顺序一致性 | 页级虚拟共享内存的开山之作：基于 MMU 页错误 + 单一所有者（owner）+ 写失效 + 所有权迁移；证明了”用 VM 做 DSM 可以保证顺序一致性” |
| Munin（Carter et al.） | 1991-1992 | 多种 | 入口一致性 / 类型特定一致性 | 按访问模式自动选择协议（写失效 / 写更新 / 延迟更新 / 只读复制 / 归约）；把同步对象（锁、屏障）与数据关联，acquire 时只更新关联变量 |
| TreadMarks（Keleher et al.） | 1994-1996 | 页 | 懒惰释放一致性 LRC | 写在（write notices）+ 版本向量 + 孪生页/差分（twin/diff）+ 多写者；只传改动的字节而不是整页，是 DSM 中最成功的实现之一 |
| Mirage | 1989-1990 | 固定粒度（可调，非 MMU 页） | 顺序一致性 | 实验性地研究”粒度对性能的影响”，支持固定大小的段与迁移 |
| Clouds | 1990 | 段/对象 | 顺序一致性 | 基于对象/段的操作，研究了”计算迁移 + 数据迁移” |
| Linda / 元组空间（Tuple Space） | 1985- | 元组 | 无（由操作语义定义） | 另一种共享抽象：不是共享内存而是共享”元组空间”，用 out/in/rd 三个操作通信（生成式通信，详见第 13 章）；天然解耦、天然异步 |
| Orca | 1989-1993 | 对象 | 顺序一致性（对象级） | 基于对象的 DSM：共享对象复制到多节点，对象上的操作串行化；编译时利用类型信息 |
| Shasta（DEC） | 1994-1996 | 细粒度（子页/64 B） | 释放一致性 | 编译器辅助的细粒度共享：在访问点插入检查代码，用”guarded region”处理子页权限，避开页粒度假共享 |
| Cashmere（DEC） | 1994-1995 | 页 + 写共享 | 释放一致性 | 集群 DSM，支持多写者 + 写共享（与其硬件平台 AlphaServer 的 cache line 失效机制配合），用”shadow page”复制页 |
| SVM / SoftFLASH（Stanford） | 1994-1997 | 细粒度（编译器） | 释放一致性 | 利用 FLASH 多处理器的 可编程协议处理器，把细粒度一致性的协议处理下移到硬件/固件，验证”细粒度 DSM 可行但有硬件门槛” |
- 表格 4：IVY vs Munin vs TreadMarks 全面对比
| 维度 | IVY | Munin | TreadMarks |
|---|---|---|---|
| 粒度 | 页（4 KB） | 页 + 按变量类型细分 | 页（4 KB） |
| 一致性模型 | 顺序一致性（严格） | 入口一致性（entry）/ 类型特定 | 懒惰释放一致性 LRC |
| 何时传播更新 | 写时立即失效（急切） | acquire 同步对象时，且只传播该锁关联的变量 | release 只发写在；acquire 时按需拉取 diff |
| 多写者支持 | 不支持（同一时刻只有唯一写者） | 部分（写共享协议允许并发写） | 支持（孪生页 + diff 合并） |
| 假共享处理 | 无对策（页级失效，flip-flopping） | 靠”类型特定协议 + 访问模式自动选择”缓解 | 直接用 diff 只传改动字节，从机制上消解搬运成本 |
| 一次读缺失的消息 | $O(1)$（请求 + 数据；需定位 owner） | $O(1)$（只取关联变量） | $O(1)$（按需拉 diff） |
| 一次写缺失的消息 | $O(N)$（向所有副本发失效） | 取决于所选协议（写更新为 $O(N)$，惰性更新更低） | $O(1)$ 条写在（release 时），字节数 = 改动量 |
| 空间开销 | 页表 + 所有者信息 | 页表 + 类型/锁关联信息 | 页表 + 孪生页（每页一份额外副本）+ 版本向量 |
| 失败处理 | 基本不处理（所有者崩溃即数据丢失风险） | 部分处理（可配置） | 弱（研究原型，无生产级故障恢复） |
| 代表贡献 | 第一个实用的页级软件 DSM，顺序一致性证明 | 协议按访问模式自动选择；入口一致性；类型特定一致性 | LRC + 多写者 + diff：把假共享的带宽成本降一个数量级 |
- 其他系统（简述）与现代的相关技术：
- Mirage（固定粒度，可调页大小）、Clouds（段/对象）、Linda/元组空间（生成式通信，另一种”共享”抽象）、Orca（基于对象的 DSM）、Shasta（细粒度、编译器辅助）、Cashmere（集群 DSM、写共享）、SVM/SoftFLASH（可编程协议处理器上的细粒度 DSM）共同构成了 DSM 的完整谱系：粒度从字到段、一致性从顺序到懒惰释放、实现从纯软件到编译器/硬件辅助。
- NUMA（Non-Uniform Memory Access）：硬件层面的”共享内存，但有远近”——同一台服务器内，访问本地内存节点约 100 ns，访问远端内存节点约 200-300 ns。NUMA 的核心问题与 DSM 完全相同（远端访问慢、粒度与局部性决定性能），只是它用硬件（目录 + 片上网络）解决了；理解 NUMA 是理解 DSM 的最佳捷径，也是”DSM 思想在单机内的体现”。
- RDMA（Remote Direct Memory Access）与 InfiniBand：讲义明确指出 DSM “可能正在回归“，原因是”更快的网络（如 InfiniBand）+ SSD 让 RDMA 变得流行“。RDMA 允许一台机器的网卡直接读写远端机器的内存（绕过远端 CPU 与内核），一次远端内存读写延迟约 1-2 μs，只比本地内存慢一个数量级——这与 1990 年代”页错误 100-500 μs”的处境完全不同，把 DSM 最致命的成本（同步延迟）压缩了两个数量级。讲义为此留了一个开放问题：”它会继续增长？还是维持现状？时间会告诉我们！”
- 内存解耦 / 内存池化（Memory Disaggregation）：在数据中心里把内存变成独立资源池（如 Infiniswap、LegoOS 的远端内存、CXL 内存池化/共享），应用通过高速网络访问”别人的内存”——这正是 DSM 的核心思想在云时代的复兴形态：不是”让程序员写共享内存程序”，而是”让内存像存储一样被池化与共享”。
- 分布式共享内存数据库 / 共享存储集群：如 Oracle RAC（多实例共享同一份数据，用 Cache Fusion 在实例间搬运数据块——本质就是一个页（块）级 DSM，只不过共享的是数据库块）、内存数据库集群（FaRM/DrTM 用 RDMA 做远端内存事务）。这些系统说明：只要网络足够快，”共享内存式的抽象”在工程上就有价值。
- 为什么经典 DSM 在实践中没有流行（四条原因，缺一不可地叠加）：
- 性能很难超过手工优化的消息传递：DSM 的一致性协议只能做”通用”的搬运决策，而程序员能用 MPI 精确地只传需要的数据、只在需要时传（第 23.5 节给出量化对比）；在 1990 年代的 10-100 Mbps 网络上，DSM 的页错误延迟（数百微秒）直接决定了它跑不过仔细写的 MPI 程序。
- 假共享难以根治：粒度为页 ⇒ 假共享是结构性缺陷，只能靠填充/重排等外围手段缓解，程序一旦有指针数据结构（链表、哈希表、图）就无从下手。
- 调试困难：非确定性（页错误的时机依赖调度与网络）使得 bug 难以复现；同时”性能 bug”（假共享、抖动）没有任何显式线索——程序结果正确但慢 100 倍，这在传统调试手段下几乎不可见。
- 多核 + NUMA + RDMA 让”共享内存”在单机/机架内用硬件解决更划算：单机内 8-128 核共享内存比 DSM 快 3-5 个数量级；跨机架用 RDMA 时，程序员更愿意显式调用
rdma_read/rdma_write（一次 1-2 μs）而不是让运行时偷偷帮他搬整页。换句话说：DSM 想解决的问题，被”更好的硬件 + 更诚实的接口”从两头夹击了。
23.3 算法伪代码与正确性分析
本章的五个算法构成一条清晰的演化链：IVY 的页级写失效协议（急切、强一致、$O(N)$ 失效广播）→ Munin 的入口一致性（按同步对象精确同步）→ TreadMarks 的懒惰释放一致性 LRC（release 只发写在、acquire 按需拉取）→ TreadMarks 的多写者 diff 机制（从机制上消解假共享的搬运成本）→ 屏障的集中式与树形实现（同步本身的开销）。所有算法都建立在同一套系统模型上，只是”什么时候传播什么”不同。
算法 23.3.1：IVY 的页级写失效协议（Page-Level Write-Invalidate with Ownership Migration）
假设与系统模型
- 进程与故障：$N$ 个进程（节点），crash-stop（进程可能崩溃并永久停止）；经典 IVY 协议不处理崩溃恢复——所有者崩溃会使该页的数据无法访问，因此下述正确性论证以”无故障执行（failure-free run）”为前提，故障处理见 23.5 与 23.7。
- 通道：可靠、FIFO 的点对点通道（TCP 级别）；失效请求可以用多播一次发给整组（讲义明确使用 multicast 来定位所有者、广播失效），我们同时按”等价的单播消息条数”给出复杂度。
- 共享空间：地址空间被划分为固定大小的页，每页恰好有一个所有者（owner）——”拥有该页最新版本的进程”；每页在任意时刻处于 R 状态（owner 有 R 副本，其他进程也可以有 R 副本，但不存在 W 副本）或 W 状态（只有 owner 有副本）。
- 访问拦截：本地没有该页（或权限不足）时由 页错误（page fault，内核 trap） 进入 DSM 软件层；页错误是同步的——进程阻塞等待页到达。
- 同步原语：本节只讲数据一致性；锁/屏障见 23.3.5。
伪代码
每个节点 i 的本地状态：
copy[p] ∈ {ABSENT, R, W} # 本节点持有的副本及模式
data[p] : 页内容（copy[p] ≠ ABSENT 时有效）
dirty[p] : bool # 自上次传播以来是否被写过（用于统计与页替换）
全局（一致性）元数据（可由目录节点维护，或通过多播询问动态获得）：
owner[p] : 当前所有者节点号
state[p] ∈ {R, W} # 页的全局模式
sharers[p] : 持有该页副本的节点集合（含 owner）
────────────── 本地访问路径（进程 i 访问页 p）──────────────
upon read(p) at i:
if copy[p] = R # 讲义读场景 1/3/4：命中
or (copy[p] = W and owner[p] = i): # 讲义读场景 2：命中
return data[p][offset] # 0 条消息
else:
read_fault(i, p) # 讲义读场景 5/6
upon write(p, v) at i:
if copy[p] = W and owner[p] = i: # 讲义写场景 1
data[p][offset] ← v ; dirty[p] ← true # 0 条消息
elif copy[p] = R: # 讲义写场景 2/3
write_upgrade(i, p) ; data[p][offset] ← v
else: # 讲义写场景 4（本节点无副本）
write_fault(i, p) ; data[p][offset] ← v
────────────── 读缺失：复制一份只读副本 ──────────────
upon read_fault(i, p):
multicast LOCATE(p) to group # 定位 owner（讲义：Use multicast）
o ← reply carrying owner[p] # owner 应答（或目录直接给出）
send READ_REQUEST(p) to o
upon receiving READ_REQUEST(p) at o:
if state[p] = W: state[p] ← R # W → R（降级，允许共享读）
send PAGE_DATA(p, data[p]) to i
upon receiving PAGE_DATA(p, d):
copy[p] ← R ; data[p] ← d
sharers[p] ← sharers[p] ∪ {i} # 关键：登记副本，供写者失效
return # 页错误解除，进程继续
────────────── 写升级：本节点已有有效 R 副本 ──────────────
upon write_upgrade(i, p):
for each j ∈ sharers[p] \ {i}: # multicast INVALIDATE
send INVALIDATE(p) to j
wait until all such j have replied ACK # 必须等所有副本作废！
owner[p] ← i ; state[p] ← W ; sharers[p] ← {i}
copy[p] ← W # 数据本地已有，无需传输
────────────── 写缺失：本节点没有副本 ──────────────
upon write_fault(i, p):
multicast LOCATE(p) to group ; o ← owner[p]
send WRITE_REQUEST(p) to i's peer o
upon receiving WRITE_REQUEST(p) at o:
snapshot ← data[p] # 先快照（失效会摧毁本地副本）
for each j ∈ sharers[p] \ {i}: send INVALIDATE(p) to j
wait until all such j have replied ACK
send PAGE_DATA(p, snapshot) to i # 所有权与唯一副本一起迁移
owner[p] ← i ; state[p] ← W ; sharers[p] ← {i}
upon receiving PAGE_DATA(p, d):
copy[p] ← W ; data[p] ← d ; owner[p] ← i ; sharers[p] ← {i}
────────────── 收到失效 ──────────────
upon INVALIDATE(p) at j:
copy[p] ← ABSENT ; data[p] ← ⊥ ; send ACK to sender
算法逻辑解说（用一个 4 节点的小例子走一遍） 设 4 个节点 P1-P4 都要访问第 5 页（记为 p5），初始时 p5 无人持有。按讲义给出的十个场景依次发生：
| 步 | 事件 | 协议动作 | 消息数（单播等价） | 结束状态 |
|---|---|---|---|---|
| 1 | P4 读 p5 | 无副本 → read_fault：多播 LOCATE，P4 自己是第一个接触者，demand-zero 建页 | 1 条多播（$N-1$） | P4: R+owner，sharers={P4}，state=R |
| 2 | P1 读 p5 | 本地无副本 → read_fault：向 owner P4 取一份 R 副本 | 定位 + 请求 + 数据 = 2-3 条 | P1、P4: R，sharers={P4,P1} |
| 3 | P1 读 p5（再来一次） | 本地命中（copy=R） | 0 | 不变 |
| 4 | P1 写 p5 | 本地是 R，且 owner=P4≠P1 → write_upgrade：失效 P4 | 1 条 INVALIDATE + 1 条 ACK = 2 | P1: W+owner，sharers={P1}，P4 副本作废 |
| 5 | P1 再写 100 次 | 本地是 W 且 owner=P1 | 0 × 100 | 不变（失效协议的红利） |
| 6 | P3 读 p5 | 无副本 → read_fault：owner P1 处于 W，降级为 R 并把页发给 P3 | 2-3 条 | P1、P3: R，state=R |
| 7 | P2 写 p5 | 无副本 → write_fault：owner P1 先失效 P3 与 P1 自己，再把页 + 所有权交给 P2 | 2 条失效 + 2 条 ACK + 1 条数据 = 5 | P2: W+owner（唯一副本） |
第 4 步与第 7 步是理解整个协议的关键：任何”写”都伴随着一次”把所有其他副本作废”的广播（讲义的”写场景 2/3/4”都写着 Ask other processes to invalidate their copies of page. Use multicast.），而“读”只复制不失效（讲义”读场景 5/6”），因此 读可以并行、写必须串行。
讲义在两个场景后特意留了两个反问，正好是学生最容易想错的地方：
- 读场景 4：”P1 有 R 副本，别人也有 R 副本，而 owner 是别人——P1 能直接从本地 cache 读吗？”能。因为页处于 R 状态意味着不存在 W 副本，而任何一次写都会让所有其他副本作废，所以 P1 手里的 R 副本必然是”最后一次写之后”取得的，一定是最新内容。这是协议的不变式在起作用，而不是运气。
- 写场景 2：”P1 是 owner 且有 R 副本，它能直接把页标成 W 然后写吗？”不能！ 其他进程可能还持有 R 副本，如果不失效它们，那些副本就会变成永远不会被更新的脏数据，之后它们再读就会读到旧值——顺序一致性当场被破坏。所以”owner”这个身份只保证”最新版本在我手上”，不保证”我是唯一持有者”；写操作必须先做一次失效广播并收集齐 ACK。
正确性论证（安全性 Safety：保证顺序一致性） 我们需要证明：任何一次执行的结果，都等价于把所有进程对共享内存的操作按某个全序执行，且每个进程自己的操作保持程序顺序。分三步论证。
不变式 I（每页只有一个写者、且 W 副本唯一）：对任意页 $p$，在任意时刻，至多一个节点满足 copy[p]=W，并且此时 sharers[p] 只含该节点、state[p]=W、owner[p] 就是它。 证明：初始为空。write_upgrade 与 write_fault 是唯一把 copy[p] 置为 W 的动作；两者都在设置 W 之前，向当前 sharers[p] 中除自己以外的每一个节点发送 INVALIDATE 并等待全部 ACK，然后才把 sharers[p] 重置为 {i}。收到 INVALIDATE 的节点把 copy[p] 置为 ABSENT，此后任何”命中”判断都不成立，必须重新走缺失路径。由”所有非自己副本都已被作废”与”sharers 精确记录了持有副本的节点集合”（每次复制副本时 sharers ∪ {i}，每次失效后从集合中移除），可得结论。前提依赖：通道可靠（ACK 不会丢、INVALIDATE 不会丢）——否则不变式失效，这正是 DSM 必须依赖可靠多播的原因（第 13 章）。$\square$
不变式 II（owner 的副本就是最新版本）：对任意页 $p$，owner[p] 持有的 data[p] 等于”最后一次完成的写”所写入的内容。 证明：对写事件归纳。每次写都发生在某个持有 W 副本的节点上，由不变式 I，该节点就是 owner 且是唯一持有者，因此”写的效果”直接落在 owner 的副本上；写完页面仍是 W 状态，owner 不变。当发生读缺失时，owner 把页交给读者（并在 W→R 时降级），转移的是同一份内容（PAGE_DATA(p, data[p])），所以读者的副本 = owner 的副本。当发生写缺失/写升级时，所有权迁移到写者，而写缺失路径先把 owner 的当前内容快照下来再传给写者（伪代码中的 snapshot ← data[p]），写升级路径则使用自己那份”由不变式 II 保证最新”的 R 副本。因此所有权如何迁移，最新内容始终跟着走。$\square$ （讲义在写场景 4 的措辞是”Fetch all copies; use the latest copy”，这里给出补充说明：在 IVY 的所有者制下无需真的取回所有副本——由不变式 II，最新副本一定在 owner 手上，因此只向 owner 取一份即可；失效广播仍然必须覆盖所有持有者，这是两件不同的事。）
安全性结论：设某次读操作 $R$ 返回了值 $v$。若 $R$ 是本地命中，则本地 copy[p] 为 R（或自己就是 W 状态 owner）；由不变式 I，此刻不存在其他写者，且该副本自其被创建/升级为 R 之后没有被任何写作废（否则 copy[p] 会变成 ABSENT，命中不成立），因此由不变式 II，$R$ 读到的是”创建该副本时 owner 的版本”，而此后没有写发生，所以它等于最近一次完成的写的值。若 $R$ 是缺失路径，则由不变式 II 它直接取自 owner，同样返回最近一次完成的写。于是：
- 每个读都返回”最近一次完成的写”的值（不存在”读到被覆盖的旧值”的情形）；
- 每个写都作为一个原子事件发生（失效全部 ACK 之后才写；失效之前该写对任何其他节点不可见——注意新的 owner 在收齐 ACK 前不会开始写，因此不存在”写了一半让别人看见”）。
取所有操作上的真实时间顺序作为全序：由 (1)(2)，该全序满足”读看到的就是它之前最后一次写”，而每个进程的操作在真实时间上本来就是有序的（因而保持程序顺序），所以这个执行完全等价于”所有操作按真实时间顺序依次执行”。因此 IVY 协议提供的不仅是顺序一致性，实际上是逐页的线性一致性（linearizability）——这比顺序一致性更强，也是”急切失效 + 唯一写者”这套设计的直接收益。$\square$
活性论证（Liveness）
- 无死锁：协议中唯一的”等待”是写者等待失效 ACK（
wait until all such j have replied ACK）。等待关系是”请求者 → 服务者”的单向关系：读者等 owner 回数据；写者等 owner（或等各 sharer 回 ACK）；而 sharer 收到 INVALIDATE 后立即应答、不再等待任何第三方，owner 收到请求后虽然要等 sharer 的 ACK，但 sharer 不会再去等别人，因此等待链的末端总是”无等待”的节点，不可能成环。$\Rightarrow$ 无死锁。 - 每个访问最终完成：若 owner 存活且通道可靠，
READ_REQUEST最终得到数据、INVALIDATE最终得到 ACK，缺失路径必然结束。故障前提：该论证要求 owner 与所有 sharer 都存活。这正是 IVY 类协议的活性软肋——只要有一个 sharer 崩溃，”等它的 ACK”就永远等不到（除非引入超时 + 成员管理，见第 7 章的故障检测）。DSM 系统普遍没有把这件事做扎实，这也是它在生产环境中败给复制状态机（第 17 章）的原因之一。 - 无饥饿：读/写请求之间没有优先级争夺，页错误是同步阻塞的，不存在”某个进程永远抢不到页”的情形（在所有节点都遵守协议、通道 FIFO 的前提下）。
复杂度
| 操作 | 消息复杂度（单播等价） | 数据量 | 说明 |
|---|---|---|---|
| 本地命中（读/写 W） | $O(1)$（0 条） | 0 | 命中的路径完全不进网络 |
| 读缺失 | $O(N)$ 定位（无目录时）$+\,O(1)$（请求 + 数据） | 1 页 | 有目录/所有者缓存则降为 $O(1)$ |
| 写升级（已有 R 副本） | $O(N)$（向所有其他 sharer 发失效 + 收 ACK） | 0（数据已在本地） | 写密集的页会反复触发 |
| 写缺失（无副本） | $O(N)$ 失效 + $O(1)$ 数据传输 | 1 页 | 所有权与数据一起迁移 |
| 空间 | 每节点 $O(\text{页数})$ 页表；全局元数据 $O(\text{页数} \times N)$ 的 sharer 集合（或由目录维护） | —— | 失效广播需要”谁有副本”，因此副本集合必须被精确跟踪 |
性能要点：读可以并行（复制），写必须串行（失效）。因此在”读多写少”的负载上 IVY 表现良好；一旦共享页被反复写，每次写都是一次 $O(N)$ 的失效广播 + 可能的整页回取，性能立刻崩塌（这就是 23.2.5 的假共享实验所量化的 333 倍消息放大）。
IVY 写失效协议的时序图（读缺失复制 / 写缺失失效 + 所有权迁移）：
P1 P2 P3 P4(owner,R) 网络/说明
│ │ │ │
│ ①读缺失(本地无 p5) │
│──── multicast LOCATE(p5) ──────────────►│ P4 应答"我是 owner"
│◄───────────────────────────────────────│
│──── READ_REQUEST(p5) ──────────────────►│ state[p5]=R，允许共享读
│◄──── PAGE_DATA(p5) ─────────────────────│ 复制一份只读副本
│ copy[p5]=R sharers={P4,P1} │
│ │ │ │
│ ②读命中（本地 R 副本）→ 0 条消息 │
│ │ │ │
│ ③写缺失/写升级 │
│ a. 若本地已有 R 副本： │
│──── multicast INVALIDATE(p5) ──────────►│ (发给 sharers \ {P1})
│◄─────────── ACK ────────────────────────│ 等齐所有 ACK 才继续
│ b. 若本地无副本（写缺失）： │
│──── WRITE_REQUEST(p5) ─────────────────►│ P4 先 snapshot ← data[p5]
│──── multicast INVALIDATE(p5) ──────────►│ 再失效所有其他副本
│◄─────────── ACK ────────────────────────│
│◄──── PAGE_DATA(p5)（数据 + 所有权迁移）──│ owner[p5] ← P1
│ copy[p5]=W owner=P1 sharers={P1} │ P4 的副本作废(ABSENT)
│ ④后续写在本地直接进行 → 0 条消息 │
│ │ │ │
▼ ▼ ▼ ▼
关键不变式：任一时刻"W 副本唯一 + 写者唯一" = 顺序一致性/线性一致性的来源
关键代价：每次"从读到写"的转换都要一次 O(N) 失效广播 + 一次网络 RTT
算法 23.3.2：Munin 的入口一致性（Entry Consistency）
假设与系统模型
- 进程与故障：$N$ 个进程，crash-stop；与 IVY 一样假定无故障执行（Munin 是 1990 年代初的研究原型，其故障处理并不完备）。
- 通道：可靠 FIFO 点对点通道 + 可靠多播；同步原语由 DSM 运行时提供（不是硬件锁）。
- 关键新假设（入口一致性的前提）：每个共享变量都与某个同步对象（锁或屏障）关联，程序员（或编译器）在程序里显式声明这种关联：
assoc(lock_L) = {x, y, z}。没有被任何同步对象关联的共享变量，被并发访问时行为未定义——这是”弱一致性换取性能”必须付出的编程代价。 - 粒度与结构：页为传输单位，但同步的粒度是”同步对象”：一次 acquire 只同步该锁关联的那些变量。
伪代码
变量声明（程序员/编译器给出）：
type(v) ∈ {READ_ONLY, WRITE_INVALIDATE, WRITE_UPDATE, DELAYED_UPDATE,
MIGRATORY, PRODUCER_CONSUMER, RESULT_ACCUMULATION, SYNC}
assoc(s) = {v | 变量 v 由同步对象 s（锁或屏障）保护}
每个节点 i 的本地状态：
copy[v] : 本地副本（含版本号 ver[v]）
dirty(v) : 本次临界区内是否写过 v
pending(v) : 需要向谁索取更新的标记
────────────── Munin 的"协议自动选择"（编译期/运行期）──────────────
classify(v):
if v 只被读且写极少 → READ_ONLY （到处复制，永不失效）
elif 写频繁且读者多、变量小 → WRITE_UPDATE （写时把新值多播给持有者）
elif 写频繁但读者暂时不需要 → DELAYED_UPDATE （推迟到下一次释放再传播）
elif 只有一个进程会写 → MIGRATORY （页跟着写者搬迁，不复制）
elif 生产者-消费者、每份数据只被消费一次 → PRODUCER_CONSUMER（消费后即失效）
elif 多个进程累加同一个结果 → RESULT_ACCUMULATION（累加型归约：把 +x 而非 x 传回去）
else → WRITE_INVALIDATE（默认：写失效）
────────────── 同步操作：入口一致性的核心 ──────────────
upon acquire(s) at i:
for each v ∈ assoc(s): # 只同步"这把锁保护的变量"
if copy[v] 过期（ver[v] < 全局版本）:
按 type(v) 的规则向持有最新副本的节点索取/接收更新
ver[v] ← 当前版本
enter_critical_section(s) # 现在这些变量是本节点私有的
upon release(s) at i:
for each v ∈ assoc(s) with dirty(v):
按 type(v) 的规则传播：
WRITE_INVALIDATE : 向所有其他副本持有者发送 INVALIDATE
WRITE_UPDATE : 把新值多播给所有持有者
DELAYED_UPDATE : 只登记"已改动"，等到下一次 acquire/release 再传播
MIGRATORY : 无须传播（自己是唯一写者，页已在本地）
RESULT_ACCUMULATION: 把"增量"而非"新值"送回累加器
dirty(v) ← false
exit_critical_section(s)
────────────── 屏障同步（另一种同步对象）──────────────
upon barrier_arrive(b):
for each v ∈ assoc(b): 按上述规则收集更新 # 屏障同样携带变量集合
report arrival to the barrier coordinator
wait for the release notification
算法逻辑解说 入口一致性与释放一致性的差别，可以用一句“锁保护什么，就同步什么”来概括。设程序里有 1000 个共享变量、20 把锁，每把锁保护 50 个变量（互不重叠）：
- 释放一致性：acquire 时要保证”看到所有在因果上先于它的释放所做的更新”。若实现得比较保守（比如按页同步），一次 acquire 可能会牵动大量与该锁无关的页——因为一个页上可能混装了几十把锁保护的变量。
- 入口一致性：acquire(lock_7) 只同步
assoc(lock_7)里的 50 个变量对应的数据（Munin 的实现里，这些变量往往被特意布局在一起，编译器协助做数据布局），因此同步的数据量与”这把锁保护多少数据”成正比，而不是与”进程碰过多少数据”成正比。
Munin 的另一半贡献是类型特定的内存一致性（type-specific memory coherence）：同样的共享数据，按访问模式选择最合适的协议。讲义里强调的”根据访问模式自动选择协议”在工程上的价值在于：没有一种协议对所有模式都最优——只读数据用复制（零失效）、写小变量且读者多用更新、单写者用迁移、累加用归约，Munin 把这些策略放进同一个运行时并按变量分类自动切换。
正确性论证
- 安全性（互斥访问下不读旧值、不丢更新）：考虑任意共享变量 $v$ 与它的关联同步对象 $s=\text{prot}(v)$。前提假设 H（数据竞争自由）：程序对 $v$ 的所有访问都在持有 $s$ 的临界区内进行（这是入口一致性对程序员的硬性要求）。于是对 $v$ 的任意两次冲突访问（至少一次是写）都被同一把锁的 acquire/release 全序化了：设写 $W$（持有者 A）在释放 $s$ 之前发生，读 $R$（持有者 B）在 A 释放之后 acquire $s$ 才发生。由伪代码，A 在
release(s)时按type(v)传播了 $v$ 的更新（失效/更新/登记延迟传播），而 B 在acquire(s)时会检查ver[v]并取回比自己新的版本，因此在 B 进入临界区时，它手上的 $v$ 至少和 A 释放时一样新。读 $R$ 因此不会读到被 $W$ 覆盖的旧值。对”两个写”同理：B 在 acquire 时拿到了 A 的版本（或在 WRITE_UPDATE 下已被推送），所以 B 的写是基于最新值的读-改-写，不会丢失 A 的更新（这正是第 23.4.1 节实验里”不加锁 ⇒ 丢失 60 次更新”的反面）。$\square$ - 为什么必须有假设 H：如果程序员访问了 $v$ 却没有持有 $s$，那么上面这条推理链断裂——此时没有任何协议能保证顺序（这正是讲义一致的立场：一致性模型只在”程序遵守契约”的范围内提供保证）。Munin 的实现会尽量把这类访问归类到 WRITE_INVALIDATE 并用页级保护兜底，但语义上不做承诺。
- 活性：
acquire是请求-应答式的单向等待（等到更新或超时放弃），只要被请求者存活且通道可靠就会返回；锁的授予由运行时保证 FIFO 或至少无饥饿；屏障的活性见 23.3.5。$\square$
复杂度
| 操作 | 消息复杂度 | 数据量 | 与 IVY 的对比 |
|---|---|---|---|
acquire(s) | $O(\text{该锁关联变量中过期的个数})$ 个请求 | 只含该锁关联的变量 | IVY 的读缺失以”页”为单位，可能牵入无关变量 |
release(s) | 按 type(v)：失效 $O(\text{复制数})$ / 更新 $O(\text{复制数})$ | 只含改动的变量 | IVY 每次写都触发 $O(N)$ 失效 |
| 临界区内访问 | $O(1)$（0 条消息） | 0 | 两者相同（本地命中） |
| 空间 | 页表 + 变量→同步对象、变量→协议类型 的映射表 | —— | Munin 需要编译器/语言支持来做布局与分类 |
算法 23.3.3：TreadMarks 的懒惰释放一致性（Lazy Release Consistency, LRC）
假设与系统模型
- 进程与故障：$N$ 个进程，crash-stop；TreadMarks 是研究原型，不提供故障恢复（进程崩溃会导致其未传播的 diff 丢失）。
- 通道：可靠 FIFO 的点对点通道（TreadMarks 在 UDP/TCP 之上实现自己的可靠消息层）；不要求”地址多播”，因为数据是拉取的。
- 一致性契约：释放一致性——程序必须无数据竞争（data-race-free） 且正确使用同步对象；运行时的保证是：任何 acquire 都能看到所有”因果上先于它的 release”所做的更新。
- 多写者前提：多个节点可以在同一同步区间内同时持有同一页的写权限，但它们写的字节必须互不重叠（这一前提在 23.3.4 中精确化）。
- 元数据：每个节点维护一个向量时间戳（version vector / interval），记录”我已经同步到每个节点的第几次 release”。
伪代码
每个节点 i 的本地状态：
ts_i # i 自己的逻辑计数器，每次 release 加 1
V_i[1..N] # 版本向量：V_i[j] = i 已知的 j 的最新 release 号
WN[j] # 从 j 那里收到但尚未应用的"写在"集合
# 写在 write notice = "第 ts 次 release 改动了这些页"
copy[p] # 页 p 的本地副本（可能因写在而失效）
twin[p] # 第一次写 p 之前保存的"孪生页"（见 23.3.4）
needed[p] # 需要从哪些节点拉取 p 的 diff
dirty[p] # 自上次 release 以来是否写过 p
────────────── release(s)：只发布"写在"，不传数据 ──────────────
upon release(s) at i:
ts_i ← ts_i + 1
WN_i ← { p | dirty[p] = true } # 本次 release 区间内改动过的页
记录 (WN_i, ts_i) 为"我的第 ts_i 次 release"（供别人 acquire 时来取）
dirty[p] ← false for all p
# 注意：这里【不发送任何页数据】——这就是"懒惰"的含义
# 复杂性：一条（通常很小的）write-notice 消息，而不是 N-1 次整页推送
────────────── acquire(s)：拉取因果上先于它的所有写在 ──────────────
upon acquire(s) at i:
r ← 上一个释放 s 的节点（由锁/屏障的元数据给出）
send ACQUIRE_REQUEST(V_i) to r # 带上我的版本向量
upon receiving ACQUIRE_REQUEST(V) at r:
# 收集所有"V 还没有覆盖到的" release 的写在（含 r 自己的与 r 转发来的）
WN ← union over j of { (WN_j, ts_j) | ts_j > V[j] }
send WRITE_NOTICES(WN) back to i
upon receiving WRITE_NOTICES(WN) at i:
for each (WN_j, ts_j) in WN:
for each page p ∈ WN_j:
copy[p] ← INVALID # 只需作废，无需取数据
needed[p] ← needed[p] ∪ {j}
V_i[j] ← max(V_i[j], ts_j)
return (进程进入临界区)
────────────── 真正需要数据时才拉取（懒惰的关键）──────────────
upon access(p) at i where copy[p] = INVALID:
if needed[p] ≠ ∅:
for each j ∈ needed[p]:
send DIFF_REQUEST(p, ts) to j # 只要"改动的那几个字节"
upon receiving DIFF_REQUEST at j:
d ← compute_diff(j, p) # 见算法 23.3.4：copy[p] XOR twin[p]
send DIFF(p, d) to i
upon receiving all diffs:
base ← 从最新版本持有者取一份基线页（若本地完全没有副本）
apply(d) to base for each d # 合并多个写者的差分
needed[p] ← ∅
copy[p] ← VALID ; return data
算法逻辑解说（时间线：为什么”懒惰”能省掉大量流量） 设节点 A 与节点 B 在同一个同步区间内各自写了 100 次不同的页/变量，然后在屏障处同步。
- 急切释放一致性（release 时推送）：A 在 release 时把 100 次写涉及的所有页推送给所有可能感兴趣的人（哪怕 B 根本不会读它们）；B 同样做一遍。若页大小 4 KB、涉及 20 页，则单向推送 80 KB，双向 160 KB，且其中有大量”传了没人看”的数据。
- 懒惰释放一致性（LRC）：A 在 release 时只发布一条很小的写在（”我改过第 3、7、11…页”，约几十字节）；B 的 acquire 从上一个释放者那里取回它还没见过的写在集合，把相应页本地作废；只有当 B 真的访问某一页时才去拉取差分（可能只有 8 个字节）。
- 效果：把”可能需要的所有数据”变成”确实需要的那部分数据”，并且把传输单位从”整页”降到”改动的字节”。这就是 TreadMarks 相比 IVY 减少一个数量级流量的原因。
释放一致性 vs 懒惰释放一致性的时间线（何时推送、何时拉取）：
(A) 释放一致性 RC（release 推送 + acquire 拉取）
Node A 网络 Node B
│ 写 p1,p2（本地，0 消息） │ 写 p1,p2（本地，0 消息）
│ │
release(s) ──► [PUSH p1,p2 整页] ──► │ （B 可能根本不用 p1！）
│ │
│ ◄── [PULL 我需要的页] ── acquire(s)
│ │
特点：release 主动推、acquire 被动等；推的数据可能没人要；消息数 = O(页数×N)
(B) 懒惰释放一致性 LRC（release 只发写在，acquire 按需拉 diff）
Node A 网络 Node B
│ 写 p1,p2（本地，0 消息） │ 写 p1,p2（本地，0 消息）
│ │
release(s) ──► [WRITE NOTICES: {p1,p2}, ts=7]（几十字节，不传数据）
│ │ acquire(s) ──► [ACQUIRE(V_B)]
│ ◄────────────────────────────────┤ ◄── [WRITE NOTICES 未覆盖的部分]
│ │ B 本地把 p1,p2 作废（0 字节数据传输）
│ │
│ ◄── [DIFF_REQUEST(p1)] ──────────┤ B 第一次访问 p1 时才拉
│ ──── [DIFF p1: 8 字节] ─────────► │ 只传改动字节
│ │
特点：release 一条小消息，acquire 只得到"哪些页变了"，
真正的数据在【第一次访问时】按需拉取，且单位是 diff 而不是整页
代价：元数据（版本向量 O(N) / 写在集合）+ 多一次消息往返（先要写在，再要 diff）
但换来的是：流量与"实际共享的数据量"成正比，而不是与"共享页的数量"成正比
正确性论证（安全性 Safety：acquire 能看到所有因果上先于它的更新）
- 定义：把”release $R$ 发生在 acquire $A$ 之前”记为 $R \to A$，其传递闭包（经由”同一节点上的先后”与”acquire 之后紧接的 release”）就是 happens-before（第 11 章）。
- 不变式 III（版本向量的单调覆盖）：$V_i[j]$ 的值总是”节点 $i$ 已经取得写在的、节点 $j$ 的最高 release 号”，且满足：若 release $R_j^{(k)}$ 到 acquire $A$ 之间满足 $R_j^{(k)} \to A$，则 $A$ 完成时 $V_i[j] \ge k$。 证明（对 happens-before 的长度归纳）：基例：若 $R_j^{(k)}$ 与 $A$ 在同一节点（$i=j$），则节点自己的
ts_i已经包含了 $k$，$V_i[i] \ge k$ 显然成立。归纳步：若 $R_j^{(k)} \to A$ 是通过链条 $R_j^{(k)} \to A^{\prime} \to R^{\prime\prime} \to \dots \to A$，则按归纳假设，在中间的 acquire $A^{\prime}$ 完成时，执行 $A^{\prime}$ 的节点 $m$ 已满足 $V_m[j] \ge k$；而当 $m$ 随后执行 release 时，它把 $V_m$ 作为自己 release 的上下文（写在 + 版本向量）一并发布（伪代码中写在按节点索引、并且 acquire 请求携带 $V_i$，服务端返回所有 $V$ 未覆盖的 $j$ 的写在），因此后一个 acquire 从 $m$ 那里取回的写在集合必然包含 $j$ 的 $k$ 号 release 所覆盖的页（因为 $V_m[j]\ge k > V_{\text{后者的}}[j]$，该写在不会被跳过）。$\square$ - 安全性结论：设 $A$ 是节点 $i$ 的一次 acquire，$R$ 是任意满足 $R \to A$ 的 release，$p$ 是 $R$ 改动过的页。由不变式 III，$A$ 完成后 $V_i$ 覆盖了 $R$，且伪代码保证 $R$ 的写在必然出现在 $i$ 收到的
WRITE_NOTICES中（服务端返回所有 $V_i$ 未覆盖的 release 的写在），于是copy[p] ← INVALID、needed[p]记录了 $R$ 的生产者节点。此后 $i$ 对 $p$ 的任何访问都会先触发copy[p]=INVALID路径：向needed[p]中所有节点索取 diff 并应用，然后才返回数据。因此 $A$ 之后的第一次访问 $p$ 一定看到 $R$ 的写效果，不存在”读到被覆盖的旧值”。$\square$ - 多写者合并的顺序无关性：多个节点的 diff 被应用到同一页，其最终结果与”按任意顺序应用”无关——前提是它们写的字节互不重叠（证明见 23.3.4）。若重叠，协议不保证正确，但会检测并报错（guarded byte → SIGBUS）。
- 活性：
acquire只需要与”上一个释放者”通信一次（请求/应答），DIFF_REQUEST同样是一次请求-应答，不构成循环等待，因此只要相关节点存活、通道可靠，每个操作最终完成。注意：LRC 的acquire复杂度与”未同步的 release 数量”有关，若某节点长时间不 acquire，其积累的写在会很大（这是”懒惰”的代价）。
复杂度
| 操作 | 消息复杂度 | 数据量 | 备注 |
|---|---|---|---|
release(s) | $O(1)$ 条消息（写在通常随同步消息捎带） | $O(\text{写在数量})$ 字节 | 不传页数据 |
acquire(s) | $O(1)$ 次请求-应答（取写在） | $O(\text{未覆盖的 release 数})$ 字节 | 写在集合可能较大 |
| 缺失访问（需数据） | $O(\text{生产者数})$ 次请求-应答 | $O(\text{改动的字节})$（diff） | 只在真正访问时发生（懒惰） |
| 临界区内命中 | $O(1)$（0 条消息） | 0 | 与 IVY 相同 |
| 空间 | 每节点 $O(N)$ 版本向量 + $O(\text{页数})$ 写在表 + 每页一份孪生页 | —— | 孪生页是”多写者”的内存代价 |
算法 23.3.4：TreadMarks 的多写者差分机制（Multiple-Writer with Twin Pages and Diffs）
假设与系统模型
- 与 23.3.3 相同，外加核心前提 P：在同一个同步区间内，多个节点对同一页的写必须落在互不重叠的字节上。这是”多写者”能安全合并的充分必要条件；重叠写 = 真正的数据竞争（data race），协议不负责。
- 实现基础：需要能在”第一次写某页”时截获并保存旧内容 ⇒ TreadMarks 用
mprotect把页设为只读产生”保护页（guarded page）”，第一次写触发 SIGSEGV，运行时在信号处理函数里复制一份孪生页（twin），再把页恢复为可写。因此每页的第一次写会付出一次额外的页保护开销（但只付一次，之后随你怎么写）。
伪代码
每个节点 i，对每个页 p 维护：
copy[p] : 当前内容（字节数组）
twin[p] : 孪生页（修改前的快照），或 ⊥ 表示"本区间还没写过 p"
dirty[p]: bool
────────────── 写路径：第一次写时保存孪生页 ──────────────
upon write(p, off, val) at i:
if twin[p] = ⊥: # 本区间第一次写这一页
twin[p] ← copy_of(copy[p]) # ★ 保存"修改前"的整页快照
mark p as "written in this interval"
copy[p][off] ← val # 后续写只是普通内存写（本地，0 消息）
────────────── 生成差分：请求者来要的时候才算 ──────────────
compute_diff(i, p) -> runs:
if twin[p] = ⊥: return ∅ # 本区间没写过 → 无差分
delta[off] ← copy[p][off] XOR twin[p][off] for all off # 逐字节 XOR
runs ← compress(delta) # 把连续的非零字节压成 [(offset, bytes), ...]
twin[p] ← ⊥ # 孪生页被消费掉（下次写会重新快照）
return runs # 典型大小：改了几个字节就传几个字节
────────────── 应用差分：合并多个写者的差分 ──────────────
upon apply_diff(p, runs, from j) at i:
for each (off, bytes) in runs:
if 本地在同一区间也写过这些字节（本地 delta 重叠）:
raise WRITE_WRITE_CONFLICT(p, off) # TreadMarks: SIGBUS，程序终止
for k in range(len(bytes)):
copy[p][off+k] ← copy[p][off+k] XOR bytes[k]
# 不重叠时：直接异或即可，无需加锁、无需排序
────────────── 与三种"写者集合"的配合（TreadMarks 的三种页面状态）──────────────
页面状态： UNOWNED（无写者）/ SINGLE-WRITER（一个写者）/ MULTI-WRITER（多写者）
- 第一个写者把页加入自己的写在集合，并创建孪生页 → SINGLE-WRITER
- 若另一个节点在【同一区间】也要写同一页，它同样作废本地副本、拉取一份
基线、创建自己的孪生页 → 页面进入 MULTI-WRITER，此后两个写者的差分都要合并
- 接收方按"写在/版本向量"给出的顺序合并所有差分（不重叠 ⇒ 顺序无关）
机制图解：两个”不重叠的写”如何被正确合并（多写者 diff 的核心图）。
基线页 base = a0 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0 （16 字节）
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ← 偏移
节点 A：只写偏移 2 节点 B：只写偏移 5 （两人写的是"不同的字节"）
┌──────────────────┐ ┌──────────────────┐
│ twin_A = base │ │ twin_B = base │ ← 第一次写前各自快照孪生页
│ copy_A[2] = 11 │ │ copy_B[5] = 22 │ ← 之后只改本地副本
└────────┬─────────┘ └─────────┬────────┘
│ diff = copy XOR twin │
▼ ▼
diff_A = [(2, b1)] diff_B = [(5, 82)] 每个差分只有 1 个非零字节
3 字节上网 3 字节上网
└────────────┬───────────┘
▼
节点 C（读者 / 需要该页的 acquire 者）
第一步应用 diff_A : a0 a0 11 a0 a0 a0 a0 a0 … ← A 的写生效
第二步应用 diff_B : a0 a0 11 a0 a0 22 a0 a0 … ← B 的写也生效 ✔
交换顺序再合并一次: a0 a0 11 a0 a0 22 a0 a0 … ← 结果完全相同（可交换）
对比"整页传输"实现（没有 twin、没有 diff）：
A 的整页先到 → a0 a0 11 a0 a0 a0 … ；B 的整页后到 → a0 a0 a0 a0 a0 22 …
★ 后到的整页把先到的写【覆盖】掉 ⇒ 必然丢失一个更新（假共享的灾难形态）
★ 为什么可交换？每个字节只有一个写者（不重叠），且异或自反：base ⊕ (base ⊕ v) = v
★ 什么时候不能合并？两个节点写【同一个字节】⇒ 前提 P 被破坏 ⇒ SIGBUS
算法逻辑解说（具体到字节） 设页 $p$ 的初始内容为 16 个字节 $[\texttt{a0}\times16]$（算法 23.4.2 的实验就是这个例子）：
- 节点 A（只关心偏移 2）第一次写：
twin_A ← a0 a0 … a0，然后copy_A[2] ← 11。 - 节点 B（只关心偏移 5）第一次写：
twin_B ← a0 a0 … a0，然后copy_B[5] ← 22。 - A 的差分：
copy_A XOR twin_A = 00 00 b1 00 …，压缩后是[(2, b1)]——3 个字节（2 字节偏移 + 1 字节数据）。 - B 的差分：
[(5, 82)]—— 也是 3 个字节。 - 节点 C 收到两份差分，先应用 A 的（
C[2] ^= b1⇒C[2] = 11），再应用 B 的（C[5] ^= 82⇒C[5] = 22）。两个写都在！ - 反过来先应用 B 再应用 A，结果完全一样（
a0 a0 11 a0 a0 22 a0 …）——合并是可交换的。 - 对比”整页传输”：若 A、B 各自把自己的整页推给 C，后到的整页会把先到的覆盖掉，必然丢失一个更新（
a0 a0 a0 a0 a0 22 …或a0 a0 11 a0 …），这正是假共享在”整页推送”实现下的灾难。 - 若 A 和 B 都写偏移 2（真数据竞争）：A 的差分
[(2, b1)]与 B 的差分[(2, 82)]都作用在同一个字节上，异或合并得到 $\texttt{a0}\oplus\texttt{b1}\oplus\texttt{82}=\texttt{93}$——一个谁也没写过的值。TreadMarks 不会静默接受它：应用差分时会检查”这些字节是否与本节点未传播的写重叠”，重叠即抛出 SIGBUS（写-写冲突），宁可让程序崩溃，也不让它悄悄算错。
正确性论证（多写者 + diff 合并的正确性）
- 前提 P（字节不重叠）：$\forall$ 同一区间内的两个写者 $j\neq k$，其差分涉及的字节集合 $B_j \cap B_k = \emptyset$。
- 引理 1（最终内容 = 所有写的效果都保留）：设基线页内容为 $base$，写者 $j$ 把偏移 $o$ 写成值 $v$（即 $\text{copy}_j[o]=v$，$\text{twin}_j[o]=base[o]$，故 $d_j[o]=base[o]\oplus v$）。应用差分时 $\text{copy}[o] \leftarrow base[o] \oplus d_j[o] = base[o]\oplus base[o]\oplus v = v$（XOR 自反性）。且由前提 P，其他写者的差分在字节 $o$ 上的分量均为 0（即 $d_k[o]=0$），因此对 $o$ 的后续应用都不改变它的值。所以每个被写过的字节最终都等于”唯一写它的那个写者所写的值”。$\square$
- 引理 2（与合并顺序无关）：异或运算满足交换律与结合律，且各字节相互独立；又由前提 P，任意字节 $o$ 至多被一个差分修改，于是对该字节的操作为 $\text{copy}[o]\leftarrow\text{copy}[o]\oplus(\text{至多一个非零 }d[o])$，结果与差分的到达顺序无关。因此合并结果 = 按任意串行顺序执行这些写的结果——这正是”可串行化”在该页上的体现。$\square$
- 引理 3（与”整页覆盖”的对比）：整页推送等价于”最后一次到达的写者覆盖其他所有写者的结果”，在前提 P 成立（写不同字节）时也会丢更新，因此 diff 机制不是”锦上添花”，而是多写者共享同一页的正确前提。$\square$
- 前提被破坏时的行为（重要）：若 $B_j \cap B_k \neq \emptyset$，引理 1 的”每个字节至多一个写者”不再成立，异或合并产生的是两个值的异或而非任一写者的值（实验结果
93既不是 11 也不是 22）。TreadMarks 的处理是检测并报错（guarded byte 重叠 ⇒ SIGBUS），把”静默错误”变成”响亮的失败”。结论：DSM 用 diff 解决了假共享（不同字节），但没有、也不可能解决数据竞争（同一字节）——数据竞争的串行化只能靠程序员用锁/屏障做到。$\square$ - 活性：差分在首次访问时按需拉取，请求-应答无循环等待；孪生页在生成差分后被释放，不会无限增长（长时间不同步时孪生页数量 = 本区间写过的页数，这是内存开销的上界）。$\square$
复杂度
| 项目 | 代价 | 说明 |
|---|---|---|
| 每页第一次写 | 1 次页保护陷入 + 复制一整页（$O(g)$ 内存与时间） | 只付一次 |
| 生成差分 | $O(g)$ 时间（逐字节比较/异或） | 只在有人要的时候算 |
| 传输 | $O(\text{改动字节数} + \text{游程数})$ | 相比整页可减少 1-3 个数量级 |
| 应用差分 | $O(\text{改动字节数})$ + 重叠检查 | 重叠检查是”数据竞争检测”的成本 |
| 内存 | 每页最多一份孪生页（$O(\text{本区间写过的页数} \times g)$） | 这是多写者的空间代价 |
| 冲突处理 | 重叠 → SIGBUS | 不做自动合并（避免不可预测的语义） |
算法 23.3.5：集中式屏障与树形（组合树）屏障（Centralized vs Combining-Tree Barrier）
假设与系统模型
- $N$ 个进程，无故障（或故障进程被成员管理剔除，见第 7 章）；可靠 FIFO 通道；屏障是可重复使用的——因此必须处理”快的进程抢跑到下一轮”的问题。
- 集中式屏障：指定一个协调者（coordinator），它必须处理 $O(N)$ 的到达报数。
- 树形屏障：进程按 fan-in 为 $k$ 的树组织（$h=\lceil \log_k N\rceil$ 层），叶子是进程，内部节点负责”汇总到达、向下释放”。
伪代码
────────── 集中式屏障（带 sense reversal，防止"代"混淆）──────────
协调者 C 的状态： count ← 0 ; sense_C ← 0
进程 i 的状态： my_sense ← 0
upon barrier_arrive(i):
send ARRIVE(i) to C # 1 条消息
block until 本地 release 通知到达 # 等待释放
upon receiving ARRIVE(i) at C:
count ← count + 1
if count = N: # 全员到齐
count ← 0
sense_C ← 1 − sense_C # ★ 翻转"代"标志
for j in 1..N: send RELEASE(sense_C) to j # N 条消息
# 用 sense 而不是简单的计数器，可以区分"上一轮的 release"与"这一轮的 arrive"
upon receiving RELEASE(s) at i:
if s ≠ my_sense: # 这是新一轮的释放
my_sense ← s ; unblock the waiting process
────────── 树形（组合树）屏障：两阶段，向上汇总 + 向下释放 ──────────
进程 i 维护： arrived_i ← 0 ; sense_i ← 0
内部节点 v 维护：arrived_v ← 0 ; sense_v ← 0 ; children(v) ; parent(v)
阶段 1（向上：到达汇总）
upon barrier_arrive(i) at leaf i:
send ARRIVE to parent(i) # 叶子只发 1 条
block until released
upon receiving ARRIVE at internal node v:
arrived_v ← arrived_v + 1
if arrived_v = k: # 我的 k 个孩子都到齐了
arrived_v ← 0 ; sense_v ← 1 − sense_v
if v = root:
go to 阶段 2（从 root 向下释放）
else:
send ARRIVE to parent(v) # 只向上转发 1 条 ★ 这就是 O(log N) 的来源
阶段 2（向下：释放传播）
upon release at internal node v:
for c in children(v): send RELEASE(sense_v) to c # k 条
if v ≠ leaf: unblock 本地进程（若有）并翻转本地 sense
upon receiving RELEASE at node u:
unblock the local process ; set sense_u ← sense from parent
算法逻辑解说
- 集中式：$N-1$ 个进程各发 1 条 ARRIVE，协调者收齐后发 $N-1$ 条 RELEASE ⇒ 总消息 $2(N-1)$，延迟 2 个 RTT，但协调者要处理 $O(N)$ 条消息（在网络与 CPU 上都是瓶颈：$N=1024$ 时协调者每轮收 1023 条、发 1023 条）。
- 树形（fan-in $k$）：每个叶子只与父节点交互，每个内部节点只等齐 $k$ 个孩子就向上转发 1 条 ⇒ 每个节点收发 $O(1)$ 条消息、没有任何节点处理超过 $k$ 个孩子；总消息仍约 $2N$（$N-1$ 个内部节点各转发一次上、一次下），但延迟变成 $2h$ 跳（$h=\log_k N$）。也就是说：树形屏障用”更多跳的延迟”换”更好的负载分布”。
- 为什么需要 sense reversal：如果只用计数器重置，那么一个跑得快的进程可能在协调者重置计数器之后立刻到达下一轮，并把”上一轮遗留的 release 消息”误当作”本轮的释放”而提前放行——屏障的安全性就被破坏了。用一个”代（sense）”标志并每轮翻转，可以让进程区分”这是第几轮的释放”。这是实现屏障时最经典的坑之一。
- 成本下界：任何屏障至少需要 2 个 RTT（信息必须”上去”再”下来”）；若每 $B$ 个操作同步一次、RTT 为 $100\ \mu s$，则单个进程的吞吐上限约为 $B / 200\ \mu s$。$B=1000$ 时上限约 $5\times10^{6}$ 次操作/秒/进程——看起来还行；但若 $B=10$（细粒度并行），上限只有 $5\times10^4$ 次/秒，比本地计算慢两个数量级。这就是”同步点密度决定并行程序上限“的量化表达，也是 Amdahl 定律在分布式并行程序上的体现：屏障把串行部分（同步）的成本乘以轮数。
正确性论证
- 安全性（无进程能提前越过屏障）：集中式：协调者只在
count = N（即收到全部 $N$ 个 ARRIVE）后才发送 RELEASE，而每个进程只有在收到本轮 RELEASE 后才解除阻塞；sense标志保证进程不会把上一轮的 RELEASE 当作本轮放行（每轮 release 携带唯一的sense值，进程用my_sense比对）。树形：对树高归纳。叶子只有收到父节点的 RELEASE 才放行；内部节点 $v$ 只有在arrived_v = k（即它的全部 $k$ 个孩子都已经 ARRIVE）之后才向上转发或（若为根）向下释放；对子树高度归纳可得：节点 $v$ 向上转发的那一刻，$v$ 子树中的全部进程都已经到达屏障；因此根节点向下释放时，整棵树的 $N$ 个进程都已到达。$\square$ - 活性（只要所有存活进程都到达，屏障最终完成）：每个到达的叶子向父节点发送 ARRIVE；父节点在收齐 $k$ 个后必然继续向上（不需要等待除自己孩子以外的任何东西），因此最终传播到根；根向下发布 RELEASE，逐层到达每个进程。假设：所有进程都到达（这是屏障的语义前提）且通道可靠、无进程故障。若有进程崩溃，则其父（或协调者）会永远等不到它的 ARRIVE ⇒ 屏障死锁——这说明屏障的活性完全依赖故障检测/成员管理（第 7 章）把死掉的进程从集合中剔除，并把屏障的”合格人数”动态更新。$\square$
- 可重复使用性（无残留状态污染下一轮）：每轮结束时所有计数器归零、
sense翻转一次，且所有进程观察到同一个sense序列 —— 因此下一轮的 ARRIVE 不会被误认为上一轮的残余。$\square$
复杂度对比
| 屏障实现 | 每节点消息数 | 总消息数 | 延迟 | 瓶颈 | 适用规模 |
|---|---|---|---|---|---|
| 集中式 | 2（1 发 + 1 收） | $2(N-1)$ | 2 RTT + 协调者排队 | 协调者处理 $O(N)$ 条消息 | 小规模（几十节点）、低延迟网络 |
| 树形（fan-in $k$） | $O(1)$（向上 1 + 向下 1） | $\approx 2N$（每内部节点 2 条） | $2\lceil\log_k N\rceil$ 跳 | 无单点（每节点最多 $k$ 个孩子） | 大规模；可结合”组合（combining）”把多个请求合并 |
| 基于多播的 all-to-all | 1 条多播 + $N$ 条接收 | $O(N)$（多播为 1 条） | 1 RTT + 多播延迟 | 依赖可靠多播（第 13 章） | 支持硬件多播的网络 |
| 基于 RDMA 原子操作 | $O(1)$ 个 RDMA 往返 | $O(N)$ 个原子操作 | ~1-2 μs/次往返 | 网卡原子单元 | 现代数据中心（FaRM/DrTM 风格） |
23.4 代码示例与分布式实现
三个程序都用纯标准库实现，可单机直接 python3 运行，随机种子固定、并发节奏由显式的”轮转令牌（Turn）”或屏障确定，因此每次运行的输出完全一致（真实 DSM 当然不可复现，这里刻意消除调度不确定性，好让数字可以对照理论）。统一使用同一套成本模型：一条消息记 $50\ \mu s$（约半个 $100\ \mu s$ 的 RTT，请求 + 应答），一个字节记 $0.08\ \mu s$（100 Mbps 有效带宽，即 80 ns/字节）。这两个常数把”消息数/字节数”折算成可比较的时间，也让大家看到控制消息的延迟与数据体积的带宽这两项谁在主导。
23.4.1 一个完整的 DSM 模拟器：IVY 写失效 + 释放一致性（实验 1 / 2 / 3）
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
DSM simulator: IVY-style page-level write-invalidate protocol
+ release consistency (acquire / release sync points)
Experiments:
1) Correctness: N processes * M increments under a DSM lock (release
consistency) -> final value must be N*M.
Without synchronization (non-atomic read-modify-write) -> lost updates.
2) False sharing: two processes update two variables packed on the SAME
page vs. padded onto DIFFERENT pages; count faults / messages / bytes.
3) Granularity: sweep page size, print faults / bytes / cost -> U curve.
Only the Python standard library is used. Deterministic (threads are
sequenced by an explicit round-robin token, so every run prints the same
numbers).
"""
import random
import threading
# ---------------------------------------------------------------- cost model
WORD_BYTES = 8 # one shared word = 8 bytes
PER_MSG_US = 50.0 # one message ~= one 100us RTT hop (us)
PER_BYTE_US = 0.08 # 100 Mbps effective bandwidth (80 ns / byte)
class Turn(object):
"""Deterministic round-robin token: node i may run only when it is i's
turn. It plays the role of a centralized lock server whose grant order
is fixed, so that every run of this simulation prints identical numbers
(real DSM runs are of course not reproducible like this)."""
def __init__(self, n):
self.n = n
self.turn = 0
self.cv = threading.Condition()
def wait_for(self, i):
with self.cv:
while self.turn != i:
self.cv.wait()
def done(self, i):
with self.cv:
self.turn = (i + 1) % self.n
self.cv.notify_all()
class Stats(object):
def __init__(self):
self.read_faults = 0
self.write_faults = 0
self.upgrades = 0
self.invalidations = 0
self.messages = 0
self.bytes = 0
def msg(self, nbytes):
self.messages += 1
self.bytes += nbytes
def cost_us(self):
return self.messages * PER_MSG_US + self.bytes * PER_BYTE_US
# ------------------------------------------------------------------- the DSM
class DSM(object):
"""Pages have exactly one owner. Two protocols are provided:
'invalidate' : eager IVY protocol (write fault -> invalidate every
other copy, migrate ownership to the writer)
'release' : lazy protocol. Writes stay local until release();
copies of other writers are dropped at acquire().
"""
def __init__(self, n_nodes, page_words, n_words, protocol="invalidate"):
self.n = n_nodes
self.g = page_words
self.n_pages = (n_words + page_words - 1) // page_words
self.protocol = protocol
self.lock = threading.RLock()
self.st = Stats()
self.events = []
self.copies = [dict() for _ in range(n_nodes)] # node -> page -> words
self.version = [0] * self.n_pages # for 'release'
self.cached_version = [dict() for _ in range(n_nodes)]
self.owner = [None] * self.n_pages
self.mode = ["-"] * self.n_pages # 'R' or 'W'
self.sharers = [set() for _ in range(self.n_pages)]
self.store = [None] * self.n_pages # authoritative data
self.dirty = [set() for _ in range(n_nodes)]
# -------------------------------------------------------------- helpers
def page_of(self, addr):
return addr // self.g
def data_bytes(self):
return self.g * WORD_BYTES
def _new_page(self):
return [0] * self.g
def _get_data(self, pg):
if self.store[pg] is None:
self.store[pg] = self._new_page()
return list(self.store[pg])
def _miss(self, node, pg):
"""Bring page pg into node's cache; returns nothing (fault counted)."""
if self.protocol == "release":
self.st.read_faults += 1
self.st.msg(32) # request
self.st.msg(self.data_bytes()) # data reply
self.copies[node][pg] = self._get_data(pg)
self.cached_version[node][pg] = self.version[pg]
self.sharers[pg].add(node)
self.events.append("n%d READ-FAULT page%d (pull, v%d)"
% (node, pg, self.version[pg]))
else:
owner = self.owner[pg]
if owner is None: # demand-zero page
self.st.read_faults += 1
self.st.msg(32)
self.st.msg(self.data_bytes())
self.copies[node][pg] = self._get_data(pg)
self.owner[pg] = node
self.mode[pg] = "R"
self.sharers[pg].add(node)
self.events.append("n%d READ-FAULT page%d (demand-zero, "
"becomes owner R)" % (node, pg))
return
self.st.read_faults += 1
self.st.msg(32) # request to owner
self.st.msg(self.data_bytes()) # data reply
if self.mode[pg] == "W": # (read scenario 6): degrade
self.mode[pg] = "R"
self.events.append("n%d: page%d degrade W->R at owner n%d"
% (node, pg, owner))
self.copies[node][pg] = list(self.copies[owner][pg])
self.sharers[pg].add(node)
self.events.append("n%d READ-FAULT page%d (copy from owner n%d, "
"mode R)" % (node, pg, owner))
def _invalidate_others(self, node, pg, data):
"""Send invalidations to every sharer except node, then hand the page
(content = `data`, snapshot taken BEFORE the invalidations go out)
and the ownership over to `node`."""
for s in sorted(self.sharers[pg]):
if s == node:
continue
self.st.invalidations += 1
self.st.msg(16) # invalidate
self.st.msg(16) # ack
self.copies[s].pop(pg, None)
self.cached_version[s].pop(pg, None)
self.events.append("n%d <- INVALIDATE page%d (from n%d)"
% (s, pg, node))
self.copies[node][pg] = list(data)
self.sharers[pg] = set([node])
self.owner[pg] = node
self.mode[pg] = "W"
# ------------------------------------------------------------ interface
def read(self, node, addr):
with self.lock:
pg = self.page_of(addr)
if self.protocol == "release":
if pg not in self.copies[node] or \
self.cached_version[node][pg] < self.version[pg]:
self.copies[node].pop(pg, None)
self._miss(node, pg)
return self.copies[node][pg][addr % self.g]
if pg not in self.copies[node]:
self._miss(node, pg)
return self.copies[node][pg][addr % self.g]
def write(self, node, addr, val):
with self.lock:
pg = self.page_of(addr)
if self.protocol == "release":
if pg not in self.copies[node] or \
self.cached_version[node][pg] < self.version[pg]:
self.copies[node].pop(pg, None)
self._miss(node, pg)
self.copies[node][pg][addr % self.g] = val
self.dirty[node].add(pg)
return
# ---------------- eager write-invalidate (IVY)
if pg in self.copies[node] and self.owner[pg] == node \
and self.mode[pg] == "W":
pass # local write, no messages
elif pg in self.copies[node]: # valid R copy -> upgrade
self.st.upgrades += 1
self.st.msg(32) # invalidate request (multicast)
self.events.append("n%d WRITE-UPGRADE page%d (R->W, owner %s)"
% (node, pg, self.owner[pg]))
self._invalidate_others(node, pg, self.copies[node][pg])
else: # write fault: fetch + invalidate
self.st.write_faults += 1
self.st.msg(32) # request (locate owner)
src = self.owner[pg]
if src is None:
self.store[pg] = self._get_data(pg)
self.copies[node][pg] = self._get_data(pg)
self.sharers[pg].add(node)
self.owner[pg] = node
self.mode[pg] = "W"
self.st.msg(self.data_bytes())
self.events.append("n%d WRITE-FAULT page%d (demand-zero, "
"owner W)" % (node, pg))
else:
self.st.msg(self.data_bytes()) # data transfer
snapshot = list(self.copies[src][pg])
self.events.append("n%d WRITE-FAULT page%d (fetch from "
"owner n%d, invalidate all, become "
"owner W)" % (node, pg, src))
self._invalidate_others(node, pg, snapshot)
self.copies[node][pg][addr % self.g] = val
self.dirty[node].add(pg)
# --------------------------------------------------- synchronization ops
def acquire(self, node):
"""Release consistency: at acquire, drop copies that are stale."""
with self.lock:
dropped = []
for pg in list(self.copies[node]):
if self.cached_version[node][pg] < self.version[pg]:
self.copies[node].pop(pg, None)
self.cached_version[node].pop(pg, None)
dropped.append(pg)
if dropped:
self.events.append("n%d ACQUIRE: drop stale pages %s"
% (node, sorted(dropped)))
return dropped
def release(self, node):
"""Release consistency (TreadMarks/LRC flavour): publish the dirty
pages and a new version, but do NOT push the data -- a peer that
wants it will pull it after its own acquire(). Publishing costs one
small 'write notice' message per release, not one page per write."""
with self.lock:
pushed = sorted(self.dirty[node])
if pushed:
self.st.msg(64) # write notices (piggybacked)
for pg in pushed:
self.store[pg] = list(self.copies[node][pg])
self.version[pg] += 1
self.events.append("n%d RELEASE: publish page%d (v%d) -- "
"no data sent" % (node, pg, self.version[pg]))
self.dirty[node] = set()
return pushed
# --------------------------------------------------------------- experiment 1
def experiment_correctness(n=4, m=20, verbose=True):
print("=" * 72)
print("EXPERIMENT 1: correctness under release consistency "
"(N=%d processes, M=%d increments each)" % (n, m))
print("=" * 72)
# ---- (a) safe: non-atomic RMW done while holding a DSM lock ----------
dsm = DSM(n, page_words=8, n_words=64, protocol="release")
counter_addr = 0
lock = Turn(n) # the DSM lock: one holder at a time
def worker_safe(i):
for _ in range(m):
lock.wait_for(i) # --- critical section ---
dsm.acquire(i) # sync point: pull updates
v = dsm.read(i, counter_addr) # read (atomic w.r.t. lock)
dsm.write(i, counter_addr, v + 1) # write
dsm.release(i) # sync point: push updates
lock.done(i) # --- end critical section ---
threads = [threading.Thread(target=worker_safe, args=(i,)) for i in range(n)]
for t in threads:
t.start()
for t in threads:
t.join()
final_safe = dsm.read(0, counter_addr)
print(" safe (lock + acquire/release): counter = %-4d expected = %d %s"
% (final_safe, n * m, "OK" if final_safe == n * m else "WRONG"))
st_safe = (dsm.st.read_faults, dsm.st.write_faults, dsm.st.messages,
dsm.st.bytes)
# ---- (b) unsafe: same RMW, but no lock -------------------------------
dsm2 = DSM(n, page_words=8, n_words=64, protocol="release")
bar = threading.Barrier(n) # force a fixed interleaving
def worker_unsafe(i):
for _ in range(m):
dsm2.acquire(i)
v = dsm2.read(i, counter_addr) # (1) every one reads ...
bar.wait() # ... the SAME old value
dsm2.write(i, counter_addr, v + 1) # (2) ... then writes it back
dsm2.release(i)
bar.wait()
threads = [threading.Thread(target=worker_unsafe, args=(i,)) for i in range(n)]
for t in threads:
t.start()
for t in threads:
t.join()
final_unsafe = dsm2.read(0, counter_addr)
print(" unsafe (no lock, barrier-interleaved RMW): counter = %-4d "
"expected = %d -> %d updates LOST"
% (final_unsafe, n * m, n * m - final_unsafe))
print(" -> DSM keeps pages coherent, but it does NOT make a non-atomic")
print(" read-modify-write atomic: data races stay the programmer's job.")
if verbose:
print(" stats (safe run): read_faults=%d write_faults=%d msgs=%d "
"bytes=%d cost=%.1f ms"
% (st_safe + (dsm.st.cost_us() / 1000.0,)))
print(" last events of the safe run:")
for e in [x for x in dsm.events if "ACQUIRE" in x or "RELEASE" in x][-4:]:
print(" " + e)
return final_safe, final_unsafe
# --------------------------------------------------------------- experiment 2
def run_false_sharing(packed, n=2, rounds=200, page_words=8):
"""Two processes, each owns ONE counter variable.
packed=True -> the two counters live on the SAME page (offset 0 and 1)
packed=False -> each counter starts its own page (padded layout)
"""
n_words = 4096
dsm = DSM(n, page_words=page_words, n_words=n_words, protocol="invalidate")
if packed:
addr = [0, 1]
else:
addr = [0, page_words]
turn = Turn(n)
def worker(i):
for _ in range(rounds):
turn.wait_for(i) # worst case: n0 updates, then n1 updates
v = dsm.read(i, addr[i])
dsm.write(i, addr[i], v + 1)
turn.done(i)
threads = [threading.Thread(target=worker, args=(i,)) for i in range(n)]
for t in threads:
t.start()
for t in threads:
t.join()
return dsm
def experiment_false_sharing(rounds=200):
print()
print("=" * 72)
print("EXPERIMENT 2: false sharing (2 processes, %d writes each, "
"page = 8 words = 64 B)" % rounds)
print("=" * 72)
packed = run_false_sharing(True, rounds=rounds)
padded = run_false_sharing(False, rounds=rounds)
rows = [("packed (both counters on ONE page)", packed),
("padded (one counter per page)", padded)]
print(" %-38s %8s %8s %7s %7s %10s %10s"
% ("layout", "r-fault", "w-fault", "upgr", "inval", "messages",
"bytes"))
for name, dsm in rows:
st = dsm.st
print(" %-38s %8d %8d %7d %7d %10d %10d"
% (name, st.read_faults, st.write_faults, st.upgrades,
st.invalidations, st.messages, st.bytes))
cp, cd = packed.st, padded.st
pf = cp.read_faults + cp.write_faults + cp.upgrades
df = cd.read_faults + cd.write_faults + cd.upgrades
print(" %-38s %8s %8s %7s %7s %10s %10s"
% ("amplification (packed / padded)",
"%.0fx" % (cp.read_faults / max(1, cd.read_faults)),
"%.0fx" % (pf / max(1, df)),
"%.0fx" % (cp.upgrades / max(1, cd.upgrades)),
"%.0fx" % (cp.invalidations / max(1, cd.invalidations)),
"%.0fx" % (cp.messages / max(1, cd.messages)),
"%.0fx" % (cp.bytes / max(1, cd.bytes))))
print(" simulated cost: packed %.1f ms vs padded %.1f ms (%.0fx)"
% (cp.cost_us() / 1000.0, cd.cost_us() / 1000.0,
cp.cost_us() / max(1e-9, cd.cost_us())))
print(" sample of the event log (packed):")
for e in packed.events[:6]:
print(" " + e)
# --------------------------------------------------------------- experiment 3
def experiment_granularity(rounds=200, n=4, ws_words=4096):
print()
print("=" * 72)
print("EXPERIMENT 3: granularity sweep (N=%d, %d rounds, %d-word "
"read-only workspace)" % (n, rounds, ws_words))
print("=" * 72)
def run(page_words):
dsm = DSM(n, page_words=page_words, n_words=ws_words + n,
protocol="invalidate")
ws_base = n # workspace starts after the counters
chunk = ws_words // n
turn = Turn(n)
def worker(i):
base = ws_base + i * chunk
acc = 0
for r in range(rounds):
turn.wait_for(i) # worst-case rhythm: the N
v = dsm.read(i, i) # hot counters are touched in
dsm.write(i, i, v + 1) # a fixed order every round
turn.done(i)
# sliding sequential scan of my own private slice (32 words
# per round, so the whole slice is walked every chunk/32 rounds)
for k in range(32):
acc += dsm.read(i, base + (r * 32 + k) % chunk)
assert acc >= 0
threads = [threading.Thread(target=worker, args=(i,)) for i in range(n)]
for t in threads:
t.start()
for t in threads:
t.join()
return dsm
print(" %6s %10s %10s %12s %12s %12s"
% ("page", "faults", "invalids", "messages", "bytes", "cost(ms)"))
best = None
for g in (1, 2, 4, 8, 16, 32, 64, 128, 256, 512):
dsm = run(g)
st = dsm.st
faults = st.read_faults + st.write_faults + st.upgrades
cost = st.cost_us() / 1000.0
print(" %6d %10d %10d %12d %12d %12.1f"
% (g, faults, st.invalidations, st.messages, st.bytes, cost))
if best is None or cost < best[1]:
best = (g, cost)
print(" minimum simulated cost at page = %d words (%d bytes)"
% (best[0], best[0] * WORD_BYTES))
print(" small pages -> too many faults (protocol latency dominates);")
print(" large pages -> false sharing + huge transfers (bandwidth, and")
print(" every fault stalls a whole RTT) => an interior optimum exists.")
# ------------------------------------------------------------------ experiment
def experiment_event_trace():
print()
print("=" * 72)
print("EVENT TRACE: the IVY protocol on one shared page (3 processes)")
print("=" * 72)
dsm = DSM(3, page_words=4, n_words=16, protocol="invalidate")
dsm.read(0, 0) # p0 read fault -> owner, R
dsm.read(1, 1) # p1 read fault -> copy from owner, R
dsm.write(0, 0, 42) # p0 write upgrade -> invalidate p1, owner W
dsm.read(2, 2) # p2 read fault -> owner W degrades to R
dsm.write(1, 1, 7) # p1 write fault -> fetch + invalidate all
for e in dsm.events:
print(" " + e)
st = dsm.st
print(" totals: r-fault=%d w-fault=%d upgrades=%d invalidations=%d "
"messages=%d bytes=%d"
% (st.read_faults, st.write_faults, st.upgrades,
st.invalidations, st.messages, st.bytes))
if __name__ == "__main__":
random.seed(425)
experiment_event_trace()
experiment_correctness(n=4, m=20)
experiment_false_sharing(rounds=200)
experiment_granularity()
运行输出（完整输出，可复现）：
========================================================================
EVENT TRACE: the IVY protocol on one shared page (3 processes)
========================================================================
n0 READ-FAULT page0 (demand-zero, becomes owner R)
n1 READ-FAULT page0 (copy from owner n0, mode R)
n0 WRITE-UPGRADE page0 (R->W, owner 0)
n1 <- INVALIDATE page0 (from n0)
n2: page0 degrade W->R at owner n0
n2 READ-FAULT page0 (copy from owner n0, mode R)
n1 WRITE-FAULT page0 (fetch from owner n0, invalidate all, become owner W)
n0 <- INVALIDATE page0 (from n1)
n2 <- INVALIDATE page0 (from n1)
totals: r-fault=3 w-fault=1 upgrades=1 invalidations=3 messages=15 bytes=384
========================================================================
EXPERIMENT 1: correctness under release consistency (N=4 processes, M=20 increments each)
========================================================================
safe (lock + acquire/release): counter = 80 expected = 80 OK
unsafe (no lock, barrier-interleaved RMW): counter = 20 expected = 80 -> 60 updates LOST
-> DSM keeps pages coherent, but it does NOT make a non-atomic
read-modify-write atomic: data races stay the programmer's job.
stats (safe run): read_faults=81 write_faults=0 msgs=242 bytes=12896 cost=13.1 ms
last events of the safe run:
n2 ACQUIRE: drop stale pages [0]
n2 RELEASE: publish page0 (v79) -- no data sent
n3 ACQUIRE: drop stale pages [0]
n3 RELEASE: publish page0 (v80) -- no data sent
========================================================================
EXPERIMENT 2: false sharing (2 processes, 200 writes each, page = 8 words = 64 B)
========================================================================
layout r-fault w-fault upgr inval messages bytes
packed (both counters on ONE page) 400 0 400 399 1998 63968
padded (one counter per page) 2 0 2 0 6 256
amplification (packed / padded) 200x 200x 200x 399x 333x 250x
simulated cost: packed 105.0 ms vs padded 0.3 ms (328x)
sample of the event log (packed):
n0 READ-FAULT page0 (demand-zero, becomes owner R)
n0 WRITE-UPGRADE page0 (R->W, owner 0)
n1: page0 degrade W->R at owner n0
n1 READ-FAULT page0 (copy from owner n0, mode R)
n1 WRITE-UPGRADE page0 (R->W, owner 0)
n0 <- INVALIDATE page0 (from n1)
========================================================================
EXPERIMENT 3: granularity sweep (N=4, 200 rounds, 4096-word read-only workspace)
========================================================================
page faults invalids messages bytes cost(ms)
1 4104 0 8204 164128 423.3
2 3648 798 8092 187840 419.6
4 2624 799 6046 167904 315.7
8 2115 799 5028 177408 265.6
16 1859 799 4516 220608 243.4
32 1731 799 4260 319296 238.5
64 1667 799 4132 522816 248.4
128 1635 799 4068 932928 278.0
256 1619 799 4036 1754688 342.2
512 1611 799 4020 3398976 472.9
minimum simulated cost at page = 32 words (256 bytes)
small pages -> too many faults (protocol latency dominates);
large pages -> false sharing + huge transfers (bandwidth, and
every fault stalls a whole RTT) => an interior optimum exists.
【代码做什么？】
DSM类实现页级共享内存：共享地址空间被切成定长页，每页记录owner（所有者）、mode（R/W）、sharers（持有副本的节点集合）。节点本地的”页存储”就是copies[node]这个dict（页号 → 该页的字列表），即本地内存里的页缓存。read()/write()是访存路径：先在本地copies[node]里找页；找到且权限足够 → 命中（0 条消息）；否则调用_miss()/ 写升级路径，按 IVY 协议与 owner 交互，并把每次故障、失效、所有者迁移写进events日志（实验 4「EVENT TRACE」把这条路径完整打印出来：3 次读缺失、1 次写缺失、1 次写升级、3 次失效）。- 两种一致性协议：
protocol="invalidate"实现 IVY 的急切写失效 + 所有权迁移；protocol="release"实现释放一致性——write()只改本地副本并标记dirty，release()才把页发布出去（只发一条小的”写在”消息，不推数据），acquire()检查cached_version < version并把过期的本地副本丢掉，下次访问时再从store拉取（这就是 23.3.3 的懒惰拉取）。 - 实验 1（正确性）：4 个线程各对同一个共享计数器累加 20 次。安全版用 DSM 锁（
Turn令牌）+acquire/release划分临界区 → 结果 80 = 4×20 ✓；不安全版用threading.Barrier强制”所有人先读、再一起写回”的经典竞态时序 → 结果 20，丢失 60 次更新。 - 实验 2（假共享量化）：2 个线程各自反复更新自己的计数器，两种布局：（a）两个计数器放在同一页（偏移 0 与 1）；（b）每个计数器独占一页（
padding）。统计读缺失、写升级、失效广播、消息数、字节数与模拟耗时，并打印放大倍数。 - 实验 3（粒度影响）：把页大小从 1 个字扫描到 512 个字（8 B → 4 KB），每次跑同样的负载（每轮写自己的热点计数器 + 滑动扫描自己那 1024 字的工作区），打印故障数、失效数、消息数、字节数与成本，寻找最小值。
- 全程统计
messages/bytes，最后按成本模型折算成毫秒。
【分布式机制透视】
- 消息通道：
stats.msg(n)就是”发一条网络消息”的桩函数——每一次页请求、每一次失效、每一个 ACK 都会调用它。代码里没有真实的 socket，但每一条被计数的消息在真实 DSM 里都对应一次网络往返，因此计数可以定量比较不同协议的代价。 - 页错误与内核陷入：
_miss()对应 trap handler 里的”联系其他进程取页”；copy[p]对应本地页缓存；owner[p]/sharers[p]对应目录（directory） 中每页的元数据（真实系统里可能由一个”管理者（manager）”节点维护，也可能像 IVY 那样靠多播询问）。 - 并发与时序：
threading.RLock包住 DSM 的全部状态，模拟”内核串行地处理页错误”；Turn令牌与threading.Barrier用来构造最坏（也最典型）的访问交错，例如实验 2 中”n0 写完 n1 马上写”的交替节奏——这正是讲义说的 flip-flopping 场景。 - 多写者前提：
release协议里每个节点写的是自己那一个字节；acquire/release保证跨节点可见性。代码没有做字节级合并（那是 23.4.2 的内容），因此它只支持”不重叠写”。 - 对应关系表：
copies↔ 本地内存页；copy[p]的 R/W ↔ 讲义中的页状态 R/W；owner[p]↔ 讲义中的 owner（持有最新版本的进程）；_invalidate_others↔ 讲义的 “Ask other processes to invalidate their copies of page. Use multicast.”；acquire/release↔ 释放一致性的同步点。
【与理论的对应】
- 实验 1 的安全版验证了算法 23.3.3 的”acquire 之后必然看到之前的写”（事件日志里能看到
n3 ACQUIRE: drop stale pages [0]，即 acquire 主动把过期副本作废），最终值严格等于 $N\times M$；不安全版验证了本章反复强调的结论：DSM 保证的是”页是一致的”，不是”你的读-改-写是原子的”——不满足”无数据竞争”假设时，任何一致性模型都救不了程序。 - 实验 2 是算法 23.3.1 正确性论证中不变式 I（写前必须失效所有其他副本）的代价演示：紧凑布局下每次写都触发”升级 + 失效广播”，实测 400 次写升级、399 次失效、1998 条消息、63,968 字节、105.0 ms；填充布局下同样 400 次写，只有 2 次读缺失、6 条消息、256 字节、0.3 ms。消息放大 333 倍、时间放大 328 倍——这正是讲义 “Can happen when unrelated variables fall on same page; called false sharing.” 的定量版本，也是”粒度要能捕捉一个进程的局部性“这条讲义结论的证据。
- 实验 3 验证 23.2.4 的 $g^*=\sqrt{DPB/(Sw)}$ 推导：页 = 1 字时故障数 4104（协议延迟主导），页 = 512 字时字节数 3.4 MB（假共享与带宽主导），最小成本出现在 256 字节（32 个字），呈清晰的 U 形。把工作区从 4096 字提高到 65536 字（顺序局部性更强）再跑，最优粒度右移到 512 字节（64 个字）——说明最优点随负载的”顺序局部性 / 热点争用”比例移动，而真实系统最终被 MMU 的 4 KB 页”钉”在了一个大致合理的点上。
23.4.2 TreadMarks 的孪生页与差分机制演示
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
TreadMarks-style multiple-writer support: twin pages + byte-level diffs.
A "twin" is a snapshot of a page taken the first time a node writes it
after the last synchronization point. At the next synchronization point the
node computes diff = current XOR twin (a byte-wise delta), compresses it to
(offset, bytes) runs, and ships only the non-zero runs instead of the whole
page. The receiver applies the delta with XOR.
Scenarios
A) two nodes write DIFFERENT bytes of the same page: whole-page forwarding
loses one of the updates, diff merging keeps both (and is commutative)
B) two nodes write the SAME byte (a real data race): the diffs conflict --
XOR merging produces a value nobody wrote, so TreadMarks instead detects
the overlapping byte while applying the diff and delivers SIGBUS.
C) a timeline of one node's twin, showing exactly what travels the wire.
Only the standard library is used; the output is fully deterministic.
"""
import random
import sys
PAGE_BYTES = 16
# ------------------------------------------------------------ diff primitives
def make_diff(cur, twin):
"""raw byte-wise XOR delta = exactly what the twin is for."""
return bytes(a ^ b for a, b in zip(cur, twin))
def compress(diff):
"""run-length compress: [(offset, bytes_of_run), ...] for non-zero runs."""
runs, i, n = [], 0, len(diff)
while i < n:
if diff[i] == 0:
i += 1
continue
j = i
while j < n and diff[j] != 0:
j += 1
runs.append((i, diff[i:j]))
i = j
return runs
def apply_compressed(cur, runs):
for off, data in runs:
for k, b in enumerate(data):
cur[off + k] ^= b
def run_bytes(runs):
return sum(len(d) + 2 for _, d in runs) # + 2 bytes for the offset
def conflict_bytes(local_runs, incoming_runs):
"""offsets written both locally (not yet propagated) and by the incoming
diff -- TreadMarks signals SIGBUS for exactly these bytes."""
def cover(runs):
s = set()
for off, data in runs:
s.update(range(off, off + len(data)))
return s
return sorted(cover(local_runs) & cover(incoming_runs))
def show(runs):
"""readable form of a compressed diff: [(offset, 'hexbytes'), ...]"""
return "[" + ", ".join("(%d, '%s')" % (o, d.hex()) for o, d in runs) + "]"
def fmt(page, limit=PAGE_BYTES):
return " ".join("%02x" % b for b in page[:limit])
class Node(object):
"""One DSM participant."""
def __init__(self, name, page):
self.name = name
self.page = bytearray(page)
self.twin = None
def write(self, offset, value):
if self.twin is None: # first write since the last sync
self.twin = bytearray(self.page) # snapshot BEFORE modifying
self.page[offset] = value
def compute_diff(self): # called at release()
assert self.twin is not None, "no write since the last sync point"
runs = compress(make_diff(self.page, self.twin))
self.twin = None
return runs
def apply(self, runs, src):
apply_compressed(self.page, runs)
def header(title):
print()
print("=" * 74)
print(title)
print("=" * 74)
# ------------------------------------------------------------------ scenario C
def scenario_twin_timeline():
header("SCENARIO C: what a twin is (one page at one node, one epoch)")
n = Node("n0", [0x00] * PAGE_BYTES)
print(" t0 after acquire() : page = %s twin = None" % fmt(n.page))
n.write(0, 0xAA)
print(" t1 first write : twin := snapshot(%s)" % fmt(n.twin))
n.write(1, 0xBB)
print(" t2 second write : page = %s twin = %s (pre-sync image)"
% (fmt(n.page), fmt(n.twin)))
runs = n.compute_diff()
print(" t3 release() : runs = %s -> %d bytes on the wire "
"(whole page would be %d B)"
% (show(runs), run_bytes(runs), PAGE_BYTES))
n.write(1, 0xCC)
print(" t4 write again : twin := snapshot(%s) (a NEW twin)"
% fmt(n.twin))
runs2 = n.compute_diff()
print(" t5 release() : runs = %s (only byte 1 changed in epoch 2)"
% show(runs2))
print(" => every diff carries exactly the bytes changed in that epoch, so")
print(" two nodes writing different bytes of one page never fight.")
# ------------------------------------------------------------------ scenario A
def scenario_disjoint_writes():
header("SCENARIO A: two nodes write DIFFERENT bytes of the same page")
base = bytearray([0xA0] * PAGE_BYTES)
n0, n1 = Node("n0", base), Node("n1", base)
print(" base page : %s" % fmt(base))
n0.write(2, 0x11) # n0 owns byte 2
n1.write(5, 0x22) # n1 owns byte 5 (a different byte)
print(" n0 page : %s twin = base" % fmt(n0.page))
print(" n1 page : %s twin = base" % fmt(n1.page))
print("\n (1) whole-page forwarding (no twin, no diff):")
final1 = bytearray(n1.page) # n0's page arrives first, n1's overwrites it
print(" arrival n0 then n1 -> %s" % fmt(final1))
print(" byte 2 = %02x : n0's update is LOST" % final1[2])
final2 = bytearray(n0.page) # reversed arrival order
print(" arrival n1 then n0 -> %s" % fmt(final2))
print(" byte 5 = %02x : n1's update is LOST" % final2[5])
print(" => with whole pages the last writer wins and the other")
print(" update disappears. This is the false-sharing killer.")
print("\n (2) twin + diff (what TreadMarks does):")
r0, r1 = n0.compute_diff(), n1.compute_diff()
print(" diff(n0) = %s -> %d bytes" % (show(r0), run_bytes(r0)))
print(" diff(n1) = %s -> %d bytes" % (show(r1), run_bytes(r1)))
a = Node("reader", base); a.apply(r0, "n0"); a.apply(r1, "n1")
b = Node("reader", base); b.apply(r1, "n1"); b.apply(r0, "n0")
exp = bytearray(base); exp[2], exp[5] = 0x11, 0x22
print(" merge order n0,n1 -> %s" % fmt(a.page))
print(" merge order n1,n0 -> %s" % fmt(b.page))
print(" expected -> %s" % fmt(exp))
assert a.page == b.page == exp
print(" => both updates survive and the merge is commutative:")
print(" disjoint bytes mean the XOR deltas touch disjoint bits,")
print(" so applying them in any order gives the same page.")
print(" wire cost: %d bytes of diffs vs %d bytes for two whole pages"
% (run_bytes(r0) + run_bytes(r1), 2 * PAGE_BYTES))
# ------------------------------------------------------------------ scenario B
def scenario_conflicting_writes():
header("SCENARIO B: two nodes write the SAME byte (a real data race)")
base = bytearray([0xA0] * PAGE_BYTES)
n0, n1 = Node("n0", base), Node("n1", base)
n0.write(2, 0x11)
n1.write(2, 0x22)
r0, r1 = n0.compute_diff(), n1.compute_diff()
print(" n0 writes 0x11 at byte 2, n1 writes 0x22 at byte 2, concurrently")
print(" diff(n0) = %s" % show(r0))
print(" diff(n1) = %s" % show(r1))
reader = Node("reader", base)
reader.apply(r0, "n0")
reader.apply(r1, "n1")
print(" naive XOR merge -> %s" % fmt(reader.page))
print(" byte 2 = %02x : neither 0x11 (n0) nor 0x22 (n1) -- the merge"
% reader.page[2])
print(" of two writes to the SAME byte is garbage, not a resolution.")
bad = conflict_bytes(r0, r1)
print(" TreadMarks instead checks the page's guarded bytes before")
print(" applying a diff: overlap = %s -> raise SIGBUS" % bad)
if bad:
print(" (the application dies loudly instead of silently")
print(" computing a value that no process ever wrote)")
print()
print(" CONCLUSION: multiple-writer + diff merging removes FALSE sharing")
print(" (different bytes inside one page). It does NOT make concurrent")
print(" accesses to the SAME byte safe -- data races are still the")
print(" programmer's job (locks, barriers, atomics).")
if __name__ == "__main__":
random.seed(425)
scenario_twin_timeline()
scenario_disjoint_writes()
scenario_conflicting_writes()
print()
print("all assertions passed (%s)" % sys.version.split()[0])
运行输出：
==========================================================================
SCENARIO C: what a twin is (one page at one node, one epoch)
==========================================================================
t0 after acquire() : page = 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 twin = None
t1 first write : twin := snapshot(00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00)
t2 second write : page = aa bb 00 00 00 00 00 00 00 00 00 00 00 00 00 00 twin = 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 (pre-sync image)
t3 release() : runs = [(0, 'aabb')] -> 4 bytes on the wire (whole page would be 16 B)
t4 write again : twin := snapshot(aa bb 00 00 00 00 00 00 00 00 00 00 00 00 00 00) (a NEW twin)
t5 release() : runs = [(1, '77')] (only byte 1 changed in epoch 2)
=> every diff carries exactly the bytes changed in that epoch, so
two nodes writing different bytes of one page never fight.
==========================================================================
SCENARIO A: two nodes write DIFFERENT bytes of the same page
==========================================================================
base page : a0 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0
n0 page : a0 a0 11 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0 twin = base
n1 page : a0 a0 a0 a0 a0 22 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0 twin = base
(1) whole-page forwarding (no twin, no diff):
arrival n0 then n1 -> a0 a0 a0 a0 a0 22 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0
byte 2 = a0 : n0's update is LOST
arrival n1 then n0 -> a0 a0 11 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0
byte 5 = a0 : n1's update is LOST
=> with whole pages the last writer wins and the other
update disappears. This is the false-sharing killer.
(2) twin + diff (what TreadMarks does):
diff(n0) = [(2, 'b1')] -> 3 bytes
diff(n1) = [(5, '82')] -> 3 bytes
merge order n0,n1 -> a0 a0 11 a0 a0 22 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0
merge order n1,n0 -> a0 a0 11 a0 a0 22 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0
expected -> a0 a0 11 a0 a0 22 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0
=> both updates survive and the merge is commutative:
disjoint bytes mean the XOR deltas touch disjoint bits,
so applying them in any order gives the same page.
wire cost: 6 bytes of diffs vs 32 bytes for two whole pages
==========================================================================
SCENARIO B: two nodes write the SAME byte (a real data race)
==========================================================================
n0 writes 0x11 at byte 2, n1 writes 0x22 at byte 2, concurrently
diff(n0) = [(2, 'b1')]
diff(n1) = [(2, '82')]
naive XOR merge -> a0 a0 93 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0 a0
byte 2 = 93 : neither 0x11 (n0) nor 0x22 (n1) -- the merge
of two writes to the SAME byte is garbage, not a resolution.
TreadMarks instead checks the page's guarded bytes before
applying a diff: overlap = [2] -> raise SIGBUS
(the application dies loudly instead of silently
computing a value that no process ever wrote)
CONCLUSION: multiple-writer + diff merging removes FALSE sharing
(different bytes inside one page). It does NOT make concurrent
accesses to the SAME byte safe -- data races are still the
programmer's job (locks, barriers, atomics).
all assertions passed (3.9.21)
【代码做什么？】
Node表示一个 DSM 参与者，持有页内容page与孪生页twin；write(off, val)在本区间第一次写时先twin = 修改前的整页快照，之后才落笔（对应 TreadMarks 用mprotect保护页、第一次写触发信号后创建孪生页的做法）。compute_diff()在同步点算出copy XOR twin（逐字节异或差分），再用compress()压成[(offset, bytes), ...]游程——只有非零游程会过网，twin随即被消费掉（下一次写会重新快照）。- 场景 C 打印孪生页的时间线：第一次写前快照、写两个字节后 diff 只有
[(0, 'aabb')]（4 字节），新一轮再写时只有[(1, '77')]（3 字节）。 - 场景 A（不同字节）：n0 写偏移 2、n1 写偏移 5。（1）先演示”整页转发”：无论谁后到，后到的整页都会覆盖先到的，必然丢失一个更新；（2）再用两份 diff 合并，分别以 n0→n1 与 n1→n0 两种顺序应用，结果完全相同且两个写都保留，并用断言验证与期望页一致。
- 场景 B（同一字节）：两个节点并发写偏移 2。先展示”朴素异或合并”得到的
93既不是11也不是22；再用conflict_bytes()展示 TreadMarks 的做法——应用 diff 前检查被写字节是否与本节点未传播的写重叠，重叠即报 SIGBUS。
【分布式机制透视】
- 孪生页 = 用内存换带宽：每个”本区间被写过的页”多占一页内存，换来”只传改动字节”。这是一个非常典型的分布式系统权衡：用本地空间换网络流量。
- 多个写者的合并：代码把”合并”实现为逐字节异或，并且刻意演示了两种应用顺序结果相同——这不是巧合，而是”写不同字节 ⇒ 每个字节只有一个写者 ⇒ 各字节独立的异或”这一数学性质的直接体现。
- 保护字节（guarded bytes）与冲突检测：
conflict_bytes()对应 TreadMarks 的 guard 机制。真实系统在检测到重叠时让应用收到 SIGBUS——宁可崩溃也不要静默算错，这是分布式系统里非常重要的工程哲学（对比第 9 章 Cassandra”最后写入者胜”的静默收敛）。 - 与一致性模型的关系：diff 只在”同步点之间发生了并发写”时才有意义，而”同步点之间”正是释放一致性/LRC 定义的区间——所以 diff 机制与 LRC 是一体两面：LRC 决定”什么时候传播”，diff 决定”传播多少字节”。
【与理论的对应】
- 场景 A 的合并结果直接验证了算法 23.3.4 的引理 1（每个被写字节最终等于唯一写它的写者的值）与引理 2（与合并顺序无关）；两种顺序输出完全一致即为引理 2 的实验证明。
- 场景 A(1) 的”整页转发丢更新”验证了引理 3：整页覆盖等价于”最后一个写者胜”，这正是假共享在多写者场景下的灾难形态（也是 23.4.1 实验 2 那句”399 次失效”背后的故事）。
- 场景 B 验证了前提 P（字节不重叠）不可省：重叠时异或合并产生”谁也没写过的值”，TreadMarks 用 SIGBUS 把它变成显式失败。因此本章的结论是：DSM 的 diff 机制解决假共享（不同字节），但绝不解决数据竞争（同一字节）。
23.4.3 一致性模型强弱 vs 通信开销：同一个程序，三种协议
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Consistency model -> cost: three DSM protocols on ONE workload.
eager : sequential-consistency-style eager coherence. Every write
invalidates every other copy immediately; every miss fetches the
page from the owner. (What you must do if the application is
allowed to observe any interleaving.)
rc : release consistency. Writes stay local and are PUSHED to every
other copy holder at release(); acquire() needs no traffic.
lrc : lazy release consistency (TreadMarks). release() only publishes
write notices (which pages changed); the acquirer PULLS the pages
it actually needs, on demand, after acquire().
Workload (one "period" per synchronization point, 4 nodes):
20 x { write my own word in the shared output page ; read my neighbour's
word in the same page } <- classic producer/consumer + false
sharing pressure
then ONE barrier (release + acquire)
The program is race-free *between* synchronization points, so all three
protocols are correct for it -- only the cost differs.
Cost model: 50 us per message (~half a 100 us RTT), 0.08 us per byte
(100 Mbps effective bandwidth, i.e. 80 ns/byte).
"""
import random
import threading
WORD = 8
PER_MSG_US = 50.0
PER_BYTE_US = 0.08
class Turn(object):
"""Deterministic round-robin token: makes the whole run reproducible
(every process touches the shared page in a fixed order every round)."""
def __init__(self, n):
self.n = n
self.turn = 0
self.cv = threading.Condition()
def wait_for(self, i):
with self.cv:
while self.turn != i:
self.cv.wait()
def done(self, i):
with self.cv:
self.turn = (i + 1) % self.n
self.cv.notify_all()
class Sim(object):
def __init__(self, n, page_words, n_words, protocol):
self.n, self.g, self.protocol = n, page_words, protocol
self.n_pages = (n_words + page_words - 1) // page_words
self.mem = [None] * self.n_pages # authoritative page content
self.version = [0] * self.n_pages
self.cache = [dict() for _ in range(n)] # node -> page -> bytearray
self.valid = [dict() for _ in range(n)]
self.cver = [dict() for _ in range(n)]
self.holders = [set() for _ in range(self.n_pages)]
self.dirty = [dict() for _ in range(n)] # node -> page -> {offsets}
self.lock = threading.RLock()
self.messages = 0
self.bytes = 0
self.faults = 0
# ------------------------------------------------------------- plumbing
def _msg(self, nbytes=32):
self.messages += 1
self.bytes += nbytes
def _page_bytes(self):
return self.g * WORD
def _zero(self, pg):
if self.mem[pg] is None:
self.mem[pg] = bytearray(self._page_bytes())
return self.mem[pg]
def _fetch(self, node, pg):
"""one DSM page fault: request + data reply."""
self.faults += 1
self._msg(32)
self._msg(self._page_bytes())
self.cache[node][pg] = bytearray(self._zero(pg))
self.valid[node][pg] = True
self.cver[node][pg] = self.version[pg]
self.holders[pg].add(node)
def _invalidate(self, node, pg):
for h in sorted(self.holders[pg]):
if h == node:
continue
self._msg(16) # invalidate
self._msg(16) # ack
self.valid[h][pg] = False
# ---------------------------------------------------------- operations
def read(self, node, addr):
with self.lock:
pg, off = addr // self.g, addr % self.g
if not self.valid[node].get(pg, False):
self._fetch(node, pg)
return self.cache[node][pg][off]
def write(self, node, addr, value):
with self.lock:
pg, off = addr // self.g, addr % self.g
if not self.valid[node].get(pg, False):
self._fetch(node, pg)
if self.protocol == "eager":
self._invalidate(node, pg) # everybody else loses the page
self._msg(32) # ownership/push of the new value
self._zero(pg)[off] = value
self.cache[node][pg] = bytearray(self.mem[pg])
self.version[pg] += 1
else:
self.cache[node][pg][off] = value
self.dirty[node].setdefault(pg, set()).add(off)
def acquire(self, node):
with self.lock:
if self.protocol == "lrc":
self._msg(32) # acquire request -> write notices
self._msg(64) # reply: list of changed pages
for pg in range(self.n_pages):
if self.cver[node].get(pg, -1) < self.version[pg]:
self.valid[node][pg] = False
# 'eager' and 'rc' keep their copies valid across the barrier
def release(self, node):
with self.lock:
dirty = self.dirty[node]
if self.protocol == "rc":
# only the WORDS this node changed travel (a tiny diff), and
# they are pushed to every holder of the page
for pg in sorted(dirty):
offs = sorted(dirty[pg])
self._zero(pg)
for off in offs:
self.mem[pg][off] = self.cache[node][pg][off]
self.version[pg] += 1
for other in sorted(self.holders[pg]):
if other == node:
continue
self._msg(32) # update notification
self._msg(len(offs)) # diff payload
for off in offs:
self.cache[other][pg][off] = self.mem[pg][off]
self.valid[other][pg] = True
self.cver[other][pg] = self.version[pg]
elif self.protocol == "lrc":
if dirty:
self._msg(64) # piggybacked write notices
for pg in sorted(dirty):
self._zero(pg)
for off in sorted(dirty[pg]):
self.mem[pg][off] = self.cache[node][pg][off]
self.version[pg] += 1
self.dirty[node] = dict()
def cost_ms(self):
return (self.messages * PER_MSG_US + self.bytes * PER_BYTE_US) / 1000.0
# ------------------------------------------------------------------- workload
def run(protocol, n=4, page_words=8, periods=20, iters=20, verbose=False):
n_words = 256
sim = Sim(n, page_words, n_words, protocol)
bar = threading.Barrier(n)
turn = Turn(n)
def worker(i):
for _ in range(periods):
for k in range(iters):
turn.wait_for(i) # fixed order => same
v = sim.read(i, i) # numbers on every run
turn.done(i)
turn.wait_for(i)
sim.write(i, i, (v + 1) & 0xFF) # write it back
turn.wait_for(i)
nb = sim.read(i, (i + 1) % n) # read my neighbour
turn.done(i)
assert nb >= 0
bar.wait()
sim.release(i) # ---- sync point
sim.acquire(i)
bar.wait()
threads = [threading.Thread(target=worker, args=(i,)) for i in range(n)]
for t in threads:
t.start()
for t in threads:
t.join()
stats = (sim.faults, sim.messages, sim.bytes) # freeze the cost
# ---- verification (its own traffic is NOT counted) -------------------
expect = (periods * iters) & 0xFF # one word = one byte here
ok = True
for i in range(n):
sim.acquire(i)
for j in range(n):
if sim.read(i, j) != expect:
ok = False
sim.faults, sim.messages, sim.bytes = stats
if verbose:
print(" node0 sees out = %s (each word should be %d)"
% ([sim.read(0, j) for j in range(n)], periods * iters))
return sim, ok
# ----------------------------------------------------------------------- main
def main():
print("=" * 74)
print("CONSISTENCY MODEL vs COST (4 nodes, 20 periods x 20 iterations,")
print("each iteration: write my word, read my neighbour's word on the")
print("SAME page -> maximal false-sharing pressure, then 1 barrier)")
print("=" * 74)
print(" %-6s %12s %10s %12s %12s %10s"
% ("proto", "page faults", "messages", "bytes", "cost(ms)", "vs eager"))
print(" (each node increments its own byte-sized word 20x20 = 400 times,")
print(" so every word must read 400 mod 256 = 144 at the end)")
base = None
results = {}
for proto in ("eager", "rc", "lrc"):
sim, ok = run(proto)
cost = sim.cost_ms()
results[proto] = sim
if base is None:
base = cost
print(" %-6s %12d %10d %12d %12.1f %9.2fx"
% (proto, sim.faults, sim.messages, sim.bytes, cost, cost / base))
print(" correctness after the final sync: every node reads")
print(" out[0..3] = %d for all four words : %s"
% ((20 * 20) & 0xFF, "OK" if ok else "FAILED"))
print()
print(" eager = sequential-consistency-style eager invalidate (every")
print(" write pays a coherence round trip)")
print(" rc = release consistency: push once per release, no acquire")
print(" traffic")
print(" lrc = lazy release consistency: write notices at release,")
print(" pages pulled on demand after acquire")
print(" => the weaker the model, the fewer the messages: the same")
print(" workload costs %.1fx less under release consistency."
% (results["eager"].cost_ms() / results["lrc"].cost_ms()))
print()
sim = results["eager"]
print(" where the eager cost goes: %d faults x (request+reply) + " %
sim.faults)
print(" invalidations on every single write of the hot shared page.")
if __name__ == "__main__":
random.seed(425)
main()
运行输出：
==========================================================================
CONSISTENCY MODEL vs COST (4 nodes, 20 periods x 20 iterations,
each iteration: write my word, read my neighbour's word on the
SAME page -> maximal false-sharing pressure, then 1 barrier)
==========================================================================
proto page faults messages bytes cost(ms) vs eager
(each node increments its own byte-sized word 20x20 = 400 times,
so every word must read 400 mod 256 = 144 at the end)
eager 2401 16002 435296 834.9 1.00x
correctness after the final sync: every node reads
out[0..3] = 144 for all four words : OK
rc 4 488 8304 25.1 0.03x
correctness after the final sync: every node reads
out[0..3] = 144 for all four words : OK
lrc 80 400 20480 21.6 0.03x
correctness after the final sync: every node reads
out[0..3] = 144 for all four words : OK
eager = sequential-consistency-style eager invalidate (every
write pays a coherence round trip)
rc = release consistency: push once per release, no acquire
traffic
lrc = lazy release consistency: write notices at release,
pages pulled on demand after acquire
=> the weaker the model, the fewer the messages: the same
workload costs 38.6x less under release consistency.
where the eager cost goes: 2401 faults x (request+reply) +
invalidations on every single write of the hot shared page.
【代码做什么？】
- 一个精简的页级 DSM 模拟器，实现三种协议：
eager（顺序一致性风格的急切失效：每次写都把其他副本作废并走一次一致性往返）、rc（释放一致性：写只落本地，release时把本节点改动的字节推给其他持有者）、lrc（懒惰释放一致性：release只发布写在，acquire拿到”哪些页变了”后把本地副本作废，真正访问时再按需拉取）。 - 同一份负载跑三遍：4 个节点、20 个同步区间，每区间内 20 次迭代，每次迭代 = 写自己的那个字 + 读邻居的那个字，而这 4 个字全部落在同一页上（刻意制造最大的假共享压力），区间末尾一次屏障。
- 结束后做一次最终同步再验证：每个节点读到的 4 个字都必须等于 400（mod 256 = 144），即三种协议都正确；统计消息数、字节数、页缺失数与折算耗时。
【分布式机制透视】
- 同一个程序的三种”一致性契约”：
eager提供更强的保证（读写随时可能被同步），代价是每次写都付一次一致性往返；rc/lrc只在同步点付账，把一致性保证弱化到”同步点之间允许看到旧值”。三者的结果都正确，因为程序在同步点之间没有依赖别人写的值——这正是”弱一致性只在程序遵守契约时成立”的可运行版本。 - 懒惰的收益来自”批量摊薄”与”按需拉取”：
rc把一整个区间的多次写合并成一次推送（区间内 20 次写 → 1 次传播），lrc更进一步——只发布”哪页变了”，数据等别人真正要的时候再拉。 - 注意
lrc的页缺失数（80 次）高于rc（4 次）：懒惰不是免费的，它把成本从”消息数”换成了”按需拉取的故障次数”。这一对数字（消息 vs 故障）正是设计者要权衡的地方：如果数据大概率会被用到，推送更划算；如果数据大概率用不到，拉取更划算。
【与理论的对应】
eager的 16002 条消息 ≈ 4800 次共享访存 × 3.3 条/次（每次写要失效 3 个副本、每次缺失要一次请求-应答），与算法 23.3.1 的复杂度分析（写升级/写缺失 = $O(N)$ 条消息）一致；rc的 488 条 = 80 次 release × 3 个持有者 × 2 条 + 4 次初始缺失 × 2 条，与算法 23.3.2/23.3.3 的 release 侧 $O(1)$ 条消息一致；lrc的 400 条 = 80 条写在 + 80 次 acquire × 2 条 + 80 次按需拉取 × 2 条，说明 release 侧几乎只剩”写在”。- 最终耗时 834.9 ms（eager）→ 25.1 ms（rc）→ 21.6 ms（lrc），即释放一致性比急切失效便宜约 38.6 倍。这直接回答了 23.2.4 表格 2 下方那个问题——“为什么 DSM 实践中都选择弱一致性模型”：不是理论上更好，而是在 DSM 里”一致性”就等于”通信”，弱一致性把通信从”每次访存”降到”每个同步区间”。
- 三种协议都通过了最终一致性校验，同时验证了 23.3.3 的安全性结论（正确同步的程序在任何一种模型下都能看到应有的更新）。
23.5 性能与可扩展性分析
23.5.1 一次远端访问到底有多贵？——延迟构成分解
| 组成部分 | 典型耗时 | 说明 |
|---|---|---|
| 本地内存命中 | $\sim 100\ ns$ | 基线：DSM 想模拟的就是它 |
| 页错误陷入内核（trap）+ 运行时协议处理 | $1\text{-}5\ \mu s$ | 信号/trap 处理 + 元数据查找 + 构造消息 |
| 网络往返 RTT（局域网） | $50\text{-}200\ \mu s$ | 1990 年代以太网 ~$200\ \mu s$；现代数据中心 ~$50\ \mu s$；RDMA ~1-2 $\mu s$ |
| 整页传输（4 KB） | 1 Gbps：$\sim 32\ \mu s$；100 Mbps：$\sim 328\ \mu s$ | 页越大越明显；这也是”粒度”影响延迟的地方 |
| 一次 DSM 页错误总计 | $10^2\text{-}10^3\ \mu s$（0.1-1 ms） | 比本地访存慢 $10^3\text{-}10^5$ 倍 |
| 同步点（锁/屏障） | 每个屏障 $\ge 2$ RTT（$10^2\ \mu s$ 起） | 每次同步都是一次全网交互 |
结论：DSM 的性能几乎完全由”每秒钟发生了多少次远端事件“决定，而不是由”算得多快”决定。因此所有 DSM 优化都在做同一件事：减少远端事件的次数（粒度、缓存、失效/更新、弱一致性）或降低单次事件成本（批量传输、diff 传输、RDMA）。
23.5.2 粒度、假共享与抖动的定量关系
- 假共享的放大系数：设页 $g$ 字节、热点字被 $k$ 个节点交替写、每个节点每秒写 $f$ 次，则每秒丢到网络上的字节数约为 $k\cdot f\cdot g$，而其中有用的数据只有 $k\cdot f\cdot 8$ 字节，有效载荷比 $=8/g$（4 KB 页时仅 0.2%）。即 $g=4096$ 时浪费因子约 512 倍——与 23.4.1 实验实测的 333 倍消息放大、250 倍字节放大完全同一量级。
- 页错误率上界：每次故障要一个 RTT（$100\ \mu s$），因此单节点故障速率上限约 $10^4$ 次/秒。若程序的每次”有用操作”都伴随一次故障，则单节点吞吐被钉在 $10^4$ ops/s——比本地访存（$10^7$ ops/s）慢 1000 倍。
- 抖动（thrashing）的成因：三种典型模式——（a）两个节点交替写同一页（flip-flopping：每次访问都是故障，见实验 2 的紧凑布局）；（b）工作集超过本地内存导致页被换出后立刻又被访问，形成”取页-换出-再取页”的循环；（c）循环依赖的迁移：多个节点轮流要求独占同一批页，谁都无法连续前进。
- 抖动的避免：（1）数据布局上做填充/重排，让”不同节点的热点”落在不同页（最有效，且无需改协议）；（2）减小粒度（需要有编译器/硬件支持）；（3）多次写检测 + diff（TreadMarks 的做法，从机制上避免整页搬运）；（4）工作集分析 + 动态粒度调整（运行时检测争用，对热点区域改用细粒度）；（5）控制并行度/分块（blocking）：让每个节点在一段时间内只碰自己那一块数据（这是程序员能做的最有效的事：把”共享写”变成”分区写”）。
- 可扩展性上限：失效协议一次写要广播到 $O(N)$ 个副本，且必须等齐 ACK，因此（1）消息数随 $N$ 线性增长；（2）等待时间取决于最慢的副本（长尾延迟被放大）；（3）每个节点要维护”谁有这一页”的副本集合（$O(\text{页数}\times N)$ 元数据）。这些因素叠加，使经典 DSM 在几十个节点以内还能用，上百节点就基本不可行；相比之下，消息传递（MPI）的通信是点对点的、可扩展的，这是它在集群上胜出的结构性原因。
23.5.3 消息传递 vs 软件 DSM：全面对比与”抽象泄漏”的教训
- 表格 5：消息传递 vs 软件 DSM 全面对比
| 维度 | 消息传递（MPI / socket / RPC） | 软件 DSM |
|---|---|---|
| 编程模型 | 显式 send/recv（或 RPC 调用） | 隐式共享变量访问（x = x + 1） |
| 编程难度 | 高：要显式处理数据分布、同步、序列化、乱序、失败 | 低：像单机共享内存一样写（但必须遵守一致性契约） |
| 性能可预测性 | 高：程序员知道每条消息何时发、多大 | 低：页错误/协议开销对程序员不可见，性能随时可能崩塌 |
| 通信开销 | 精确：只发需要的数据 | 可能浪费：整页传输、假共享、失效广播 |
| 可扩展性 | 好（点对点，$O(1)$~$O(\log N)$ 通信模式常见） | 受一致性协议限制（失效广播 $O(N)$、屏障瓶颈、元数据增长） |
| 调试 | 相对容易（通信是显式的，可以在日志里看到） | 困难：非确定性 + “正确但慢 100 倍”的性能 bug 无显式线索 |
| 一致性由谁负责 | 程序员（他写的同步逻辑） | 运行时协议（且只提供弱模型，需要程序员正确使用同步） |
| 容错 | 由程序员/框架处理（检查点、重启） | 经典 DSM 基本不处理（owner 崩溃 = 数据不可用） |
| 代表系统 | MPI、socket、RPC/gRPC、MapReduce 的消息层 | IVY、Munin、TreadMarks、Shasta、Cashmere |
- 结论：DSM 的”编程简单”被”性能不可预测 + 调试困难”抵消了。当然，这不是说 DSM 一无是处——在不规则、指针密集、共享结构动态变化的应用里（例如图算法、有限元网格的某些阶段），手工用消息传递写起来极其痛苦（要自己维护分布式数据结构与消息缓冲区），而 DSM 让程序员先”正确”再”优化”；TreadMarks 时代的实测也表明，在若干不规则应用上 DSM 的性能与手工 MPI 相当。但总体上，手工优化的 MPI（或现代的 RDMA 显式接口 + 分区数据结构）通常更快，因为程序员能利用 DSM 看不见的应用语义（”这个数组未来 1000 次迭代都不会被邻居碰”）。
- 这一权衡的历史经验（本章最重要的元教训）：隐藏分布式本质的抽象（RPC 的透明性、DSM 的共享内存假象）在简化编程的同时，往往把性能与故障的复杂性留给了不可见的地方。这与第 18 章关于”RPC 的透明性是危险的”结论完全同构：
- RPC 假装”远端调用就是本地调用” ⇒ 但网络会延迟、会丢、会重复、会分区，于是”看起来像本地”的调用需要一个超时 + 幂等 + 重试的完整机制来兜底，而这些都是本地调用不需要的。
- DSM 假装”远端内存就是本地内存” ⇒ 但远端访问慢 $10^3$-$10^5$ 倍、一致性必须靠协议维护、假共享由粒度决定，于是”看起来像本地”的
x = x + 1背后可能是一次网络往返，程序员却看不见。 - 正确的态度不是”不要抽象”，而是：抽象必须把它的代价暴露给使用者（例如 NUMA 用
numactl暴露节点距离、RDMA 用显式的rdma_read暴露远端访问、分布式事务用显式的延迟预算与失败处理），否则程序员会写出”逻辑正确、性能灾难”的系统。
23.5.4 现代复兴：NUMA、RDMA 与内存解耦如何让 DSM 思想回归
- 机制图解 / 延迟量级对比（”DSM 思想回归”的物理解释）：
访问类型 典型延迟 比本地慢 一致性由谁保证
──────────────────────────────────────────────────────────────────────────────
本地内存（同一 NUMA 节点） ~100 ns 1x 硬件
远端 NUMA 内存（同机、跨 socket） ~200-300 ns ~2-3x 硬件（目录）
单机内多进程共享内存（shm/mmap） ~100-500 ns ~1-5x 硬件 + OS
───────────────────────── 机内 / 机架内的"共享内存"─────────────────────────
RDMA 远端内存读（InfiniBand, 1-2 us） ~1-2 us ~10-20x 软件（显式读写/原子）
RDMA 原子操作（CAS / fetch-add） ~2-4 us ~20-40x 软件（网卡原子单元）
───────────────────────── 网络化内存（DSM 复兴的主战场）─────────────────────
TCP/IP 上的远程过程调用 ~50-200 us ~500-2000x 软件
DSM 页错误（1990 年代以太网） ~200-500 us ~2000-5000x 软件（页错误协议）
───────────────────────── 传统 DSM 的处境──────────────────────────────────
结论：1990 年代 DSM 输在"一次同步 = 数百微秒"；
RDMA 把它压到 1-2 微秒 —— 与本地内存只差一个数量级，
于是"共享远端内存"这件事重新变得可行。
- NUMA（Non-Uniform Memory Access）：单机内的”DSM 思想”。多路服务器里每个 CPU socket 挂自己的内存，”共享内存”依然成立，但远端 socket 的访问要慢 2-3 倍。NUMA 用硬件的目录协议解决了 DSM 用软件苦苦挣扎的问题（细粒度、无页错误、无假共享），但暴露了同样的核心矛盾：局部性决定性能。学习 NUMA 是理解 DSM 的捷径——它告诉你”如果一致性协议足够快、粒度足够细、代价透明，共享内存就是好抽象”。
- RDMA（Remote Direct Memory Access）与 InfiniBand：讲义明确指出这是 DSM “可能回归”的原因。RDMA 让网卡直接读写远端机器的内存（绕过远端 CPU 与内核），一次远端内存读约 1-2 μs，并提供远端原子操作（CAS、fetch-add）。这带来两个后果：（1）同步的物理成本下降两个数量级，锁和屏障的往返不再是”毫秒级”；（2）“共享内存”的粒度可以细到 cache line / 字，因为每次远端访问本身就足够便宜，不必再用”整页搬运”摊薄 RTT。代表系统：FaRM（把整个集群的内存做成一个带事务的共享地址空间）、DrTM（用 RDMA + HTM 做快速内存事务）。
- 内存解耦 / 内存池化（Memory Disaggregation）：数据中心把内存从服务器里”拆”出来变成独立资源池，通过高速网络按需分配给计算节点（Infiniswap、LegoOS 的远端内存、CXL 的内存池化与共享）。应用访问”别人的内存”时，本质上就是 DSM 的核心场景，只是接口更诚实（显式的远端内存语义、明确的延迟与失败语义），而不再假装”这就是我的本地内存”。
- 分布式共享内存数据库与共享存储集群：Oracle RAC 的 Cache Fusion 让多个实例共享同一份数据（块在实例之间搬运——这就是一个块级 DSM）；内存数据库集群用 RDMA 做远端内存事务。在这些系统里，”共享”是业务需求（多实例并发访问同一份数据），而网络足够快，使共享的代价可以接受。
- 一个开放问题（讲义原话的精神）：“会更流行吗？还是维持现状？时间会告诉我们。” 从今天的视角看，答案更像”DSM 的思想赢了，DSM 的产品形态输了“：软件 DSM 这个具体形态没有成为主流，但”共享远端内存”的思想以 NUMA、RDMA、内存解耦、CXL、共享数据库的形式持续扩张。
23.6 关键要点
- DSM = 物理上消息传递 + 逻辑上共享内存。它让共享内存程序（几乎）不用改写就能跑在集群上，代价是把”远端访问”伪装成了
load/store：本地命中 ~100 ns，一次远端页错误 0.1-1 ms，相差 $10^3$-$10^5$ 倍。 - 共享内存真正的成本是一致性维护，而不是读写本身。DSM 的全部设计都围绕”每秒钟发生多少次远端事件“展开：粒度决定单次事件的代价，一致性模型决定事件的频率。
- 粒度是一把双刃剑：细粒度 ⇒ 假共享少但故障/元数据多；粗粒度 ⇒ 通信摊薄但假共享严重。理论最优 $g^{*}=\sqrt{DPB/(Sw)}$，而实际系统被 MMU 的 4 KB 页钉在一个”大致最优”的点上。假共享是 DSM 最著名的性能杀手（实验实测 333 倍消息放大），它不是正确性问题，所以只能靠测量、不能靠测试发现。
- 一致性模型的强弱 = 同步的频率。IVY 追求顺序一致性 ⇒ 每次写都要 $O(N)$ 失效广播；Munin 的入口一致性 ⇒ 只在 acquire 时同步”这把锁保护的变量”；TreadMarks 的 LRC ⇒ release 只发写在、acquire 按需拉 diff（实验实测比急切失效便宜 38.6 倍）。DSM 实践中一律选择弱一致性，因为在这里”一致性”就等于”通信”。
- 多写者 + 孪生页/diff 解决假共享，但不解决数据竞争。diff 合并只在”写不同字节“时正确且顺序无关；写同一字节时会产生”谁也没写过的值”，TreadMarks 用 SIGBUS 把它变成显式失败。DSM 从不替你修复数据竞争——那需要你自己的锁和屏障。
- 黄金法则：DSM 试图用软件在网络上重建共享内存，但共享内存的真正成本在于一致性维护；粒度决定了通信开销与假共享的权衡，一致性模型的强度决定了同步的频率。DSM 的兴衰史告诉我们：把分布式伪装成本地，往往要把代价藏到程序员看不见的地方。
23.7 常见陷阱与注意事项
以为”用了 DSM，共享变量就不用同步了”。 为什么错：DSM 只保证”页是一致的”（读到的页不会比最近一次已传播的写更旧），不保证”你的读-改-写是原子的”。实验 1 里 4 个线程各加 20 次，结果只有 20 而不是 80——丢失了 60 次更新。 正确做法：所有对共享变量的复合操作都放进临界区，并用
acquire/release（或锁/屏障）作为一致性同步点；把”无数据竞争（data-race-free）”当作使用弱一致性模型的前提条件来设计程序。以为”我是 owner，所以我可以直接把页标成 W 去写”。 为什么错：owner 只意味着”最新版本在我手上”，不意味着”只有我有副本”（讲义写场景 2 的反问就是这个陷阱）。若还有其他 R 副本没被失效，写完之后它们就是永不更新的脏数据，之后有人从它们那里读到旧值——顺序一致性被破坏。 正确做法：任何写之前先做失效广播并收齐 ACK，再把
sharers重置为{自己}（算法 23.3.1 的write_upgrade/write_fault）。把假共享当成正确性 bug 去”修”。 为什么错：假共享不影响结果正确性（协议保证一致性），只影响性能。因此用”结果对不对”的测试永远发现不了它，而很多人会在并发/同步逻辑里瞎找一通。 正确做法：测量通信量（页错误次数、消息数、字节数）而不是测量正确性；用本讲的实验 2（
padding前后对比）这类方法定位；必要时做数据布局填充或改用 diff 方案。认为”页越大越好”或”页越小越好”。 为什么错：两者都错。页太大 ⇒ 假共享与带宽浪费（实验 3 中 4 KB 页的成本是 256 B 页的 2 倍）；页太小 ⇒ 故障次数爆炸（实验 3 中 8 B 页的成本同样翻倍）。成本曲线是 U 形的，最优点取决于顺序局部性 / 热点争用的比例与延迟/带宽比。 正确做法：先按 $g^{*}=\sqrt{DPB/(Sw)}$ 估算量级，再用真实访问模式做扫描实验（像实验 3 那样把页大小当参数扫一遍）。
在 acquire/release 之外依赖一致性。 为什么错：弱一致性模型（尤其 LRC）的定义就是”同步点之间不保证任何顺序“。如果在两次 release 之间去读别的节点写的变量，读到旧值是符合契约的，程序 bug 在你而不在系统。 正确做法：把”读别人写的数据”严格放在 acquire 之后、release 之前；用同一把锁保护一组相关的变量（这正是 Munin 的入口一致性要求的精神）。
用”整页推送”实现多写者。 为什么错：两个节点各自把整页推给第三方，后到的整页会覆盖先到的，必然丢更新（实验 23.4.2 场景 A 的第一种做法就是这样）。 正确做法：用孪生页 + diff 只合并改动的字节（TreadMarks 的做法），并明确前提——写必须字节不重叠；重叠时应当检测并报错，而不是”随便挑一个赢”。
忽略”唯一副本”的页替换语义，以及 owner 崩溃的后果。 为什么错：DSM 的页替换不同于虚拟内存——被换出的页可能是全网唯一副本（owner 处于 W 状态），直接丢弃就丢数据；而 owner 崩溃后，任何”等待它 ACK/回数据”的进程会永久阻塞（活性依赖所有相关节点存活）。 正确做法：区分”多副本页（可直接丢）”与”唯一副本页（必须写回或迁移所有权）”；在生产级系统中引入超时 + 成员管理 + 数据复制（这就退化成第 17 章的复制状态机方案——也说明”可靠的共享内存”最终要靠共识来兜底）。
屏障忘记”代（sense）翻转”，或假设屏障不需要故障处理。 为什么错：没有 sense reversal，跑得快的进程会把上一轮遗留的释放消息当作本轮放行，直接破坏屏障安全性；而只要有一个进程崩溃且没被剔除，协调者/父节点就会永远等它，屏障死锁。 正确做法：每轮翻转
sense并让释放消息携带该值（算法 23.3.5）；把屏障的”合格人数”交给成员管理动态更新（第 7 章），并配合超时。
23.8 思考题（带答案）
题 1（概念）：为什么”严格一致性（strict consistency）”在多计算机上不可实现？DSM 实际上退到了什么模型，代价和收益分别是什么？
答：严格一致性要求”任何读都返回最近一次写的值”，而”最近”是按真实时间（全局时钟）定义的。它隐含两个要求：（1）所有节点对”此刻”有完全一致的认知——需要一个全局同步时钟（在分布式系统中不存在，见第 11 章物理时钟的偏差与不确定性）；（2）一次写要在返回前传播到所有副本，否则别人读到旧值就不满足”最近”——这要求写操作的延迟至少一个全网往返，且要让所有节点串行化。两条都无法在消息传递网络上满足（第一条物理上做不到，第二条代价不可接受），因此严格一致性不可实现。DSM 实际退到顺序一致性（IVY）甚至释放一致性/LRC（Munin、TreadMarks）。收益：普通访存不必每次都通信（本地命中 0 条消息），只在同步点上付账（实验实测弱模型便宜 26.5 倍）。代价：程序员必须保证程序是”无数据竞争 + 正确同步”的；一旦违反，结果不再有保证（实验 1 的”丢失 60 次更新”）。
题 2（计算）：某 DSM 使用 4 KB 页、100 Mbps 有效带宽、每次页错误的消息往返延迟 $P=200\ \mu s$。两个进程各自每秒更新自己那一个 8 字节计数器 1000 次，而这两个计数器恰好落在同一页上（每次写都触发一次整页所有权的往返）。请计算：（a）每秒的假共享事件数与传输字节数；（b）有效载荷占比；（c）若把两个计数器填充到不同页，传输量下降多少倍？（d）在 (b) 的传输量下，每秒的传输时间占多少带宽比例？
答： （a）两个进程各 1000 次写，每次写都要”失效对方 + 取回整页”⇒ 约 2000 次假共享事件/秒（每个进程的写都会让对方下一次访问失效，最坏情况下每次写都引发一次往返）。每次往返传输一页 4 KB ⇒ $2000 \times 4096 = 8.192\times10^{6}$ B/s $\approx$ 8.19 MB/s。 （b）真正有用的数据是每次写 8 个字节，而每次假共享往返搬运一整页 4096 字节 ⇒ 有效载荷比 $8/4096 \approx 0.2\%$（若把”一次往返服务两个计数器”算进去也仅 $16/4096\approx 0.39\%$）。按每秒计：$2000 \times 4096\ \text{B} \approx 8.192$ MB/s 的传输量里，有用的只有 $2000 \times 8\ \text{B} = 16$ KB/s，约 99.8% 的带宽在搬运没有人需要的数据。 （c）填充后两个计数器各占一页，每个进程写自己的页（首次故障后长期处于 W 状态）⇒ 后续写 0 条消息、0 字节，传输量下降约 500 倍（从 8.19 MB/s 降到”几乎没有”，量级上就是”每次写摊到的字节数” $4096/8=512$ 倍的浪费被消除）。 （d）100 Mbps $\approx 12.5$ MB/s，8.19 MB/s 占 约 65% 的带宽——两个进程各写一个 8 字节变量，就能吃掉三分之二的网络；而且每次往返还要等 $200\ \mu s$，因此每个进程的写速率被限制在约 $1/(200\ \mu s)=5000$ 次/秒，与”本地内存每秒上千万次”相比慢了三个数量级。
题 3（”错在哪”）：有同学说：”TreadMarks 用 diff 合并多个写者对同一页的写，所以 DSM 已经能自动处理多个进程同时写同一页的情况，程序员不需要考虑数据竞争了。”这个说法错在哪里？
答：错在把”不重叠的写“与”数据竞争“混为一谈。diff 合并的正确性依赖前提 P：同一同步区间内，各节点写的字节互不重叠（这样每个字节只有一个写者，异或合并正好复原该写者的值，且与顺序无关）。而数据竞争的定义恰恰是”多个进程并发访问同一字节且至少一个是写”——此时前提 P 被破坏，异或合并会得到两个值的异或（实验里 11 xor 22 经过基线异或后得到 93，既不是 11 也不是 22）。TreadMarks 的做法是检测重叠并报 SIGBUS 终止程序，而不是”解决”它。正确理解：diff 机制解决的是假共享（不同字节同一页时的整页搬运浪费），它把”页级”的冲突降级到”字节级”；而真正的数据竞争仍然必须由程序员用锁/屏障串行化。这也再次印证本章的立场：一致性协议管”内存看起来一致”，互斥管”操作看起来原子”，两者不能互相替代。
题 4（应用）：你要用 DSM 写一个 4 节点的直方图程序：每个节点对同一份输入做统计，把结果累加到共享的 1024 个计数器上（每个计数器 8 字节，全在 4 KB 页的划分下，1024 个计数器 = 8 KB = 2 页）。已知输入数据分布使得 4 个节点都会访问全部 1024 个计数器。请给出两种避免假共享/减少通信的设计，并说明各自的代价。
答：
- 设计 A：私有直方图 + 末尾归约（推荐）。每个节点维护自己私有的 1024 个计数器（私有内存，零通信），全部统计结束后做一次归约：用一个屏障同步，然后每个节点只把自己的第 $i$ 段（$i$ 为节点号）发送给负责合并的节点，或让每个节点读取所有节点的分段并累加。代价：$4\times8\ \text{KB}=32\ \text{KB}$ 的最终通信量 + 每个节点 8 KB 的额外内存；通信从”每次计数一次远端事件（$O(\text{输入规模})$ 次）”降到”每个程序一次 $O(\text{直方图大小})$ 的数据传输“——这是把”细粒度共享写”变成”分区 + 批量归约”的经典手法，也是 MPI 里最自然的写法。若用 DSM，可让每个节点把私有直方图放在自己的页上（天然的 padding），最后用
acquire/release一次性同步。 - 设计 B：共享直方图分段所有权 + diff。把 1024 个计数器切分到 4 个节点（每节点 256 个 = 2 KB，各占独立页），每个节点只写自己那一段所在的页（用”所有权迁移”让写者长期持有该页的 W 状态），读取时做一次汇总。代价：如果输入分布导致访问不均匀（某节点经常要写别人那一段），仍然会引发假共享与失效；此时要改用 TreadMarks 的多写者 + diff（每个节点在自己的副本上写自己碰到的计数器，同步时合并 diff），把代价降到”改动的字节数”，前提是不同节点不会同时改同一个计数器的同一个字节——而累加同一个计数器恰恰会违反这个前提，所以必须换成”每节点一个分片（私有计数）+ 归约”（即设计 A）。
- 结论：在这个例子里，“归约”比”共享计数器”更适合分布式环境：它把 $O(\text{输入规模})$ 次远端同步压成一次批量传输，代价是内存翻倍与一次显式同步。这也解释了为什么真实的数据处理系统（MapReduce、Spark）宁可”先分区、再归约”，而不去提供一个”全局共享计数器”的抽象——因为共享内存的抽象在分布式环境下的每一次写都可能变成一次网络往返。