下载掌阅APP，畅读海量书库
立即打开
读/写操作之间的并发只有一种需求，即要求读的一方看到完整版本的数据，相当于要求一段数据（例如一个结构体）中的所有内容都是事务性的修改。例如，一个事务要求同时改动一个结构体的三个域，那么读的一侧（简称读侧）就不能看到只改动了一个域的事务中间过程。
顺序锁设计了一种方法，让读侧可以判断自己是否读到了中间过程的数据，如果没读到，就重新读取。而RCU锁的方法则是将多个数据域的原子更新成整个数据结构体的指针。也就是要更新一段数据的内容，先申请一块同样大小的内存，在这块新的内存中完成对数据内容的修改。保证所有的读侧看到的都是完整事务版本的数据。
举个例子，我们要修改一个结构体的内容，可以只持有这个结构体的指针，在修改的时候先重新创建一个结构体，然后在新的结构体上把要修改的内容修改好，最后进行一次指针内容交换，即可完成对结构体的更新，实例代码如下。
如上述代码，在change的时候将A结构体三个域的更新变为一个指针的更新，这样就不需要在更新操作中加锁了。同时，由于是原子的更新，所以可以让读侧放心自己读到的数据一定是确定原子事务版本的数据，而不是修改了一半的数据，这样理论上读侧不需要加任何锁，直接读取即可。在更新时依赖了指针的更新，但是两次使用指针a得到的数据位置并不一定一样，也就是在两次使用a指针的过程中，a指针的内容可能已经发生了变化。所以读侧需要先将指针保存到局部变量，然后使用这个局部变量的版本进行读取，就可以确保读到原子的数据。下面的读侧函数是读取f1和f2两个域的和。
这一切看起来很完美，读侧与写侧都没有加锁，却同时保证了读侧读到的数据是原子的，只是并不确定读到的是什么版本。在并发情况下读取到的数据到底是哪一个版本的并不重要，重要的是读取到的应该是有效结果，可以保证f1+f2的结果的曾经正确性。这两个并发的事务在两个CPU核上并发地产生，最后到底哪个先生效有很大的随机性，毕竟两个CPU的运行频率可能不一样。
一直有一个悬而未决的问题，就是被替换下来的指针指向的结构体的释放，如果free_rcu（）直接调用了free，就会导致竞态崩溃。比如，我们思考a原来的内容有其他的读取者正在读取其中的内容，而其他的线程调用change函数会立刻把原来的结构体释放，导致其他在读取的线程轻则只读取到错误的信息，重则访问了非法地址，导致core dump。
针对这个问题，有一个很简单的思路，就是在释放资源之前保证没有程序正在使用这个资源，即针对资源使用引用计数，但是原子操作作为一个高频操作，其带来的cache性能损失也很大，并且需要一个额外的存储字节。实际上，在内核的范畴存在比普通引用计数更高效的保证方法。只要发现被调度抢占或者返回了用户空间或者进入了idle循环状态，就可以放心回收资源，因为这时一定没有读操作在持有资源。这相当于利用内核锁的无抢占特性实现了RCU锁的读操作高性能无锁。这个发现等待的过程叫作grace period，是释放资源的一端所需要阻塞等待的一个时间长度，也就是free_rcu（）函数要达成的功能。这种思路的最大优点就是读取的时候不用加锁，资源的可用性保证由释放资源的推理得出。而RCU锁承诺的不会就地修改内容，使得读侧可以一直读到内容，并不会发生内存问题。
RCU锁也用于读多写少的情况，与seqlock锁的使用场景基本吻合，是一个比seqlock锁更高效的读写锁。RCU锁与seqlock锁都要求写操作占读/写总操作的10%以内，且越小越好。在静态数组的情况下，推荐使用seqlock锁，在其他大部分情况，在内核中都应该使用RCU锁。很多内核的链表就是直接使用了RCU链表（include/rculist.h）。
RCU锁克服了seqlock锁在高效并发时候的CPU瞬时飙高的问题。但是RCU锁也不是万能的，因为RCU锁的动态申请释放内存的运行方式决定了RCU锁的行为需要内存的重度参与和释放。而seqlock锁则可以直接使用已经申请好的结构体数组进行就地修改，不需要动态管理内存。
上述的示例函数中实现了更轻量级的读侧和不加锁的写侧，但是RCU锁机制在内核本身是不保证写侧不加锁的。RCU锁机制只是用于确保更轻量的读侧，至于写侧完全可以接受使用额外的锁来保证写入数据的原子性。这里之所以可以不加锁，是因为修改操作并不依赖a指向的内容的前序值，如果修改操作需要依赖a指针中当前指向内容的值，这里就需要确保b值的设置过程与a的修改过程都是原子的，也就需要使用额外的写锁保证，单纯的原子操作无法做到。用一个使用了RCU函数的版本重写上述逻辑，具体如下。
这里的RCU锁的用法增加了读锁和rcu_dereference过程，因为RCU锁是内核的核心基础设施，是跨平台的实现，需要考虑很多特殊的平台。在CONFIG_PREEMPT_RCU没有定义的情况下，rcu_read_lock（）函数是要调用preempt_disable（）函数来关闭抢占的，这么做是为了做到grace period的定量确定，确定的逻辑需要写侧的free_rcu（）函数一起参与。
总结一下RCU锁的特点：RCU锁是读侧非常轻量级的读写锁，并且该读写锁并不像其他锁一样有一个内存锁状态的值；通常的RCU锁是一种算法，不存在内存中的锁状态值，这也就意味着一个没有具体锁数据的函数可以同时作用于不同数据的加锁需求；不对应具体锁数据，看似全局的锁行为，却能同时作用在不同的数据上；对死锁和优先级翻转免疫，且相互不影响。
一般，正常流程的RCU锁的基本接口有以下6个。
● rcu_read_lock（）：读侧加锁。
● rcu_read_unlock（）：读侧解锁。
● synchronize_rcu（）/call_rcu（）：写侧等待grace period结束。
● rcu_assign_pointer（）：写侧替换指针。
● rcu_dereference（）：读侧使用指针。
每一个函数在不同的平台下都可能会有不同的实现，在是否可抢占RCU锁的编译选项下实现的原理也不相同，但是在编码上，读侧都使用rcu_read_lock（）获得锁，使用rcu_dereference（）取得指针的值，并将其放入局部变量，在整个读锁过程中使用局部变量来访问指针内容。在读侧结束时使用rcu_read_unlock（）释放读锁。在x86下，rcu_dereference（）就是简单的a=b的取值操作，只是会有一些额外的锁检测代码。
在写侧，RCU锁并不提供加锁函数，这是因为写侧的并发需要考虑的仅仅是写与写之间的并发，而写与写之间的并发是否需要额外的锁保护与场景相关。RCU锁的写侧需要使用rcu_assign_pointer（）来原子地替换原有的指针。rcu_assign_pointer（）与rcu_dereference（）是读/写两侧成对出现的，内有成对的内存栅acquire和release的语义。
在x86下，RCU锁提供了TSO的强内存一致性，大部分操作都是空。在这些接口函数中，只有synchronize_rcu（）和call_rcu（）才具备有意义的逻辑，其他函数可以全部是空。synchronize_rcu（）和call_rcu（）这两个函数都是等待grace period结束释放内存，但是前者是同步阻塞等待的，后者是异步等待的。
RCU锁的整体思想抽象起来就是将写的一侧进一步变为更新内容和释放内存两个部分。需求本来只是更新数据，但是更新数据做不到原子的，而更新指针可以做到。为了使用更新指针这个原子操作来替代更新数据的原子性，必须引入每次更新的内存申请和释放。RCU锁使用更新指针解决了更新数据的原子性问题的同时，还引入了何时回收内存的大问题。回收内存的问题也就产生了grace period时间是同步等待还是异步等待，以及谁来回收的进一步的问题。
Intel的TSX机制从程序员编码习惯的角度解决锁的问题，它并不试图修改连续数据的原子性，而是直接从硬件层面检测假性的锁需求。
grace period等待有两种形式，一种是synchronize_rcu（），表示同步的等待，在当前线程上下文中同步等待grace period结束。因为这种形式要求阻塞当前线程，所以有另一种不阻塞当前线程的grace period等待形式，即call_rcu（）。call_rcu（）提供一个回调函数，在grace period结束时异步调用回调函数，从而不阻塞当前的线程。在大部分情况下，经过grace period之后的操作都是释放内存，也就是call_rcu（）回调函数的实现内容一般都是释放内存，所以内核还提供了一个替换call_rcu（）的简便释放内存的函数kfree_rcu（），语义就是在grace period结束后释放内存。
下面我们列举grace period结束后释放内存的三种不同的写法，具体如下。
kfree_rcu是call_rcu的简化版本，两个版本都是异步等待grace period，为了实现异步的等待，需要在数据结构上引入额外的域。从上面的例子可以看到，reclaim函数的参数是一个struct rcu_head指针，这个指针必须位于struct A中，函数中通过container_of（rp，struct A，rcu）从rp指针使用RCU域在结构体A中的偏移来得到结构体A的指针，也就是结构体A要做如下的修改。
多出来的RCU域相当于在当前的A数据结构中记录了回调函数的地址，并且这个地址结构体被组织成一个链表。struct rcu_head结构体的操作是在call_rcu（）中完成的，tiny实现的代码如下。
RCU锁在内核中有两套实现，一套用于单核CPU下的精简版的tiny实现（/kernel/rcu/tiny.c），另外一套用于SMP复杂版本的tree实现（/kernel/rcu/tree.c）。两种实现逐渐演化成完全不同的结构，主要区别在于如何确定grace period和最后的回调执行。tiny和tree两种RCU锁的实现都是在classic RCU的基础上进行的分化迭代，tiny追求单核轻量级，tree追求SMP复杂性管理。tiny RCU完全无视抢占，默认为单核，没有每CPU变量，代码量不到200行，而tree RCU的代码量则接近5000行。
grace period属于等待读操作都结束的行为，在很多其他的同步机制中也有类似的思想，即通过一个类似引用计数的变量来控制信号量，也就是说专门的场景有专门的锁数据结构来判断并发程度。RCU锁的一个很大的特点是并没有采用专门的锁结构，而是使用了一个系统层面的机制，但是在异步回调中仍然需要添加额外的数据类型，并且待回收的数据仍然需要额外的外部统一管理的数据结构。与其他的锁一样，RCU锁的读取操作也有临界区，进入临界区和出临界区的行为必须成对出现。
在更新的操作里，同步调用synchronize_rcu（）函数可以阻塞到所有的读临界区都退出，然后才会继续执行，其原理是判断各个CPU发生上下文切换，所以在tiny RCU的实现下就是空操作，也就是tiny RCU下的grace period是即刻发生的。从这里可以看出，Linux内核设计上的UP和SMP两种结构的运作方式是有本质区别的。
由于tiny RCU的实现是默认无抢占的，所有支持抢占的RCU锁版本只存在于tree RCU中。在tree RCU的实现下，如果支持RCU锁抢占（CONFIG_PREEMPT_RCU），那么在rcu_read_lock（）中不需要关闭抢占，读侧也增加一个每线程的变量的计数器。
RCU锁的一个关键限制是读侧不能睡眠，由于存在锁状态的版本数据，可以检测重读的机制设计，使得读侧可以自由睡眠，不用担心结果的正确性。RCU锁强依赖上下文切换来确定读侧是否释放，如果在持有读锁的过程中睡眠，就意味持有读锁的时候发生了上下文切换，也就使得RCU锁所依赖的grace period的判断方式出现了问题。
如果要支持读侧睡眠，grace period的判断方法就必须要改进。读侧可睡眠意味着grace period等待可以被无限延长，对于同步的synchronize_srcu（）函数意味着阻塞时间不确定，对于异步的call_srcu（）意味着内存回收的时间不确定。同步所要面临的问题是如何让grace period可控，异步所要面临的问题是如何防止调用速度大于回收速度，使内存占用失控。
SRCU（Sleepable Read-Copy Update）的实现同样也分别位于tiny RCU和tree RCU两个版本的实现中。
当读写锁发生写数据的时候，读的部分需要阻塞等待，这个等待是自旋的。读写锁的最大特点是写者具有排他性，一个读写锁同时只能有一个写者或多个读者，但不能同时既有读者又有写者或者同时有多个写者。
也就是说，在写操作发生的时候，读操作要全部自旋等待写操作完成。这对于耗时比较多的写操作来说，在更新期间读侧几乎不可用，处于自旋状态。例如路由表的更新时间比较久，如果使用读写锁，路由表的服务质量就会显著降低。而在RCU锁写的过程中所有的读操作都不需要暂停，只是在更新之前进行的读操作读取到的是旧条目，更新之后的读操作读取到的是新条目。这就意味着整个系统能稳定地、不中断地对外提供服务能力。
对于系统不中断地对外提供服务这一点上，RCU锁有天然的优势，其在读/写并发的时候是全程无spin的。
seqlock的原理是允许读与写同时发生，但是在写操作发生之后的读取会被回滚丢弃，重新读取新的值。seqlock是读写锁的升级，在写操作发生时会更快速地获得锁。因为seqlock只有写操作需要加锁，在写操作发生的时候不需要等待读的锁释放，而读写锁则是读与写互斥，当写入发生的时候需要等待读取结束。seqlock在某一个时刻写者显著并发的时候，读者不是像rwlock那样自旋，而是一遍一遍地读取死循环，seqlock会导致CPU突发。
当同时有很多写操作的时候，RCU锁几乎没有什么作用，但仍然需要其他的锁机制来提供多写的顺序化能力。seqlock和读写锁都可以天然地处理多写的问题，但是代价也很高。读写锁的应用场景几乎是万能的，但seqlock不能用于保护指针资源。seqlock比读写锁性能更好，所以seqlock与读写锁也不是取代关系，在很多场景下seqlock是读写锁的优化版本。
从性能上看，seqlock与RCU锁最接近，RCU锁的写性能不如seqlock，seqlock还能提供多写的支持。seqlock在读取时遇到不一致需要回滚，而RCU锁不需要回滚，所以两者的区别在于业务场景的问题。如果业务要求新数据到达的时候旧数据必须立刻作废，就只能使用seqlock，反之，如果没有这个要求，则应当使用RCU锁。RCU锁真正强大的地方并不在于对读写锁的控制能力，而是它不需要为每个资源都准备一个锁结构。
hlist是开链哈希表常用的链表数据结构，在多线程的情况下要加锁。内核提供了一个带RCU接口的hlist实现（类似的实现还有list），通过带RCU后缀的API直接封装了RCU锁操作，主要用到的API如下。
update的更新操作对应hlist_replace_rcu（）函数，读取操作对应hlist_for_each_entry_rcu（）函数，遍历操作如下。
在使用hlist_replace_rcu（）函数的时候，遍历函数的外面还需要加上rcu_read_lock（）函数和rcu_read_unlock（）函数，才能组成RCU锁的读取临界区。
如果在遍历过程中删除了当前遍历到的pos节点，遍历就会中断，为了能在遍历中同时删除节点，hlist_del_rcu（）函数的定义如下。在调用hlist_for_each_entry_rcu遍历的时候，可以直接在循环内部删除当前entry。
hlist_del_rcu（）函数的n->next不能被无效（POISON），也就是遍历可以继续执行，但是删除操作仍然不能跟添加操作并行发生，需要额外加锁，如果该函数与遍历函数一起使用，那么与写操作不冲突了就可以直接使用，所以删除操作一般发生在RCU遍历之中。
replace函数是一个典型的update操作，但是没有调用同步函数，所以这个函数不是等待读操作完就可以执行的。replace函数并不涉及内存回收，定义如下。
整个RCU锁操作中只涉及内存栅，没有涉及内存回收。无论是add还是del操作都是排他的，这意味着同时只能发生一个写操作，这个保证只能由使用者自己用其他的锁机制来保证。这里封装的RCU锁的API的最大意义是可以同时进行修改与遍历操作，不需要加锁。
这样就产生了另外一个问题，既然所有的API中都没有synchronize_rcu（）函数，为何在遍历函数的外部增加rcu_read_lock（）函数和rcu_read_unlock（）函数呢？因为修改操作不涉及释放内存，整个RCU锁的核心是释放内存带来的读取错误问题，既然hlist操作（list操作同样）在语义上不释放内存，那么整个API的内部也就没有临界区和写同步的函数使用。但是，如果使用者需要从链表上删除节点的同时释放内存，就需要在遍历的外部加临界区，在释放内存之前加synchronize_rcu（）函数。
资源锁在本质上是同步和互斥的问题，且大部分是处理同时写的问题，所以只要能保证比较和写的操作都是原子的，线程就可以是无锁的。
同样的思想，Linux也提供了两组原子操作：一组针对整数；另一组针对位。使用自旋锁代价很大，因为当一个CPU运行时需要另外的CPU空转等待，但是当要锁住的代码量很少时，使用自旋锁就比使用信号量付出的代价小很多，所以，自旋锁不仅用于软中断，还可以用于给很少的一段代码加锁，示例如下。
从以上简单的模型可以看出，自旋锁的核心原理就是一个取值为0或1的整数的加减问题。自旋锁只在SMP中才有意义，否则一个CPU自旋就会永久堵塞。当一个自旋锁上有很多进程在自旋等待时，就可以判断在自旋锁上的操作非常忙。判断的方式是在自旋的过程中会发现自旋锁的所有者发生了改变，此时，应该睡眠而不是继续自旋。
除了自旋锁，还有一种锁需要忙等，这就是顺序锁。顺序锁使用了一个巧妙而又非常简单的思想：在读之前看锁值，在读之后再看锁值，如果锁值在读的前后没变化，就表明在读的过程中读的值没有被写，不需要重读，否则就重读。写的时候会改变锁值，原理相当于自旋锁，但是可以允许有多个写操作。读操作在多个写操作全部完成后才能读到正确的值。
当要加锁的是复杂的逻辑时，就需要使用信号量这种重量级的锁，但是一般应该尽量避免大块代码的加锁。信号量有一个问题：如果多个CPU获得读锁，则信号量本身会在各个CPU的cache中不断地刷新，从而降低效率。解决的方式是在内核定义一个新型的信号量：percpu-rw-semaphore。
RCU锁允许不阻塞写操作，当进行多个写操作时不是写到同一个地方，而是拷贝一份新的数据进行写操作。读操作还继续读旧的数据，这样以提高对内存的占用为代价换来读和写都不阻塞。
资源被抢占的情况有两种：SMP系统下多个CPU的并发访问和一个CPU下的可抢占访问。大部分应用在开发时都使用一样的锁来锁数据，资源被抢占的两种情况有不一样的特点。在很多情况下，一个CPU的可抢占锁可以做得更轻巧。
通过preempt_enable（）、preempt_disable（）、preempt_enable_no_resched（）、preempt_count（）、preempt_check_resched（）这几个函数可以在可抢占单CPU的情况下完成锁的工作，就不需要其他种类的锁了。在中断处理中，可以禁止流程被抢占，示例如下。
这样就不能在中间代码发生中断，也避免了在load之后中断可能修改num大小的这种情况的发生。
最有效的资源访问方式就是不加锁，大部分的问题都可以使用无锁设计来实现，但是这样可能带来内存上更大的损耗和代码更难管理的问题。