内核共享了大量的资源，例如内存，CPU，磁盘缓存，inode缓存，这些东西都在后台被不同的进程所共享。这意味着，即使两个完全不相关的进程在执行两个系统调用，如果这两个系统调用需要分配内存或使用磁盘缓存或者涉及到线程调度决策，它们可能最终会使用内核中相同的数据结构，因此我们需要有办法能让它们在使用相同数据的同时，又互不影响
文章目录
- 读写锁 (Read-Write Lock)
- RCU
读写锁 (Read-Write Lock)
- 功能：可以有多个数据的读取者获取了读锁，这样可以获得并行执行读操作的能力；要么只能有一个数据写入者获取了写锁。但是不能两种情况同时发生，要么只有一个数据写入者，要么有多个数据读取者。
- Linux实际上有读写锁的实现
-
rwlock结构体里面有一个计数器n，
- 如果n等于0那表示锁没有以任何形式被被任何人持有
- 如果n等于-1那表示当前有一个数据写入者持有写锁
- 如果n大于0表示有n个数据读取者持有读锁。我们需要记录这里的数字，因为我们只有在n减为0的时候才能让数据写入者持有写锁。
-
r_lock函数会一直在一个循环里面等待数据写入者释放锁。首先它获取读写锁中计数器n的拷贝，如果n的拷贝小于0的话那意味着存在一个数据写入者，我们只能继续循环以等待数据写入者退出。
- 但是我们只能在读写锁的计数器仍然大于等于0的时候，对其加1。所以我们不能直接对n加1，因为如果一个数据写入者在我们检查n和我们增加n之间潜入了，那么我们有可能在数据写入者将n设置为-1的同时，将n又加了1。所以我们只能在检查完n大于等于0，且n没有改变的前提下，将其加1。
- 利用特殊的原子指令来实现这一点——compare-and-swap（CAS）
- CAS的语义是，硬件首先会设置一个内部的锁，使得一个CAS指令针对一个内存地址原子的执行；之后硬件会检查当前内存地址的数值是否还是x；如果是的话，将其设置为第三个参数，也就是x+1，之后CAS指令会返回1；如果不是的话，并不会改变内存地址的数值，并返回0。这里必须是原子性，因为这里包含了两个操作，首先是检查当前值，其次是设置一个新的数值。
-
- 缺陷
- 因为存在多个数据读取者，n不等于0，所以CAS指令会失败。数据写入者会在w_lock的循环中不断尝试并等待n等于0，如果存在大量的数据读取者，这意味着数据写入者有可能会一直等待。这是这种锁机制的一个缺陷。
- 糟糕的性能
- 在一个多核的系统中，每个CPU核都有一个关联的cache，也就是L1 cache。每当CPU核读写数据时，都会保存在cache中。除此之外，还有一些内部连接的线路使得CPU可以彼此交互，因为如果某个CPU核修改了某个数据，它需要告诉其他CPU核不要去缓存这个数据，这个过程被称为(cache) invalidation。
- 如果有多个数据读取者在多个CPU上同时调用r_lock，它们都会读取读写锁的计数l->n，并将这个数据加载到CPU的cache中，它们也都会调用CAS指令，但是第一个调用CAS指令的CPU会修改l->n的内容。作为修改的一部分，它需要使得其他CPU上的cache失效。所以执行第一个CAS指令的CPU需要通过线路发送invalidate消息给其他每一个CPU核，之后其他的CPU核在执行CAS指令时，需要重新读取l->n，但是这时CAS指令会失败，因为l->n已经等于1了，但x还是等于0。之后剩下的所有数据读取者都会回到循环的最开始，重复上面的流程，但这一次还是只有一个数据读取者能成功。
- 假设有n个数据读取者，那么每个r_lock平均需要循环n/2次，每次循环都涉及到O(n)级别的CPU消息，因为至少每次循环中所有CPU对于l->n的cache需要被设置为无效。这意味着，对于n个CPU核来说，同时获取一个锁的成本是O(n^2)，当你为一份数据增加CPU核时，成本以平方增加。
- 对于一个只读数据，如果数据只在CPU的cache中的话，它的访问成本可能只要几十个CPU cycle。但是如果数据很受欢迎，由于O(n^2)的效果，光是获取锁就要消耗数百甚至数千个CPU cycle，因为不同CPU修改数据（注，也就是读写锁的计数器）需要通过CPU之间的连线来完成缓存一致的操作。
RCU
引言
如果我们写的是可能与其他CPU核共享的数据，写操作通常会比读操作成本高得多。因为读一个未被修改的数据可以在几个CPU cycle内就从CPU cache中读到，但是修改可能被其他CPU核缓存的数据时，需要涉及CPU核之间的通信来使得缓存失效。不论如何修改数据结构，任何涉及到更改共享数据的操作对于性能来说都是灾难。
所以r_lock中最关键的就是它对共享数据做了一次写操作。所以我们期望找到一种方式能够在读数据的同时，又不需要写数据，哪怕是写锁的计数器也不行。这样读数据实际上才是一个真正的只读操作。
- 一种可能的解决方案是：数据读取者完全不使用锁。在有些场景数据读取者可以直接读数据，只有数据的写入者才需要锁。
- 针对链表 (存字符串) ，数据写入的三种情况
- 数据的写入者只修改了链表元素的内容 —— 数据读取者可能会读到部分旧的字符串和部分新的字符串
- 数据写入者插入了一个链表元素 —— 数据的写入者可能在初始化新元素之前，就将前一个指针指向新元素，读的数据无效 (编译器 / CPU 重排)
- 数据写入者删除了一个链表元素 —— 数据读取者看到的是释放了的元素（在使用旧的元素，却被释放了，就是何时释放的问题）
- **RCU是一种实现并发的特殊算法，它是一种组织数据读取者和写入者的方法，通过RCI数据读取者可以不用使用任何锁。**RCU的主要任务就是修复上面的三种数据读取者可能会陷入问题的场景，它的具体做法是让数据写入者变得更加复杂一些，所以数据写入者会更慢一些。
RCU —— Read-Copy-Update
-
针对读入场景的问题
-
针对修改元素的场景，RCU不会直接修改链表里的元素，而是创建并初始化一个新的链表元素。所以新的内容会写到新的链表元素中，之后数据写入者会将新链表元素的next指针指向E3，之后在单个的写操作中将E1的next指针指向新的链表元素。
所以数据读取者 只会读到 老的数据 或者 新的数据
这里将E1的next指针从旧的E2切换到新的E2，在我（Robert教授）脑海里，我将其称为committing write。这里能工作的部分原因是，单个committing write是原子的，从数据读取者的角度来说更新指针要么发生要么不发生。通过这一条不可拆分的原子指令，我们将E1的next指针从旧的E2切换到的新的E2。写E1的next指针完成表明使用的是新版本的E2。
这是对于RCU来说一个非常基本同时也是非常重要的技术，它表示RCU主要能用在具备单个committing write的数据结构上。 -
针对插入元素的场景，许多计算机中都不存在“之后”或者“然后”这回事，通常来说所有的编译器和许多微处理器都会重排内存操作。
实现RCU的第二个部分就是数据读取者和数据写入者都需要使用memory barriers，这里背后的原因是因为我们这里没有使用锁。对于数据写入者来说，memory barrier应该放置在committing write之前——这样可以告知编译器和硬件，先完成所有在barrier之前的写操作，再完成barrier之后的写操作。
-
针对删除元素的场景，需要解决“ 何时释放避免读到的旧空间不存在的问题 ”，
- 引用计数（不行，引入了CPU之间的共享元素）
- 使用自带垃圾回收（Garbage Collect）的编程语言
- 遵守一些规则
- 数据读取者不允许在context switch时持有一个被RCU保护的数据（也就是链表元素）的指针。所以数据读取者不能在RCU critical 区域内出让CPU。
- 对于数据写入者，它会在每一个CPU核都执行过至少一次context switch之后再释放链表元素（因为数据读取者不能在context switch的时候持有数据的引用）。
- 所以数据写入者或许要在第二条规则上等待几个毫秒的时间才能确保没有数据读取者还在使用链表元素，进而释放链表元素
- 对于数据写入者不想等待的场景，可以调用另一个函数call_rcu，将你想释放的对象和一个执行释放的回调函数作为参数传入，RCU系统会将这两个参数存储到一个列表中，并立刻返回。之后在后台，RCU系统会检查每个CPU核的context switch计数，如果每个CPU核都发生过context switch，RCU系统会调用刚刚传入的回调函数，并将想要释放的对象作为参数传递给回调函数。这是一种避免等待的方法，因为call_rcu会立即返回。
但大量的调用call_rcu可能会导致系统OOM，因为所有的内存都消耗在这里的列表上了。
-
-
写的流程
- RCU并不能帮助数据写入者之间避免相互干扰，所以必须有一种方法能确保一次只能有一个数据写入者更新链表。这里我们假设我们将使用普通的spinlock，所以最开始数据写入者获取锁。
- 如果我们要替换链表的第一个元素，我们需要保存先保存链表第一个元素的拷贝，因为最后我们需要释放它，所以有old=head。
- 接下来的代码执行的是之前介绍的内容，首先是分配一个全新的链表元素，之后是设置该链表元素的内容，设置该链表元素的next指针指向旧元素的next指针。
- 之后的rcu_assign_pointer函数会设置一个memory barrier，以确保之前的所有写操作都执行完，再将head指向新分配的链表元素e。
- 之后就是释放锁。
- 之后调用synchronize_rcu确保任何一个可能持有了旧的链表元素的CPU都执行一次context switch，因此这些CPU会放弃指向旧链表元素的指针。
- 最后是释放旧的链表元素。
-
读的注意事项
- 我们必须只在RCU critical区域内查看被RCU保护的数据，如果我们写了一个通用的函数返回链表元素，或许我们能要求这个函数的调用者也遵循一些规则，但是函数的调用者还是可能会触发context switch。如果我们在函数的调用者返回之前调用了rcu_read_unlock，这将会违反23.5中的规则1，因为现在定时器中断可以迫使context switch，而被RCU保护的数据指针仍然被持有者。所以使用RCU的确会向数据读取者增加一些之前并不存在的限制。
- 在其他区域，我们只能读取它的拷贝（新建一个链表，元素内容 拷贝 和指针地址 重新申请）
可以返回一个拷贝，如果e->x是个字符串，那么我们可以返回一个该字符串的拷贝，这是没有问题的。但是如果我们直接返回一个指针指向e->x，那就违反了RCU规则。
-
性能
- 读性能：如果你使用RCU，数据读取会非常的快，除了读取数据本身的开销之外就几乎没有别的额外的开销了。如果你的链表有10亿个元素，读取链表本身就要很长的时间，但是这里的时间消耗并不是因为同步（注，也就是类似加锁等操作）引起的。所以你几乎可以认为RCU对于数据读取者来说没有额外的负担。唯一额外的工作就是在rcu_read_lock和rcu_read_unlock里面设置好不要触发context switch，并且在rcu_dereference中设置memory barrier，这些可能会消耗几十个CPU cycle，但是相比锁来说代价要小的多。
- 写性能：对于数据写入者，性能会更加的糟糕。首先之前使用锁的时候所有的工作仍然需要做，例如获取锁和释放锁。其次，现在还有了一个可能非常耗时的synchronize_rcu函数调用。实际上在synchronize_rcu内部会出让CPU，所以代码在这不会通过消耗CPU来实现等待，但是它可能会消耗大量时间来等待其他所有的CPU核完成context switch。所以基于数据写入时的多种原因，和数据读取时的工作量，数据写入者需要消耗更多的时间完成操作。
-
总结
- 主要的原因是RCU完全帮不到写操作，甚至会让写操作更慢，只有当读操作远远多于写操作时才有可能应用RCU。因为RCU有这样的限制：代码不能在sleep的时候持有指针指向被RCU保护的数据，所以这会使得一些代码非常奇怪。当一定要sleep的时候，在sleep结束之后需要重新进入RCU critical区域再次查找之前已经看过的数据，前提是这些数据还存在。所以RCU使得代码稍微复杂了一些。
- 论文中介绍的RCU对于Linux来说是一个巨大的成功。它在Linux中各种数据都有使用，实际中需要频繁读取的数据还挺常见的，例如block cache基本上就是被读取，所以一种只提升读性能的技术能够应用的非常广泛。
写操作多的时候的两个改进建议
- **最有效的方法就是重新构造你的数据结构，这样它就不是共享的。**有的时候共享数据完全是没必要的，一旦你发现数据共享是个问题，你可以尝试让数据不共享。
- **但是某些时候你又的确需要共享的数据，而这些共享数据并没有必要被不同的CPU写入。**实际上你们已经在lab中见过这样的数据，在locking lab的kalloc部分，你们重构了free list使得每个CPU核都有了一个专属的free list，这实际上就是将一个频繁写入的数据转换成了每个CPU核的半私有数据。大部分时候CPU核不会与其他CPU核的数据有冲突，因为它们都有属于自己的free list。唯一的需要查看其他CPU核的free list的场景是自己的free list用光了。有很多类似的例子用来处理内核中需要频繁写入的数据，例如Linux中的内存分配，线程调度列表。对于每个CPU核都有一套独立的线程对象以供线程调度器查看（注，详见11.8，线程对象存储在struct cpu中）。CPU核只有在自己所有工作都完成的时候才会查看其他CPU核的线程调度列表。另一个例子是统计计数，如果你在对某个行为计数，但是计数变化的很频繁，同时又很少被读出，你可以重构你的计数器，使得每个CPU核都有一个独立的计数器，这样每个CPU核只需要更新属于自己的计数器。当你需要读取计数值时，你只需要通过加锁读出每个CPU核的计数器，然后再加在一起。这些都是可以让写操作变得更快的方法，因为数据写入者只需要更新当前CPU核的计数器，但是数据读取者现在变得更慢了。如果你的计数器需要频繁写入，实际上通常的计数器都需要频繁写入，通过将更多的工作转换到数据读取操作上，这将会是一个巨大的收益。