Spinlock
在xv6中我们通过spinlock（自旋锁）来解决多个进程对共享数据进行读写的一致性和正确性，当两个进程可能会相互影响时，spinlock会阻止并行运行，所以spinlock的直接效果就是降低性能。假如我们的数据主要是在被读取，相对来说很少被写入，这个时候spinlock的性能就会极其的低，因为即使只是两个读取数据的线程也只能一次执行一个线程。于是一种改进方法是使用一种新的锁即read-write lock（读写锁），它可以允许多个读取线程和一个写入线程。
Read-Write Lock
Read-Write Lock相比spinlock要复杂一些：想要读取数据，那么可以调用r_lock，将锁作为参数传入，同样的还会有个r_unlock。数据的写入者则调用w_lock和w_unlock接口。Read-Write Lock的语义是要么你可以有多个数据的读取者获取了读锁，这样可以获得并行执行读操作的能力；要么你只能有一个数据写入者获取了写锁。但是不能两种情况同时发生，读写锁排除了某人获取了数据的写锁，同时又有别人获取读锁的可能性。你要么只有一个数据写入者，要么有多个数据读取者。代码实现如下：
r_lock函数会一直在一个循环里面等待数据写入者释放锁。首先它获取读写锁中计数器n的拷贝，如果n的拷贝小于0的话那意味着存在一个数据写入者，继续循环以等待数据写入者退出。如果n的拷贝不小于0，我们会调用一个特殊的原子指令compare-and-swap（CAS）增加读写锁的计数器。CAS接收三个参数，第一个参数是内存的某个地址，第二个参数是我们认为内存中该地址持有的数值，第三个参数是我们想设置到内存地址的数值。CAS的语义是，硬件首先会设置一个内部的锁，使得一个CAS指令针对一个内存地址原子的执行；之后硬件会检查当前内存地址的数值是否还是x；如果是的话，将其设置为第三个参数，也就是x+1，之后CAS指令会返回1；如果不是的话，并不会改变内存地址的数值，并返回0。再次强调整个CAS操作是原子性的，包含了检查当前值（以防数据写入者进行了修改）和设置新值两个操作。
多个r_lock同时调用的场景同样也很有趣。假设n从0开始，当两个r_lock同时调用时，我们希望当两个r_lock都返回时，n变成2，因为我们希望两个数据读取者可以并行的使用数据。两个r_lock在最开始都将看到n为0，并且都会通过传入第二个参数0，第三个参数1来调用CAS指令，但是只有一个CAS指令能成功。CAS是一个原子操作，一次只能发生一个CAS指令。不管哪个CAS指令先执行，将会看到n等于0，并将其设置为1。另一个CAS指令将会看到n等于1，返回失败，并回到循环的最开始，这一次x可以读到1，并且接下来执行CAS的时候，第二个参数将会是1，第三个参数是2，这一次CAS指令可以执行成功。最终两次r_lock都能成功获取锁。
上面这个例子也正好说明了read-write lock的缺陷，即使没有任何的数据写入者，仅仅是在多个CPU核上有大量的数据读取者，r_lock也可能会有非常高的代价。在一个多核的系统中，每个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个CPU核来说，同时获取一个锁的成本是O(n^2)，当你为一份数据增加CPU核时，成本以平方增加。
所以read-write lock，将一个原本成本很低的读操作，因为要修改读写锁的l->n，变成了一个成本极高的操作。如果你要读取的数据本身就很简单，这里的锁可能会完全摧毁任何并行带来的可能的性能提升。r_lock中最关键的就是它对共享数据做了一次写操作。所以我们期望找到一种方式能够在读数据的同时，又不需要写数据，哪怕是写锁的计数器也不行。这样读数据实际上才是一个真正的只读操作。
RCU
RCU（Read Copy Update）是一种实现并发的特殊算法，它是一种组织数据读取者和写入者的方法。通过RCU，数据读取者可以不用使用任何锁，而数据写入者会变得更加复杂一些，所以数据写入者会更慢一些。假设我们有一个链表，数据写入者想要更新链表元素E2。
现在不能直接修改E2的内容，RCU会创建并初始化一个新的链表元素。所以新的内容会写到新的链表元素中，之后数据写入者会将新链表元素的next指针指向E3，之后在单个的写操作中将E1的next指针指向新的链表元素。
所以这里不是修改链表元素的内容，而是用一个包含了更新之后数据的新链表元素代替之前的链表元素。对于数据读取者来说，如果遍历到了E1并正在查看E1的next指针：
- 要么看到的是旧的元素E2，这并没有问题，因为E2并没有被改变；
- 要么看到的是新版本的E2，这也没有问题，因为数据写入者在更新E1的next指针之前已经完全初始化好了新版本的E2。
不管哪种情况，数据读取者都将通过正确的next指针指向E3。这里核心的点在于，数据读取者永远也不会看到一个正在被修改的链表元素内容。
这里将E1的next指针从旧的E2切换到新的E2，称为committing write。单个committing write是原子的，从数据读取者的角度来说更新指针要么发生要么不发生。通过这一条不可拆分的原子指令，我们将E1的next指针从旧的E2切换到的新的E2。这对于RCU来说一个非常基本同时也是非常重要的技术（实现RCU的第一步），它表示RCU主要能用在具备单个committing write的数据结构上。这意味着一些数据结构在使用RCU时会非常的奇怪，例如一个双向链表，其中的每个元素都有双向指针，这时就不能通过单个committing write来删除链表元素，因为在大多数机器上不能同时原子性的更改两个内存地址。所以双向链表对于RCU来说不太友好。相反的，树是一个好的数据结构。如果我们要更新图中的节点，我们可以构造树的虚线部分，然后再通过单个committing write更新树的根节点指针，切换到树的新版本。数据写入者会创建树中更新了的那部分，同时再重用树中未被修改的部分，最后再通过单个committing write，将树的根节点更新到新版本的树的根节点。但是对于其他的数据结构，就不一定像树一样能简单的使用RCU。
在前面的介绍中其实存在一个问题：如果要更新E2的内容，需要先创建一个新的E2，并设置好它的内容，然后将新的E2的next指针指向E3，最后才会将E1的next指针指向新的E2。但通常来说所有的编译器和许多微处理器都会重排内存操作，例如编译器或者计算机会重排数据读取者的读操作顺序。如果我们在初始化新的E2的内容之前，就将E1的next指针设置成新的E2，那么某些数据读取者可能就会读到垃圾数据并出错。所以实现RCU的第二个部分就是数据读取者和数据写入者都需要使用memory barriers：
- 对于数据写入者来说，memory barrier应该放置在committing write之前。这样可以告知编译器和硬件，先完成所有在barrier之前的写操作，再完成barrier之后的写操作。所以在E1设置next指针指向新的E2的时候，新的E2必然已经完全初始化完了。
- 对于数据读取者，需要先将E1的next指针加载到某个临时寄存器中，我们假设r1保存了E1的next指针，之后数据读取者也需要一个memory barrier，然后数据读取者才能查看r1中保存的指针。这里的barrier表明的意思是，在完成E1的next指针读取之前，不要执行其他的数据读取，这样数据读取者从E1的next指针要么可以读到旧的E2，要么可以读到新的E2。通过barrier的保障，我们可以确保成功在r1中加载了E1的next指针之后，再读取r1中指针对应的内容。
到这里你会发现前面我们一直忽视了旧的E2的释放问题，我们需要在某个时候释放旧的E2，但是最好不要在某些数据读取者还在读的时候释放。所以我们需要等待最后一个数据读取者读完旧的E2，然后才能释放旧的E2，这就是RCU需要解决的第三个问题。比如引用计数（read-write lock中讲了代价，排除），带GC的编程语言（GC真的能提升性能吗？）。
RCU使用的是另一种方法，数据读取者和写入者都需要遵循一些规则，使得数据写入者可以在稍后再释放链表元素。规则如下：
- 数据读取者不允许在context switch（线程切换的context switch）时持有一个被RCU保护的数据（也就是链表元素）的指针。所以数据读取者不能在RCU critical 区域内出让CPU。
- 对于数据写入者，它会在每一个CPU核都执行过至少一次context switch之后再释放链表元素，即synchronize_rcu。每个CPU核都知道自己有没有发生context switch数据写入者或许要在第二条规则上等待几个毫秒的时间才能确保没有数据读取者还在使用链表元素，进而释放链表元素。
synchronize_rcu要花费不少时间，可能要将近1个毫秒，这是事实并且不太好。其中一种辩解的方法是：对于RCU保护的数据来说，写操作相对来说较少，写操作多花费点时间对于整体性能来说不会太有影响。
来看下RCU示例：
数据读取位于rcu_read_lock和rcu_read_unlock之间，这两个函数几乎不做任何事情。rcu_read_lock会设置一个标志位，表明如果发生了定时器中断，请不要执行context switch，因为接下来要进入RCU critical区域。所以rcu_read_lock会设置一个标志位（仅针对单个CPU，不涉及CPU缓存一致性）来阻止定时器中断导致的context switch，中断或许还会发生，但是不会导致context switch。rcu_read_unlock会取消该标志位。所以这是一个集成在RCU critical区域的计数器。rcu_read_lock和rcu_read_unlock因为几乎不做任何工作所以极其的快。
其中的while循环会扫描链表，rcu_dereference函数会插入memory barrier，它首先会从内存中拷贝e，触发一个memory barrier，之后返回指向e的指针。之后我们就可以读取e指针指向的数据内容，并走向下一个链表元素。数据读取部分非常简单。
数据写入部分更复杂点。
- RCU并不能帮助数据写入者之间避免相互干扰，所以必须有一种方法能确保一次只能有一个数据写入者更新链表。这里我们假设我们将使用普通的spinlock，所以最开始数据写入者获取锁。
- 如果我们要替换链表的第一个元素，我们需要保存先保存链表第一个元素的拷贝，因为最后我们需要释放它，所以有old=head。
- 接下来的代码执行的是之前介绍的内容，首先是分配一个全新的链表元素，之后是设置该链表元素的内容，设置该链表元素的next指针指向旧元素的next指针。
- 之后的rcu_assign_pointer函数会设置一个memory barrier，以确保之前的所有写操作都执行完，再将head指向新分配的链表元素e。
- 之后就是释放锁。
- 之后调用synchronize_rcu确保任何一个可能持有了旧的链表元素的CPU都执行一次context switch，因此这些CPU会放弃指向旧链表元素的指针。
- 最后是释放旧的链表元素。
Conclusion
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。所以基于数据写入时的多种原因，和数据读取时的工作量，数据写入者需要消耗更多的时间完成操作。如果数据读取区域很短（注，这样就可以很快可以恢复context switch），并且数据写入并没有很多，那么数据写入慢一些也没关系。所以当人们将RCU应用到内核中时，必须要做一些性能测试来确认使用RCU是否能带来好处，因为这取决于实际的工作负载。
但RCU对于Linux来说是一个巨大的成功。它在Linux中各种数据都有使用，实际中需要频繁读取的数据还挺常见的，例如block cache基本上就是被读取，所以一种只提升读性能的技术能够应用的非常广泛。尽管已经有了许多有趣的并发技术，同步（synchronization）技术，RCU还是很神奇，因为它对数据读取者完全去除了锁和数据写入（注，这里说的数据写入是指类似读写锁时的计数值，但是RCU在读数据的时候还是需要写标志位关闭context switch，只是这里的写操作代价并不高），所以相比读写锁，RCU是一个很大的突破。RCU能工作的核心思想是为资源释放（Garbage Collection）增加了grace period，在grace period中会确保所有的数据读取者都使用完了数据。所以尽管RCU是一种同步技术，也可以将其看做是一种特殊的GC技术。
