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：

• https://rsms.me/wasm-intro
• https://hacks.mozilla.org/2017/02/a-cartoon-intro-to-webassembly/

Wasm 的历史发展

早期（Wasm MVP - 2017）

• 诞生背景： Wasm 的设计目标是为了替代 asm.js，提供更小、更快、更安全的 Web 二进制格式。
• 核心模块的初步定义： MVP（Minimum Viable Product）阶段定义了 Wasm Core Module 的基本结构：函数、内存、表、导入、导出、全局变量等。
• 主要用例： 游戏引擎、音视频编解码、计算密集型任务等。
• 限制：
  • 没有模块化系统： 模块之间没有标准的链接机制，只能通过宿主环境（如 JavaScript）进行协调。
  • 缺乏垃圾回收（GC）： 需要手动内存管理或使用语言自带的 GC 机制（如 Emscripten 的 mimalloc）。
  • 没有线程： 无法直接利用多核 CPU。
  • 没有宿主 API 标准化： 模块与宿主环境的交互方式高度依赖宿主（如浏览器），没有统一的接口定义。
  • 没有组件模型： 模块重用和组合非常困难。

中期（MVP 之后 - 持续演进）

Wasm 社区和工作组认识到 MVP 的局限性，并开始着手扩展 Wasm 的能力，这直接影响了 Core Module 的能力：

• 多值（Multiple Returns & Parameters）： 允许函数返回多个值，接收多个参数，提高表达能力。
• 引用类型（Reference Types）： 引入了 externref 和 funcref，允许 Wasm 直接引用宿主对象和函数，而无需通过数字 ID 传递，为未来的 GC 和组件模型打下基础。
• 固定大小的 SIMD（Fixed-width SIMD）： 引入了新的指令集，允许在 Wasm 中进行向量化操作，进一步提升某些计算密集型任务的性能。
• 线程（Threads）： 引入了共享内存和原子操作，允许 Wasm 模块在多线程环境下运行，极大地提升了并行计算能力。
• 内存增长和限制（Memory Growth and Limits）： 提供了更灵活的内存管理机制。
• Tail Calls（尾调用）： 优化了函数调用的性能。

近期和未来（Wasm Component Model）

这是 Wasm 发展中最重要的方向之一，旨在解决 Core Module 在模块化和互操作性方面的根本性问题：