并发数据结构的关键点

• 安全性： 安全是并发程序对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语句前面。

标准库中的并发API

Rust 标准库中基于锁的 API 主要围绕几个核心原语构建，这些原语提供了不同级别的并发控制和用途。它们都包含在 std::sync 模块中。以下是一些最常用的基于锁的 API：

1. std::sync::Mutex<T> (互斥锁)
   • 用途： 最常见的互斥锁，用于保护共享数据，确保一次只有一个线程可以访问该数据。
   • 特点：
     • 当线程尝试获取已被锁定的 Mutex 时，它会阻塞直到锁被释放。
     • 提供内部可变性（&T -> &mut T）通过 RAII (Resource Acquisition Is Initialization) 机制，即 MutexGuard。当 MutexGuard 离开作用域时，锁会自动释放。
     • 是“poisoning”感知的：如果持有锁的线程在锁被释放前发生 panic，Mutex 会被标记为 poisoned。后续尝试获取锁的线程会得到一个 PoisonError，其中包含原始的 MutexGuard，允许它们决定如何处理被中断的数据。
   • 何时使用： 当你需要独占访问某个共享资源时，例如全局计数器、数据结构或配置设置。
2. std::sync::RwLock<T> (读写锁)
   • 用途： 允许多个读取者同时访问共享数据，但只允许一个写入者独占访问数据。
   • 特点：
     • 读取者（read()）： 允许多个线程并行获取读锁。只要没有写入者持有锁，所有读锁请求都会成功。
     • 写入者（write()）： 只允许一个线程获取写锁。当有写入者持有锁时，所有读锁和写锁请求都会阻塞。
     • 也提供 RAII 机制，通过 RwLockReadGuard 和 RwLockWriteGuard。
     • 同样是“poisoning”感知的。
   • 何时使用： 当你的数据被频繁读取但很少写入时，RwLock 可以提供比 Mutex 更好的并发性能。例如，一个缓存系统或一个配置对象。
3. std::sync::Once (只运行一次)
   • 用途： 确保某个代码块（一个初始化函数）在程序生命周期中只被执行一次，即使有多个线程同时尝试触发它。
   • 特点：
     • call_once() 方法会执行一个闭包。第一次调用会实际执行闭包，后续的调用会等待第一次调用完成，但不会再次执行闭包。
     • 通常用于惰性初始化全局数据或单例模式。
   • 何时使用： 初始化全局静态变量（例如日志系统、配置加载器）或实现单例模式。通常与 lazy_static crate (在稳定版 Rust 中) 或 std::sync::OnceLock (在 1.70+ 版本中，见下文) 结合使用。
4. std::sync::Barrier (屏障)
   • 用途： 用于同步一组线程，确保所有线程都到达某个预定义点后才能继续执行。
   • 特点：
     • 通过 wait() 方法实现等待。当调用 wait() 的线程数量达到预设值时，所有等待的线程都会同时被释放。
     • wait() 返回一个 BarrierWaitResult，指示当前线程是否是最后一个到达屏障的。
   • 何时使用： 需要协调多个并行任务的执行，例如在某个阶段结束后开始下一阶段，或者在所有子任务完成后进行汇总。

Rust 1.70+ 中引入的更现代的基于锁的 API：