Skip to main content

第 10 章 思路与灵感（Ideas and Inspiration）

并发相关的话题、算法、数据结构、轶事，以及其他可能成为本书章节的内容，数量几乎是无限的。不过，我们已经来到最后一章，也差不多到了分别的时候。希望你带着一种对新可能性感到兴奋的心情离开，并准备好在实践中应用新的知识和技能。

最后这一章的目的，是通过展示一些可以自行学习、探索和构建的想法，为你自己的创造和未来工作提供灵感。

信号量（Semaphore）​

信号量本质上只是一个带有两个操作的计数器：signal（也称为 up 或 V）和 wait（也称为 down 或 P）。signal 操作会把计数器递增到某个最大值，而 wait 操作会递减计数器。如果计数器为零，wait 操作就会阻塞，等待匹配的 signal 操作，从而防止计数器变成负数。它是一个灵活的工具，可以用于实现其他同步原语。

信号量可以实现为一个用于计数器的 Mutex<u32> 与一个用于等待操作的 Condvar 的组合。不过，有几种方式可以更高效地实现它。最值得注意的是，在支持类 futex 操作的平台上，它可以更高效地实现为单个 AtomicU32，甚至 AtomicU8。

最大值为一的信号量有时被称为二值信号量，可以作为构建其他原语的基础构件。例如，把计数器初始化为一，用 wait 操作加锁，用 signal 操作解锁，它就可以作为互斥锁使用。把它初始化为零，它也可以像条件变量一样用于发信号。例如，std::thread 中标准的 park() 和 unpark() 函数，就可以实现为与线程关联的二值信号量上的 wait 和 signal 操作。

注意，互斥锁可以用信号量实现，而信号量又可以用互斥锁和条件变量实现。建议避免使用基于互斥锁的信号量来实现基于信号量的互斥锁，反过来也一样。

进一步阅读：

  • Wikipedia 上关于信号量的文章
  • Stanford University 关于信号量的课程笔记

RCU​

如果你想允许多个线程大多读取、偶尔修改某些数据，可以使用 RwLock。当这些数据只是单个整数时，可以使用原子变量（例如 AtomicU32）避免加锁，这样更高效。不过，对于较大的数据块，例如包含许多字段的结构体，并没有可用的原子类型能对整个对象执行无锁原子操作。

就像计算机科学中的其他问题一样，这个问题可以通过增加一层间接性来解决。你可以不用存储结构体本身，而是用原子变量存储指向它的指针。这仍然不能让你把整个结构体作为一个整体原子修改，但可以让你原子地替换整个结构体，这几乎同样有用。

这种模式常被称为 RCU，代表 read、copy、update，也就是替换数据所需的步骤。读取指针之后，可以把结构体复制到一个新的分配中，并在那里修改它，而不必担心其他线程。准备好之后，可以用 compare-and-exchange 操作更新原子指针。只有在此期间没有其他线程替换数据时，该操作才会成功。

RCU 模式最有趣的部分是最后一步，它并没有出现在缩写中：释放旧数据。成功更新后，如果其他线程在更新之前读取了指针，它们可能仍然在读取旧副本。你必须等待所有这些线程完成，才能释放旧副本。

这个问题有许多可能的解决方案，包括引用计数（如 Arc）、泄漏内存（忽略问题）、垃圾回收、hazard pointer（让线程告诉其他线程自己当前正在使用哪些指针的一种方式），以及静止状态跟踪（等待每个线程到达一个它肯定没有使用任何指针的位置）。最后一种在某些条件下可以极其高效。

Linux 内核中的许多数据结构都基于 RCU，并且有许多关于其实现细节的有趣演讲和文章，可以提供大量灵感。

进一步阅读：

  • Wikipedia 上关于 read-copy-update 模式的文章
  • LWN 文章 “What is RCU, Fundamentally?”

无锁链表（Lock-Free Linked List）​

在基础 RCU 模式之上，可以给结构体增加一个原子指针，指向下一个结构体，从而把它变成一个链表。这允许线程在不为每次更新复制整个链表的情况下，原子地向链表添加或移除元素。

要在链表开头插入一个新元素，只需要分配该元素，让它的指针指向链表中的第一个元素，然后原子地更新初始指针，让它指向新分配的元素。

类似地，移除一个元素可以通过原子地更新它前面的指针，让该指针指向它后面的元素来完成。不过，当涉及多个写者时，必须小心处理相邻元素上的并发插入或移除操作。否则，可能会意外地同时移除一个并发新插入的元素，或者撤销一个并发移除的元素。

为了保持简单，可以使用常规互斥锁避免并发修改。这样读取仍然是无锁操作，但你不必担心处理并发修改。

从链表中分离一个元素之后，会遇到和之前一样的问题：等待直到可以释放它，或者以其他方式重新取得所有权。我们为基础 RCU 模式讨论过的同样解决方案，也适用于这里。

一般来说，可以基于原子指针上的 compare-and-exchange 操作构建各种复杂的无锁数据结构，但始终需要一个良好的策略，用于释放分配或以其他方式重新取得所有权。

进一步阅读：

  • Wikipedia 上关于非阻塞链表的文章
  • LWN 文章 “Using RCU for Linked Lists--A Case Study”

基于队列的锁（Queue-Based Locks）​

对于大多数标准锁原语，操作系统内核会跟踪阻塞在其上的线程，并负责在被要求时选择一个线程唤醒。一个有趣的替代方案是，通过手动跟踪等待线程队列来实现互斥锁或其他锁原语。

这样的互斥锁可以实现为单个 AtomicPtr，指向一个等待线程列表。

列表中的每个元素都需要包含某种可用于唤醒对应线程的东西，例如 std::thread::Thread 对象。原子指针中一些未使用的位可以用于存储互斥锁本身的状态，以及管理队列状态所需的任何内容。

可能的变体很多。队列可以由自己的锁位保护，也可以实现为部分无锁结构。元素不必分配在堆上，也可以是等待线程的局部变量。队列可以是双向链表，不仅有指向下一个元素的指针，也有指向前一个元素的指针。第一个元素还可以包含指向最后一个元素的指针，以便高效地把元素追加到队尾。

这种模式允许仅使用某种能够阻塞并唤醒单个线程的东西（例如线程挂起）来实现高效锁原语。Windows SRW 锁就是用这种模式实现的。

进一步阅读：

  • Windows SRW 锁实现说明
  • 一个基于队列的锁的 Rust 实现

基于 Parking Lot 的锁（Parking Lot-Based Locks）​

要制作一个尽可能小的高效互斥锁，可以在基于队列的锁思路之上，把队列移入一个全局数据结构，只在互斥锁本身内部保留一两个位。这样互斥锁只需要单个字节。甚至可以把它放进指针的一些未使用位中，以几乎没有额外成本的方式实现非常细粒度的加锁。

这个全局数据结构可以是一个 HashMap，把内存地址映射到等待该地址处互斥锁的线程队列。这个全局数据结构通常称为 parking lot，因为它是一组已挂起线程的集合。

这种模式可以泛化：不仅跟踪互斥锁队列，也跟踪条件变量和其他原语的队列。通过为任意原子变量跟踪队列，这实际上提供了一种在没有原生支持的平台上实现类 futex 功能的方式。

这种模式最有名的来源是 WebKit 在 2015 年的实现，当时它用于锁定 JavaScript 对象。它的实现启发了其他实现，例如流行的 Rust parking_lot crate。

进一步阅读：

  • WebKit 博客文章 “Locking in WebKit”
  • parking_lot crate 文档

顺序锁（Sequence Lock）​

顺序锁是另一个不用传统阻塞锁就能原子更新较大数据的解决方案。它使用一个原子计数器：数据正在更新时计数器为奇数，数据准备好被读取时计数器为偶数。

写线程必须在修改数据之前把计数器从偶数递增为奇数，然后在修改完成后再次递增计数器，让它停留在另一个偶数值。

任意读线程都可以在任何时刻、无需阻塞地读取数据，方式是在读取数据前后各读取一次计数器。如果从计数器得到的两个值相等且为偶数，就说明没有并发修改，意味着你读到了数据的有效副本。否则，可能读到了正在被并发修改的数据，这时只需要重试。

这是一种很棒的模式，可以让其他线程读取数据，同时不会让读线程阻塞写线程。它常用于操作系统内核和许多嵌入式系统。由于读者只需要对内存的只读访问，而且不涉及指针，这可以成为一种很适合在进程之间的共享内存中安全使用的数据结构，而无需信任读者。

例如，Linux 内核使用这种模式，通过向进程提供对共享内存的只读访问，非常高效地向进程提供时间戳。

一个有趣的问题是它如何适配内存模型。对同一数据进行并发的非原子读取和写入会导致未定义行为，即使读取到的数据被忽略也是如此。这意味着严格来说，读取和写入数据都应该只使用原子操作完成，尽管整个读取或写入不必是单个原子操作。

进一步阅读：

  • Wikipedia 上关于 Linux Seqlock 的文章
  • Rust RFC 3301，AtomicPerByte
  • seqlock crate 文档

教学材料（Teaching Materials）​

花许多小时，甚至许多年，发明新的并发数据结构并为它们设计符合人体工学的 Rust 实现，可以非常有趣。如果你正在寻找其他方式来使用自己关于 Rust、原子操作、锁、并发数据结构以及并发的一般知识，创建新的教学材料并与他人分享知识，也会非常有成就感。

面向这些主题新手的易懂资源非常缺乏。Rust 在让系统编程对所有人更容易接近方面发挥了重要作用，但许多程序员仍然会避开低层并发。原子操作常常被认为是某种有些神秘的话题，最好留给极少数专家处理，这很可惜。

我希望这本书本身能带来显著改变，但关于 Rust 并发，仍然有大量空间留给更多书籍、博客文章、文章、视频课程、会议演讲和其他材料。

~

我很期待看到你创造出的东西。

祝你好运。♥