内核中的调度与同步

摘要

　　本章将为大家介绍内核中存在的各种任务调度机理以及它们之间的逻辑关系（这里将覆盖进程调度、推后执行、中断等概念），在此基础上向大家解释内核中需要同步保护的根本原因和保护方法。最后提供一个内核共享链表同步访问的例子，帮助大家理解内核编程中的同步问题。

　　内核任务调度与同步关系引言

　　对于从事应用程序开发的朋友来说，用户空间的任务调度与同步之间的关系相对简单，无需过多考虑需要同步的原因。这一是因为在用户空间中各个进程都拥有独立的运行空间，进程内部的数据对外不可见，所以各个进程即使并发执行也不会产生对数据访问的竞争。第二是因为用户空间与内核空间独立，所以用户进程不会与内核任务交错执行，因此用户进程不存在与内核任务并发的可能。以上两个原因使得用户同步仅仅需要在进程间通讯和多线程编程时需要考虑。

　　但是在内核空间中情况要复杂得多，需要考虑同步的原因大大增加了。这是因为内核空间中的共享数据对内核中的所有任务可见，所以当在内核中访问数据时，就必须考虑是否会有其他内核任务并发访问的可能、是否会产生竞争条件、是否需要对数据同步。而内核并发的“罪魁祸首”便是内核中复杂多变的任务调度――这里的任务调度包含所有可能引起内核任务更换的情况。

　　并发，竞争和同步的概念，我们假定大家都有所了解，本文不再重申。下面一段描述了上述几个概念之间的大致关系，这种关系在内核中同样适用。

　　对于多线程程序的开发者来说，往往会利用多线程访问共享数据，避免繁琐的进程间通讯。但是多线程对共享数据的并发访问有可能产生竞争，使得数据处于不一致状态，所以需要一些同步方法来保护共享数据。多线程的并发执行是由于线程被抢占式的调度――一个线程在对共享数据访问期间（还未完成）被调度程序中断，将另一个线程投入运行――如果新被调度的线程也要对这个共享数据进行访问，就将产生竞争。为了避免竞争产生，需要使线程串行地访问共享数据 ，也就是说访问需要同步――在一方对数据访问结束后，另一方才能对同一数据进行访问。

　　内核任务

　　这里所定义的内核任务是指内核中执行的一切活动对象，每个内核任务都拥有一个独立的程序计数器、栈和一组寄存器。更重要的是,它们都属于内核调度（这里的调度是广义上的，不要与进程调度混淆）对象，也就是说它们是可以在内核中交错执行的。

　　内核任务分类

　　内核任务包含“内核线程”、“系统调用”、“硬件中断”、“半底任务”等几类。下来我们就简要地讨论上述几类内核任务的特点。

　　系统调用

　　系统调用是用户程序通过门机制来进入内核执行的内核例程，它运行在内核态，处于进程上下文中（进程上下文包括进程的堆栈等等环境），可以认为是代表用户进程的内核任务，因此具有用户态任务的特性，比如可以执行进程调度程序（schedule()）、可以睡眠、可以访问当前进程数据（通过current）。但它属于内核任务，所以在执行过程中不能被抢占（2.6内核前），只能自己放弃cpu（睡眠）时，系统才能可能重新调度别的任务。（有关系统调用部分请看《系统调用》一章）

　　硬中断任务

　　硬中断是指那些由处理器以外的外设产生的中断，这些中断被处理器接收后交给内核中的中断处理程序处理。要注意的是：第一, 硬中断是异步产生的，中断发生后立刻得到处理，也就是说中断操作可以抢占内核中正在运行的代码。这点非常重要。第二，中断操作是发生在中断上下文中的（所谓中断上下文指的是和任何进程无关的上下文环境）。中断上下文中不可以使用进程相关的资源，也不能够进行调度或睡眠。因为调度会引起睡眠，但睡眠必须针对进程而言（睡眠其实是标记进程状态，然后把当前进程推入睡眠列队），而异步发生的中断处理程序根本不知道当前进程的任何信息，也不关心当前哪个进程在运行，它完全是个过客。（有关硬件中断部分请看《硬件中断》一章）

　　下半底任务

　　半底的来历完全出自上面提到的硬中断的影响。硬件中断任务（处理程序）是一个快速、异步、简单地对硬件做出迅速响应并在最短时间内完成必要操作的中断处理程序。硬中断处理程序可以抢占内核任务并且执行时还会屏蔽同级中断或其它中断，因此中断处理必须要快、不能阻塞。这样一来对于一些要求处理过程比较复杂的任务就不合适在中断任务中一次处理。比如，网卡接收数据的过程中,首先网卡发送中断信号告诉CPU来取数据，然后系统从网卡中读取数据存入系统缓冲区中，再下来解析数据然后送入应用层。这些如果都让中断处理程序来处理显然过程太长，造成新来的中断丢失。因此Linux开发人员将这种任务分割为两个部分，一个叫上底，即中断处理程序，短平快地处理与硬件相关的操作（如从网卡读数据到系统缓存）；而把对时间要求相对宽松的任务（如解析数据的工作）放在另一个部分执行，这个部分就是我们这里要讲的下半底。

　　下半底是一种推后执行任务，它将某些不那么紧迫的任务推迟到系统更方便的时刻运行。内核中实现下半底的手段经过不断演化，目前已经从最原始的BH(bottom thalf)演生出BH、任务队列（Task queues）、软中断（Softirq）、Tasklet、工作队列（Work queues）（2.6内核中新出现的）。下面我们就介绍一下他们各自的特点。

　　软中断操作

　　软中断（softirq）不象硬中断那样是由硬件中断信号触发执行的，所以也不同于硬件中断那样时随时都能够被执行，笼统来讲,软中断会在内核处理任务完毕后返回用户级程序前得到处理机会。具体的讲,有三个时刻它将被执行(do_softirq())：硬件中断操作完成后；系统调用返回时；内核调度程序中；（另外,内核线程ksoftirqd周期执行软中断）。从中可以看出软中断会紧随硬中断处理(好象狐假虎威),所以抢占内核任务――至少在时钟中断后总有机会运行一次。还要记得软中断可以在不同处器上并发执行。

　　在有对称多处理器的机器上，那么两个任务就可以真正的在临界区中同时执行了，这种类型被称为真并发。相对而言在,单处理器上并发其实并不是真的同时发生，而是相互交错执行，是伪并发。但它们都同样会造成竞争条件，而且也需要同样的保护。

　　软中断是很底层的机制，一般除了在网络子系统和SCSI子系统这样对性能要求很高以及要求并发处理的时候，才会选择使用软中断。软中断虽然灵活性高和效率高，但是你自己必须处理复杂的同步处理（因为它可在多处理器上并发），所以通常都不直接使用，而是作为支持Tasklet和BH的根本。

　　需要说明的是,软中断的执行也处于中断上下文中，所以中断上下文对它的限制是和硬中断一样的。

　　Tasklet

　　Tasklet和bottom half都是建立在软中断之上的两种延迟机制，其具体不同之处在于软中断是静态分配的，而且同类软中断可以并发地在几个CPU上运行；Tasklet可以动态分配，并且不同种类的Tasklets可以并发地在几个CPU上运行，但同类的tasklets 不可以；bottom half只能静态分配，实质上,下半部分是一个不能与其它下半部分并发执行的高优先级tasklet，即使它们类型不同，而且在不同CPU上运行。Tasklet可以理解为软中断的派生，所以它的调度时机与软中断一致。

　　对于内核中需要延迟执行的多数任务都可以利用tasklet来完成，由于同类tasklet本身已经进行了同步保护，所以使用tasklet相比软中断要简单得多，而且效率也不错。

　　bottom half

　　是 BH时最早的内核延迟方法，它原始、简单且容易控制，因为所有的BH处理程序都被严格地顺序执行――不允许任何两个BH处理程序同时并发执行，即使它们的类型不同也不可以，这样一来BH执行其间减少了许多同步保护。但是BH不得不被淘汰，因为它的“简便”牺牲了多处理器并发处理的高性能，等于一队人过独木桥那样速度受到牵制。

　　任务队列

　　任务列队是BH的替代品，来自BH，所以它的属性也和BH相同。它的原意在于简化BH的操作接口，但它的随意性（数量随意、执行时机随意）却给系统带来了混乱，所以到今天已经被工作队列（在2.6内核中）所取代。

　　不过在2.4内核中任务队列还是被大量应用，尤其是调度队列、定时器队列和立即队列等三种任务队列（除了这三种系统已接管的特定任务队列外，你自己也可随心所欲的建立自己的任务队列，当然这时你要自己调度它）。调度队列的任务会在每次进程调度时得到处理，它是在进程上下文中处理的；定时器队列会在每次时钟滴答时得到处理；立即队列会在中断返回或调度时获得处理（所以处理最快），他们都是在中断上下文中处理的。

　　这些任务队列在内核内由一个统一的内核线程调度，该线程名为keventd，进程号是2（2.4.18）。你可用ps命令查看到该进程。

　　内核线程

　　内核线程可以理解成在内核中运行的特殊进程，它有自己的“进程上下文”（借用调用它的用户进程的上下文），所以同样被进程调度程序调度，也可以睡眠――它和用户进程属性何其相似，不同之处就在于内核线程运行于内核空间，可访问内核数据，运行期间不能被抢占。

　　传统的Unix系统把一些重要的任务委托给周期性执行的进程，这些任务包括刷新磁盘高速缓存，交换出不用的页面，维护网络链接等等。事实上，以严格线性的方式执行这些任务的确效率不高，如果把他们放在后台调度，不管是对它们的函数还是对终端用户进程都能得到较好地响应。因为一些系统进程只运行在内核态，现代操作系统把它们的函数委托给内核线程（Kernel Thread），内核线程不受不必要的用户态上下文的拖累。

　　内核中的同步

　　内核只要存在任务交错执行，就必然会存在对共享数据的并发问题，