linux内核设计与实现笔记<七>---内核同步介绍

共享内存的应用程序必须特别留意保护共享资源，防止共享资源被并发访问。内核也不例外。共享资源之所以要防止并发访问，是因为如果多个执行线程同时访问和操作数据，就有可能发生各线程之间相互覆盖共享数据的情况，造成被访问数据处于不一致状态。并发访问共享数据是造成系统不稳定的一类隐患，而且这种错误一般难以跟踪和调试—所以首先应该认识到这个问题的重要性。

8.1   临界区和竞争条件

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

8.2   加锁

      现在我们来讨论一个更为复杂的竞争条件，相应的解决方法也更为复杂。假设需要处理一个队列上的所有服务请求，我们可以任意选一种方法实现这种队列，这里我们假定该队列是一个链表，链表中的每个节点就代表一个请求。有两个函数可以用来操作此队列：一个函数将新请求添加到队列尾部，另一个函数从队列头删除请求，然后处理它。内核各个部分都会调用这两个函数，所以内核会频繁的在队列中加入请求，从队列中删除和处理请求。对请求队列的操作无疑要用到多条指令。如果一个线程试图读取队列，而这时正好另一个线程正在处理该队列，那么读取线程就会发现队列此刻正处于不一致状态。很明显，如果允许并发访问队列，就会产生危害。我们需要一种方法确保一次有且只有一个线程对数据结构操作，或者当另一个线程在对临界区标记时，就禁止其他访问。

      锁提供的就是这种机制：它就如同一把锁，门内的房间就是一个临界区。在一个指定的时间里，房间只能有一个执行线程存在，当一个线程进入房间后，它会锁住房门，当他结束对共享数据的操作后，就会走出房间，打开门锁。如果另一个线程在门上锁的时候来了，就必须等到房间内的线程出来并打开锁后，才能进入房间。

       锁的使用是自愿的、非强制性的，它完全属于一种编程者自选的编程手段。没有什么可以强制编程者在操作我们虚构的队列时必须使用锁。

       在中断处理程序中能避免并发访问的安全代码称作中断安全代码，在对称多处理的机器中能避免并发访问的安全代码称为SMP安全代码，在内核抢占时能避免并发访问的安全代码称为抢占安全代码。

8.2.1            到底是什么造成了并发执行

用户空间之所以需要同步，是因为用户程序会被调度程序抢占和重新调度。由于用户进程可能在任何时刻被抢占，而调度程序完全可能选择另一个高优先级的进程到处理器上执行，所以就有可能在一个程序正处于临界区时，就被非自愿地的抢占了，如果新调度的进程随后也进入同一个临界区（比如说，这两个进程是同一个进程的两个可执行线程，它们两个要访问共享的内存），前后两个进程相互之间就会产生竞争。另外，因为信号处理是异步发生的，所以，即使是单线程的多个进程共享文件，或者在一个程序内部处理信号，也有可能产生竞争条件。这种类型的并发操作—这里其实两者并不真是同时发生的，但它们相互交叉进行，所以也可称作伪并发执行。

如果你有一台支持对称多处理器的机器，那么两个进程就可以真正的在临界区中同时执行了，这种类型被称为真并发。虽然真并发和伪并发的原因和含义不同，但它们都同样会造成竞争条件，而且也需要同样的保护。

内核中有类似可能造成并发执行的原因。它们是：

·中断—中断几乎可以在任何时刻异步发生，也就可能随时打断当前正在执行的代码。

·软中断和tasklet—内核能在任何时刻唤醒或调度软中断和tasklet，打断当前正在执行的代码。

·内核抢占—因为内核具有抢占性，所以内核中的任务可能会被另一任务抢占。

·睡眠及与用户空间的同步—在内核执行的进程可能会睡眠，这就会唤醒调度程序，从而导致调度一个新的用户进程执行。

·对称多处理—两个或多个处理器可以同时执行代码。

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

8.2.2 要保护些什么

       找出哪些数据需要保护是关键所在。由于任何可能被并发访问的代码都可能需要保护，所以寻找那些代码不需要保护反而更容易些，我们也就从这里入手。执行线程的局部数据仅仅被他本身访问，显然不需要保护，比如，局部自动变量（还有动态分配的数据结构，其地址仅存放在堆栈中）不需要任何形式的锁，因为他们独立存在于执行线程的栈中。同样，如果数据只是被特定的进程访问，那么也不需要加锁。

      到底什么数据需要加锁呢？如果其他执行线程可以访问这些数据，那么就给这些数据加上某种形式的锁，如果任何其他什么东西能看到它，就要锁住它。记住：要给数据加锁而不是代码。

8.3 死锁

死锁的产生需要一定条件：要有一个或多个执行线程和一个或多个资源，每个线程都在等待其中的一个资源，但所有的资源都已经被占用了。所有线程都在相互等待，但它们永远不会释放已经占有的资源。于是任何线程都无法继续，这便发生了死锁。

      预防死锁的发生非常重要，虽然很难证明代码不会发生死锁，但是可以写出避免死锁的代码，以下是一些简单的规则：

（1）加锁的顺序是关键。使用嵌套的锁时必须保证以相同的顺序获取锁，这样可以阻止致命拥抱类型的死锁。最好能记录下锁的顺序，以便其他人也能照此顺序使用。

（2）防止发生饥饿。试问，这个代码的执行是否一定会结束？

（3）不可重复请求同一个锁。

（4）越复杂的加锁方案越有可能造成死锁——设计应力求简单。