Dekker 算法
纯软件互斥可行，但复杂度随进程数快速膨胀
CS152 · 第 23 课
有了一致性和相合性模型，还差最后一块拼图：程序员该用什么原语来保证多个线程正确地互斥访问共享资源？这一课从纯软件的 Dekker 算法出发，一路讲到 RISC-V 真正提供的原子指令。
两种同步需求：生产者-消费者（消费者必须等待生产者产出数据）与互斥（同一时刻只允许一个进程使用某项资源）。假设底层是 SC 模型，只用普通 load/store 能否实现互斥？第一次尝试（各自设置忙碌标志 c1/c2，检测对方标志再决定是否等待）会死锁：两个进程都设置了自己的标志，又都因为看到对方的标志而拒绝继续，谁都不肯让步。第二次尝试修复了死锁，却引入了活锁/饥饿：死锁不会发生了，但小概率下可能出现"倒霉的进程永远抢不到临界区"。
Dekker 算法（T. Dekker，1966）用三个共享变量 c1、c2、turn 彻底解决问题：turn=i 确保"只有进程 i 可能等待"，c1/c2 确保互斥本身。幻灯片补充了一个有趣的历史注脚：把这个方案推广到 n 个进程的解法由 Dijkstra 给出，而且相当精巧复杂——这提示我们，纯软件的互斥算法虽然理论上可行，但复杂度会随进程数快速膨胀。
幻灯片明确指出：普通 load/store（配合弱模型下的 fence）理论上足够实现互斥，但代码低效且复杂——这正是硬件提供原子读-改-写（RMW）指令的动机。两个经典原语：Test-and-Set（reg_x=M[a]; M[a]=1，一步完成"读旧值+置位"）；Swap（reg_x=M[a]; M[a]=reg_y，一步完成"读旧值+写新值"）。基于 amoswap 的自旋锁：获取锁时反复尝试把锁字原子交换为"已锁定"，直到交换前读到的旧值是"未锁定"；释放锁时把锁字写回"未锁定"。
RISC-V 的原子内存操作（AMO）指令带有两个可选排序位——获取（acquire, aq）和释放（release, rl）：两者都不设置时，不附加任何额外排序；设置 aq 后，这条 AMO"发生在"其后所有 load/store 之前；设置 rl 后，这条 AMO"发生在"其前所有 load/store 之后；两者都设置时，AMO 严格按程序顺序发生。
FENCE vs. AMO.aq/rl：排序范围的关键区别——幻灯片用一张对比图明确指出："AMO 只对自己与其他 load/store/AMO 之间的顺序做出约束；FENCE 则约束 FENCE 前后所有的 load/store/AMO"。也就是说，AMO 的 aq/rl 位只保护"临界区边界与 AMO 本身"这一层关系，临界区外那些与锁无关的"无关 store/load"完全不受影响；而一条通用 FENCE 指令则会把它前后所有访存都纳入排序约束，粒度粗得多。这正是为什么 RISC-V 既提供通用 FENCE、又单独给 AMO 配备 aq/rl 位——后者能用更小的排序代价实现同样的锁语义。
动机：如果一个软件线程在持有锁的时候被操作系统换出调度，其他线程在锁被释放之前完全无法在临界区内取得任何进展。无锁（non-blocking）同步让临界区可以在不真正持锁的情况下原子执行。
Compare-and-Swap (CAS)：Compare&Swap(m), Rt, Rs——如果 Rt==M[m]，则 M[m]=Rs，Rs=Rt，返回成功；否则返回失败。CAS 的已知问题：ABA 问题——设想 Load(A)，处理一段时间后 CAS(A,Y)；如果在处理期间，另一个任务把 A 从某个值改成 B、又改回原来的值，CAS 会误以为"没人动过"而成功——但实际上数据已经被别人动过了。解决办法是双重比较交换（DCAS）：额外加一个计数器，让 CAS 同时访问两个字（一个地址、两个待比较值、两个待写入值，共 5 个源操作数）。
Load-Reserve / Store-Conditional (LR/SC)：Load-reserve R,(m) 设置一个隐藏的 <flag,addr>=<1,m>预约标记，并把值读入 R；Store-conditional (m),R 只有当预约标记仍然是 <1,m> 时才真正写入并使其他处理器对 m 的预约失效，否则失败。真实硬件实现（借助 MESI）：Load-Reserve 确保该行进入独占/已修改状态；Store-Conditional 只有在该行仍处于独占/已修改状态时才成功（幻灯片补充说明："实践中这种实现只适用于较小规模的系统"）。
LR/SC vs. CAS 的权衡：LR/SC 天然免疫 ABA 问题——因为对该地址的任何访问都会清除预约标记，无论新写入的值是什么（不需要额外的版本计数器）；但 LR/SC 的无锁同步可能在两个竞争处理器之间发生活锁。相反，CAS 保证前进性——CAS 只有在另一个线程成功时才会失败，所以整个系统必然有进展。RISC-V 通过要求 LR/SC 配对之间的代码遵守特定规则，来保证前进性，从而弥补了朴素 LR/SC 的活锁风险。
RISC-V 还提供一整套原子操作指令：swap、add、and、or、xor、有符号/无符号的 max/min，覆盖了绝大多数常见的无锁数据结构操作需求。
问题 1：RISC-V 的 FENCE 指令和 AMO 指令上的 aq/rl 排序位，在排序范围上有什么关键区别？
问题 2：为什么 Load-Reserve/Store-Conditional (LR/SC) 天然免疫 ABA 问题，而 Compare-and-Swap (CAS) 不能？
问题 3：朴素的 LR/SC 相对 CAS，在"前进性保证"上存在什么风险？
纯软件互斥可行，但复杂度随进程数快速膨胀
Test-and-Set、Swap，简化互斥锁的实现
更精细的排序粒度，用更小代价实现锁语义
ABA 免疫性 vs. 前进性保证，各有取舍
sp23/lecture_slides/L23_Synchronization.pdf（UC Berkeley CS152/CS252A, Spring 2023, Sophia Shao）