一．说明
本文以linux-2.4.10 为例主要分析Linux 进程调度模块中的schedule 函数及其相关的函数。另外相关的前提知识也会说明。默认系统平台是自己的i386 架构的pc。
二．前提知识
在进行schedule 分析之前有必要简单说明一下系统启动过程，内存分配使用等。这样才能自然过渡到schedule 模块。
首先是Linux各个功能模块之间的依赖关系：
可见进程调度是整个内核的核心。但这部分，我想说明的是，我的pc是怎样把操作系统从硬盘装载到内存中，并启动进程调度模块的。然后才是后面对schedule的具体分析。
首先，启动操作系统部分，涉及到到三个文件：/arch/i386/boot/bootsect.s、/arch/i386/boot/setup.s、/arch/i386/boot/compressed/head.s。编译安装好一个Linux系统后，bootsect.s模块被放置在可启动设备的第一个扇区（磁盘引导扇区，512字节）。那么下面开始启动过程，三个文件在内存中的分布与位置的移动如下图。
在经过上图这一系列过程后，程序跳转到system模块中的初始化程序init中执行，即/init/main.c文件。该程序执行一系列的初始化工作，如寄存器初始化、内存初始化、中断设置等。之后内存的分配如下图：
此后，CPU有序地从内存中读取程序并执行。前面的main从内核态移动到用户态后，操作系统即建立了任务0，即进程调度程序。之后再由schedule模块进行整个Linux操作系统中进程的创建（fork），调度（schedule），销毁（exit）及各种资源的分配与管理等操作了。值得一说的是schedule将创建的第一个进程是init（pid=1），请注意它不是前面的/init/main.c程序段。如果是在GNU/Debian系统下，init 进程将依次读取rcS.d，rcN.d（rc0.d~rc6.d），rc.local三个run command脚本等，之后系统的初始化就完成了，一系列系统服务被启动了，系统进入单用户或者多用户状态。然后init 读取/etc/inittab，启动终端设备（(exec)getty）供用户登陆，如debian中会启动6个tty，你可以用组合键ctrl+alt+Fn（F1~F6）来切换。
到这里就知道了Linux怎样启动进程调度模块了，也知道了进程调度模块启动的第一个进程init及之后的系统初始化和登陆流程。下面就回过头来分析schedule代码及其相关函数调用。
三．进程调度涉及的数据结构
文件：/linux/include/linux/sched.h
下面只简单介绍数据结构task_struct中的两个字段。
在Linux中，进程（Linux中用轻量级的进程来模拟线程）使用的核心数据结构。一个进程在核心中使用一个task_struct结构来表示，包含了大量描述该进程的信息，其中与调度器相关的信息主要包括以下几个：
1. state
volatile long state; /* -1 unrunnable, 0 runnable, >0 stopped */
Linux的进程状态主要分为三类：可运行的（TASK_RUNNING，相当于运行态和就绪态）；被挂起的（TASK_INTERRUPTIBLE、TASK_UNINTERRUPTIBLE和TASK_STOPPED）；不可运行的（TASK_ZOMBIE），调度器主要处理的是可运行和被挂起两种状态下的进程，其中TASK_STOPPED又专门用于SIGSTP等IPC信号的响应，而TASK_ZOMBIE指的是已退出而暂时没有被父进程收回资源的"僵死"进程。
2. counter
long counter;
该属性记录的是当前时间片内该进程还允许运行的时间。
四． 就绪进程选择算法（即进程调度算法）
文件：/kernel/sched.c
1.上下文切换
从一个进程的上下文切换到另一个进程的上下文，因为其发生频率很高，所以通常都是调度器效率高低的关键。schedule()函数中调用了switch_to宏，这个宏实现了进程之间的真正切换，其代码存放于include/i386/system.h。switch_to宏是用嵌入式汇编写成的，较难理解。
由switch_to()实现，而它的代码段在schedule()过程中调用，以一个宏实现。
switch_to()函数正常返回，栈上的返回地址是新进程的task_struct::thread::eip，即新进程上一次被挂起时设置的继续运行的位置（上一次执行switch_to()时的标号"1:"位置）。至此转入新进程的上下文中运行。
这其中涉及到wakeup，sleepon等函数来对进程进行睡眠与唤醒操作。
2.选择算法
Linux schedule()函数将遍历就绪队列中的所有进程，调用goodness()函数计算每一个进程的权值weight，从中选择权值最大的进程投入运行。
Linux的调度器主要实现在schedule()函数中。
调度步骤：
Schedule函数工作流程如下：
（1）清理当前运行中的进程
（2）选择下一个要运行的进程（pick_next_task）
（3）设置新进程的运行环境
（4） 进程上下文切换
五. Linux 调度器将进程分为三类
进程调度是操作系统的核心功能。调度器只是调度过程中的一部分，进程调度是非常复杂的过程，需要多个系统协同工作完成。本文所关注的仅为调度器，它的主要工作是在所有 RUNNING 进程中选择最合适的一个。作为一个通用操作系统，Linux 调度器将进程分为三类：
1. 交互式进程
此类进程有大量的人机交互，因此进程不断地处于睡眠状态，等待用户输入。典型的应用比如编辑器 vi。此类进程对系统响应时间要求比较高，否则用户会感觉系统反应迟缓。
2. 批处理进程
此类进程不需要人机交互，在后台运行，需要占用大量的系统资源。但是能够忍受响应延迟。比如编译器。
3. 实时进程
实时对调度延迟的要求最高，这些进程往往执行非常重要的操作，要求立即响应并执行。比如视频播放软件或飞机飞行控制系统，很明显这类程序不能容忍长时间的调度延迟，轻则影响电影放映效果，重则机毁人亡。
根据进程的不同分类 Linux 采用不同的调度策略。对于实时进程，采用 FIFO 或者 Round Robin 的调度策略。对于普通进程，则需要区分交互式和批处理式的不同。传统 Linux 调度器提高交互式应用的优先级，使得它们能更快地被调度。而 CFS 和 RSDL 等新的调度器的核心思想是“完全公平”。这个设计理念不仅大大简化了调度器的代码复杂度，还对各种调度需求的提供了更完美的支持。
六. 调度时机：调度什么时候发生？即：schedule()函数什么时候被调用？
调度的发生主要有两种方式：
1：主动式调度(自愿调度)
在内核中主动直接调用进程调度函数schedule()，当进程需要等待资源而暂时停止运行时，会把状态置于挂起（睡眠），并主动请求调度，让出cpu。
2：被动式调度（抢占式调度、强制调度）
用户抢占（2.4 2.6）
内核抢占（2.6）
(1)用户抢占发生在：从系统调用返回用户空间；
从中断处理程序返回用户空间。
内核即将返回用户空间的时候，如果need_resched标志被设置，会导致schedule()被调用，此时就会发生用户抢占。
主动式调度是用户程序自己调度schedule，也许有人会觉得自己的代码中能引用schedule吗？也许不行吧，但大家知道wait4我们是可以调用的，前面我们没有给出wait4的代码，但我们知道在执行了wait4效果是父进程被挂起，所谓的挂起就是不运行了，放弃了CPU，这里发生了进程调度是显而易见的，其实在代码中有如下几行：
current->state = TASK_INTERRUPIBLE;schedule();
还有exit也有
current->state = TASK_ZOMBIE; schedule();
这2种发生了进程调度，从代码上也可以看出（状态被改成了睡眠和僵死，然后去调度可运行进程，当前进程自然不会再占有CPU运行了），从效果中也能看出。这说明用户程序自己可以执行进程调度。
(2)内核抢占：在不支持内核抢占的系统中，进程/线程一旦运行于内核空间，就可以一直执行，直到它主动放弃或时间片耗尽为止。这样一些非常紧急的进程或线程将长时间得不到运行。
在支持内核抢占的系统中，更高优先级的进程/线程可以抢占正在内核空间运行的低优先级的进程/线程。
关于抢占式调度(强制调度），需要知道的是，CPU在执行了当前指令之后，在执行下一条指令之前，CPU要判断在当前指令执行之后是否发生了中断或异常，如果发生了，CPU将比较到来的中断优先级和当前进程的优先级（有硬件参与实现，如中断控制器8259A芯片；通过比较寄存器的值来判断优先级；中断服务程序的入口地址形成有硬件参与实现，等等，具体实现请见相关资料和书籍），如果新来任务的优先级更高，则执行中断服务程序，在返回中断时，将执行进程调度函数schedule。
关于抢占式调度，系统代码中，除了前面我们说到的wait4和exit等外（这两个系统函数是自愿或主动调度），还有一个地方会出现了schedule，就是中断返回代码里面出现了，这里出现了还加了限制条件，我们可以看看这个代码（所谓的中断返回代码，就是恢复中断现场的代码，每一个发生中断都会执行到的代码，无论是什么中断），这段代码是：
277 testl $(VM_MASK | 3),
