内核同步介绍

在使用共享内存的应用程序中，程序员必须特别留意保护共享资源，防止共享资源并发访问。内核也不例外。共享资源之所以要防止并发访问，是因为如果多个执行线程同时访问和操作数据，就有可能发生各线程之间相互覆盖共享数据的情况，造成被访问数据处于不一致的状态。并发访问共享数据是造成系统不稳定的一类隐患，而且这种错误一般难以跟踪和调试–所以首先要认识到这个问题的重要性。
要做到对共享资源的恰当保护往往很困难。多年之前，在Linux还未支持对称多处理器的时候，避免并发访问数据的方法相对来说比比较简单。在单一处理器的时候，只有在中断发生的时候，或在内核代码明确请求调度、执行另一个任务的时候，数据才有可能被并发访问。因此早期内核开发工作相比如今要简单许多！
但当年的太平日子一区不复返了，从2.0版开始，内核就开始支持对称多处理器了，而且从那以后对它的支持不断地加强和完善。支持多处理器意味着内核代码可以同时运行在两个或者更多的处理器上。因此如果不加保护运行在两个不同处理器上的内核代码完全可能在同一时间并发访问共享数据。随着2.6版本内核的出现，Linux内核已经发展成抢占式内核，这意味着调度程序可以在任何时刻抢占正在运行的内核代码，重新调度其他的进程执行。现在，内核代码中有不少部分都能够同步执行，而它们都必须妥善的保护起来。
本章我们将提纲挈领式地讨论操作系统内核中的并发和同步问题。下一章我们将详细介绍Linux内核为解决同步问题和防止产生竞争条件而提供的机制及接口。

临界区和竞争条件

所谓临界区即使访问和操作共享数据的代码段。多个执行线程并发访问同一资源通常是不安全的，为了避免在临界区中并发访问，编程者必须保证这些代码原子的执行–也就是说，操作在执行结束之前不可被打断，就如同整个临界区是一个不可分割的指令一样。如果两个执行线程有可能处于同一临界区中同时执行，那么这就是程序包含的一个bug。如果这种情况确实发生了，我们就称它是竞争条件（race conditions），这样命名是因为这里会存在线程竞争。这种情况出现的机会往往非常小–就是因为竞争引起的错误非常不易重现，所以调试这种错误才会非常困难。避免并发和防止竞争条件称为同步（synchronization）。

为什么我们需要保护

为了认清同步的必要性，我们首先要明白临界区无处不在。作为第一个例子，让我考察一下现实世界的情况：ATM自动取款机。
自动提款机所进行的主要操作就是从个人银行账户取钱。某人走到机器前，插入ATM卡，输入密码作为验证，选择取款，输入金额，敲确认，取出钱，然后发信息通知本人。
当用户要求取，某一特定的金额后，提款机需要确保在其账户上的确那么有钱。如果有，取款机就要从现有的金额中扣除取款额。实现这一描述的代码如下：

int total = get_total_from_account();       //账户上的总额
int withdrawal = get_withdrawal_amount();   //用户要求的取款额

//检查用户账户上是否有足够的金额
if(total < withdrawal) {
    error("You do not have that much money!");
    return -1;
}

//好啦，用户有足够的金额，从总额中扣除取款项
total -= withdrawal;
update_total_funds(total);

//把钱给用户
spit_out_money(withdrawal);

现在让我们假定在用户账户上的另一个扣款操作同时发生。看看扣款是如何同时发生的：假设用户的配偶在另一台ATM上开始另外的取款；而这和上述扣款同时进行–或者以电子形式从账户转出资金，或者是银行从账户上扣除某一费用，或者是其他形式的扣款。
正在取款的两个系统都会执行我们刚刚看到的代码：首先检查扣款是否有可能，然后计算新的总额，最后进行实际的扣款。现在让我们虚拟一些数字。假定第一次从ATM扣款额是100，第二次扣除银行申请费10。假定客户在银行总共有105。显然，如果账户不出现赤字，这两个操作中有一个就无法完成。
你可能希望发生的顺序是这样的：收费事务先发生。10小于105，因此从105中减去10得到新的金额95。之后，ATM取款发生，但未取到，因为95小于100。
在竞争的环境下，实际生活可能更有趣。假定两个事务几乎同时开始。两个事务都验证是否有足够的金额存在：105既大于100，也大于10，所以两个条件都满足。于是，取款过程从105减去100，剩余5。收费事务也如法炮制，从105减去10，剩余95。此刻，收费事务也更新新的总额，结果得到95。
显而易见，金融机构必须确保类似情况绝不发生，他们必须在某些操作期间对账户加锁，确保每个事务相对其他任何事务的操作是原子性的。这样的事务必须完整的发生，要么干脆不发生，但是绝不能打断。

单个变量

现在，让我们看一个特殊计算的例子。考虑一个非常简单的共享资源：一个全局整形变量和一个简单的临界区，其中的操作仅仅是将整形变量的值增加1。

i++;

该操作可以转化成类似于下面动作的机器指令序列：

得到当前变量i的值并且拷贝到一个寄存器中
将寄存器中的值加1
把i的新值写回到内存中

现在假定有两个执行线程同时进入这个临界区，如果i的初始值是7，那么，我们所期望的结果应该像下面这样（每一行代表一个时间单元）：

线程1               线程2
获得i(7)            ---
增加i(7->8)         ---
写回i(8)            ---
---                 获得i(8)
---                 增加i(8->9)
---                 写回i(9)

正如所期望的，7被两个线程分别加1变为9。但是，实际的执行序列却可能如下：

线程1               线程2
获得i(7)            获得i(7)
增加i(7->8)         ---
---                 增加i(7->8)
写回i(8)            ---
---                 写回i(8)

如果两个执行线程都在变量i值增加前读取它的初值，进而又分别增加变量i的值，最后再保存该值，那么变量i的值就变成了8，而变量i的值本该是9的。这是最简单的临界区例子，幸好对于这种简单竞争条件的解决办法也同样简单–我们仅仅需要将这些指令作为一个不可分割的整体来执行就完事大吉了。多数处理器都提供了指令来原子地读变量、增加变量，然后再写回变量，使用这样的指令就能解决一些问题。使用这些原子指令唯一可能地的结果是：

线程1                线程2
增加i(7->8)          ----
---                  增加i(8->9)
或者是相反
线程2                线程1
增加i(7->8)          ----
---                  增加i(8->9)

两个原子操作交错执行根本就不可能发生，因为处理器会从物理上确保这种不可能。使用这样的指令会缓解这种问题，内核也提供了一组实现这些原子操作的接口，我们将在下一章中讨论它们。

加锁

现在我们来讨论一个更为复杂的竞争条件，相应的解决办法也更为复杂。假设需要处理一个队列上的所有请求。我们假定该队列是通过链表得以实现，链表中的每个节点就代表一个请求。有两个函数可以用来操作此队列：一个函数将新请求添加到队列尾部，另一个函数从队列头部删除请求，然后处理它。内核各个部分都会调用这老两个函数，所以内核会不断地在队列中加入请求，从队列中删除和处理请求。对请求队列的操作无疑是要用到多条指令。如果一个线程试图读取队列，而这时正好另一个线程正在处理该队列，那么读取线程就会队列此刻正处于不一致状态。很明显，如果允许并发访问队列，就会产生危害。当共享资源是一个复杂的数据结构时，竞争条件往往会使该数据结构遭到破坏。
表面上看，这种情况好像没有一个好的方法来解决，一个处理器读取队列的时候，我们怎么能禁止另一个处理器更新队列呢？虽然有些体系结构提供了简单的原子指令，实现算术运算比较之类的原子操作，但让体系结构提供专门的指令，对像上例中那样的不定长度的临界区进行保护，就强人所难了。我们需要一种方法确保一次有且只有一个线程对数据结构进行操作，或者当另一个线程在对临界区标记时，就禁止（或者说锁定）其他访问。
锁提供的就是这种机制：它如同一把门锁，门后的房间可想象成一个临界区。在一个指定的时间内，房间里面只能有一个执行线程存在，当一个线程进入房间之后，它会锁住身后的房门；当它结束对共享数据的操作后，就会走出房间，打开门锁。如果另一个线程在房门上锁时来了，那么它就必须等待房间内的线程出来并打开门锁后，才能进入房间。这样，线程持有锁，而锁保护了数据。
前面例子中讲到的请求队列，可以使用一个单独的锁进行保护。每当一个新请求要加入队列，线程会首先占住锁，然后就可以安全地将请求加入到队列中，结束操作后再释放该锁；同样当一个线程想从请求队列删除一个请求时，也需要先占住锁，然后才能从队列中读取和删除请求，而且在完成操作后也必须释放锁。任何要访问队列的其他线程也类似，必须占住锁后才能进行操作。因为在一个时刻只能有一个线程持有锁，所以在一个时刻只有一个线程可以操作队列。如果一个线程正在更新队列时。另一个线程出现了，则第二个线程必须等待第一个线程释放锁，它才能继续进行。由此可见锁机制可以防止并发执行，并且保护队列不受竞争条件的影响。
任何要访问队列的代码首先都需要占住相应的锁，这样该锁就能阻止来自其他执行线程的并发访问：

请注意锁的使用是自愿的、非强制的，它完全属于一种编程者自选的编程手段。没有什么可以强制编程者在操作我们虚构的队列时必须使用锁。当然，如果不这么做，无疑会造成竞争条件而破坏队列。
锁有多种多样的形式，而且加锁的粒度范围也各不相同–Linux自身实现了几种不同的锁机制。各种锁机制之间的区别主要在于：当锁已经被其他线程持有，因而不可用时的行为表现–一些锁被争用时会简单地执行忙等待，而另外一些锁会使用当前任务睡眠直到锁可用为止。下一章我们将讨论Linux中不同锁之间的行为差别以及它们的接口。
机灵的读者此时会尖叫起来，锁根本解决不了什么问题，它只不过是把临界区缩小到加锁和开锁之间（也许更小）的代码，但是仍然有潜在的竞争！所幸，锁是采用原子操作实现的，而原子操作不存在竞争。单一指令可以验证它的关键部分是否抓住，如果没有的话，就抓住它。其实现是与具体的体系结构密切相关的，但是，几乎所有的处理器都实现了测试和设置指令，这一指令测试整数的值，如果其值为0，就设置一新值。0意味着开锁。在流行的x86体系结构中，锁的实现也不例外，它使用了称为compare和exchange的类似指令。

造成并发执行的原因

用户空间之所以需要同步，是因为用户程序会被调度程序抢占和重新调度。由于用户进程可能在任何时刻被抢占，而调度程序完全可能选择另一个高优先级的进程到处理器上执行，所以就会使得一个程序正处于临界区，被非自愿地抢占了。如果新调度的进程随后也进入了同一临界区（比如说，这两个进程要操作共享的内存，或者向同一文件描述符中写入），前后两个进程相互之间就会产生竞争。另外，因为信号处理是异步发生的，所以，即使是单线程的多个进程共享文件，或者在一个程序内部处理信号，也有可能产生竞争条件。这种类型的并发操作–这里其实两者并不真是同时发生，但它们相互交叉进行，所以也可称作伪并发执行。
如果你有一台支持对称都处理器的机器，那么两个进程就可以真正地在临界区中同时执行了，这种类型称为真并发。虽然真并发和伪并发的原因和含义不同，但它们都同样会造成竞争条件，而且也需要同样的保护。
内核中有类似可能造成并发执行的原因。它们是：

1. 中断–中断几乎可以在任何时刻异步发生，也就可能随时打断当前正在执行的代码。
2. 软中断和tasklet–内核能在任何时刻唤醒或调度软中断和tasklet，打断当前正在执行的代码。
3. 内核抢占–因为内核具有抢占性，所以内核中的任务可能会被另一任务抢占。
4. 睡眠及与用户空间的同步–在内核执行的过程可能会睡眠，就会唤醒调度程序，从而导致调度另一个新的用户进程执行。
5. 对称多处理–两个或多个处理器可以同时执行代码。

对内核开发者来说，必须理解上述这些并发执行的原因，并且为它们事先做足准备工作。如果在一段内核代码操作某资源的时候系统产生了一个中断，而且该中断的处理程序还要访问这一资源，这就是一个bug；类似的，如果一段内核代码在访问一个共享资源期间可以被抢占，这也是一个bug；还有，如果内核代码在临界区里睡眠，那简直就是鼓掌欢迎竞争条件的到来。最后还要注意，两个处理器绝对不能同时访问同一共享数据。当我们清除什么样的数据需要保护时，提供锁来保护系统稳定也就不能做到了。然而，真正困难的就是发现上述的潜在并发执行的可能，并有意识地采取某些措施来防止并发执行。
我们要重申这点，因为它实在是很重要。其实，真正用锁来保护共享资源并不困难，尤其是在设计代码的早期就这么做了，事情就更简单了。辨认出真正需要共享的数据和相应的临界区，才是真正具有挑战的地方。要记住，最开始设计代码的时候就要考虑加入锁，而不是事后才想到。如果代码已经写好了，再在其中找到需要上锁的部分并向其中追加锁，是非常困难的，结果也往往不尽人意。所以，避免这种亡羊补牢的做法是：在编写代码的开始阶段就要设计恰当的锁。
在中断处理程序中能避免并发访问的安全代码称作中断安全代码（interrupt-safe），在对称多处理的机器中能避免并发访问的安全代码称为SMP安全代码（SMP-safe），在内核抢占时能避免并发访问的安全代码称为抢占安全代码（preempt-safe）。

了解要保护什么

找出哪些数据需要保护是关键所在。由于任何可能被并发访问的代码几乎无例外地需要保护，所以寻找哪些代码不需要保护反而相对容易些，我们也就从这里入手。执行线程的局部数据仅仅被它本身访问，显然不需要保护，比如，局部自动变量（还有动态分配的数据结构，其地址仅存放在堆栈中）不需要任何形式的锁，因为它们独立存在于执行线程的栈中。类似的，如果数据只会被特定的进程访问，那么也不需要加锁（因为进程一次只在一个处理器上执行）。
到底什么数据需要加锁呢？大多数内核数据结构都需要加锁！有一条很好的经验可以帮助我们判断：如果有其他执行进程可以访问这些数据，那么就给这些数据加上某种形式的锁；如果任何其他什么东西都能看到它，那么就要锁住它。记住：要给数据而不是给代码加锁。
配置选项
因为Linux内核可在编译时配置，所以你可以针对指定机器进行内核裁剪。更重要的是，CONFIG_SMP配置选项控制内核是否支持SMP。许多加锁问题在单处理器上是不存在的，因而当CONFIG_SMP没被设置时，不必要的代码就不会被编入针对单处理器的内核映像中。这样做可以使单处理器机器避免使用自旋锁带来的开销。同样的技巧也适用于CONFIG_PREEMPT（允许内核抢占的配置选项）。这种设计真的很优越–内核只用维护一些简洁的基础资源，各种各样的锁机制当需要时可随时被编译进内核使用。在不同的体系结构上，CONFIG_SMP和CONFIG_PREEMPT设置不同，实际编译时包含的锁就不同。
在代码中，要为大多数糟糕的情况提供适当的保护，例如具有内核抢占的SMP，并且要考虑到所有的情况。

在编写内核代码时，你要问自己下面这些问题：

1. 这个数据是不是全局的？除了当前线程外，其他线程能不能访问它？
2. 这个数据会不会在进程上下文和中断上下文中共享？它是不是要在两个不同的中断处理程序中共享？
3. 进程在访问数据时可不可能被抢占？被调度的新程序会不会访问统一数据？
4. 当前进程是不是会睡眠（阻塞）在某些资源上，如果是，它会让共享数据处于何种状态？
5. 怎样防止数据失控？
6. 如果这个函数又在另一个处理器上被调度将会发生什么呢？
7. 如何确保代码远离并发威胁呢？

死锁

死锁的产生需要一定条件：要有一个或多个执行线程和一个或多个资源，每个线程都在等待其中的一个资源，但所有的资源都已经被占用了。所有线程都在相互等待。但它们永远不会释放已经占用的资源。于是任何线程都无法继续，这便意味着死锁的发生。
一个很好的死锁例子就是四路交通堵塞问题。如果每一辆停止的车都决心等待其他的车开动后自己再启动，那么就没有任何一辆车能启动，于是就造成了交通死锁的发生。
最简单的死锁例子就是自死锁：如果一个执行线程试图去获得一个自己已经持有的锁，它将不得不等待锁被释放，但因为它正忙着等待这个锁，所以自己永远无法有机会释放锁，最终的结果就是死锁：

获得锁
再次试图获得锁
等待锁重新可用
......

同样道理，考虑有n个线程和个锁，如果每个线程都持有一把其他线程需要得到的锁，那么所有线程都将阻塞地等待它们希望得到的锁重新可用。最常见的例子是有两个线程和两把锁，它们通常被叫做ABBA死锁。

线程1               线程2
获得锁A             获得锁B
试图获得锁B         试图获得锁A
等待锁B             等待锁A

每个线程都在等待其他线程持有的锁，但是绝没有一个线程会释放它们一开始就持有的锁，所以没有任何锁会会在释放后被其他线程使用。
预防死锁的发生非常重要，虽然很难证明代码不会发生死锁，但是可以写出避免死锁的代码，一些简单的规则对避免死锁大有帮助：

1. 按顺序加锁。使用嵌套的锁时必须保证以相同的顺序获取锁，这样可以阻止致命拥抱类型的死锁。最好能记录下锁的顺序，以便其他人也能照此顺序使用。
2. 防止发生饥饿。试问，这个代码的执行是否一定会结束？如果“张”不发生？“王”要一直等下去吗？
3. 不要重复请求同一个锁。
4. 设计应力求简单–越复杂的加锁方案越有可能造成死锁。

最值得强调的是第一点，它最为重要。如果有两个或多个锁曾在同一时间里面被请求，那么以后其他函数请求它们也必须按照前次的加锁顺序进行。假设有cat、dog和fox这几个锁来保护某同名的多个数据结构，同时假设有一个函数对这三个锁保护的数据结构进行操作–可能在它们之间进行拷贝。不管哪种情况，这些数据结构都需要保护才能被安全访问。如果有一个函数以cat、dog，然后以fox的顺序获得了锁，那么其他任何函数都必须以同样的顺序来获得这些锁（或是它们的子集）。如果其他函数首先获得了锁fox，然后获得锁dog（因为锁dog总是应该先于锁fox被获得），就有死锁的可能（所以是个bug）。为更直观的说明，下面给出一个造成死锁的例子：

线程1               线程2
获得锁cat           获得锁fox
获得锁dog           试图获得锁dog
试图获得锁fox       等待锁dog
等待锁fox           ......

线程1在等待锁fox，而该锁此刻被线程2持有；同样线程2正在等待锁dog，而该锁此刻又被线程1持有。任何一方都不会放弃自己已持有的锁，于是双方都会永远等待下去–也就是死锁。但是，只要线程都按照相同的顺序去获取这些锁，就可以避免上述的死锁情况。
只要嵌套地使用多个锁，就必须按照相同的顺序去获取它们。在代码中使用锁的地方，对锁的获取顺序加上注释是个良好习惯。下面的例子就做得很不错：

/*
    cat_lock---用于保护访问cat数据结构的锁，总是要在获得锁dog前先获得
*/

尽管释放锁的顺序和死锁是无关的，但最好还是以获得锁的相反顺序来释放锁。
防止死锁很重要，所以Linux内核提供了一些简单易用的调试工具，可以在运行时检测死锁。

争用和扩展性

锁的争用（lock contention），或简称争用，是指当锁正在被占用时，有其他线程试图获得该锁。说一个锁处于高度争用状态，就是指有多个其他线程在等待获得该锁。由于锁的作用是使程序以串行方式对资源进行访问，所以使用锁无疑会降低相同的性能。被高度争用（频繁被持有，或者长时间持有–两者都有就更糟糕）的锁会成为系统的瓶颈，严重降低系统性能。即使是这样，相比于被几个相互抢夺共享资源的线程撕成碎片，搞得内核崩溃，还是这种同步保护来得更好一点。当然，如果有办法能解决高度争用问题，就更好不过了。
扩展性（scalability）是对系统可扩展程度的一个量度。对于操作系统，我们在谈及可扩展性时就会和大量进程、大量处理器或是大量内存等联系起来。其实任何可以被计量的计算机组件都可以涉及这种扩展性。理想情况下，处理器的数量加倍应该会使系统处理性能翻倍。而实际上，这是不可能达到的。
自从2.0版内核引入多处理支持后，Linux对集群处理器的可扩展性大大提高了。在Linux刚加入对多处理器支持的时候，一个时刻只能有一个任务在内核中执行；在2.2版本中，当加锁机制发展到细粒度（fine-grained）加锁后，便取消了这种限制，而在2.4和后续版本中，内核加锁的粒度变得越来越精细。如今，在Linux2.6内核中，内核加的锁是非常细的粒度，可扩展性也很好。
加锁粒度用来描述加锁保护的数据规模。一个过粗的锁保护大块数据—比如，一个子系统用到的所有的数据结构；相反，一个过于精细的锁保护很小的一块数据—比如，一个大数据结构中的一个元素。在实际使用中，绝大多数锁的加锁范围都处于上述两种极端之间，保护的既不是一个完整的子系统也不是一个独立元素，而可能是一个单独的数据结构。许多锁的设计在开始阶段都很粗，但是当锁的争用问题问题变得严重时，设计就向更加精细的加锁方向进化。
在之前讨论过的运行队列，就是一个锁从粗到精细化的实例。在2.4版和更早的内核中，调度程序有一个单独的调度队列（回忆一下，调度队列是一个由可调度进程组成的链表），在2.6版本内核系列的早期版本中，O(1)调度程序为每个处理器单独配备一个运行队列，每个队列拥有自己的锁，于是加锁由一个全局锁精化到了每个处理器拥有各自的锁。这是一种重要的优化，因为运行队列锁在大型机器上被争着用，本质上就是要在调度程序上每次都把整个调度进程下放到单个处理器上执行。在2.6版内核系列的新近版本中，CFS调度器进一步提升了锁的可扩展性。
一般来说，提高可扩展性是件好事，因为它可以提高Linux在更大型的、处理能力更强大的系统上的性能。但是一味的“提高”可扩展性，却会导致Linux在小型SMP和UP机器上的性能降低，这是因为小型机器可能用不到特别精细的锁，锁的过细只会增加复杂度，并加大开销。考虑一个链表，最初的加锁方案可能就是用一个锁来保护链表，后来发现，在拥有集群处理器机器上，当各个处理器需要频繁访问该链表的时候，只用单独一个锁却成了扩展性的瓶颈。为解决这个瓶颈，我们将原来加锁的整个链表变成为链表中的每一个节点都加入自己的锁，这样一来，如果要对节点进行读写，必须先得到这个节点对应的锁。将加锁粒度变细后，多处理器访问同一个节点的时候，只会争用一个锁。可是这时锁的争用仍然没有完全避免，那么，能不能为每个节点中的每个元素都提供一个锁呢？答案是不能。严格的讲，即使这么细的锁可以在大规模SMP机器上执行的很好，但它在双处理器机器上的表现又会怎样？如果在双处理器机器锁争用表现得并不明显，那么多余的锁会加大系统开销，造成很大的浪费。
不管怎么说，可扩展性都是很重要的，需要慎重考虑。关键在于，在设计锁的开始阶段就应该考虑到要保证良好的扩展性。因为即使在小型机器上，如果对重要资源锁得太粗，也很容易造成系统性能瓶颈。锁加得过粗或过细，差别往往只在一线之间。当锁争用严重时，加锁太粗会降低可扩展性；而锁争用不明显时，加锁过细会加大系统开销，带来浪费，这两种情况都会造成系统性能下降。但要记住：设计初期加锁方案应该力求简单，仅当需要时再进一步细化加锁方案。精髓在于力求简单。

小结

要编写SMP安全代码，不能等到编码完成后才考虑如何加锁。恰当的同步（也就是加锁）（既要满足不死锁、可扩展，而且还要清晰、简洁）需要从头到尾，在整个编码过程中不断考虑与完善。无论你在编写哪种内核代码，是新的系统调用也好，还是重写驱动程序也好，首先应该考虑的就是保护数据不被并发访问，记住，加锁你的代码。
下一章将讨论如何为SMP、内核抢占和其他各种情况提供充分的同步保护，确保数据在任何机器和配置中的安全。
了解了同步、并发和加锁的基本原理之后，让我们现在潜心钻研Linux内核提供的实际工具，以确保你的代码有竞争力但免于死锁。