rust 2024年12月28日

Rust Atomics and Locks

Rust 并发编程内幕

Rust Atomics and Locks

作者：Mara Bos 出版日期：2022-12-14 出版社：O'Reilly Media, Inc.

该书旨在帮助Rust程序员理解底层并发编程，涵盖了原子操作、内存排序、锁的实现（包括互斥锁和读写锁）以及操作系统相关的并发原语。书中包含大量Rust代码示例，并解释了不同处理器架构（x86-64和ARM64）的底层细节，以及缓存一致性对并发性能的影响。

前言

本书作者 Mara Bos 在 Rust 标准库团队工作，并有多年并发实时系统开发经验。
本书的重点是 Rust 中 底层的并发 实现，而不是高级的抽象。
本书适合那些对并发编程的底层机制感兴趣的读者，例如原子操作、锁、内存排序等.
本书通过从零开始构建各种并发原语，来深入理解其工作原理.
本书的写作灵感来源于 Rust 社区关于并发的讨论，作者希望通过实践来深入理解软件安全特性.

本书目录列出了主要章节，包括原子操作、自旋锁、通道、Arc 智能指针、锁、条件变量等主题.
- 第一章：Rust 并发基础
- 第二章：原子操作
- 第三章：内存排序
- 第四章：构建自己的自旋锁
- 第五章：构建自己的通道
- 第六章：构建自己的"Arc"
- 第七章：理解处理器
- 第八章：Linux Futex
- 第九章：构建自己的锁

第一章：Rust 并发基础

本章介绍了 Rust 并发编程的基础概念，包括线程、Send 和 Sync Trait.
- Send Trait 表示类型可以安全地在线程之间转移所有权. 例如 Arc<i32> 是 Send 的，但 Rc<i32> 不是.
- Sync Trait 表示类型可以安全地在线程之间共享引用. 例如 i32 是 Sync 的，但 Cell<i32> 不是.
- 自动 Trait：Send 和 Sync 是自动 Trait，如果结构体中的所有字段都满足 Send 和 Sync，则该结构体本身也满足. 可以通过添加 PhantomData 字段来选择不实现这些 trait.
- 静态变量：静态变量的生命周期是整个程序，多个线程可以同时借用静态变量.
```
static X: [i32; 3] =;
thread::spawn(|| dbg!(&X));
thread::spawn(|| dbg!(&X));
```
- 内部可变性：Cell 和 RefCell 允许通过不可变引用进行修改.
  - Cell 仅适用于单线程，只能整体替换值，或者复制值（如果类型实现 Copy）.
  - RefCell 在运行时检查借用规则，允许多个共享借用或一个独占借用.
- Mutex 和 RwLock: Mutex 和 RwLock 是多线程环境下的可变性类型.
  - Mutex 允许独占访问.
  - RwLock 允许多个读者同时访问，或者一个写者独占访问.
- 原子类型：原子类型是多线程环境下的 Cell. * 通过复制的方式写入和读取，避免数据竞争.
- 线程停车：线程停车是一种等待条件满足的机制. * Condvar（条件变量）用于等待 Mutex 保护的数据上的条件，比线程停车更方便和高效.
本章还讨论了 共享所有权 和 引用计数 (例如 Arc)，以及如何使用 thread::scope 创建 作用域线程.

第二章：原子操作

本章深入探讨了 原子操作，这是并发编程的基石.
- 原子性：原子操作是不可分割的操作，要么完全完成，要么完全不发生.
- AtomicI32：本章以 AtomicI32 为例，介绍了原子类型的基本操作.
  - load：原子加载操作，读取原子变量的值.
  - store：原子存储操作，向原子变量写入新值.
```
impl AtomicI32 {
    pub fn load(&self, ordering: Ordering) -> i32;
    pub fn store(&self, value: i32, ordering: Ordering);
}
```
- fetch_add， fetch_sub 等：原子获取并修改操作，例如原子加法，减法，按位或等.
  impl AtomicI32 { pub fn fetch_add(&self, v: i32, ordering: Ordering) -> i32; }
- compare_exchange：原子比较和交换操作，只有当原子变量的值等于预期值时，才将其替换为新值.
  impl AtomicI32 { pub fn compare_exchange(&self, expected: i32, new: i32) -> Result<i32, i32>; }
  - 此操作返回之前的值，以及是否进行了替换.
- 使用场景：
  - 自增计数器：通过 fetch_add 来实现.
  - 懒加载：使用 compare_exchange 初始化变量，避免重复初始化.
内存排序：本章开始介绍了内存排序的概念，原子操作的内存排序参数决定了其在不同线程之间的可见性.

第三章：内存排序

本章详细介绍了 内存排序 的概念，以及如何在并发程序中保证数据的一致性.
- happens-before 关系：happens-before 关系定义了操作之间的顺序.
  - 在同一个线程内的操作，按照代码顺序执行，构成 happens-before 关系.
  - 线程的 spawn 和 join 操作也会建立 happens-before 关系.
  - 互斥锁 的加锁和解锁操作会建立 happens-before 关系.
  - 使用 非 Relaxed 内存排序的原子操作 会建立 happens-before 关系.
- Relaxed 内存排序：最基本的内存排序，不建立跨线程的 happens-before 关系，只保证单个原子变量的修改顺序在所有线程中是一致的.
  - 使用 Relaxed 排序的原子操作，可能导致不同的线程看到不一致的数据状态.
- Release 和 Acquire 内存排序：用于同步线程之间的数据，建立 happens-before 关系.
  - Release 存储操作保证该操作之前的写入对其他线程可见.
  - Acquire 加载操作保证该操作之后的操作能看到其他线程的写入.
  - Release 和 Acquire 通常配对使用，例如，解锁操作使用 Release，加锁操作使用 Acquire.
  - 当一个 Acquire 加载操作观察到一个 Release 存储操作的结果时，会形成一个 happens-before 关系.
- SeqCst 内存排序：最强的内存排序，保证所有操作的全局一致性.
- Fences：内存屏障，用于显式地插入内存排序.
  - Release 存储操作可以分解为 Release 内存屏障和 Relaxed 存储操作.
  - Acquire 加载操作可以分解为 Relaxed 加载操作和 Acquire 内存屏障.
本章还通过实例，讲解了如何使用内存排序来解决并发编程中的常见问题，例如 懒初始化 和 锁的实现.

第四章：构建自己的自旋锁

本章从零开始构建了一个 自旋锁，学习如何使用原子操作来实现锁.
- 自旋锁：一种忙等待锁，当锁被占用时，线程会不断循环检查锁是否可用.
- 最小实现：自旋锁可以使用一个原子布尔变量来实现，用 swap 获取锁，用 store 释放锁.
```
   pub struct SpinLock {
       locked: AtomicBool,
   }
   impl SpinLock {
       pub fn lock(&self) {
         while self.locked.swap(true, Acquire) {
           std::hint::spin_loop();
         }
       }
       pub fn unlock(&self) {
         self.locked.store(false, Release);
       }
   }
```
- 安全接口：通过使用 UnsafeCell 和 LockGuard 来提供安全的接口.
  - UnsafeCell 用于封装可变数据.
  - LockGuard 在 Drop 时自动释放锁.
  - Deref 和 DerefMut Trait 用于实现类似引用的行为.
- 自旋锁适合于 短时间持有的锁，避免上下文切换的开销.

第五章：构建自己的通道

本章从零开始构建了一个 单次发送通道，学习如何在线程之间传递消息.
- 通道：用于在线程之间传递消息的机制.
- Mutex 和 Condvar 实现：简单的通道可以使用 Mutex 和 Condvar 来实现，但是效率可能不高.
- 单次发送通道：只能发送一次消息的通道.
  - 使用 UnsafeCell 和 AtomicBool 来存储和同步消息.
  - MaybeUninit<T> 用于表示未初始化的数据.
  - 通过使用 Release 和 Acquire 内存排序来同步发送和接收操作.
- 运行时检查：通过运行时检查来保证通道的安全性，例如，避免多次发送或多次接收.
- 使用单原子变量表示状态：可以使用单个 AtomicU8 来表示通道的多种状态，节省内存.
- 通过类型系统实现安全：通过类型系统来实现通道的安全性，例如，使用 Sender 和 Receiver 类型，避免多次发送或多次接收.
- 通过借用来避免分配：通过借用机制，避免通道的额外内存分配.
本章演示了如何在 Rust 中使用各种技巧来实现并发编程的安全性和效率，同时提供了不同设计决策之间的权衡.

第六章：构建自己的 “Arc”

本章从零开始构建了一个类似于 std::sync::Arc 的 原子引用计数智能指针，学习如何管理共享所有权.
- Arc：允许多个所有者共享同一块内存，直到所有所有者都释放.
- 手动管理所有权：使用 NonNull 来表示非空指针.
- Send 和 Sync 的实现： Arc<T> 只有在 T 同时实现 Send 和 Sync 时，才是 Send 和 Sync 的.
- 引用计数：使用原子变量来维护引用计数.
- Weak 指针：弱引用指针，不增加引用计数，可以避免循环引用.
  - 使用 compare_exchange 来升级弱指针到强指针.
- 性能优化：
  - 通过减少原子操作，优化克隆操作的性能.
  - 通过使用 ManuallyDrop 来减少内存占用.
  - 通过 “锁定” 弱指针计数器来避免竞争条件.
- 可变性：get_mut 方法用于获取独占引用，前提是只剩下一个 Arc.

第七章：理解处理器

本章深入探讨了 处理器 的工作原理，以及如何影响并发程序的性能.
- 指令集：本章介绍了 x86-64 和 ARM64 指令集中的一些指令，包括原子操作和内存屏障.
  - x86-64: mov、add、cmpxchg、lock prefix, mfence.
  - ARM64: ldxr, stxr, cas.
- 缓存一致性：本章介绍了缓存一致性的概念，以及 MESI 协议.
  - MESI：修改 (Modified)、独占 (Exclusive)、共享 (Shared) 和无效 (Invalid) 状态.
- 缓存行：本章解释了缓存行的概念，以及 伪共享 的问题.
  - 伪共享：当多个线程访问位于同一缓存行的数据时，会导致性能下降.
  - 可以使用 #[repr(align(64))] 来避免伪共享.
- 内存排序：展示了不同的内存排序在汇编代码上的区别.
本章的目的是让读者理解底层硬件如何影响并发程序，从而编写更高效的代码.

第八章：Linux Futex

本章介绍了 Linux 中的 futex 系统调用，这是实现许多并发原语的基础.
- futex：快速用户空间互斥量 (fast userspace mutex)，用于实现用户空间的同步原语.
- futex 操作： * FUTEX_WAIT：等待原子变量的值变为指定值. * FUTEX_WAKE：唤醒等待在原子变量上的线程. * FUTEX_REQUEUE：唤醒一些线程，并将其他线程重新排队到另一个原子变量. * FUTEX_CMP_REQUEUE：原子比较并重排队列.
- 线程停车：Linux 中的线程停车机制使用一个原子变量来表示线程的状态.
本章旨在让读者了解 Linux 中底层的同步机制，以便更好地理解并发原语的实现.

第九章：构建自己的锁

本章从零开始构建了自己的 互斥锁， 条件变量 和 读者-写者锁，学习如何使用 futex 或类似的平台 API 实现锁机制.
- 互斥锁 (Mutex):
  - 使用 AtomicU32 来表示锁的状态，0 表示解锁，1 表示锁定.
  - 使用 wait 和 wake_one 来实现阻塞和唤醒.
  - 使用 compare_exchange 来获取锁.
  - 优化：通过在 wait 前进行自旋，减少系统调用的开销.
- 条件变量 (Condvar):
  - 使用一个额外的原子计数器 num_waiters 来优化唤醒操作，只唤醒需要唤醒的线程.
- 读者-写者锁 (RwLock):
  - 允许多个读者同时访问，但只允许一个写者独占访问.
  - 使用 AtomicU32 来表示锁的状态，并通过比较和交换操作来获取锁.
  - 使用 wait 和 wake_all 来实现阻塞和唤醒.
  - 优化：通过使用两个原子变量 state 和 writer_wake_counter 来优化唤醒操作.
  - 通过使用奇数和偶数来区分读者和写者，优化了读取效率.
本章展示了如何通过使用原子操作和系统调用来构建复杂的同步原语.

总结

本书涵盖了 Rust 并发编程的底层知识，从原子操作到高级同步原语，通过实践来深入理解并发编程.
本书强调了 内存排序 和 缓存一致性 的重要性.
本书不仅讲解了理论，还提供了大量的代码示例和实现细节.
本书强调，每个设计决策都存在权衡，需要根据具体用例进行选择.