无锁数据结构和传统的数据结构在内存管理有一点区别是：当数据不用了，需要释放内存时，传统数据结构直接调用free()就可以了，但是无锁数据结构不行。举个例子，如下图所示，T1正在读取b1的时候，T2释放了b1，T1中的指针就变成了野指针，造成不安全的内存访问。

因此，在无锁数据结构中，内存的释放操作一般要延后执行，即保证没有线程能够访问到该片内存后，再执行内存回收。这种方式被称作Safe Memory Reclamation（SMR）。

从上述例子中，我们可以从两个方面去理解一个SMR算法：

1. 如何保护正在使用的数据不被释放？
2. 什么时候能安全地释放已经被标记为需要释放的内存？

下面介绍两种常用的SMR算法：

1. Hazard Pointers（Protected Pointers）
2. Epoch-Based Reclamation（基于代际的内存释放）

Hazard Pointers

Hazard Pointers的基本思想是线程访问数据块时会将指针记录下来，其它线程尝试释放内存时会感知到数据块引用的存在，从而延迟释放内存，直到所有线程对该数据块的访问结束。

如上图所示，使用hazard pointers有如下几个步骤：

1. 在线程访问共享数据时，先调用reserve()方法，将指针记录在一个list内；
2. T2线程尝试释放释放b1时，调用retire()，因为检测到还有线程访问b1，延迟释放内存；
3. 因为内存没有真正释放，T1能在b1 retire后继续访问b1。访问结束后，T1调用unreserve()将指针从list中移除；
4. T3调用gc()（可以周期性运行，也可以事件触发），遍历所有retired的数据块，如果list内没有指向数据块的指针，即可以真正回收内存。

Hazard Pointers有些致命的缺点：

1. 不够快。因为reserve()保护的指针需要立即被gc()感知到，所以，两个函数都需要引入开销非常大的store-load fence。在遍历整个数据结构时，每个数据块都会调用reserve()，导致遍历效率降低；
2. 并不是所有的数据结构都适用Hazard Pointers。在前文的Lock-free Linked List中，我们也提过Harris-Michael‘s traversing是为了专门支持Hazard Pointers的。Harris’s traversing会retire一个连续的数据块，这样，即便T1线程保护了其中一个数据块，gc()仍然可以回收其它的数据块内存，T1线程访问next指针时，仍然会出现问题。

Epoch-Based Reclamation

Hazard Pointers只保护无锁数据结构中真正被访问的那部分数据，这也导致了上文中Hazard Pointers的两个缺陷。与Hazard Pointers不同的是，EBR保护的是数据结构中所有可能潜在的访问。这样也就不需要频繁地在线程间同步。

每个线程在访问数据结构前都会开启一个代际（epoch）。T1在代际e中retire了b1和b2。那么什么时候能安全地reclaim b1和b2的内存呢？

如上图，我们在这个EBR算法中规定了一个代际一致性规则：并发的代际之间最多只能相差1。也就是说，只要T1还没有调用set_quiescent()结束掉e代，那么其它线程通过set_active()开启的代际号只能是e+1。而所有的e+1代的线程是有可能引用到b1和b2的。当e代结束，T2开启e+2代时，因为e+2代和e代不存在同时发生的可能性（通过代际一致性规则保证），所以在e+2代是不可能访问到e代retire的b1和b2的。到了e+3代，表示所有可能访问到b1和b2的e+1代都已经结束，此时即可安全地回收b1和b2内存。

不同的代际一致性规则，可以安全回收的代际是不一样的。

并发数据结构的关键点

• 安全性： 安全是并发程序对CDS的最基本的要求
  • Sequential specification：多线程对数据结构的操作要能像一个队列一样
  • Synchronization：如在栈操作中，不同的线程进行pushing和popping操作时是要同步的，不能这边线程执行完了，另外一边无法感知到这边的操作。
  • 通过锁或者更加底层的同步原语来保护并发数据结构
• 可扩展性： 随着CPU核数/并发度的增长，有着良好的性能增长
  • 理想情况下，性能增长应该是线性的，但现实情况往往因为各种限制因素达不到线性增长
  • 通过减少锁保护范围（更细粒度的锁）来减少竞争
    • hand-over-hand locking, lock coupling, read-write locking
  • 通过避免写操作降低缓存失效
• Progress: guaranteeing the completion (or progress) of operations
  • Lock freedom: progress of at least one
  • Wait freedom: progress of everyone

无锁策略

Lock-Free 和 Wait-Free 都旨在解决传统锁（如互斥锁 mutex）带来的性能和活性问题，但采用了不同的策略和提供了不同的保证。

Lock-Free

Lock-Free 是一个相对较弱的保证，但仍然非常强大和有用。它的核心思想是：总会有一个线程能够前进，即使其他线程被任意延迟或阻塞。

核心特点：

• 没有死锁 (Deadlock-Free)： 由于没有线程需要等待其他线程释放锁，所以不会发生死锁。
• 没有活锁 (Livelock-Free)： 虽然有可能发生活锁（即线程反复尝试但总是失败），但通常通过回退策略（如指数退避）或设计良好的原子操作序列可以避免。然而，严格意义上的 Lock-Free 并不直接保证 Livelock-Free。
• 进度保证 (Progress Guarantee)： 只要系统不是完全停滞，总有一个或多个线程可以完成操作。这意味着整个系统的吞吐量不会因为某个线程的无限期暂停而归零。
• 饥饿可能 (Starvation Possible)： 某个特定的线程可能会无限期地重试它的操作，而从未成功（即所谓的“饥饿”）。这是 Lock-Free 与 Wait-Free 的一个主要区别。
• 实现方式： 主要依赖于原子操作，如CAS (Compare-And-Swap)，FAA (Fetch-And-Add)，LL/SC (Load-Link/Store-Conditional)等。这些操作通常由硬件提供，能够以原子方式读取、修改和写入内存位置，而无需使用操作系统级别的锁。
• 常见数据结构： 无锁队列 (Lock-Free Queue)，无锁栈 (Lock-Free Stack)，无锁哈希表 (Lock-Free Hash Table) 等。

工作原理示例（CAS）：

Naive Spin Lock

Naive Spin Lock的缺陷

• 无法保证公平性，可能有的倒霉蛋空转了一辈子也无法cas成功，无法做到按竞争线程先来后到的次序占有锁。
• 扩展性差，大量对同一内存区域的自旋引发性能问题。

对Naive Spin Lock的优化

关键思路：

• 通过release/acquire同步机制保证互斥量的排他性
  • 从一个临界区的结束（release）到另一个临界区的开始（acquire）
  • 在ticket lock里面是curr成员，CLH/MCS lock是每个waiter的一个新内存区域
• 通过排队和等待不同的区域释放保证公平性
  • 通过公平的指令来排队（如swap, fetch-and-add）
  • Ticket lock：通过next来排队，curr来等待锁
  • CLH/MCS lock：通过tail来排队，等待每个锁调用者申请的不同区域中值的变化来获取锁

Ticket Lock

ticket lock在锁的结构体里面新增了一个原子变量next，每次需要竞争锁时，需要先从next中拿到一个ticket，然后再去监听curr，只有curr被更新成当前的ticket值后，才能去占领锁。

优点

• 利用公平指令排队解决了公平性问题

缺点

• API相对较复杂（调用者感知ticket）（为什么不直接用curr+1？）
• 没有解决spinlock中所有线程监听同一个原子变量的问题

CLH Lock

为了减少缓存一致性带来的开销，CLH lock被发明了。CLH是三个人首字母的缩写：Craig, Landin, and Hagersten。

CLH lock给所有等待线程分配了一个Node，每个Node初始为true，在锁内维护一个链表，所有竞争锁的线程都会获取到前一个线程的Node，并将tail指针指向自己的Node。

不同于spin lock和Ticket lock，CLH lock的临界区是前一个Node中的原子变量。在锁释放时，当前线程会将自己的Node值置为false，而排队的下一个线程监听到这个变化，则可以安全地占有锁了。

优点

• 线程监听的不同临界区，减少缓存一致性的开销
• 链表排队，也能保证公平性

缺点

• O(n)的空间复杂度开销，n是临界区数目
• 每个线程都是在前驱节点的Node上自旋，如果跨NUMA会有性能问题

MCS Lock

MCS lock也是以三个人名命名的：John M. Mellor-Crummey and Michael L. Scott。MCS lock和LCH lock最大的不同是：CLH lock是在前驱节点上自旋，MCS则是在自己节点上自旋。

在CLH的Node结构里面，MCS又添加了一个next字段，新的线程竞争锁时，会将自己的Node添加到前驱节点的next字段中。

本章是基于作者的研究“Promising semantics”: https://sf.snu.ac.kr/promise-concurrency/ ，提出的一种对宽松内存（relaxed-memory）并发的建模方法。

主要观点有4个：

• modeling load hoisting w/ multi-valued memory
  • 允许一个线程从某个位置读取到一个旧值
• modeling read-modify-write w/ message adjacency
  • 禁止对单个值同时进行多个read-modify-write操作
• modeling coherence & ordering w/ views
  • 限制线程的行为
• modeling store hoisting w/ promises
  • Allowing a thread to speculatively write a value

个人理解，**即便是编译器/硬件的指令重排，也是需要遵循一定的规则的，不能随意乱排。**作者从值读取、存储、read-modify-write多种角度对线程的行为进行了建模，是为了解释哪些情况下出现多线程执行出现哪些结果是可能的，哪些是不被允许的。

hoisting load/store在网上没有搜到解释，但是有个gcc的优化提到了这个概念。大概意思时将存值/取值操作从原先的指令顺序中调整位置，优化执行效率。

Load/Store Hoisting - GNU Project

multi-value memory

内存是一系列消息（message）所在的位置，而消息可以看作是值和时间戳的组合。线程很有可能在读取时从内存中读到一个旧值。（effectively hoisting loads）

在作者举的例子中，r1=r2=0是被允许的，因为r1 r2都有可能从Y X中读到一个旧值。从后文的view角度理解，因为在独立的线程中，X和Y的赋值并没有改变当前线程中相应Y和X的view，所以，r1 r2的读取操作是可以读到旧值的。

message adjacency

上面说了，消息是值和时间戳范围的组合。read-modify-write操作修改了消息的值，在时间轴上应该和前值紧邻在一起（no gap）。

可以看到，两次fetch_add操作后，从X的视角上看，0、1、2是紧邻的。第二次fetch_add操作，只能紧贴着1操作，而不能插到0和1之间。

views

这个semantics对我是启发性最强的一章。

multi-valued memory允许了太多不在预期中的行为，因此我们需要做些限制，保证一致性和同步。

View分为三种，分别是：

• Per-thread view：一致性
• Per-message view：release/acquire同步
• Global view：SC同步

Per-thread view

Per-thread view表示线程对消息的确认。

Nondeterminism

thread interleaving

interleaving semantics： 将多线程的指令交替组合成好像是单线程执行一样。

不同线程间的Load/store指令是穿插执行的，导致最终的行为有多种多样的可能。

static COUNTER = AtomicUsize::new(0);
// thread A & B
let c = COUNTER.load();
COUNTER.store(c + 1);

如上示例，两个线程A和B同时对COUNTER进行+1操作，预期结果当然是2。但是由于线程调度的不确定性可能出现如下的执行顺序：

[COUNTER=0] A load, B load, A store, B store [COUNTER=1]

导致结果不符合预期。

解决方案

使用原子的reading & writing，禁止掉这种不符预期的执行顺序。

// thread A & B
let c = COUNTER.fetch_and_add(1);

• “Read-modify-write”, e.g. swap, compare-and-swap, fetch-and-add

reordering

同一个线程中的指令会因为硬件和编译器的优化发生指令重排。

DATA = 42;       ||   if FLAG.load() {
FLAG.store(1);   ||       assert(DATA == 42);
                 ||   }

如上图示例，预期是当FLAG.load()为1时，DATA == 42。但是因为指令重排，左边线程中，FLAG.store(1)可能发生在赋值语句前面；右边线程中assert语句也可能发生在if语句前面。