Linux内核同步
临界区和竞争条件
所谓临界区（也称为临界段）就是访问和操作共享数据的代码段。多个执行线程并发访问同一个资源通常是不安全的，为了避免在临界区中并发访问，必须保证这些代码原子执行，操作在执行结束前不可被打断，就如同整个临界区是一个不可分割的指令一样。如果两个执行线程有可能处于同一个临界区中同时执行，那么就是程序包含一个bug。如果这种情况确实发生了，我们就称它是竞争条件（race conditions），这样命名是因为这里会存在线程竞争。
加锁
假设我们需要处理一个队列上的所有请求，该队列通过链表实现，链表中的每一个节点就代表一个请求，有两个函数可以用来操作此队列，一个函数将请求添加到队列的尾部，一个函数从队列头部删除请求，并处理它。如果一个线程试图读取队列，而这时正好另一个线程正在处理该队列，就会产生危害。当共享资源是一个复杂的数据结构时，竞争条件往往使该数据结构遭到破坏。
表面上看，这种情况好像没有一个好的解决方法，一个处理器读取队列的时候，我们怎么能禁止另外一个处理器更新队列呢？虽然有些体系结构提供了简单的原子指令，实现算术运算和比较之类的原子操作，但让体系结构提供专门的指令，对于像上例中那样不定长度的临界区进行保护，就强人所难了。我们需要一种方法确保一次只有一个线程对数据结构进行操作，或者当另一个线程在临界区标记时，就禁止其他线程访问。锁提供的就是这样的机制。
锁有多种多样的形式，而且加锁的粒度范围也各不相同--Linux自身实现了几种不同的锁机制。各种锁机制之间区别主要在于，当锁已经被其他线程持有，因而不可用时的行为表现--- 一些锁被征用时会简单地执行等待，而另外一些锁会使当前任务睡眠直到锁可用为止。
锁使用原子操作实现的，而原子操作不存在竞争。几乎所有处理器都实现了测试和设置指令，这一指令测试整数的值，如果其值为0，就设置一新值。0意味着 开锁。在流行的x86体系结构中，锁的实现也不例外，它使用了称为compare和exechange的类似指令。
造成并发的原因
用户空间之所以需要同步，是因为用户程序会被调度程序抢占和重新调度。由于用户进程可能在任何时刻抢占，而调度程序完全可能选择另一个高优先级的进程到处理器上执行，所以就会使得一个程序正处于临界区时，被非自愿的抢占了。如果新调度的程序也进入同一个临界区，前后两个进程互相之间就会产生竞争。另外，因为信号处理是异步发生的，所以即使是单线程的多个进程共享文件，或者一个程序内处理信号，也有可能产生竞争条件。其实两者并不是同时发生的，他们之间是互相交叉执行，所以也称为为并发执行。如果有一台支持对称多处理器的机器，那么两个进程可以真正的在临界区中同时执行。内核中有类似可能造成并发执行的原因：
- 中断 中断几乎可以在任何时刻发生，也就可能随时打断当前正在执行的代码。
- 软中断和tasklet 内核能在任何时刻唤醒或调度软中断和tasklet,打断当前正在执行的代码。
- 内核抢占 因为内核具有抢占性，所以内核中的任务可能会被另一个任务抢占。
- 睡眠及与用户和空间的同步 内核执行的进程可能会睡眠，这就会唤醒调度程序，从而导致调度一个新的用户进程执行。
- 对称多处理 两个或多个处理器可以同时执行代码
死锁
死锁的产生需要一定条件，要有一个或多个执行线程和一个或多个资源，每个线程都在等待其中的一个资源，但所有的资源都已经被占用了。所有线程都在互相等待，但他们永远不会释放已经占有的资源。于是任何线程都无法继续，这便意味着死锁的发生。
预防死锁的发生非常重要，虽然很难证明代码不会发生死锁，但是可以写出避免死锁的代码，一些简单的规则对避免死锁大有帮助：
- 按照顺序加锁 使用嵌套的锁时必须保证以相同的顺序获取锁，这样可以阻止指明拥抱类型的死锁。最好能记录下锁的顺序，以便其他人也能照此顺序使用。
- 防止发生饥饿 试问，这个代码的执行是否一定会结束？如果A不发生？B要一直等下去吗？
- 不要重复请求同一个锁
- 设计应该保持简单 越复杂的加锁方案越有可能造成死锁
争用和扩展性
锁的争用（lock contention），或简称争用，是指当锁正在被占用是，有其他线程试图获得锁。说一个锁处于高度争用状态，就是指有多个其他线程在等待获得该锁。由于锁的作用是使程序以串行的方式对资源进行访问，所以使用锁无疑会降低系统的性能。被高度争用的锁会成文系统的瓶颈，严重降低系统性能。即使是这样，相比于被互相抢夺共享资源的线程撕成碎片，搞得内核崩溃，还是这种同步保护来的更好一点，当然如果能够解决高度争用问题，那更好了。
扩展性（scalability）是对系统可扩展程度的一个度量。理想情况下，处理器的数量加倍应该会使系统处理性能翻倍，而实际上这是不可能达到的。
原子操作
原子操作可以保证指令以原子的方式执行----执行过程不被打断，众所周知，原子原本指的是不可分割的微粒，所以原子操作也就是不能够被分割的指令。比如：原子加操作，它通过把读和增加变量的行为包含在一个单步中执行，从而防止了竞争的发生，保证了操作结果总是一致。
线程1 线程2
获得i(T) 获得i(7)
增加i(7-->8) -
- 增加i(8-->9)
写回i(8) -
- 写回i(8)
使用原子操作，上述的竞争不会发生--事实上不可能发生。从而，计算过程无疑会是下述之一：
线程1 线程2
获得、增加和存储i(7-8) -
- 获得、增加和存储(8-->9)
或者
线程1 线程2
- 获得、增加和存储(7-->8)获得、增加和存储i(8-->9) -
原子整数操作
64位原子整型操作
随着64位的体系结构越来越普及，内核开发者也在考虑原子变量除32位atomic_t类型外，也应该引入64位atomic64_t。因为移植性原因，atomic_t变量大小无法再体系结构之间改变，所以atomic_t类型即便在64位体系结构下也是32位的，如果使用64位的原子变量，则要使用atomic64_t类型--其功能和32位的西东无异，使用方法完全相同，不同的只有整型变量大小从32位变为了64位。几乎经典的32位系统都有64位的实现。
原子位操作
自旋锁
如果每个临界区都能像增加变量这样简单就好了，现实世界里，临界区甚至可以跨越多个函数。我们经常碰到这种情况：先从一个数据结构中移除数据，对其进行格式转换和解析，最后再把它加入到另一个数据结构中。整个过程中必须是原子的，在数据被更新完毕前，不能有其他代码读取这些数据。显然简单的原子操作对此无能为力，这就需要使用更为复杂的同步方法--锁来提供保护。
Linux内核中最常见的锁时自旋锁（spin lock）。自旋锁最多只能被一个可执行线程持有。如果一个执行线程试图获得一个被已经持有（所谓的争用）的自旋锁，那么该线程就会一直进行循环--旋转--等待锁重新可用。要是锁未被争用，请求锁的执行线程能够立刻得到它，继续执行。
自旋锁相当于坐在门外等待同伴从里面出来，并把钥匙交给你。如果你到了门口，发现里面没有人，就可以抓到钥匙进入房间。如果你到了门口发现里面有人，就必须在门外等待钥匙，不断的检查房间是否为空。当房间为空时，你就可以抓到钥匙进入。正因为有钥匙（相当于自旋锁），才允许一次只有一个人进入房间（相当于临界区）。
一个被争用的自旋锁是的请求它的线程在等待锁重新可用时自旋（特别浪费处理器时间），这种行为是自旋锁的要点。所以自旋锁不应该被长时间持有。实时上，这点正是自旋锁的初衷：短时间内进行轻量级加锁。还可以采用另外的方式来处理对锁的争用：让请求线程睡眠，直到锁重新可用再唤醒它。这样处理器就不必循环等待，可以去执行其他代码。这也会带来一定的开销--这里有两次明显的上下文切换，被阻塞的线程要被换出和换入，因此，持有自旋锁的时间最好小于完成两次上下文切换的耗时。
读-写自旋锁
有时锁的用途可以明确地分为读取和写入两个场景，对一个链表可能既要更新又要检索。当更新写入链表时，不能有其他代码并发地写链表或从链表中读取数据，写操作要求完全互斥。另一方面，当进行检索链表时，只要其他程序不对链表进行写操作就行了。
Linux内核专门提供了读--写自旋锁，这种自旋锁为读和写分别提供了不同的锁，一个或多个读任务可以并发地持有读锁，相反，用于写的锁最多只能被一个写任务持有，而且此时不能有并发的读操作。使用读--写锁要考虑的一点是这种锁机制照顾读要比照顾读多一点。当读锁被持有是，写操作为了互斥访问只能等待，但是，读却可以继续成功的占用锁，而自旋等待的写在所有的读释放锁之前是无法获得锁的。
如果加锁时间不长且代码不会睡眠，利用自旋锁是最佳选择。如果锁的时间可能很长或者代码在持有锁时可能睡眠，那么最好使用信号量来完成加锁功能。
信号量
Linux中的信号量是一种睡眠锁。如果一个任务试图获得一个不可用的信号量时，信号量会将其推进一个等待队列，然后让其休眠。这是处理器就能重获*，从而去执行其他代码。当持有的信号量可用后，处于等待队列中的哪个任务被唤醒，并获得信号量。
从信号量睡眠特性得出一些有意思的结论：
- 由于争用的信号量的进程在等待锁重新变为可用时会睡眠，所以信号量适用于锁会被长时间持有的情况。
- 相反，锁被短时间持有，使用信号量就不太合适，因为睡眠、维护等待队列以及唤醒锁花费的开销可能比锁被占用的全部时间还要长。
- 由于执行线程在锁被争用时会睡眠，所以只能在进程上下文中才能获取信号量锁，因为在中断上下文中是不能进行调度的。
- 可以在持有信号量时去睡眠，因为当其他进程试图获得同一信号量时不会因此而次所。
- 在占用信号量的同时不能占用自旋锁，因为在你等待信号量时可能会睡眠，而在持有自旋锁时是不允许睡眠的。
信号量不同于自旋锁，它不会禁止内核抢占，所以持有信号量的代码可以被抢占。这意味着信号量不会对调度的等待时间带来负面影响。与自旋锁一样，信号量也有读--写信号量。
互斥体（mutex）
内核中唯一允许睡眠的锁时信号量。多数用户使用信号量只使用计数1，实际上是把其作为一个互斥的排他锁使用---好比允许睡眠的自旋锁。不幸的是，信号量用途更通用，没有多少限制。这点使得信号量适合用于那些较复杂的，未明情况下的互斥访问，比如内核于用户空间复杂的交互行为。但这也意味着简单的锁定而使用信号量并不方便，并且信号量也缺乏强制的规则来行使任何行使的自动调试，即便受限的调试也不可能。为了找到一个更简单睡眠锁，内核开发者引入了互斥体（mutex），互斥体是指任何可以睡眠的强制互斥锁。
mutex的简洁性和高效性源自于相比使用信号量更多的受限性。它不同于信号量，因为mutex仅仅实现了Dijkstra设计初衷中的最基本行为。因此mutex的使用场景相对而言更严格：
任何时刻中只有一个任务可以持有mutex，也就是说，mutex的使用计数永远是1
给mutex上锁者必须负责给其解锁----不能再一个上下文中锁定一个mutext，而在另外一个上下文中给它解锁。这个限制使得mutex不适合内核同用户空间复杂的同步场景。最常使用的方式是：在同一个上下文中上锁和解锁。
- 递归地上锁和解锁是不允许的。也就是说，你不能递归地持有同一个锁，同样你也不能再去解锁一个已经被解开的mutex。
- 当持有一个mutex时，进程不可以退出
- mutex不能再中断或者下半部中使用
- mutex只能通过官方api管理：初始化、不可被拷贝、手动初始化或者重复初始化。
互斥体和信号量很相似，内核中两者共存会令人混淆。他们的标准使用方式都有简单的规范：除非mutex的某个约束妨碍你使用，否则相比信号量要优先使用mutex。
何时使用自旋锁，何时使用互斥体（信号量）对编写优良代码很重要，但是多数情况下，并不需要太多考虑，因为在中断上下文中只能使用自旋锁，而在任务睡眠时只能使用互斥体。
完成变量
如果在内核中一个任务需要发出信号通知另一个任务发生了某个特定事件，利用完成变量（completion variable）是使两个任务得以同步的简单方法。如果一个任务要执行一些工作时，另一个任务就会在完成变量上等待。当这个任务完成工作后，会使用完成变量去唤醒在等待的任务。这听起来很像一个信号量，的确如此，思想上是一样的。事实上，完成变量仅仅提供了代替信号量的一个简单的解决方法。
顺序锁
顺序锁，通常简称seq，是在2.6版本内核中才引入的一种新型锁。这种锁提供了一种很简单的机制，用于读写共享数据。实现这种锁主要依靠一个序列计数器。当有疑义的数据被写入时，会得到一个锁，并且序列值会增加。会读取数据之前和之后，序列号都被读取。如果读取的序列号相同，说明在读操作进行的过程中没有被写操作打断过。如果读取的值是偶数，那么就表明写操作没有发生（锁的初始值是0，所以写锁会使值称为奇数，释放的时候变成偶数）。
在多个读和少数写共享一把锁的时候，seq锁有助于提供一种非常轻量级和具有可扩展性的外观。但是seq锁对写更有利。只要没有其他写，写锁总是能够被成功获得。读不会影响写锁，这点和读--写自旋锁以及信号量一样。挂起的写会不断地使得读操作讯黄，直到不再有任何写持有锁为止。
seq锁在遇到如下需求时会是理想的选择：
- 数据存在很多读
- 数据只有很少的写
- 虽然写很少，但是希望优先于读，而且不允许读让写饥饿
- 数据很简单，比如简单结构，不能使用原子的
禁止抢占
由于内核是抢占性的，内核中的进程在任何时刻都可能停下来以便另一个具有更高优先权的进程运行。这意味着一个任务与被抢占的任务可能会在同一个临界区内运行。为了避免这种情况，内核抢占代码使用自旋锁作为非抢占区域的标记。如果一个自旋锁被持有，内核便不能进行抢占。因为内核抢占和SMP面对相同的并发问题，并且内核已经是SMP安全的，所以，这种简单的变化使得内核也是抢占安全的（preempt-safe）。
实际中，某些情况并不需要自旋锁，但是仍然需要关闭内核抢占。最频繁出现的情况是每个处理上的数据。如果数据对每个处理器时唯一的，那么这样的数据可能就不需要使用锁来保护，因为数据只能被一个处理访问。如果自旋锁没有被持有，内核又是抢占式的，那么一个新调度的任务就可能访问同一个变量。
任务B被调度
任务B操作变量foo
任务B完成
任务A被调度
任务A继续操作变量foo
这是一个单处理器计算机，变量foo也会被多个进程以伪并发的方式访问，通常，这个变量会请求得到一个自旋锁（防止多处理器上的真并发）。但是如果这是每个处理器上的独立变量，可能就不需要锁。
为了解决这个问题，可以通过preempt_disable()禁止内核抢占，这是一个可以嵌套调用的函数，可以调用任意次。每次调用都必须有一个相应的preempt_enable()调用。当最后一次preempt_enable()被调用后，内核抢占才重新启用。
抢占计数存放着持有锁的双和preempt_disable()的调用次数，如果计数是0，那么内核可以进行抢占：如果为1或更大值，那么，内核就不会进行抢占。这个数非常有用--它是一种对原子操作和睡眠很有效的调试方法。
顺序和屏障
当处理多处理器之前或硬件设备之间的同步问题时，有时需要在你的程序代码中以指定的顺序发出读内存和写内存指令。在和硬件交互式，时常需要确保一个给定的读操作发生在其他读或写操作之前。另外，在多处理器上，可能需要按写数据的顺序读数据。但是编译器和处理器为了提高效率，可能对读和写重排序，这样无疑使问题复杂化了，幸好，所有可能重排序和写的处理器提供了机器指令来确保顺序要求。同样也可以指定编译器不要对给定点周围的指令进行重排序。这些确保顺序的指令称作屏障(barriers).
基本上，在某些处理器上存在以下代码：
a=1;
b=2;
有可能会a中存放新值之前就在b中存放新值。
编译器和处理器都看不出a和b之间的关系。编译器会在编译时按照这种顺序编译，这种顺序会是静态的，编译的目标代码就只把a放在b之前。但是处理器会重新动态排序，因为处理器在执行指令期间，会在取值指令和分派时，把表面上看似无关的指令按自认为最好的顺序排序，大多数情况下，这样的排序是最佳的，因为a和b没有明显的关系。尽管有些时候程序员知道什么事最好的顺序。
尽管前面的例子可能被重新排序，但是处理器和编译器绝不会对下面的代码冲排序：
a=1;
b=2;
此处a和b均为全局变量，因为a与b之间有明确的数据依赖关系。
但是不管是编译器还是处理器都不知道其他上下文中的相关代码。偶然情况下，有必要让写操作被其他代码识别，也让所期望的指定顺序之外的代码识别。这种情况常常发生在硬件设备上，但是在多数处理器上也很常见。
rmb()方法提供了一个读内存屏障，它确保跨越rmb()的载入动作不会发生重排序。也就是说，在rmb之前的载入操作不会被重新排在该调用之后，同理rmb()之后的载入操作不会被重新排在该调用之前。
wmb()方法提供了一个写内存屏障，这个函数的功能和rmp()功能类似，区别仅仅是它是指对存储而非载入---它确保跨越屏障的存储不会发生重排序。
mb()方法既提供了读内存屏障也提供了写屏障。载入和存储动作都不会跨越屏障重新排序。这是因为一条单独的指令（通常和rmb()使用同一个指令）既可以提供载入屏障也可以提供存储屏障。
read_barrier_depends()是rmb()的变种，它提供了一个读屏障，但是仅仅是针对后续读操作所依靠的那些载入。因为屏障后的读操作依赖于屏障前的读操作，因此，该屏障确保屏障前的读操作在屏障后的读操作之前完成，基本上说，该函数设置一个读屏障，如rmb()，但是只针对特定的读---也就是那些相互依赖的读操作。在有些体系结构上，read_barrier_depends()比rmb执行的快，因为它仅仅是个空操作，实际并不需要。
看看使用了mb()和rmb()的一个例子，其中a的初始值是1，b的初始值是2
线程1 线程2
a=2 --
mb() --
b=4 c=b
-- rmb()
-- d=a
如果不适用内存屏障，在某些处理器上，c可能接收了b的新值，而d接收了a原来的值，比如c可能等于4（正是我们期望的），然而d可能等于1（不是我们期望的）。使用mb()能确保a和b按照预定的顺序写入，而rmb去报c和d按照预定的顺序读取。
这种重排序的发生时因为现代处理器为了优化其传送管道(pipeline),打乱了分派和提交指令的顺序，如果上例中读入a、b时的顺序被打乱的话，又会发生什么呢？rmb()或wmb()函数相当于指令，他们告诉处理器在继续执行前提交所有尚未处理的载入和存储指令。
看一个类似的例子，但是其中一个线程用read_barrier_depends()代替了rmb()，例子中的a的初始值是1，p是&b。
线程1 线程2
a=3 ---
mb() ---
p=&a pp = p
--- read_barrier_depends()
--- b = *pp
再一次生命，如果没有内存屏障，有可能在pp被设置成p前，b就被设置为pp了。由于载入*pp艺考载入p，所以read_barrier_depends()提供了一个有效的屏障。虽然使用rmb()同样有效，但是因为读是数据相关的，所以我们使用read_barrier_depends()可能更快。注意，不管在那种情况下，左边的线程都需要mb()操作来确保预定的载入或存储顺序。
