CS152 · Homework 5 导读
这份导读帮你理解 HW5 在考什么、需要哪些前置知识。它不包含完整解答——答案需要你自己动手推导。
资料来源说明：2023 年春季的官方课程网站没有为这份作业发布解答文件。本页参考了 2026 年春季同名课程的解答（sp26_hw/hw05-sols.pdf）——经逐题核对，sp26 的 6 道题里有 4 道（相合性 fence 插入、锁性能、目录式更新协议、Snoopy 一致性）与 sp23 版本的题目文字完全一致，可以直接作为学习参考；但 sp23 独有的两道题——顺序相合性（Problem 1）和同步原语 LR/SC 概念题——在 sp26 的问题集里根本不存在，因此对这两道题没有任何官方解答可以参考。本页会诚实标注这两道题目前没有权威答案可查这一事实，而不是假装有。
一句话总结：用一个三线程共享变量 X 的例子，判断在顺序相合性下哪些最终值是可能/不可能的；分析 LR/SC 同步原语的实现细节；给一个 seqlock 实现插入最少数量的内存栅栏；在目录协议下计算锁竞争产生的失效消息数量；填写真实的 Snoopy 一致性协议状态转移表。
三个线程 A、B、C 各自执行几条指令，都会读写共享变量 X（初始为 0）。题目问：在严格的顺序相合性（SC）下，X 最终能否等于 8、9、10？如果一个处理器只按寄存器（本地数据）依赖重排指令、却不保证访存顺序，能否产生一个在 SC 下不可能出现的结果？
解题思路（不是答案，是方法）：这类题目最可靠的做法是枚举法——像第 22 课那道"P1/P2 各写一个变量再读另一个变量"的例子一样，把每个线程内部的程序顺序约束写清楚，然后枚举所有满足这些约束的全局交错顺序，逐一推演每种顺序下 X 的最终值，看目标值是否出现在可达集合里。如果要证明某个值"不可能"，光靠"我试了几种交错都没找到"是不够的——需要找到一个通用的结构性论证（例如：如果所有线程各自的最后一条指令都必然产生某种奇偶性的值，而"最后写入 X 的那条指令"在 SC 下必然是某个线程自己的最后一条指令，就可以从奇偶性论证某个目标值永远不可达）。第 22 课"Store 缓冲会打破 SC"的讨论，对 1.D 那道"寄存器依赖 vs. 访存顺序"的题目也有直接参考价值——关键是找到一对没有寄存器依赖、但有访存顺序关系的指令（例如一次 store 后面紧跟一次读同一地址的 load，但 load 的目的寄存器不是从 store 的源寄存器算出来的），这正是"store→load 重排序"这一经典冒险的具体体现。
几道概念题：Load-Reserve/Store-Conditional 的预约标记应该在什么情况下被清除？能否在内存总线完全不知情的情况下实现 LR/SC？为什么 LR/SC 通常被认为优于 Test-and-Set 这类原子读-改-写指令？这几道题直接对应第 23 课"LR/SC vs. CAS 的权衡"一节——回答时应该扣住"LR/SC 天然免疫 ABA 问题""任何对该地址的访问都会清除预约"这两条核心机制。
给定一个写者/读者 seqlock 的实现，要求在完全放松的内存模型下插入最少数量的内存栅栏（Membar_LL/LS/SL/SS），使其重新保证正确性。这是第 22 课"fence 指令"内容最直接的实践——先确定哪些操作顺序是算法正确性真正依赖的，再只在这些地方插入对应类型的栅栏，而不是每两条指令之间都插一个（那样虽然"安全"但会显著损害性能，也不是本题想要的答案）。
对比 Test&Set 和 Test&Test&Set 两种自旋锁实现，在目录协议下分别计算：1000 个线程同时争抢一把锁时产生多少条失效消息；某个线程持锁期间，其余线程自旋等待会产生多少条消息；锁被释放时又会产生多少条消息。这道题直观展示了第 21 课"目录式一致性只与真正持有副本的节点通信"这条机制，在高竞争场景下如何决定性地影响消息数量的量级差异。
Problem 5 分析一个假想的、基于更新（而非失效）且允许"静默丢弃"的目录协议，诊断它为什么会违反 SC、为什么会导致失效请求泛滥、以及一个 FIFO 顺序假设失效的反例。Problem 6 需要填写一个真实的 5 状态 MBus 风格 Snoopy 一致性协议（I/CE/OE/CS/OS）的状态转移表——这是第 21 课 MSI/MESI 状态机内容在一个更复杂真实协议上的直接应用。
问题 1：Problem 1 中，如果要证明在顺序相合性下某个值（如 X=10）"不可能"出现，仅仅枚举几种交错顺序都没找到这个值，是否足够？
问题 2：Problem 4 计算目录协议下锁竞争产生的失效消息数量时，依赖第 21 课的哪条核心机制？
sp23/hw05.pdf、sp23/hw05-handout.pdf、sp23/hw05-handout2.pdf（UC Berkeley CS152, Spring 2023）