Linux kernel同步机制（上篇） https://mp.weixin.qq.com/s/mosYi_W-Rp1-HgdtxUqSEg
Linux kernel 同步机制（下篇） https://mp.weixin.qq.com/s/-GnR-nryH_7xkNVhJ8AMNw
Linux kernel同步机制（上篇）
在现代操作系统里，同一时间可能有多个内核执行流在执行，因此内核其实像多进程多线程编程一样也需要一些同步机制来同步各执行单元对共享数据的访问，尤其是在多处理器系统上，更需要一些同步机制来同步不同处理器上的执行单元对共享的数据的访问。在主流的Linux内核中包含了如下这些同步机制包括：
-
原子操作
-
信号量（semaphore）
-
读写信号量（rw_semaphore）
-
Spinlock
-
Mutex
-
BKL(Big Kernel Lock，只包含在2.4内核中，不讲)
-
Rwlock
-
brlock（只包含在2.4内核中，不讲）
-
RCU（只包含在2.6内核及以后的版本中）
-
seqlock（只包含在2.6内核及以后的版本中）
本文章分为两部分，这一章我们主要讨论原子操作，自旋锁，信号量和互斥锁。
一、原子操作
原子操作的概念来源于物理概念中的原子定义，指执行结束前不可分割（即不可打断）的操作，是最小的执行单位。
原子操作与硬件架构强相关，其API具体的定义均位于对应arch目录下的include/asm/atomic.h文件中，通过汇编语言实现，内核源码根目录下的include/asm-generic/atomic.h则抽象封装了API，该API最后分派的实现来自于arch目录下对应的代码。
Structure Definition
typedefstruct{intcounter;}atomic_t;
原子操作主要用于实现资源计数， 许多引用计数(refcnt)就是通过原子操作实现，例如TCP/IP协议栈的IP碎片中，struct ipq中的refcnt字段，类型即为atomic_t。
atomic_add
原子操作的实现比较简单，以下为例。
原子操作的原子性依赖于ldrex与strex实现，ldrex读取数据时会进行独占标记，防止其他内核路径访问，直至调用strex完成写入后清除标记。自然strex也不能写入被别的内核路径独占的内存，若是写入失败则循环至成功写入。
API
原子操作的API包括如下, 以arm平台为例：
二 、自旋锁（spinlock)
自旋锁是这样一种同步机制：若自旋锁已被别的执行者保持，调用者就会原地循环等待并检查该锁的持有者是否已经释放锁（即进入自旋状态），若释放则调用者开始持有该锁。自旋锁持有期间不可被抢占。
Structure Definition
从定义出发， spinlock根本的实现依赖于具体架构实现中slock这个变量，由于spin_lock是大多locking机制的基础，我们看一看它的实现。
Lock & Unlock
核心unlock函数，使owner自增，保持数据同步。
核心lock函数，使slock +2^16, 当next==owner时，释放锁，否则进入循环等待。Prefetchw用于cache预加载数据。
由于slock与tickets共享同一块内存(union)，slock 占32位4字节，tickets内部变量next与owner各16位2字节。以大端序为例，slock 高2字节与next共享，低2字节与owner共享，因此arch_spin_lock实际上是将tickets.next+1。假设初始时next与owner皆为0，此时next与owner不等，通过wfe指令进入一小段时间等待状态，而后读取新的owner值检查与next是否相等，不等则继续等待，相等则结束等待。
而owner的值由arch_spin_unlock控制，即unlock控制何时结束等待。
Spin_lock basic API
Spin_lock API & irq
性能上，spin_lock > spin_lock_bh > spin_lock_irq > spin_lock_irqsave。
安全上，spin_lock_irqsave > spin_lock_irq > spin_lock_bh >spin_lock。
Spin_lock 不同版本的使用
spin_lock用于阻止在不同CPU上的执行单元对共享资源的同时访问以及不同进程上下文互相抢占导致的对共享资源的非同步访问，而中断失效（spin_lock_irq）和软中断失效(spin_lock_bh)却是为了阻止在同一CPU上软中断或中断对共享资源的非同步访问。
-
如果被保护的共享资源只在进程上下文访问和软中断上下文访问，那么当在进程上下文访问共享资源时，可能被软中断打断，从而可能进入软中断上下文来对被保护的共享资源访问，因此对于这种情况，对共享资源的访问最好使用spin_lock_bh和spin_unlock_bh来保护。
-
如果被保护的共享资源只在进程上下文和tasklet或timer上下文访问，那么应该使用与上面情况相同，因为tasklet和timer是用软中断实现的。
-
如果被保护的共享资源只在两个或多个tasklet或timer上下文访问，那么对共享资源的访问仅需要用spin_lock和spin_unlock来保护，不必使用_bh版本，因为当tasklet或timer运行时，不可能有其他tasklet或timer在当前CPU上运行。 如果被保护的共享资源只在一个软中断（tasklet和timer除外）上下文访问，那么这个共享资源需要用spin_lock和spin_unlock来保护，因为同样的软中断可以同时在不同的CPU上运行。
-
如果被保护的共享资源在软中断（包括tasklet和timer）或进程上下文和硬中断上下文访问，那么在软中断或进程上下文访问期间，可能被硬中断打断，从而进入硬中断上下文对共享资源进行访问，因此，在进程或软中断上下文需要使用spin_lock_irq和spin_unlock_irq来保护对共享资源的访问。
-
在使用spin_lock_irq和spin_unlock_irq的情况下，完全可以用spin_lock_irqsave和spin_unlock_irqrestore取代，那具体应该使用哪一个也需要依情况而定，如果可以确信在对共享资源访问前中断是使能的，那么使用spin_lock_irq更好一些，因为它比spin_lock_irqsave要快一些。
三、信号量（Semaphore）
三、信号量（Semaphore）
Linux内核的信号量在概念和原理上与用户态的System V的IPC机制信号量是一样的，但是它不可能在内核之外使用，因此它与System V的IPC机制信号量完全不同。
信号量是这样一种同步机制：信号量在创建时设置一个初始值count，用于表示当前可用的资源数。一个任务要想访问共享资源，首先必须得到信号量，获取信号量的操作为count-1，若当前count为负数，表明无法获得信号量，该任务必须挂起在该信号量的等待队列等待；若当前count为非负数，表示可获得信号量，因而可立刻访问被该信号量保护的共享资源。当任务访问完被信号量保护的共享资源后，必须释放信号量，释放信号量通过把count+1实现，如果count为非正数，表明有任务等待，它也唤醒所有等待该信号量的任务。
Structure Definition
可以发现，信号量是基于spinlock实现的，对其封装以满足高级的功能，例如全局共享资源的配置，并通过等待队列较为灵活的调度。信号量与接下来要讲的mutex都建立在自旋锁实现的执行同步上。
了解了信号量的结构与定义，我们来看看最核心的两个实现down ，up。
down & up
down用于调用者获得信号量，若count大于0，说明资源可用，将其减一即可。
若count<0,将task加入等待队列，并进入等待队列，并进入调度循环等待，直至其被__up唤醒，或者因超时以被移除等待队列。
up用于调用者释放信号量，若waitlist为空，说明无等待任务，count+1，该信号量可用。
若waitlist非空，将task从等待队列移除，并唤醒该task,对应__down条件。
Semaphore API
四、互斥锁（Mutex）
Linux 内核互斥锁是非常常用的同步机制，互斥锁是这样一种同步机制：在互斥锁中同时只能有一个任务可以访问该锁保护的共享资源，且释放锁和获得锁的调用方必须一致。因此在互斥锁中，除了对锁本身进行同步，对调用方（或称持有者）必须也进行同步。当互斥锁无法获得时，task会加入等待队列，直至可获得锁为止。
Structure Definition
互斥锁从结构上看与信号量十分类似，但将原本的int类型的count计数，改成了atomic_long_t的owner以便同步，保证释放者与持有者一致。
mutex_lock & mutex_unlock
上图简单的表现了mutex_lock与mutex_unlock实现的对称性，___mutex_trylock_fast用于owner为0的特殊状态，用于快速加锁，实现核心在slowpath版本上。
*might_sleep指在之后的代码执行中可能会sleep。
由于mutex实现的具体步骤相当复杂，这里选讲比较核心简单的两块。Mutex有关等待队列的处理比较复杂，有兴趣阅读相关内核书籍。
当且仅当lock当前的owner没有变化时（没有其他mutex抢先拥有该锁），此时获得锁，返回NULL, owner 为 curr | flags,owner本身对应task指针。若该锁已被占用，owner和当前task不匹配，返回owner对应指针。
当unlock时，不考虑等待队列的影响，则与上述类似，当且仅当之前持有锁的owner可以解锁，解锁时本来应将lock的owner置为初始0，但是这里保留了mutex的flag以便后续操作。
*这里的owner实际上是task_struct的指针，也就是地址，由于task_struct的地址是L1_cache对齐的，因此实际上指针地址后三位为0，因此linux内核利用这三个比特位用于设置mutex的标志位，不影响指针地址的表示也更高效利用了冗余的比特位。
Mutex 的改进
最初的互斥锁仅支持睡眠等待，然而经过漫长时间的改进，如今的互斥锁已经可以支持自旋等待，通过MCS锁机制实现。在内核中可以选择配置以支持，CONFIG_MUTEX_SPIN_ON_OWNER。
如上是4.9内核中mutex中常用有效的字段，目前最常用的算法是OSQ算法。自旋等待机制的核心原理是当发现持有者正在临界区执行并且没有其他优先级高的进程要被调度（need_resched）时，那么mutex当前所在进程认为该持有者很快会离开临界区并释放锁，此时mutex选择自旋等待，短时间的自旋等待显然比睡眠-唤醒开销小一些。
在实现上MCS保证了同一时间只有一个进程自旋等待持有者释放锁。MCS 的实现较为复杂，具体可参考一些内核书籍。MCS保证了不会存在多个cpu争用锁的情况，从而避免了多个CPU的cacheline颠簸从而降低系统性能的问题。
经过改进后，mutex的性能有了相当大的提高，相对信号量的实现要高效得多。因此我们尽量选用mutex。
Mutex 的使用条件
Mutex虽然高效，灵活，但存在若干限制条件，需要牢记:
-
同一时刻只有一条内核路径可以持有锁
-
只有锁持有者可以解锁
-
不允许递归加锁解锁
-
进程持有mutex时不可退出
-
Mutex 可能导致睡眠阻塞，不可用于中断处理与下半部使用
Mutex API
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
。。。Linux kernel 同步机制（下篇） https://mp.weixin.qq.com/s/-GnR-nryH_7xkNVhJ8AMNw
五、同步机制之间的比较
