在多进程的操作系统中，进程调度是一个全局性的、关键性的问题，它对系统的总体设计、系统的实现、功能设置以及各个方面的性能都有着决定性的影响。根据调度结果所做的进程切换的速度，也是衡量一个操作系统性能的重要指标。进程调度机制的设计，还对系统复杂性有着极大的影响，常常会由于实现的复杂程度而在功能与性能方面做出必要的权衡和让步。一个好的系统的进程调度机制，要兼顾三种不同应用的需要：
另外，进程调度的机制还要考虑到公正性，让系统中的所有进程都有机会向前推进，尽管其进度各有不同，并最终受到CPU速度和负载的影响。更重要的是，还要防止死锁的发生，以及防止对CPU能力的不合理使用，也就是说要防止CPU尚有能力且有进程等着执行，却由于某种原因而长时间得不到执行的情况。一旦这些情况发生时，调度机制还应能识别与化解。可以说，有关进程调度的研究是整个操作系统理论的核心。不过，本系列的博客的目的在于对linux内核的剖析和解释，而不在于理论方面的深入探讨，有兴趣的读者可以阅读操作系统方面的专著。
为了满足上述的目标，在设计一个进程调度机制时要考虑的具体问题主要有：
这三个问题，特别是第一和第三个问题，是紧密结合在一起的。例如，如果调度的性质是绝对地不可剥夺，也就是说坚持完全自愿的原则，那么调度的时机也就基本上决定了，只能在有一个进程自愿调度的时候才能进行调度。相应地，就要设计一个原语，即系统调用，让进程可以表达自己的这个意愿。同时，还要考虑，如果一个进程陷入死循环而抓住CPU不放该怎么办。
这里要说明一下，在中文里也许应该把是否可以剥夺称为政策，但是在英文的书中已经把调度准则或标准称为policy，所以我们只好把这称为方式，以免引起不必要的混淆。
进一步，如果调度的性质是有条件地可剥夺，那么，在什么情况下可剥夺就成了重要的问题。例如，可以把时间划分成时间片，每个时间片来一次时钟中断，而调度可以在时间片中断时进行。按进程的优先级别的高低进行调度，每个时间片一次，除此之外就只能在进程自愿时才可进行调度。这样，只要时间片划分得当，交互式应用的要求就可以满足了。但是，这样的系统显然不适合实时的应用。因为，有可能发生“急惊风遇上慢中郎”的情况，优先级别高的进程急着要运行，而正在运行中的进程偏偏觉悟不高，不懂得先人后己，别的进程只好干等着它把时间片用完而坐失良机。从另一个角度将，这也取决于技术的发展，特别是CPU的速度。例如，就在这么一个系统中，如果可以把时间片分到0.5毫秒，而CPU仍能在这么短的时间里作足够多的事情，那么对 一般的实时应用来说可能还是能满足要求的，虽然从整体上将CPU用在调度与切换上的开销所占的比例上升了。
那么，linux内核的调度进制到底是什么样的呢？我们还是分三个方面来回答这个问题。
在往下叙述之前，此处先给出一个进程的状态转换关系示意图。
先看调度的机制。
首先，自愿的调度随时都可以进行。在内核里面，一个进程可以通过schedule启动一次调度，当然也可以在调度schedule之前，将本进程的状态设置成TASK_INTERRUPTIBLE或TASK_UNINNTERRUPTIBLE，暂时放弃运行而进入睡眠。在用户空间中，则可以通过系统调用pause来达到同样的目的。也可以为这种自愿的暂时放弃运行加上时间限制。在内核中有schedule_timeout用于此项目的；相应地，在用户空间则可以通过系统调用nanosleep而达到目的（注意，sleep是库函数，不是系统调用，但最终要通过系统调用来完成）。这里要指出：从应用的角度看，只有在用户空间自愿放弃运行这一举动是可见的；而在内核中资源放弃运行则是不可见的，它隐藏在其它可能受阻的系统调用中。几乎所涉及到外设的系统调用，如open、read、write和select等，都是可能受阻的。
除此之外，调度还可以非自愿地，即强制地发生在每次从系统调用返回的前夕，以及每次从中断或异常处理返回到用户空间的前夕。注意，这里返回到用户空间几个字是关键性的，因为这意味着只有在用户空间（当CPU在用户空间运行时）发生的中断或异常才会引起调度。冠以这一点我们在前面讲述中断返回时提到过，但是有必要再次加以强调，并重温arch/i386/kernel/entry.S中的两个片段：
ret_from_exception:
#ifdef CONFIG_SMP
GET_CURRENT(%ebx)
movl processor(%ebx),%eax
shll $CONFIG_X86_L1_CACHE_SHIFT,%eax
movl SYMBOL_NAME(irq_stat)(,%eax),%ecx # softirq_active
testl SYMBOL_NAME(irq_stat)+4(,%eax),%ecx # softirq_mask
#else
movl SYMBOL_NAME(irq_stat),%ecx # softirq_active
testl SYMBOL_NAME(irq_stat)+4,%ecx # softirq_mask
#endif
jne handle_softirq
ENTRY(ret_from_intr)
GET_CURRENT(%ebx)
movl EFLAGS(%esp),%eax # mix EFLAGS and CS
movb CS(%esp),%al
testl $(VM_MASK | 3),%eax # return to VM86 mode or non-supervisor?
jne ret_with_reschedule
jmp restore_all277行中寄存器EAX的内容有两个来源，其最低的字节来自保存在堆栈中的进入中断前夕段寄存器CS的内容，最低的两位表示当时的运行级别。从代码中可以看到，转入ret_with_reschedule的条件为中断（或异常）发生前CPU的运行级别为3，即用户态（我们在这里不关心VM_MASK，那是为VM86模式而设置的）。这一点对于系统的设计和实现有很重要的意义。因为那意味着当CPU在内核中运行时无需考虑强制性调度的可能性。发生在系统空间的中断或异常当然是可能的，但是这种中断或异常不会引起调度。这就使内核的实现简化了，早期的Unix内核正是靠这个前提来简化其设计与实现的。否则的话，内核中所有可能为一个以上进程共享的变量和数据结构就全都要通过互斥机制（如信号量）加以保护，或者说都要放在临界区中。不过，随着多处理器SMP系统结构的出现以及日益广泛的采用，这种简化正在失去重要性。在多处理器SMP系统中（见后面的 多处理器SMP系统结构系列博客），尽管在内核中由于不会发生调度而无需互斥，但却不能不考虑在另一个处理器上运行的进程访问共享资源的可能性。这样，不管在同一个CPU上是否有可能在内核中发生调度，所有可能为多个进程（可能在不同的CPU上运行）共享的变量和数据结构，都得保护起来。这就是读者在阅读代码时看到那么多up、down等信号量操作或加锁操作的原因。linux内核中一般将用于多处理器SMP结构的代码放在条件编译#ifdef SMP中，但是却没有把这些用于互斥保护的操作也放在条件编译中。究其原因，一来可能是太多了，加不胜加，再说在单处理器条件下的运行时开销也不大；二来也是为日后对调度机制的改进奠定基础。
那么，linux线性的这种调度机制有什么缺点或不足，为什么可能会有日后的改进呢？例如，在实时的应用中，某个中断的发生可能不但要求迅速的中断服务，还要求迅速地调度有关进程进入运行，以便在较高层次上，也就是在用户空间中对时间进行及时的处理。可是，如果这样的中断发生在内核中时，本次中断返回是不会引起调度的，而要到最初使CPU从用户空间进入内核的那次系统调用或中断（或异常）返回时才会发生调度。倘若内核中的这段代码恰好需要较长时间完成的话，或者连续又发生几次中断的话，就可能将调度过分地推迟。良好的内核代码可能减轻这个问题，但不可能从根本上解决问题。所以这是个设计问题而不是实现问题。只是，随着CPU速度变得越来越快，这个问题逐渐地变得不那么重要了。
注意，从系统空间返回到用户空间只是发生调度的必要条件，而不是充分条件。具体是否发生调度还是要看看有无此种要求，看一下arch/i386/kernel/entry.S中的这一段代码：
ret_with_reschedule:
cmpl $0,need_resched(%ebx)
jne reschedule
cmpl $0,sigpending(%ebx)
jne signal_return
restore_all:
RESTORE_ALL
reschedule:
call SYMBOL_NAME(schedule) # test
jmp ret_from_sys_call可见，只有在当前进程的task_struct结构中的need_resched字段为非0时才会转到reschedule处调用schedule。那么，谁来设置这个字段呢？当然是内核，从用户空间是访问不到进程的task_struct结构的。可是，内核在什么情况下设置这个字段呢？除当前进程通过系统调用自愿让出运行及在系统调用中因某种原因受阻以外，主要就是当因某种原因唤醒一个进程的时候，以及在时钟中断服务程序发现当前进程已经连续运行太久的时候。
再看调度的方式。
linux内核的调度方式可以说是有条件的可剥夺方式。当进程在用户空间运行时，不管自愿不自愿，一旦有必要（例如已经运行了足够长的时间），内核就可以暂时剥夺其运行而调度其它进程进入运行。可是，一旦进程进入内核空间，或者说进入了长宫（supervisor）模式，那就好像是进了高层而刑不上大夫了。这时候，尽管内核知道应该要调度了，但实际上却不会发生，一直要到该进程即将下台，也就是回到用户空间的前夕才能剥夺其运行。所以，linux的调度方式从原则上来说是可剥夺的，可是在实际运行中由于调度机制的限制而变成了有条件的。正因为这样，有的书说linux的调度是可剥夺的，有的却说是不可剥夺的，甚至同一本书中有时候说可剥夺的，有时候又说是不可剥夺的，其原因盖出于此。
那么，剥夺式的调度发生在什么时候呢？同样也是发生在进程从系统空间（包括因系统调用进入内核）返回用户空间的前夕。
至于调度政策，基本上是从Unix系统继承下来的以优先级为基础的调度。内核为系统中的每个进程计算出一个反应其运行资格的权值，然后挑选权值最高的进程投入运行。在运行过程中，当前进程的资格随时间而递减，从而在下一次调度的时候原来资格较低的进程可能就更有资格运行了。到所有进程的资格都变成了0时，就重新计算一次所有进程的资格。资格的计算主要是以优先级为基础的，所以说是以优先级为基础的调度。
但是，为了适应各种不同应用的需要，内核在此基础上实现了三种不同的政策：SCHED_FIFO、SCHED_RR以及SCHED_OTHER。每个进程都有自己适用的调度政策，并且， 进程还可以通过系统调用sched_setscheduler设定自己适用的调度政策。其中SCHED_FIFO适合于时间性要求比较高、但每次运行所需的时间比较短的进程，实时的应用大都具有这样的特点。SCHED_RR中的RR表示round robin，是轮询的意思，这种政策适合比较大、也就是每次运行需时长较长的进程。而除此二者之外的SCHED_OTHER，则为传统的调度政策，比较适合于交互式的分时应用。
既然每个进程都有自己的适用的调度政策，内核怎样在适用不同调度政策的进程之间决定取舍呢？实际上最后还是都归结到各个进程的权值，只不过是在计算资格时把适用政策也考虑进来，就好像考大学时符合某些特殊条件的考生可以获得加分一样。同时，对于适用不同的进程的优先级别也加了限制。我们将结合代码更深入地讨论这些政策间的差异和作用。
下面，我们就结合代码深入到调度和切换的过程中去。在本博客中我们先看一个主动调度，也就是由当前进程自愿调用schedule暂时放弃运行的情景。在exit的博客中，读者已经看到一个正在结束生命的进程在do_exit中的最后一件事情就是调用schedule，我们就从这里接着往下看，深入到schedule里面去，其代码如下：
schedule
/*
* 'schedule()' is the scheduler function. It's a very simple and nice
* scheduler: it's not perfect, but certainly works for most things.
*
* The goto is "interesting".
*
* NOTE!! Task 0 is the 'idle' task, which gets called when no other
* tasks can run. It can not be killed, and it cannot sleep. The 'state'
* information in task[0] is never used.
*/
asmlinkage void schedule(void)
{
struct schedule_data * sched_data;
struct task_struct *prev, *next, *p;
struct list_head *tmp;
int this_cpu, c;
if (!current->active_mm) BUG();
need_resched_back:
prev = current;
this_cpu = prev->processor;
if (in_interrupt())
goto scheduling_in_interrupt;
release_kernel_lock(prev, this_cpu);
/* Do "administrative" work here while we don't hold any locks */
if (softirq_active(this_cpu) & softirq_mask(this_cpu))
goto handle_softirq;
handle_softirq_back:
这个函数中使用了许多goto语句。对于这么一个非常频繁地执行的函数，把运行效率放在第一位是可以理解的，只是给阅读和理解带来了一些困难。
以前我们讲过，在task_struct结构中有两个mm_struct指针。一个是mm，指向代表着进程的虚存（用户）空间的数据结构。如果当前进程实际上是个内核线程，那就没有用户空间，所以其mm指针为0，运行时就要暂时借用在它之前运行的那个进程的active_mm。所以，正在运行中的进程，也即当前进程，在进入schedule时其active_mm一定不能是0（见515行）。后面我们还要回到这个话题上。
以前讲过，对schedule只能由进程在内核中主动调用，或者在当前进程从系统空间返回用户空间的前夕被动地发生，而不能在一个中断服务程序的内部发生。即使一个中断服务程序有调度的要求，也只能通过把当前进程的need_resched字段设成1来表达这种要求，而不能直接调用schedule。读者也许会问，我们在之前的博客中看到，在执行中断服务程序的时候是允许开中断的，如果在执行过程中发生了嵌套中断，那么当从嵌套的中断返回时不会调用schedule，因为此时的中断返回并不是返回用户空间。还要注意：因中断而进入内核并不等于已经进入了某个中断服务程序，而当CPU要从系统空间返回用户空间之时则已经离开了具体的中断服务程序，详见中断系列博客。所以，如果在某个中断服务程序内部调用schedule，那一定是有问题了，所以转向scheduling_in_interrupt。接着看：
schedule
scheduling_in_interrupt:
printk("Scheduling in interrupt\n");
BUG();
return;
}内核对此的反应是显示或者在/var/log/messages文件末尾添上一条出错信息，然后执行一个宏操作BUG，实现代码如下：
/*
* Tell the user there is some problem. Beep too, so we can
* see^H^H^Hhear bugs in early bootup as well!
*/
#define BUG() do { \
printk("kernel BUG at %s:%d!\n", __FILE__, __LINE__); \
__asm__ __volatile__(".byte 0x0f,0x0b"); \
} while (0)这里的奥妙之处是在91行中准备下了两个字节0x0f和0x0b，让CPU当作指令去执行。可是由这两个字节构成的是非法指令，因而会产生一次非法指令（invalid_op）异常，使CPU执行do_invalid_op。当然，在实际运行中这样的错误（在中断服务程序或bf函数的内部调用schedule）是不会发生的，除非正在调试用户自己编写的中断服务程序。
我们回过头来继续往下看schedule，这里523行的release_kernel_lock对i386单处理器系统为空语句，所以接着就是检查是否有内核软中断服务请求在等待。如果有就转入handle_softirq为这些请求服务：
schedule
handle_softirq:
do_softirq();
goto handle_softirq_back;
从执行softirq队列完毕以后继续往下看：
schedule
handle_softirq_back:
/*
* 'sched_data' is protected by the fact that we can run
* only one process per CPU.
*/
sched_data = & aligned_data[this_cpu].schedule_data;
spin_lock_irq(&runqueue_lock);
/* move an exhausted RR process to be last.. */
if (prev->policy == SCHED_RR)
goto move_rr_last;
move_rr_back:指针sched_data指向一个schedule_data数据结构，用来保存供下一次调度时使用的信息：
/*
* We align per-CPU scheduling data on cacheline boundaries,
* to prevent cacheline ping-pong.
*/
static union {
struct schedule_data {
struct task_struct * curr;
cycles_t last_schedule;
} schedule_data;
char __pad [SMP_CACHE_BYTES];
} aligned_data [NR_CPUS] __cacheline_aligned = { {{&init_task,0}}};
这里的类型cycles_t实际上是无符号整数，用来记录调度发生的时间。这个数据结构是为多处理器SMP结构而设的，所以我们在这里并不关心。数组中的第一个元素，即CPU0的schedule_data结构初始化成{&init_task,0}，其余的则全为{0,0}。代码中__cacheline_aligned表示数据结构的起点应与高速缓存中的缓冲线对齐。
下面就要涉及可执行进程队列了，所以先将这个队列锁住，以防止来自其它处理器的干扰。如果当前进程prev的调度政策为SCHED_RR，即轮换调度，那就要先进行一点特殊的处理。SCHED_RR和SCHED_FIFO都是基于优先级的调度政策，可是在怎样调度具有相同优先级的进程这个问题上二者有区别。调度政策为SCHED_FIFO的进程一旦受到调度而开始运行之后，就要一直运行到自愿让出或者被优先级更高的进程剥夺为止。对于每次受到调度时要求运行时间不长的进程，这样并没什么不妥。可是，如果是受到调度后可能会长时间运行的进程 ，那样就不公平了。这种不公正性是对具有相同优先级的进程而言的。因为具有更高优先级的进程可以剥夺它的运行，而优先级更低的进程则本来就没有机会运行。但是，这样对具有相同优先级的其它进程就不公平了。所以，对这样的进程应该实行SCHED_RR调度政策，这种政策在相同的优先级上实行轮换调度。也就是说，对调度政策为SCHED_RR的进程有个时间配额，用完了这个配额就要让具有相同优先级的其他就绪进程先运行。这里，就是对调度政策为SCHED_RR的当前进程的这种处理：
schedule
move_rr_last:
if (!prev->counter) {
prev->counter = NICE_TO_TICKS(prev->nice);
move_last_runqueue(prev);
}
goto move_rr_back;这是什么意思呢？这里的prev->counter代表着当前进程的运行时间配额，其数值在每次时钟中断时都要递减。这是在一个函数update_process_times中进行的，详见下一篇博客。不管一个进程的时间配额有多高，随着运行时间的积累最终总会递减到0。对于调度政策为SCHED_RR的进程，一旦其时间配额降到了0，就要从可执行进程队列runqueue中当前的位置上移动到队列的末尾，同时恢复其最初的时间配额。对于具有相同优先级的进程，调度的时候排在前面的进程优先，所以这使队列中具有相同优先级的其它进程有了优势。宏操作NICE_TO_TICKS根据系统时钟的精度将进程的优先级别换算成可以运行的时间配额，这也是在同一个文件中定义的：
/*
* Scheduling quanta.
*
* NOTE! The unix "nice" value influences how long a process
* gets. The nice value ranges from -20 to +19, where a -20
* is a "high-priority" task, and a "+10" is a low-priority
* task.
*
* We want the time-slice to be around 50ms or so, so this
* calculation depends on the value of HZ.
*/
#if HZ < 200
#define TICK_SCALE(x) ((x) >> 2)
#elif HZ < 400
#define TICK_SCALE(x) ((x) >> 1)
#elif HZ < 800
#define TICK_SCALE(x) (x)
#elif HZ < 1600
#define TICK_SCALE(x) ((x) << 1)
#else
#define TICK_SCALE(x) ((x) << 2)
#endif
#define NICE_TO_TICKS(nice) (TICK_SCALE(20-(nice))+1)将一个进程的task_struct结构从可执行队列中的当前位置移到队列的末尾是由move_last_runqueue完成的：
schedule=>move_last_runqueue
static inline void move_last_runqueue(struct task_struct * p)
{
list_del(&p->run_list);
list_add_tail(&p->run_list, &runqueue_head);
}
把进程移到可执行进程队列的末尾意味着：如果队列中没有资格更高的进程，但是有一个资格与之相同的进程存在，那么，那个资格虽然相同而排在前面的进程就会被选中。继续在schedule中往下看：
schedule
move_rr_back:
switch (prev->state) {
case TASK_INTERRUPTIBLE:
if (signal_pending(prev)) {
prev->state = TASK_RUNNING;
break;
}
default:
del_from_runqueue(prev);
case TASK_RUNNING:
}
prev->need_resched = 0;当前进程就是正在运行中的进程，可是当进入schedule时其状态却不一定是TASK_RUNNING。例如，在我们这个情景中，当前进程已经在do_exit中将其状态改成TASK_ZOMBLE。又例如，前一篇博客中我们看到当前进程在sys_wait4中调用schedule时的状态为TASK_INTERRUPTIBLE。所以，这里的prev->state与其说是当前进程的状态还不如说是其意愿。正因为这样，当其意愿既不是继续进行也不是可中断的睡眠时，就要通过del_from_runqueue把这个进程从可执行队列中撤下来。另一方面，也可以看出TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE两种睡眠状态之间的区别，前者在进程有信号等待处理时要将其改成TASK_RUNNING，让其处理完这些信号再说，而后者则不受信号的影响。请注意，在548行与549行之间并无break语句，所以当没有信号等待处理时就落入了default的情形，同样要将进程从可执行队列中撤下来。反之，如果当前进程的意愿是TASK_RUNNING，即继续进行（见551行），那在这里就不需要由什么特殊处理。
然后，将prev->need_resched恢复成0，因为所需求的调度已经在进行。下面就要挑选一个进程来运行了：
schedule
/*
* this is the scheduler proper:
*/
repeat_schedule:
/*
* Default process to select..
*/
next = idle_task(this_cpu);
c = -1000;
if (prev->state == TASK_RUNNING)
goto still_running;
still_running_back:
list_for_each(tmp, &runqueue_head) {
p = list_entry(tmp, struct task_struct, run_list);
if (can_schedule(p, this_cpu)) {
int weight = goodness(p, this_cpu, prev->active_mm);
if (weight > c)
c = weight, next = p;
}
}在这段程序中，next总是指向已知最佳的候选进程，c则是这个进程的综合权值，或运行资格。挑选的过程从idle进程即0号进程开始，其权值为-1000，这是可能的最低值，表示仅在没有其他进程可以运行时才会让它运行。然后，遍历可执行队列runqueue中的每个进程（在单CPU系统中can_schedule的 返回值永远为1），也就是一般操作系统教科书中所称的就绪进程，为每一个这样的进程通过函数goodness计算出它当前所具有的权值，然后与当前的最高值c相比。注意这里的条件weight > c，这意味着先入为大。也就是说，如果两个 进程具有相同权值的话，那就是排在前面的进程胜出。代码中的list_for_each是个宏定义，定义如下：
/**
* list_for_each - iterate over a list
* @pos: the &struct list_head to use as a loop counter.
* @head: the head for your list.
*/
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)这里还有一个小插曲，就是如果当前进程的意图是继续运行，那就要先执行一下still_running；
schedule
still_running:
c = goodness(prev, this_cpu, prev->active_mm);
next = prev;
goto still_running_back;
也就是说，如果当前进程想要继续运行，那么在挑选候选进程时以当前进程此刻的权值开始。这意味着，相对于权值相同的其他进程来说，当前进程优先。
那么，进程的当前权值是怎样计算的呢？请看goodness代码：
schedule=>goodness
/*
* This is the function that decides how desirable a process is..
* You can weigh different processes against each other depending
* on what CPU they've run on lately etc to try to handle cache
* and TLB miss penalties.
*
* Return values:
* -1000: never select this
* 0: out of time, recalculate counters (but it might still be
* selected)
* +ve: "goodness" value (the larger, the better)
* +1000: realtime process, select this.
*/
static inline int goodness(struct task_struct * p, int this_cpu, struct mm_struct *this_mm)
{
int weight;
/*
* select the current process after every other
* runnable process, but before the idle thread.
* Also, dont trigger a counter recalculation.
*/
weight = -1;
if (p->policy & SCHED_YIELD)
goto out;
/*
* Non-RT process - normal case first.
*/
if (p->policy == SCHED_OTHER) {
/*
* Give the process a first-approximation goodness value
* according to the number of clock-ticks it has left.
*
* Don't do any other calculations if the time slice is
* over..
*/
weight = p->counter;
if (!weight)
goto out;
#ifdef CONFIG_SMP
/* Give a largish advantage to the same processor... */
/* (this is equivalent to penalizing other processors) */
if (p->processor == this_cpu)
weight += PROC_CHANGE_PENALTY;
#endif
/* .. and a slight advantage to the current MM */
if (p->mm == this_mm || !p->mm)
weight += 1;
weight += 20 - p->nice;
goto out;
}
/*
* Realtime process, select the first one on the
* runqueue (taking priorities within processes
* into account).
*/
weight = 1000 + p->rt_priority;
out:
return weight;
}
首先，如果一个进程通过系统调用sched_yield明确表示了礼让后，就将其权值定位-1。这是很低的权值，一般就绪进程的权值至少是0。
对于没有实时要求的进程，即调度政策为SCHED_OTHER的进程，其权值主要取决于两个因素。一个因素是剩下的时间配额，如果用完了则权值为0。另一个因素是进程的优先级nice，这是从早期Unix沿用下来的负向优先级，其数值表示谦让的程度，所以称为nice。其取值范围为19~-20，以-20位最高，只有特权用户才能把nice值设成小于0；而（20-p->nice）则掉转了它的方向成为1至40。所以，综合的权值在时间配额尚未用完时基本上是二者之和。此外，如果是个内核线程，或者其用户空间与当前进程的相同，因而无需切换用户空间，则会得到一点小奖励，将权值额外加1。
对于实时进程，即调度政策为SCHED_FIFO或SCHED_RR的进程，则另有一种正向的优先级，那就是实时优先级rt_priority（这里的rt表示real time），而权值为（10000+p->rt_priority）。可见，SCHED_FIFO和SCHED_RR两种有时间要求的政策赋予进程很高的权值（相对于SCHED_OTHER），这种进程的权值至少是1000。另一方面，rt_priority的值对于实时进程之间的权值比较也起着重要的作用，其数值也是在系统调用sched_setscheduler中与调度政策一起设置的。从这里还可以看出：对于这两种调度实时政策，一个进程已经运行了多久，也就是时间配额p->counter的当前值，对权值的计算不起作用。不过，前面已经看到，对于调度政策SCHED_RR的进程，当p->counter达到0时会导致将进程移到队列的尾部。实时进程的nice数值与其优先级无关，但是对SCHED_RR进程的时间配额大小有关。由于实时进程的权值有个很大的基数，当有实时进程就选时非实时进程时没有机会运行的。
由此可见，在linux内核中对权值的计算时很简单的。事实上，在早期的Unix系统中实现了一套相当复杂的算法（那时还没有实时进程），后来在实践中觉得那套算法太复杂了，就不断加以简化，在调度的效率、调度的公正性以及其它指标之间反复权衡、折衷，发展成了现在这个样子。另一方面，对实时进程的调度也是POSIX标准的要求。不过goodness这个函数并不代表linux的调度算法的全部，而要与前面讲到的SCHED_RR的特殊处理、对意欲继续运行的当前进程的特殊处理、以及下面要讲到的recalculate结合起来分析。限于篇幅，本博客将专注于代码本身的逻辑及过程，而不对调度算法进行定量的分析。
回到schedule。当代码中的while循环结束时，变量c中的值有几种可能。一种可能是一个大于0的正数，此时next指向挑选出来的进程。另一种可能是c的值为0，发生于就绪队列中所有进程的权值都是0的时候。由于除init进程和调用了（系统调用）sched_yield的进程以外，每个进程的权值最低位0，所以只要队列中有其它就绪进程存在就不可能为负数。这里要指出，队列中所有其它进程的权值都已降到0，说明这些进程的调度政策都是SCHED_OTHER，因为若有政策为SCHED_FIFO或SCHED_RR的进程存在，则其权值至少也有1000。
继续往下看：
schedule
/* Do we need to re-calculate counters? */
if (!c)
goto recalculate;如果当前已经选择的进程（权值最高的进程）的权值为0，那就要重新计算各个进程的时间配额。如上所述，这说明系统中当前没有就绪的实时进程。而且，这种情况已经持续了一段时间，因为否则SCHED_OTHER进程的权值便没有机会消耗到0。
schedule
recalculate:
{
struct task_struct *p;
spin_unlock_irq(&runqueue_lock);
read_lock(&tasklist_lock);
for_each_task(p)
p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice);
read_unlock(&tasklist_lock);
spin_lock_irq(&runqueue_lock);
}
goto repeat_schedule;
宏定义for_each_task，读者已经在前面看到过了。这里所作的计算是将每个进程当前的时间配额p->counter除以2，再在上面加上由该进程的nice值换算过来的tick数量。宏操作NICE_TO_TICKS的定义也在前面看到过了（显然，nice值对于非实时进程既表示优先级也决定着时间配额）。可见，所作的计算是很简单的。这里要注意，for_each_task是对所有进程的循环，而并不是仅对于就绪队列进程的循环。对于不在就绪进程队列中的非实时进程，这里得到了提升其时间配额、从而提升其综合权值的机会。不过，对综合权值的这种提升是很有限的，每次重新计算都将原有的时间配额减半，再与NICE_TO_TICKS(p->nice)相加，这样就决定了重新计算以后的综合权值永远也不可能达到NICE_TO_TICKS(p->nice)的两倍。因此，即使经过很长时间的韬光养晦，也不可能达到可与实时进程竞争的地步（综合权值至少是1000），所以只是对非实时进程之间的竞争有意义。至于实时进程，时间配额的增加并不会提升其综合权值，而且对于SCHED_FIFO进程则连时间配额也是没有意义的。计算完以后，程序转回标号repeat_schedule处重新挑选。这样，当再次完成对就绪进程队列的扫描时，变量c的值应该不为0了，此时next指向挑选出来的进程。
进程挑选好了之后，接下来要做的就是切换的事情了：
schedule
/*
* from this point on nothing can prevent us from
* switching to the next task, save this fact in
* sched_data.
*/
sched_data->curr = next;
#ifdef CONFIG_SMP
#endif
spin_unlock_irq(&runqueue_lock);
if (prev == next)
goto same_process;
#ifdef CONFIG_SMP
#endif /* CONFIG_SMP */
kstat.context_swtch++;
/*
* there are 3 processes which are affected by a context switch:
*
* prev == .... ==> (last => next)
*
* It's the 'much more previous' 'prev' that is on next's stack,
* but prev is set to (the just run) 'last' process by switch_to().
* This might sound slightly confusing but makes tons of sense.
*/
prepare_to_switch();
{
struct mm_struct *mm = next->mm;
struct mm_struct *oldmm = prev->active_mm;
if (!mm) {
if (next->active_mm) BUG();
next->active_mm = oldmm;
atomic_inc(&oldmm->mm_count);
enter_lazy_tlb(oldmm, next, this_cpu);
} else {
if (next->active_mm != mm) BUG();
switch_mm(oldmm, mm, next, this_cpu);
}
if (!prev->mm) {
prev->active_mm = NULL;
mmdrop(oldmm);
}
}
/*
* This just switches the register state and the
* stack.
*/
switch_to(prev, next, prev);
__schedule_tail(prev);
same_process:
reacquire_kernel_lock(current);
if (current->need_resched)
goto need_resched_back;
return;
这里我们跳过对SMP结构的条件编译部分。首先，如果挑选出来的进程next就是当前进程prev，就不用切换，直接转到标号same_process处就返回了。这里的reacquire_kernel_lock对于i386单CPU结构而言为空语句。前面应把当前进程的need_resched清0，如果现在又成了非0则一定是发生了中断并且情况有了变化，所以转回need_resched_back处再调度一次。否则，如果挑选出来的进程next与当前进程的prev不同，那就要切换了。对于i386单CPU结构而言，prepare_to_switch也是空语句，而649行的__schedule_tail则只是将当前进程prev的task_struct结构中policy字段里的SCHED_YIELD标志位清成0。所以实际上只剩下了两件事，其一是对用户虚存空间的处理，其二就是进程切换switch_to。
先来看对用户空间的处理，这里之所以要新开一个scope是因为要在堆栈中补充分配两个变量mm和oldmm，前者指向新锦成next的mm_struct结构，后者则为老进程prev的active_mm。首先，如果新进程 是个具备用户空间的内核线程，那么其active_mm指针也必须是0，否则就一定是出了问题。但是，内核的设计和实现实际上不允许一个进程（哪怕是内核线程）没有active_mm，因为指向页面映射目录的指针就在这个数据结构中。所以，如果新进程没有自己的mm_struct（因此是内核线程），就要在进入运行时向被切换出去的进程借用一个mm_struct结构（见628行和630行），可是借来的mm_struct结构能用吗？能。因为既然没有用户空间，所需的只是系统空间的映射，而所有进程的系统空间映射都是相同的。那么，借用的mm_struct结构什么时候归还呢？到下一次调度其它进程运行时，也就是说当这个内核线程被切换出去时归还，这就是638行至641行所做的事情。这里的mmdrop只是将通过共享借用的mm_struct结构中的共享计数减1，而不是真的将此结构释放，因为这个计数在减1以后不可能达到0。如果新进程next有自己的mm_struct结构（因此是个进程），那么next->active_mm必须与next->mm相同，否则就有问题了。由于新进程有自己的用户空间，所以就要通过switch_mm，进行用户空间的切换。这是个inline函数，其代码如下：
schedule=>switch_mm
#endif
static inline void switch_mm(struct mm_struct *prev, struct mm_struct *next, struct task_struct *tsk, unsigned cpu)
{
if (prev != next) {
/* stop flush ipis for the previous mm */
clear_bit(cpu, &prev->cpu_vm_mask);
/*
* Re-load LDT if necessary
*/
if (prev->context.segments != next->context.segments)
load_LDT(next);
#ifdef CONFIG_SMP
cpu_tlbstate[cpu].state = TLBSTATE_OK;
cpu_tlbstate[cpu].active_mm = next;
#endif
set_bit(cpu, &next->cpu_vm_mask);
/* Re-load page tables */
asm volatile("movl %0,%%cr3": :"r" (__pa(next->pgd)));
}
#ifdef CONFIG_SMP
else {
cpu_tlbstate[cpu].state = TLBSTATE_OK;
if(cpu_tlbstate[cpu].active_mm != next)
BUG();
if(!test_and_set_bit(cpu, &next->cpu_vm_mask)) {
/* We were in lazy tlb mode and leave_mm disabled
* tlb flush IPI delivery. We must flush our tlb.
*/
local_flush_tlb();
}
}
#endif
}
对于单CPU结构而言，这里关键的语句只有一行，那就是44行中的汇编语句，它将新进程页面目录的其实物理地址装入到控制寄存器CR3中。我们在内存管理系列博客中讲过，CR3总是指向当前进程的页面目录。至于LDT则仅在VM86模式中才使用，所以不在我们关心之列。
读者也许会问：进程本身尚未切换，而存储管理机制中的页面目录指针CR3却已经切换了，这样不会造成问题吗？不会的，因为这个时候CPU在系统空间运行，而所有进程的页面目录中与系统空间相对应的目录项都指向相同的页面表，所以，不换换上哪一个进程的页面目录都一样，受影响的只是用户空间，系统空间的映射则永远不变。
现在，到了最后要切换进程的关头了。所谓进程的切换主要是堆栈的切换，这是由宏操作switch_to完成的，定义如下：
schedule=>switch_to
#define switch_to(prev,next,last) do { \
asm volatile("pushl %%esi\n\t" \
"pushl %%edi\n\t" \
"pushl %%ebp\n\t" \
"movl %%esp,%0\n\t" /* save ESP */ \
"movl %3,%%esp\n\t" /* restore ESP */ \
"movl $1f,%1\n\t" /* save EIP */ \
"pushl %4\n\t" /* restore EIP */ \
"jmp __switch_to\n" \
"1:\t" \
"popl %%ebp\n\t" \
"popl %%edi\n\t" \
"popl %%esi\n\t" \
:"=m" (prev->thread.esp),"=m" (prev->thread.eip), \
"=b" (last) \
:"m" (next->thread.esp),"m" (next->thread.eip), \
"a" (prev), "d" (next), \
"b" (prev)); \
} while (0)
经历过前面一些的博客中的汇编程序，读者现在对嵌入C程序中的汇编语句应该不陌生了。这里的输出部有三个参数，表示这段程序执行以后有三项数据会有改变。其中%0和%1都在内存中，分别为prev->thread.esp和prev->thread.eip，而%2则与寄存器EBX结合，对应于参数中的last。而输入部则有5个参数。其中%3和%4在内存中，分别为next->thread.esp和next->thread.eip，%5、%6和%7分别与寄存器EAX、EDX以及EBX结合，分别对应于prev、next和prev。
这一段程序虽然只有寥寥几行，却很奥妙，先来看开头的三条push指令和截尾除的三条pop指令。看起来好像是很一般，其实却暗藏玄机。且看第19行和20行。第19行将当前的ESP，也就是当前进程prev的系统空间堆栈指针存入prev->thread.esp，第20行又将新收到调度要进入运行的进程next的系统空间堆栈指针next->thread.eip置入ESP。这样一来，CPU在第20行与21行这两条指令之间就已经切换了堆栈。假定我们有A、B两个进程，在本次切换中prev指向A，而next指向B。也就是说，在本次切换中A为要调离的进程，而B为要切入的进程。那么，在这里的第16至20行时在使用A的堆栈，而从第21行开始就是在用B的堆栈了。换言之，从第21行开始，当前进程，已经是B而不是A了。我们以前讲过，在内核代码中当需要访问当前进程的task_struct结构时使用的指针current实际上是宏定义，它根据当前的堆栈指针ESP计算出所需的地址。如果第21行处引用current的话，那就已经指向B的task_struct结构了。从这个意义上说，进程的切换在第20行的指令执行完就已经完成了。但是，构成一个进程的另一个要素是程序的执行，这方面的切换显然尚未完成。那么，为什么在第16至18行push进A的堆栈，而在第25行至27行却从B的堆栈POP回来呢？这就是奥妙所在了。其实，第25行至27行时在恢复新切入的进程在上一次被调离时push进堆栈的内容。
那么，程序执行的切换，具体又是怎样实现的呢？让我们呢来看第21行至24行。第21行将标号1所在的地址，实际上就是第25行的pop指令所在地址保存在prev->thread.eip中，作为进程A下一次被调度运行而切入时的返回地址。然后，又将next->thread.eip压入堆栈。所以，这里的next->thread.eip正是进程B上一次被调离时在第231行中保存的。它也指向这个里的标号1，即25行的pop指令。接着，在23行通过jmp指令，而不是call指令，转入了一个函数__switch_to。且不说在__switch_to中干了些什么，当CPU执行到那里的ret指令时，由于是通过jmp指令转过去的，最后进入堆栈的next->thread.eip就变成了返回地址，而这就是标号1所在的地址，也就是25行的pop指令所在的地址。由于每个进程在被调离时都要执行这里的第21行，这就决定了每个进程在受到调度恢复运行时都是从这里的第25行开始。但是有一个例外，那即是新创建的进程。新创建的进程并没有在上一次调离时执行过这里的第16至21行，所以一来要将其task_struct结构中的thread.eip事先设置好，二来所设置的返回地址也未必是这里的标号1所在，这取决于其系统空间堆栈的设置。事实上，读者在fork的博客中应看到，这个地址在copy_thread中设置为ret_from_fork，其代码如下：
ENTRY(ret_from_fork)
pushl %ebx
call SYMBOL_NAME(schedule_tail)
addl $4, %esp
GET_CURRENT(%ebx)
testb $0x02,tsk_ptrace(%ebx) # PT_TRACESYS
jne tracesys_exit
jmp ret_from_sys_call
也就是说，对于新创建的继承，在调用schedule_tail以后就直接转到ret_from_sys_call，返回到用户空间去了。将前面情景中子进程被创建以后第一次切入时的系统空间堆栈和父进程创建了子进程以后被调度从系统调用fork返回而切入时的（系统空间）堆栈做一比较，就可以看得更清楚了，下面一副示意图。
在堆栈空间的顶部，或者说堆栈的底部，是父进程因fork系统调用而进入系统空间时保存的返回现场，包括CPU在穿越陷阱门时自动保存在系统空间堆栈中的内容以及通过entry.S中的SAVE_ALL保存的寄存器内容，合在一起形成一个数据结构regs。这一部分被原封不动地复制到了子进程堆栈中，但其中用来返回函数值的EAX被设成0，而指向用户空间堆栈的指针ESP也作了相应的修改（见copy_thread）。
父进程在fork子进程以后，并不立即主动调用schedule，而只是将其task_struct结构中的need_resched标志设成了1，然后就从do_fork和sys_fork中返回。经过entry.S中的ret_from_sys_call到达ret_with_reschedule时，如果task_struct结构中的need_resched为0，那就直接反悔了，这时其堆栈指针已经指向了regs，所以RESTORE_ALL就使进程回到用户空间。可是，现在need_resched已经是1，就要马上会从schedule返回，就像什么事也没发生过一样。而如果调度了另一个进程运行，那么其系统空间堆栈就变成上图中的样子。处于堆栈顶部的是进程在下一次被调度运行时的切入点，那就是在前面switch_to的代码中21行设置的。注意，switch_to是一个宏操作，在switch_to的20行恢复了其堆栈指针，然后在__switch_to中执行ret指令时就返回到了25行，所以其堆栈中的这一项也可以看成是从__switch_to返回的地址。父进程最后反悔了entry.S中的289行，紧接着就会跳转到ret_from_sys_call。相比之下，子进程的这个返回地址被设置成ret_from_sys_call，所以在__switch_to一执行ret指令就直接回到了那里，抄了一段小路。
最后，在__switch_to中到底干了些什么呢？看如下代码：
schedule=>switch_to=>__switch_to
/*
* switch_to(x,yn) should switch tasks from x to y.
*
* We fsave/fwait so that an exception goes off at the right time
* (as a call from the fsave or fwait in effect) rather than to
* the wrong process. Lazy FP saving no longer makes any sense
* with modern CPU's, and this simplifies a lot of things (SMP
* and UP become the same).
*
* NOTE! We used to use the x86 hardware context switching. The
* reason for not using it any more becomes apparent when you
* try to recover gracefully from saved state that is no longer
* valid (stale segment register values in particular). With the
* hardware task-switch, there is no way to fix up bad state in
* a reasonable manner.
*
* The fact that Intel documents the hardware task-switching to
* be slow is a fairly red herring - this code is not noticeably
* faster. However, there _is_ some room for improvement here,
* so the performance issues may eventually be a valid point.
* More important, however, is the fact that this allows us much
* more flexibility.
*/
void __switch_to(struct task_struct *prev_p, struct task_struct *next_p)
{
struct thread_struct *prev = &prev_p->thread,
*next = &next_p->thread;
struct tss_struct *tss = init_tss + smp_processor_id();
unlazy_fpu(prev_p);
/*
* Reload esp0, LDT and the page table pointer:
*/
tss->esp0 = next->esp0;
/*
* Save away %fs and %gs. No need to save %es and %ds, as
* those are always kernel segments while inside the kernel.
*/
asm volatile("movl %%fs,%0":"=m" (*(int *)&prev->fs));
asm volatile("movl %%gs,%0":"=m" (*(int *)&prev->gs));
/*
* Restore %fs and %gs.
*/
loadsegment(fs, next->fs);
loadsegment(gs, next->gs);
/*
* Now maybe reload the debug registers
*/
if (next->debugreg[7]){
loaddebug(next, 0);
loaddebug(next, 1);
loaddebug(next, 2);
loaddebug(next, 3);
/* no 4 and 5 */
loaddebug(next, 6);
loaddebug(next, 7);
}
if (prev->ioperm || next->ioperm) {
if (next->ioperm) {
/*
* 4 cachelines copy ... not good, but not that
* bad either. Anyone got something better?
* This only affects processes which use ioperm().
* [Putting the TSSs into 4k-tlb mapped regions
* and playing VM tricks to switch the IO bitmap
* is not really acceptable.]
*/
memcpy(tss->io_bitmap, next->io_bitmap,
IO_BITMAP_SIZE*sizeof(unsigned long));
tss->bitmap = IO_BITMAP_OFFSET;
} else
/*
* a bitmap offset pointing outside of the TSS limit
* causes a nicely controllable SIGSEGV if a process
* tries to use a port IO instruction. The first
* sys_ioperm() call sets up the bitmap properly.
*/
tss->bitmap = INVALID_IO_BITMAP_OFFSET;
}
}
这里处理的主要是TSS，其核心就是第638行，将TSS中的内核空间（0级）堆栈指针换成next->esp0。这是因为CPU在穿越中断们或陷阱门时要根据新的运行级别从TSS中取得进程在系统空间的堆栈指针。其次，段寄存器fs和gs的内容也随后作了相应的切换。至于CPU中为debug而设的一些寄存器，以及说明进程I/O操作权限位图，那就不是我们在这里所关心的了。
我们在中断系列博客中提到过，Intel的原意是让操作系统为每个进程都设置一个TSS，通过切换TSS指针、也就是寄存器TR的内容，由CPU的硬件来实现进程（任务）的切换。表面上看这是很有吸引力的，但是实际上却未必合适。这里，代码的作者加了一段注释，说linux曾经用过由硬件实现的切换，但后来不用了。注释中说了三个原因，其中第一个原因语焉不详。但是，第二个原因是很有趣的，那就是目前的这种软件实现甚至比硬件实现可以更快，至于第三个原因，即灵活性，那倒是不言而喻的。
总之，除刚刚创建的新进程外，所有进程在受到调度时切入点都是在switch_to（其实是在schedule中，因为switch_to是个宏操作）中的标号1，一致运行到下一次进入switch_to以后在__switch_to中执行ret为止。或者也可以认为，切入点在switch_to中的25行，一直运行到下一次进入switch_to后的23行。总之，这新、就当前进程的交接点就在switch_to这段代码中。
那么，既然都是在同一点上交接，并且从此以后一直到返回用户空间这一段路程又是共同的，不同进程的不同上下文又是怎样体现的呢？这不同就在于系统空间堆栈的内容。不同进程进入系统空间时的运行现场不同，返回地址不同，用户空间堆栈指针不同，一旦回到用户空间就回到了各自的路线上，各奔前程了。
最后，让我们回到在系统调用exit中通过schedule资源让出运行的情景。由于对schedule的调用时在do_exit中作出的，在交接时这个进程的系统空间堆栈如下图所示。
从图中可以看出，如果（假定）这个进程像其他进程一样会被调度继续运行的话，它就会循下列的路线返回用户空间：
此处所讲的返回路线与前面讲的系统地阿勇fork中的父进程做一比较，可发现，进程主动交出运行时的系统空间堆栈以及返回泸县与被动地剥夺运行时有所不同。前者取决于进程在何处调用schedule，而后者则一定是在entry.S中的reschedule处。
可是，在exit这个情景中，由于在调用schedule之前已经把进程的状态改成TASK_ZOMBLE，所以不会再被调度运行。