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）
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
