Rust 并发编程进阶自学路线：KAIST CS431 的锁、访存模型与无锁数据结构（cs-self-learning 计算机自学指南）

KAIST CS431（Concurrent Programming）是计算机自学指南（cs-self-learning）Rust 学习路线中定位最深入的一门并发编程课，它不满足于教你写出能跑的线程，而是把重点放在“并发下的编程模型”与“Rust 库中锁/无锁数据结构如何实现”上。本文基于仓库内 cs431.md 与 cs431.en.md 的课程导读内容，系统梳理课程定位、双线内容结构、作业阶梯、难度评估与自学资源，并给出可落地的学习建议，帮助你判断这门课是否适合自己、以及如何最高效地自学它。

课程档案速览：一门被低估深度的 KAIST 并发课

CS431 在课程导读页中被定义为“讨论并发编程、主要使用 Rust”的课程。先看官方档案信息：

项目	内容
所属大学	KAIST（韩国科学技术院）
先修要求	Rust 编程基础 + 对并发的初步了解
编程语言	Rust
课程难度	四星（较高，满分为五星）
预计学时	约 50 小时
仓库导读页	cs431.md（中文）、cs431.en.md（英文）

在理解课程定位之前，先要知道它的“出身”。依据仓库中同目录的 cs220.md 导读所述，CS431 与 Rust 入门课 cs220、编译原理课 CS420 都出自 KAIST 的同一教学团队（Jeehoon Kang 及其领导的 Concurrency and Parallelism Laboratory），可见这是一整套以 Rust 贯穿“入门 → 并发 → 编译器”的成体系课程。也正因如此，CS431 讨论并发时不会停留在 API 层面，而会深入到与 Rust 所有权、借用、原子操作深度耦合的实现细节。

从先修要求“Rust 编程基础与对并发的初步了解”可以看出它的承接关系：它假定你已经写过足够多的 Rust 代码，并且至少知道线程、锁是什么，随后才带你走向系统级的并发实现。

课程的双线结构：理论建模 + 实践读码

cs431 导读对课程内容给出了清晰的概括——分为理论与实践两部分，这也是理解全课的一把钥匙。

理论线：建立“并发情形下的编程模型”

导读明确指出，理论部分“聚焦于建立并发情形下的编程模型”。这里要区分两个层次：

• 应用层：知道怎么创建线程、怎么加锁、怎么避免死锁，这是大多数并发入门课程的内容；
• 模型层：为并发程序建立一个能精确推理“读到什么值、按什么顺序发生”的形式化框架，这是 CS431 的落点。

导读中特别点出了两个关键词，恰好对应模型层的两大主题：

• 访存模型（memory model）：在多线程共享内存的场景下，由于编译器和 CPU 都会对指令做重排与缓存优化，一个线程的写入何时、以怎样的顺序对其他线程可见，并不像直觉那样“先写的一定先被读到”。访存模型就是回答这些问题的一整套规则。
• promising semantics：一种面向并发编程语言的内存模型形式化方法，它允许底层（编译器、硬件）保留充分的优化空间，同时仍能为程序员提供可预测、可推理的行为语义，属于并发语义研究的前沿话题。

导读作者的原话也印证了这门课的理论深度：“我所知晓的关于自旋锁、互斥锁的知识在该门课程中都是最基础的”。也就是说，课程默认你已经掌握自旋锁、互斥锁这类“使用级”知识，理论部分会沿着访存模型一路推进到这些最基础工具背后的语义依据。

实践线：理解 Rust 库中锁与无锁数据结构的实现原理

如果说理论线是“建模”，实践线就是“拆解”。导读将其概括为：实践部分“主要是理解 Rust 相关库中锁与无锁数据结构的实现原理”。

这条实践线把 Rust 在并发上的独特优势用到了极致：Rust 的原子类型、所有权与生命周期约束，使得并发数据结构不仅能跑，还能在编译期就排除数据竞争。相应地，实践内容会触及：

• 一把 Mutex/自旋锁在底层是如何用原子指令与操作系统机制拼装出来的；
• 原子操作的**内存序（memory ordering）**如何影响可见性与正确性；
• 无锁（lock-free）结构如何在不使用锁的前提下，仅凭原子读改写（如 CAS/compare_exchange）保证并发安全。

理论建模与实践读码互为印证：没有模型，你无法解释“为什么这里用 Acquire 而不是 SeqCst”；没有代码，模型又只是空中楼阁。

作业阶梯：从“基于锁”到“无锁”，再到 hazard pointer

导读对作业的评价非常到位——“代码量不大但并不简单”。这类作业不会要求你写几千行代码，但每一道都需要想清楚正确性与性能的权衡，适合精读。导读给出了清晰的内容脉络：

从基于锁的并发安全缓存设计和链表，到无锁的哈希表和著名的 hazard pointer。

这实际上是一条设计精妙的进阶阶梯，从易到难依次是：

第一阶：基于锁的并发安全缓存

用锁保护一个共享缓存（典型的键值存储结构），让多线程可以安全地并发读写。它要处理的核心问题包括：

• 锁的粒度：是整张表一把大锁（粗粒度），还是分段/分桶多把锁（细粒度）；
• 读多写少时如何用读写锁提升吞吐；
• Rust 特有的**锁中毒（poisoning）**语义与 Guard 生命周期：如何在持有锁的线程 panic 后安全恢复，如何在不违背借用规则的前提下向外返回数据。

第二阶：基于锁的并发安全链表

链表比缓存更“吃”锁的设计能力。常见要权衡的点包括：

• 粗粒度锁（整条链表一把锁）实现简单但并发度低；
• 细粒度锁（每个节点一把锁）需要按固定顺序（如从头到尾）加锁以避免死锁；
• 遍历时持有锁与借用的交互，往往是 Rust 所有权检查最容易卡壳的地方。

第三阶：无锁哈希表

这是从“有锁世界”跨入“无锁世界”的关键一跳。你要在不使用锁的前提下，用原子操作实现并发安全的哈希表，核心难题包括：

• 用 CAS/compare_exchange 实现插入与删除的原子更新，冲突时如何重试；
• 如何为各原子操作挑选正确内存序，既保证正确性又不至于性能退化；
• 哈希表扩容时如何让并发访问与搬迁过程共存。

第四阶：hazard pointer（危险指针）

hazard pointer 是著名的无锁内存回收技术，导读将其作业来源关联到一篇标志性论文（对应 IEEE 1291819 文献）。无锁结构面临一个棘手问题：某线程删除一个节点后，另一线程可能仍持有指向该节点的指针正要访问它，若直接释放就会造成悬垂访问（use-after-free），而教科书式的引用计数又与无锁的“无等待/无阻塞”目标冲突。hazard pointer 的思路是：

1. 每个线程维护一组公开可见的“危险指针”槽位；
2. 线程在解引用某节点之前，先把该节点地址发布到自己的危险指针槽位；
3. 任何线程想要回收节点前，先检查是否有其他线程的危险指针仍指向它，若有则延迟回收。

由此，回收线程可以安全地判断“现在没人会碰这个节点了”，从而在不阻塞读者线程的前提下完成内存回收。作为无锁数据结构的最后一块拼图，这一阶把课程推向真正的系统级并发前沿。

作业的本地测试：自学友好度的关键

导读特别强调，这些作业“质量较高且配有详细的本地测试，适合自学”。对自学者而言这意味着：

• 有明确的验收标准：跑过本地测试即代表你的实现满足课程预期的正确性约束，不需要依赖人工评审；
• 可以迭代式学习：先跑测试理解期望行为，再动手实现，用测试驱动自己逼近正确设计；
• 遇到难题时有据可查：测试本身往往揭示了数据结构在并发下的不变量。

这也是本仓库将它推荐给自学者的重要原因——课程源码需在课程官方渠道获取，但配合本地测试，完全可以在无人讲解的环境下独立完成。

难度评估与前置准备：想清楚再投入 50 小时

课程难度四星、预计 50 小时，结合导读作者“比我预想的要深入得多”的评价，建议在开始前做好两件事：

1. 夯实 Rust 语言基础。 本仓库 Rust 目录下的课程可为 CS431 铺路：

• cs220：同一教学团队的 Rust 入门课，习题系统完善，可作为“Rust 习题课”练手，其导读明确推荐将其用于补足 Rust 熟练度；
• CS110L：Stanford 的 Rust 系统编程课，后半部分系统讲解多进程、多线程、事件驱动等并发技术，适合先建立“Rust 版”的并发直觉；
• CS420：同一实验室的 Rust 编译器课，其先修要求同样包含 Rust 编程基础，若你对 Rust 系统编程感兴趣，可放在 CS431 之后或与之并行，形成知识闭环。

2. 提前接触“并发基础”概念。 先修要求明确写着“对并发的初步了解”，建议至少能说清：什么是线程/锁、死锁如何产生、原子操作与竞态的关系。仓库内其他课程页也可以作为背景阅读，例如 NJUOS 导读 中“把并发程序视为状态机”的视角，就能为理解并发程序的行为提供很好的直觉模型。

课程资源与自学路线建议

cs431 导读页列出了完整的官方资源清单，按原文档整理如下（资源链接见 cs431.md 课程资源一节）：

• 课程网站：官方主页，位于 GitHub 上的 kaist-cp/cs431 仓库，包含课程介绍、讲义与作业的组织结构；
• 课程视频：官方录像播放列表，适合自学时对照课程节奏推进；
• 课程教材：官方课件 Slides，是理论部分“并发编程模型”的核心学习材料；
• 课程作业：位于课程仓库 homework 目录下的作业源码与本地测试，即上文作业阶梯对应的实战部分。

在此基础上，给自学者一条可执行的推进顺序建议：

1. 先读讲义再做题：以官方 Slides 为主线建立“模型层”认知，作业中的每道题都回到讲义找它的理论依据；
2. 以测试为准绳：每完成一个阶段就运行本地测试校验，先保证正确性，再考虑性能与锁粒度；
3. 顺着阶梯进阶：严格按照“基于锁的缓存 → 基于锁的链表 → 无锁哈希表 → hazard pointer”的顺序推进，因为每一阶都复用上一阶的概念与教训；
4. 把“为什么”当作验收标准：学完后应能回答——为什么这里需要特定的内存序、为什么无锁结构仍要解决内存回收、访存模型如何决定了这些选择的边界。

总的来说，CS431 是仓库 Rust 学习路线中少见地兼顾“并发理论建模”与“Rust 系统级实现”的课程。如果你已经具备 Rust 基础、渴望理解并发背后“为什么”的机制，并且愿意投入约 50 小时啃下从锁到无锁数据结构的完整链条，那么这门课程会像导读作者所说的那样，让你对并发和 Rust 都建立远超预期的理解。