Linux kernel 同步机制（下篇）
之前的文章
在上一部分，我们讨论了最基本常见的几类同步机制，这一部分我们将讨论相对复杂的几种同步机制，尤其是读写信号量和RCU，在操作系统内核中有相当广泛的应用。
读写信号量（rw_semaphore）
BKL(Big Kernel Lock，只包含在2.4内核中，不讲)
Rwlock
brlock（只包含在2.4内核中，不讲）
RCU（只包含在2.6内核及以后的版本中）
一、读写信号量（RW_Semaphore）
读写信号量与信号量有相似也有不同，它是如下一种同步机制：读写信号量将访问者分为读者或者写者，读者在持有读写信号量期间只能对该信号量保护的共享资源进行读访问，而只要一个任务需要写，它就被归类为写者，其进行访问之前必先获得写者身份，在其不需写访问时可降级为读者。读写信号量可同时拥有不受限的读者数，写者是排他性的，独占性的，而读者不排他。若读写信号量未被写者持有或者等待，读者就可以获得读写信号量，否则必须等待直到写者释放读写信号量为止；若读写信号量没有被读者或写者持有，也没用写者等待，写者可以获得该读写信号量，否则等待至信号量全部释放（没有其他访问者）为止。
Structure Definition
若从上述结构定义看，最关键的前三个字段与mutex、信号量十分相似不再赘述，后面的OSQ字段在Mutex中提起过。由于内核有关读写信号量的实现有两种，取决于CONFIG_RWSEM_GENERIC_SPINLOCK的配置，但是一般默认该配置是关的，因此选用默认版本的实现进行解读。读写信号量同mutex一样，在最近的改进中均引入了OSQ lock机制实现自旋等待。
读写信号量与信号量之间的关系
读写信号量可能会引起进程阻塞,但是它允许N个读执行单元同时访问共享资源,而最多只允许有一个写执行单元访问共享资源;因此,读写信号量是一种相对放宽条件的、粒度稍大于信号量的互斥机制。信号量不允许任何操作之间有并发,即:读操作与读操作之间、读操作与写操作之间、写操作与写操作之间,都不允许并发;而读写信号量则只允许读操作与读操作之间的并发,但不允许读操作与写操作之间的并发,也不允许写操作与写操作之间的并发。因此读写信号量比较适合读多写少的情况，可良好地利用读者并发的特性。
Count 字段在读写信号量的表示含义
读写信号量中的count字段并不如信号量一般表示可用资源数量，而是标记了当前的访问情况，我们取32位的情况分析，默认是取32位配置。
先观察如下宏常量：
然后我们再考虑count，我们发现均是上述宏组合的结果，可以归类为以下几种情况：
所以可见count可以标记并区分许多访问情况， 尤其是当存在写者或阻塞时，其对应的有符号数(atomic_long_t)均为负数，可以作为判断的标记。
在传统的读写信号量中，会直接进阻塞，因此只有等待队列非空还是为空的问题，但是在最近的改进中存在自旋等待的问题，因此使得在锁的获取中可能出现自旋状态的写者偷出锁的情况。
__down_read & __up_read
根据count字段的含义，count + 1小于0说明原本存在写者或者等待队列非空，因此不能获得锁，rwsem_down_read_failed调用
一个读者释放后count - 1小于-1说明等待队列非空，因此还需唤醒等待的写者
Rwsem_down_read不能直接获取时调用，首先判断等待队列是否为空，为空则字段置为非空，并将count回退之前读的尝试，将当前task压入等待队列，如果当前没有人持有或正在获取锁锁,则唤醒等待队列的前面的进程，同时将唤醒进程的waiter.task置NULL，在调度中若发现自己的waiter.task为NULL，说明轮到本进程运行，置为TASK_RUNNING
down_write & up_write
一个写者获取锁后，如果返回的count不是0xffff0001，那么写者获取信号量失败
Rwsem_down_write_failed的基本逻辑与read相似，回退先前count的变化，对waitlist的处理，等待获取锁，有兴趣可以自己阅读源码。
一个写者释放锁后，如果count返回小于0，说明等待非空，将其唤醒。
RW_Semaphore API
二、读写锁（rw_lock）
读写锁实际是一种特殊的自旋锁，它把对共享资源的访问者划分成读者和写者，读者只对共享资源进行读访问，写者则需要对共享资源进行写操作。这种锁相对于自旋锁而言，能提高并发性，因为在多处理器系统中，它允许同时有多个读者来访问共享资源，最大可能的读者数为实际的逻辑CPU数。写者是排他性的，一个读写锁同时只能有一个写者或多个读者（与CPU数相关），但不能同时既有读者又有写者。
在读写锁保持期间也是抢占失效的。如果读写锁当前没有读者，也没有写者，那么写者可以立刻获得读写锁，否则它必须自旋在那里，直到没有任何写者或读者。如果读写锁没有写者，那么读者可以立即获得该读写锁，否则读者必须自旋在那里，直到写者释放该读写锁。
Structure Definition
从结构上看，读写锁与自旋锁基本相似，实际上二者的实现也十分相似，二者的关系可以类比读写信号量与信号量的关系。
arch_read_lock & arch_read_unlock
Read_lock实现上判断lock+1是否为负，为负说明有写者持有锁（0x80000000)，此时调用wfe进入一小段自旋状态后再度执行；若非负，则将lock+1更新至lock中。
对应read_lock，read_unlock仅仅需要将lock -1 更新至lock。
arch_write_lock & arch_write_unlock
write_lock 在尝试获得锁时，检查lock是否为0，不为0则说明有读者或者写者持有锁，此时wfe进入一小段等待直到lock为0，若lock为0则赋值lock获得锁。
Write_unlock只需将lock置零即可。
从这里可以看出，读写锁的实现上以及功能上，相当于针对自旋锁对于读多写少的场景提高并发度，设计原理与读写信号量十分类似。
RW_Lock API
三、顺序锁（seqlock）
顺序锁是对读写锁的一种优化:读者绝不会被写者阻塞，也就说，读者可以在写者对被顺序锁保护的共享资源进行写操作时仍然可以继续读，不必等待写者完成写操作，写者也不需要等待所有读者完成读操作才去进行写操作。但是，写者与写者之间仍然是互斥的。写操作的优先级大于读操作。
顺序锁有一个限制，它必须要求被保护的共享资源不含有指针，因为写者可能使得指针失效，但读者如果正要访问该指针，将导致OOPs。如果读者在读操作期间，写者已经发生了写操作，那么，读者必须重新读取数据，以便确保得到的数据是完整的。顺序锁适用于读多写少的情况。
这种锁对于读写同时进行的概率比较小的情况，性能是非常好的，而且它允许读写同时进行，更大地提高了并发性。顺序锁的一个典型的应用在于时钟系统。
Structure Definition
从结构上看，也是依赖于自旋锁的，seqcount用于同步写者访问的顺序以更新读者访问,自旋锁的作用在于实现写操作之间的互斥，读者访问不受限制。
write_seqlock & write_sequnlock
顺序锁对写操作之间必须互斥，实现上调用spin_lock进行互斥，另外对seqcount操作以同步读者的访问。
seqcount的计数符合以下规则：进入临界区时加一，离开临界区时也加一
read_seqretry & read_seqbegin
read_seqcount_begin返回当前seqlock的seqcount, 在读完后，需调用read_seqretry查看读者读完后的seqcount是否与读之前一致，一致则结束，不一致则说明有写操作正在或已经执行，需要重新读一次以更新数据。另外read_seqbegin返回的是lock.seqcount/2,实际上是写操作发生的次数。
seqlock API
其他_irqsave,_irq,_bh版本均是与其他锁类似的。
四、RCU（Read-Copy Update）
RCU是读写锁的高性能版本，既允许多个读者同时访问被保护的数据，又允许多个读者和多个写者同时访问被保护的数据（注意：是否可以有多个写者并行访问取决于写者之间使用的同步机制），读者没有任何同步开销，而写者的同步开销则取决于使用的写者间同步机制。
对于被RCU保护的共享数据结构，读者不需要获得任何锁就可以访问它，但写者在访问它时首先拷贝一个副本，然后对副本进行修改，最后使用一个回调（callback）机制在适当的时机(所有引用该数据的CPU都退出对共享数据的操作时)把指向原来数据的指针重新指向新的被修改的数据。有一个专门的垃圾收集器探测读者的信号，一旦所有读者都已发送信号告知它们不在使用被RCU保护的数据结构，垃圾收集器就调用回调函数完成最后的数据释放或修改操作。
RCU不能替代读写锁，当写比较多时，对读者的性能提高不能弥补写者导致的损失，但是大多数情况下RCU的表现高于读写锁。
RCU Basic API
RCU 临界区管理
之前的同步机制中，均是利用锁或原子操作实现的，一个锁管理一个临界区，并通过加锁解锁控制进程进入或者离开临界区。一个程序中可以存在若干的临界区，因此可以对应存在若干把锁分别管理，这是之前所有锁机制的基础。
然而RCU并不基于锁机制实现，RCU字段是耦合在进程描述符和CPU变量中的，是一种与系统强耦合的同步机制，RCU负责管理进程内所有的临界区，进程通过调用rcu_read_lock与rcu_read_unlock标记读者临界区，通过rcu_assign_pointer、list_add_rcu将数据纳入保护区，当写者copy出新数据时在读者全部退出临界区后，将新数据指针更新，旧数据将在垃圾收集器的检查中被释放，但存在延迟。
RCU 限制条件
RCU只保护动态分配并通过指针引用的数据结构
在被RCU保护的临界区中，任何内核路径都不能睡眠（经典实现中）
RCU callback的实现
rcu_head 是RCU回调函数的关键结构。此外，回调机制主要涉及两个基本函数__call_rcu(用于注册), __rcu_reclaim（用于调用）。
__call_rcu仅仅将func注册进rcu_head, 便立刻返回。该func一般用于回收释放copy后遗留的旧数据垃圾，但是RCU采用了延时执行防止读者还在读旧数据时回收数据造成崩溃。
Rcp主要用于全局控制，而rcu的回调函数以链式组织，next用于遍历链。
__rcu_reclaim用于回收rcu先前分配的旧数据，回调函数也是回收操作的一种。
实际上，synchronize_rcu在等待读者全数退出临界区时，也通过call_rcu注册了回调函数。
相对麻烦的是回收阶段，RCU通过一个垃圾收集器检查需要回收的旧数据并调用回调函数释放，准确的说调用rcu_check_callbacks检查是否有需要执行的回调函数，而后调用rcu_process_callbacks执行必要的rcu 回调函数。
那么问题来了，谁去调用rcu_check_callbacks函数呢？时钟系统，每当时间片消耗完或者出现时钟中断，时钟系统都将调用rcu_check_callbacks进行及时检查处理，避免过量的旧数据垃圾造成内存浪费。
RCU read
rcu_read_lock与rcu_read_unlock的经典实现是不可抢占的，从代码看，这两个函数仅仅用于开关抢占。
RCU read之所以禁止抢占，主要是由于写者必须等待读者完全执行完退出临界区方能修改数据指针。一旦读者被抢占，那么其退出临界区的过程将会阻塞，进而阻塞写者，这对性能是一种不小的开销。但是现在的linux 内核版本中提供了可抢占的版本，只是对抢占深度做了把控。
RCU Synchronize
可是RCU是如何获知所有读者已经离开临界区？RCU read实现中并没有设置字段标记进出临界区，RCU是通过什么判断的呢？既然RCU read过程不可抢占，那么换言之，若所有 CPU 都已经过一次上下文切换，则所有前置 reader 的临界区必定全部退出。
我们主要分析以下两种：
rcu_check_callbacks
synchronize_rcu
user其实在调用中真实的传入是user_tick,值为1指用户时间，0指系统时间，由于RCU必须在内核态执行，因此user为1说明必然不处于lock~unlock的时段，很有可能已经发生过rcu_read,因此发送一个RCU_SOFTIRQ软中断，调用rcu_process_callbacks。
synchronize_rcu的核心是wait_rcu_gp函数。
该函数通过注册一个func为wakeme_after_rcu的rcu_head并等待该rcu_head完成回调来判断之前的rcu读者已经全部退出。
由于该rcu_head注册较晚，当且仅当当前的读者都已退出临界区，该rcu_head的回调才可能执行，因此当该func回调完成，就必然已经满足同步条件。最后销毁该多余的head内存。
如下图：
RCU Example
Input.c 中的使用为例。
Grab_device即挂载设备，注意这里的rcu_assign_pointer用于将dev->grab加入rcu保护的共享区，handle（处理函数）是其值。在这里完成了向rcu注册数据的过程。
Input_pass_value处理所有的输入事件，首先我们read_lock标记进入临界区不可抢占，读出dev->grab并以处理输入事件，最后read_unlock退出临界区。
Release device与挂载相对，释放过程即将原本的handler变为NULL, 最后调用synchronize_rcu通知所有输入事件handler移除
五、同步机制之间的比较
