写在前面

首先必须说明一点：对于内核而言，任何一种锁机制都是需要解决多核通信问题的。对于除了RCU锁以外的其他锁而言，它们最低的开销也至少是一对原子访存指令，核心数越多，其原子访存开销也会跟着以$O(N^2)$的级别增长。

1. 自旋锁

spin_lock，最原始的自旋锁，通过一个atomic_bool的标记位指示是否有线程正在访问。

不区分读写者，一旦获取到锁就相当于同时获取读写权限。

• 优点：结构简单、能够极大程度保证原子性（事实上，你只需要把需要保证原子性的数据都放到同一个锁中即可）
• 缺点：在多读者、少写者的情况下效率低下。由于其本质是强制通过阻塞实现原子性，是一种舍弃并行性、通过串行损耗性能的行为。可以认为存在数据竞争的情况下，效率是所有锁里最低的。

适用于存在大量写者，或每次操作都需要同时获取读写权限的情况。

1.1 票锁

ticket_lock是一种公平的自旋锁，在自旋等待阶段，通过队列等方式实现先来先得式的仲裁功能。

2. 读写锁

rw_lock，通过一个atomic_usize指示当前锁中读者的个数，正数表示有若干读者，-1表示当前存在写者占用。

读写锁中，写者优先级低于读者，必须等到读者全部释放，也就是原子计数被置为0之后，才有机会让写者访问。

读写锁的优缺点都很明显：

• 优点：能够满足最高效率的读请求。

• 缺点：如果不对读写操作的顺序加以限制的话，比方说若干读操作占用锁的时间覆盖了大量时间段，那么大概率会造成写者的饥饿。

3. 顺序锁

seq_lock，融合了自旋锁和读写锁的优势，实现了多读者+单写者的情况，其实现非常优美。

思路

观察上面自旋锁和读写锁的缺点，我们有如下需求：

1. 尽量提高写者的优先级，避免写者饥饿
2. 尽量减少读者访问数据的开销，避免在无写者的情况下产生额外的自旋开销

基本思想：当读者访问锁的时候，假如访问期间不存在写者修改数据，那么可以认为读取的数据是正确的。所以，只需要通过原子访存机制，让读者检测读取过程中是否发生写操作即可。

实现

seq_lock通过一个atomic_usize进行写者状态的计数，实现了对于读操作期间的写操作检测。

具体而言，当写者进入临界区时原子计数cnt++，退出临界区时再次cnt++，并通过自旋锁保证同一时刻只存在一个写者。

而对于读者而言，只会存在下面两种需要阻塞等待的情况：

1. 当cnt的值为奇数时，表明存在写者正在访问临界资源，读者无法访问；
2. 当读者检测到读取前后cnt的值发生改变的时候，表明在读取时间内发生了写者的访问，需要重新进行读取。

而如果不发生写操作，则读者的访问开销只有对于原子计数进行的两次数值比较，相较于之前的阻塞式自旋效率大幅提升。

优点：避免了多读者、无写者情况下的数据竞争。

缺点：存在写者的情况下，仍然等效于自旋锁行为。此外，读者仍然需要执行原子访存。

4. RCU锁

对于n核竞争的情况，原子访存会导致n次对于n个核心的invalidate操作，因此这个操作会产生$O(N^2)$的无效化开销。在我们的上面三种基于原子访存的锁机制当中，都会存在这个多核之间的无效化开销，从而产生巨大的原子访存开销。（存疑）

RCU锁的使用场景是多核、多读者、少写者的情况，并且只适用于如链表维护的链/树形结构等通过能够通过指针进行明确拆分的、所谓的”可持久化“的数据结构。它通过内存屏障而不是原子指令实现，因此不会产生原子访存的$O(N^2)$的缓存无效化开销，这对于多核场景而言非常友好。

思路

我们引入RCU的最开始目的是尽可能地避免原子访存。那么思考一下，为什么自旋锁需要进行原子访存？

答：因为写者存在时，它与读者共享了同一份数据，所以需要向读者传递“写者是否存在“这一个信息。而传递写者的存在就需要原子访存来维护多核一致性了。

所以首要的目的就是，需要让写者对于读者而言变为透明，因此写者不能与读者共享同一份数据。

基于这种想法，我们可以想到解决方案：在写者执行写操作的时候开辟一段新的内存区域，用于存放写入的数据；而旧值仍然保留（因为它们可能正在被读者访问），直到所有旧值区域的读者读取完毕之后，再由写者将旧值的内存进行释放。

这是一种类似可持久化线段树或寄存器重命名的思想，通过保存多份同一对象的不同历史数据，实现了可变数据对于读者的只读性。在这种情况下， 任何数据一旦被写者初始化完成，就一直处于只读状态，不会有写者再来对它进行更改，因此读者也不需要对于写者进行任何的检测。

这种实现下，所有的资源管理的功能都交给了写者，而读者只需要在访问资源之前执行内存屏障，防止读取到未被写入的数据即可。而对于写者而言，它需要通过某种方式监听旧数据读者的状态，并在读者访问完毕之后对资源进行回收。

实现

RCU锁最难的地方就是写者对旧数据的资源回收过程。天才的做法：令持有读锁的线程关闭内核抢占，并限制在让权的时候，线程一定不能持有RCU读锁。则如果硬件线程发生了上下文切换，那么该硬件线程一定在此之前释放了旧的RCU锁。

那么，写者只需要等待所有硬件线程都发生一次上下文切换，就能够保证旧数据中不再存在读者了！

天才一样的想法！将细粒度、小概率、性能敏感事件归属到粗粒度、大概率、性能不敏感事件当中，实现了相对较小的数据同步开销。

个人想法

相较于上面三种精简小巧、基于原子指令的锁，RCU锁是完全不同的一类锁，RCU结构更复杂，会依赖于操作系统层面的context switch相关的代码。我认为RCU lock是一个与操作系统耦合的锁，很难单独解耦成库。

其实RCU锁的具体实现我没有太看懂，但大概就是这样了，只是提供一点自己的理解。