第 10 章 想法和灵感
来自 《Rust Atomics and Locks》 的翻译文章，英文原文：https://marabos.nl/atomics/inspiration.html
本书中有无数与并发相关的主题、算法、数据结构、轶事和其他潜在的章节。然而，我们已经到了最后一章，也差不多到了分道扬镳的时候了，希望能让你对新的可能性感到兴奋，并准备好在实践中应用新的知识和技能。
最后一章的目的是通过向您展示一些您可以自己学习、探索和构建的想法，为您自己的创作和未来的工作提供灵感。
信号量(Semaphore)
信号量实际上只是一个具有两个操作的计数器：信号（也称为向上或 V）和等待（也称为向下或 P）。信号操作将计数器递增到某个最大值，而等待操作则递减计数器。如果计数器为零，则等待操作将阻塞并等待匹配的信号操作，从而防止计数器变为负数。它是一个灵活的工具，可用于实现其他同步原语。
信号量可以实现为计数器的 Mutex<u32> 和等待操作的 Condvar 的组合。然而，有几种方法可以更有效地实施它。最值得注意的是，在支持类似 futex 操作的平台上（第 8 章中的“Futex”），它可以更有效地实现为单个 AtomicU32 （甚至 AtomicU8 ）。
最大值为 1 的信号量有时称为二进制信号量，并且可以用作构建其他原语的构建块。例如，可以将计数器初始化为 1，使用等待操作进行锁定，使用信号操作进行解锁，从而将其用作互斥体。通过将其初始化为零，它还可以用于发出信号，就像条件变量一样。例如， std::thread 中的标准 park() 和 unpark() 函数可以实现为与线程关联的二进制信号量上的等待和信号操作。
提示
请注意如何使用信号量来实现互斥体，而信号量可以使用互斥体（和条件变量）来实现。建议避免使用基于互斥量的信号量来实现基于信号量的互斥量，反之亦然。
进一步阅读：
RCU
如果您想允许多个线程（大部分）读取和（有时）更改某些数据，您可以使用 RwLock 。当此数据只是单个整数时，您可以使用原子变量（例如 AtomicU32 ）来避免锁定，这样效率更高。然而，对于较大的数据块，例如具有许多字段的结构，没有可用的原子类型允许对整个对象进行无锁原子操作。
就像计算机科学中的其他问题一样，这个问题可以通过增加一层间接性来解决。你可以使用一个原子变量来存储指向该结构的指针，而不是结构本身。这仍然不允许你以原子方式修改整个结构，但它确实允许你以原子方式替换整个结构，这几乎是一样好的。
这种模式通常称为 RCU，代表“读取、复制、更新”，即替换数据所需的步骤。读取指针后，可以将结构复制到新的分配中，可以修改该分配而无需担心其他线程。准备好后，可以使用比较和交换操作（第 2 章中的“比较和交换操作”）更新原子指针，只有在没有其他线程同时替换数据的情况下，该操作才会成功。
RCU 模式最有趣的部分是最后一步，它的缩写中没有字母：释放旧数据。成功更新后，如果其他线程在更新之前读取指针，则它们可能仍在读取旧副本。您必须等待所有这些线程完成才能释放旧副本。
对于这个问题有很多可能的解决方案，包括引用计数（如 Arc ）、内存泄漏（忽略问题）、垃圾收集、危险指针（一种让线程告诉其他线程它们当前是什么指针的方法）和静态跟踪（等待每个线程到达它绝对不使用任何指针的点）。最后一种在某些条件下可能非常有效。
Linux 内核中的许多数据结构都是基于 RCU 的，并且有许多关于其实现细节的有趣演讲和文章，可以提供很多启发。
进一步阅读：
无锁链表(Lock-Free Linked List)
扩展基本的 RCU 模式，您可以向结构添加一个原子指针以指向下一个，将其转换为链表。这允许线程自动添加或删除此列表上的元素，而不必为每次更新复制整个列表。
要在列表的开头插入一个新元素，您只需分配该元素并将其指针指向列表中的第一个元素，然后自动更新初始指针以指向新分配的元素。
类似地，删除一个元素可以通过原子地更新它之前的指针以指向它之后的元素来完成。但是，当涉及多个写入器时，必须注意处理相邻元素上的并发插入或删除操作。否则，您可能会意外地删除同时新插入的元素，或撤消对同时删除的元素的删除。
提示
为了简单起见，您可以使用常规互斥体来避免并发突变。这样，读取仍然是无锁操作，但您不必担心处理并发突变。
从链表中分离一个元素后，您将遇到与以前相同的问题：等待直到您可以释放它（或以其他方式声明所有权）。我们针对基本 RCU 模式讨论的相同解决方案也适用于这种情况。
一般来说，您可以基于原子指针上的比较和交换操作构建各种精心设计的无锁数据结构，但您始终需要一个良好的策略来取消分配或以其他方式回收分配的所有权。
进一步阅读：
基于队列的锁(Queue-Based Locks)
对于大多数标准锁定原语，操作系统的内核会跟踪其上阻塞的线程，并负责在被要求时选择一个唤醒线程。一个有趣的替代方案是通过手动跟踪等待线程队列来实现互斥锁（或其他锁定原语）。
这样的互斥体可以实现为单个 AtomicPtr ，它可以指向等待线程（列表）。
该列表中的每个元素都需要包含可用于唤醒相应线程的内容，例如 std::thread::Thread 对象。原子指针的一些未使用的位可用于存储互斥体本身的状态，以及管理队列状态所需的任何内容。
有许多可能的变化。队列可以通过其自己的锁位来保护，或者可以将其实现为（部分）无锁结构。这些元素不必在堆上分配，但可以是正在等待的线程的局部变量。队列可以是一个双向链表，不仅包含指向下一个元素的指针，还包含指向前一个元素的指针。第一个元素还可以包括指向最后一个元素的指针，以允许在末尾有效地附加元素。
此模式允许仅使用可用于阻止和唤醒单个线程的内容（例如线程停放）来实现高效的锁定原语。
Windows SRW 锁（第 8 章中的“Slim 读写器锁”）就是使用此模式实现的。
进一步阅读：
基于停放的锁(Parking Lot–Based Locks)
为了制作尽可能小的高效互斥体，您可以通过将队列移动到全局数据结构中，在基于队列的锁思想的基础上构建，只在互斥体本身中留下一到两个位。这样，互斥体只需是一个字节。您甚至可以将其放入指针的一些未使用的位中，从而允许非常细粒度的锁定，几乎不需要额外的成本。
全局数据结构可以是 HashMap ，它将内存地址映射到在该地址等待互斥锁的线程队列。这种全局数据结构通常称为停放，因为它是停放线程的集合。
该模式不仅可以通过跟踪互斥体的队列来推广，还可以通过跟踪条件变量和其他原语的队列来推广。通过跟踪任何原子变量的队列，这有效地提供了一种在本身不支持该功能的平台上实现类似 futex 的功能的方法。
这种模式因其 2015 年在 WebKit 中的实现而闻名，当时它用于锁定 JavaScript 对象。它的实现启发了其他实现，例如流行的 parking_lot Rust crate。
进一步阅读：
顺序锁(Sequence Lock)
顺序锁是另一种解决原子更新（较大）数据问题的方法，不需要使用传统的（阻塞）锁。它使用一个原子计数器，在数据被更新时是奇数，而在数据准备被读取时是偶数。
在改变数据之前，写入线程必须将计数器从偶数增加到奇数，之后必须再次增加计数器以使其保持在（不同的）偶数值。
任何读去线程都可以在任何时候，且在不阻塞的情况下，通过读取前后的计数器来读取数据。如果计数器的两个值相等，并且是偶数，则不存在并发突变，这意味着你读到了数据的有效副本。否则，你可能读取了正在被修改的数据，在这种情况下，你应该再试一次。
这是一个很好的模式，可以使数据对其他线程可用，而不会出现读线程阻塞写线程的情况。它经常被用在操作系统内核和许多嵌入式系统中。由于读取者只需要对内存进行读取访问，而不涉及指针，这可以是一个很好的数据结构，可以在进程之间安全地使用共享内存，而不需要信任读者。例如，Linux内核使用这种模式，通过向进程提供对（共享）内存的只读访问，非常有效地提供时间戳。
一个有趣的问题是这如何符合内存模型。对同一数据的非原子读和写会导致未定义的行为，即使读取的数据被忽略了。这意味着，从技术上讲，读和写数据都应该只使用原子操作，尽管整个读或写不一定是一个原子操作。
进一步阅读：
教材
花费大量时间（或数年）发明新的并发数据结构并设计符合人体工程学的 Rust 实现是非常有趣的。如果您正在寻找其他东西来利用您在 Rust、原子、锁、并发数据结构和一般并发方面的知识，那么创建新的教材来与他人分享您的知识也会非常令人满意。
对于这些主题的新手来说，非常缺乏可访问的资源。 Rust 在让每个人都更容易进行系统编程方面发挥了重要作用，但许多程序员仍然回避低级并发。原子通常被认为是一个有点神秘的话题，最好留给一小群专家，这是一种耻辱。
我希望这本书能带来重大改变，但是还有很多空间可以容纳更多关于 Rust 并发的书籍、博客文章、文章、视频课程、会议演讲和其他材料。
我很期待看到你的创作。 Good luck. ♥