Linux 2.4 内核说明文档（进程与中断管理篇）（3）

2.3. Linux 调度程序

调度程序的任务就是从多个进程中挑选一个访问当前CPU，它在kernel/sched.c中实现，对应的被每个内核源文件都引用的头文件定义在include/linux/sched.h。

任务结构中对应调度的字段为：
 p->;need_resched：如果schedule()函数需要在下次唤醒，则设置本字段。
 p->;counter：到下次运行调度时间片剩余的时间嘀哒，由定时器递减。当这个字段的值小于或者等于零时，它被重置为零，同时设置p->;need_resched。由于这个可以被进程自身修改，有时也称之为“动态优先级”。
 p->;priority：进程的静态优先级，仅能被系统调用如nice函数，POSIX.1b 的sched_setparam函数，4.4BSD/SVR4 的setpriority函数修改。
 p->;rt_priority：实时优先权。
 p->;policy: 调度策略，指定任务所属的调度种类，任务可以通过调用sched_setscheduler函数修改它。有效的值为SCHED_OTHER (传统UNIX进程)，SCHED_FIFO (POSIX.1b的FIFO 实时进程)和SCHED_RR (POSIX循环实时进程)。如果要标识进程绑定到某个CPU，则可以将SCHED_YIELD与其他任何值“或”操作。例如通过调用sched_yield系统调用，一个FIFO实时进程将运行于○A处于I/O阻塞，○b明确绑定到某个CPU或者○c被另一个高优先级的实时进程占用。SCHED_RR和SCHED_FIFO相同，除非时间片中止后它回到运行队列末尾。

尽管看起来schedule()函数非常复杂，然而调度算法是简单的。该函数看起来复杂的原因是由于它在一个函数中实现了三个调度算法并和精细的SMP处理细节相关。

显然，“空”跳转到schedule()有这个目的：产生优代码。同样，标识了调度程序是为2.4重写的。因此，下面的讨论是适合2.2或者更早的内核。
让我们看看函数细节：
1) 如果current.>;active_mm == NULL，则出现了错误。当前进程即使是一个内核进程，都必须在任何时候有一个有效的p->;active_mm。
2) 如果tq_scheduler任务队列需要执行，则处理它。任务队列为调度程序稍后执行提供了一个内核机制。
3) 将本地变量prev 和this_cpu分别初始化为当前任务和当前CPU。
4) 检查schedule()是否由中断处理函数调用的，如果出现这种情况是没有理由的。
5) 释放内核全局锁。
6) 如过softirq机制有任务执行，则立即执行。
7) 将本地schedule_data结构指针*sched_data初始化为pre-CPU调度数据区首指针，这个包含了last_schedule 的TSC值以及上次调度任务结构指针。
获取runqueue_lock旋转锁。注意，采用spin_lock_irq()是由于在调度函数中我们保证了中断可用。所以，当释放runqueue_lock时，可以通过重新使其生效替代保存或者恢复eflags。
9) 任务状态处理：如果处于TASK_RUNNING状态，任务继续；如果处于TASK_INTERRUPTIBLE状态且有未处理信号，则任务调整到TASK_RUNNING状态；处于其他任何状态，任务都将从执行队列中移出。
10) 本CPU的空任务被设置为下一步（优候调度者），可是这个候选者被设置为非常低的优先级，以期待有比它更好的出现。
11) 如果上一个任务处于TASK_RUNNING状态，则当前任务优先级被设置为该任务的优先级，并被标识为比空线程更优的候选者。
12) 现在开始处理运行队列，这个CPU上可被调度的每个进程的优先级都以当前值进行比较，高优先级的活得执行机会。“这个CPU上可被调度”的概念必须被理解为：在单CPU机型上，运行队列的每个进程是合格的可调度的；在多CPU机型上，仅仅在其他CPU非已经执行的进程在当前CPU是合格可调度的。优先级由goodness()函数计算，这个函数为所有的实时进程标识非常高的优先级，这个优先级高于1000，以至于超过所有的SCHED_OTHER进程；这样，它就只与其他拥有高优先级的实时进程竞争。如果进程时间片结束，goodness函数返回0。对于非实时进程，goodness的初始值设置为p->;counter，这样进程就近似于在CPU空闲时获得资源，也就是说交互进程较CPU范围计数器更有特权。常量PROC_CHANGE_PENALTY试图表达了“cpu affinity”。这也为内核进程提供了微小的优势。
13) 如果goodness返回值为零，则遍历进程入口列表，并通过简单的算法重新计算他们的动态优先级：
recalculate:
{
struct task_struct *p;
spin_unlock_irq(&runqueue_lock);
read_lock(&tasklist_lock);
for_each_task(p)
p.>;counter = (p.>;counter >;>; 1) + p.>;priority;
read_unlock(&tasklist_lock);
spin_lock_irq(&runqueue_lock);
}

注意，在重新计算前停止了runqueue_lock锁。这个原因是我们将进入到进程集合中，这需要较长的时间，当我们在这个CPU计算时，schedule函数可以在另外的CPU上被调用，并为其挑选一个合适的进程。无可否认的，这就是一个矛盾，因为当我们在这个CPU上挑选合适优先权的进程时，其他CPU正运行schedule计算动态的优先级。
14) 毫无疑问，下一个任务将会被调度，所以初始化next.>;has_cpu为1，next.>;processor为this_cpu。现在runqueue_lock可以被释放了。
15) 如果该任务有一次被调用（next == prev），那么可以简单获取内核全局锁并返回，也就是跳过所有的硬件层(registers, stack 等)和虚拟内存相关操作。
16) switch_to宏依赖于体系结构。在i386上，它与这些相关：a) FPU 处理； b)LDT 处理； c) 重装载段注册器；d) TSS处理 和 e)重装载调试注册器。

文章来源CU社区：Linux 2.4 内核说明文档（进程与中断管理篇）