CS149 笔记：Locks、Fine-grained Synchronization 与 Lock-free Programming
这一讲关注的重点不是“怎样写出一个能工作的锁”，而是共享数据结构在并发访问时如何兼顾正确性、进度与性能。课程从锁可能引起的进度问题出发，逐步讨论锁的实现、细粒度同步，以及不依赖锁的并发算法。
并发程序的三类进度问题
Deadlock 表示系统仍有未完成的操作，但所有相关线程都无法继续推进。死锁出现需要同时满足四个条件：互斥、持有并等待、不可抢占和循环等待。工程上只要主动破坏其中任意一个条件，就能避免对应的死锁。
死锁的本质是资源依赖形成闭环。固定的加锁顺序之所以有效，是因为它直接消除了循环等待。
Livelock 中线程仍在不断执行，但操作持续撤销、重试或互相让步，没有线程取得有效进展。它与死锁的区别在于系统并未停住，只是做的工作没有产生结果。
Starvation 表示系统整体仍在前进，但某个线程长期得不到资源。它主要是公平性问题，不一定会破坏系统级正确性。
锁的实现与性能
锁的竞争过程依赖原子 read-modify-write 指令。Test-and-set 能以原子方式读取并占有锁，但等待线程反复执行原子写，会持续请求锁所在 cache line 的独占权，引发大量失效和 coherence traffic。 Test-and-test-and-set 先使用普通读在本地缓存上等待，只在发现锁可能空闲时执行 test-and-set。它减少了锁被占用期间的互连流量，但解锁后多个等待者仍可能同时竞争，而且没有提供公平性保证。 注意这里的T&S是不可分割的原子操作，因为我们要保证lock的正确性所以必须使用的是读写权限 Ticket lock 为线程分配递增序号，并按照序号顺序交接锁。它改善了公平性，也避免所有线程无序争抢，但等待者仍会共同观察同一个服务计数器，因此没有彻底消除缓存通信。
评价锁不能只看无竞争时的获取速度，还要同时考虑互连流量、核心数增加后的扩展性、存储开销与公平性。锁的正确性相同，运行表现可能完全不同。
原子操作是同步的基础
**Compare-and-swap（CAS）**会原子地比较内存中的值与期望值，只有两者相同时才写入新值。它既能实现锁，也能作为无锁算法提交修改的条件：只有共享状态仍与先前观察一致时，修改才会生效。
**Load-linked / store-conditional（LL/SC）**把操作拆成关联读取和条件写入。如果两者之间目标位置被其他处理器修改，条件写入就会失败。它与 CAS 的表达方式不同，但都能检测并发修改。
C++11 的 atomic<T> 把原子读写、原子 read-modify-write 和内存顺序放进统一接口。默认顺序是 sequential consistency，也可以通过 std::memory_order 指定更弱的 ordering。这个接口并不保证所有类型都由硬件无锁实现，复杂类型仍可能在底层使用互斥机制。是否“原子”与前后操作如何排序是两个维度，不能因为使用了 CAS 就忽略内存可见性。
从粗粒度锁到细粒度锁
为整个数据结构设置一个全局锁最容易保证正确性，但所有操作都会被串行化。即使两个线程访问互不相关的区域，也无法并行执行。
细粒度锁把保护范围缩小到数据结构的局部。Hand-over-hand locking 在遍历时先取得下一个节点的锁，再释放当前节点的锁，使线程可以同时操作不同区域。
更细的锁粒度通常意味着更低的竞争和更高的潜在并行度，同时也带来更多锁对象、更多加解锁开销和更复杂的正确性证明。锁的获取顺序若设计不一致，还会重新引入死锁。
Lock-free 的真正含义
使用锁的算法属于 blocking algorithm：如果持锁线程被暂停、发生缺页或崩溃，其他线程可能无法完成操作。
Lock-free 是一种系统级进度保证：无论线程怎样交错执行，总有某个线程能够在有限步骤内取得进展。某个线程操作失败，通常意味着另一个线程已经成功改变了共享状态，因此系统整体仍在前进。
Lock-free 不等于每个线程都能及时完成。它保证的是系统整体进度，单个线程仍可能不断重试并发生 starvation。
无锁数据结构通常采用乐观更新：先读取共享状态，在私有位置准备修改，再通过 CAS 验证状态是否仍未变化并提交结果。如果验证失败就重新读取和计算。它不需要长期占有数据结构的一部分，但竞争激烈时 CAS 会频繁失败，因此 lock-free 并不等于没有竞争或没有自旋。
ABA 与内存回收
CAS 只比较当前位模式是否与旧值相同。如果共享指针从 A 变成其他值后又回到 A，CAS 可能误以为结构从未变化，这就是 ABA problem。节点地址相同并不代表链表或栈仍处于原来的逻辑状态。
常见应对方式是把指针与递增版本号一起比较，使用 double-wide CAS 同时更新二者，或者通过节点复用策略避免地址过早重新出现。
无锁结构还有更棘手的生命周期问题：线程读取一个节点指针后，另一个线程可能把节点移除并释放，前者随后访问的就是失效内存。
Hazard pointer 让线程公开自己正在访问的节点。被移除的节点先进入延迟回收列表，只有确认没有 hazard pointer 指向它时才能真正释放。它说明无锁算法的难点不只在原子更新，还在于安全地管理对象生命周期。
Lock-free 不一定更快
细粒度锁和 lock-free 都在尝试减少全局串行化，但代价不同。锁会受到持锁线程暂停、priority inversion 和 lock convoy 等问题影响；无锁算法则需要承担 CAS 重试、额外元数据、内存回收和更复杂的正确性成本。
在独占机器、线程数稳定且临界区设计良好的场景中，基于锁的实现可能与 lock-free 一样快，甚至更快。Lock-free 更突出的价值是避免单个暂停线程阻塞整个系统，而不是提供无条件的性能优势。
同时，无锁实现仍然运行在 relaxed memory consistency 硬件上。原子状态转换之外，还必须使用正确的 acquire、release 或 fence，保证数据初始化与指针发布之间具有所需的可见顺序。
这节课的主线
粗粒度锁用简单性换取串行化，细粒度锁通过缩小保护范围增加并行度，lock-free 则不再让线程持有会阻塞全局进度的资源。同步方式越灵活，正确性、内存顺序和对象生命周期也越难推理。
这节课真正建立的认识是：并发数据结构的设计目标不只是互斥，还包括进度保证、缓存通信、公平性与安全回收。