Scheduling （调度)

核心提示：所有的进程部分运行与用户态，部分运行于系统态，Scheduling （调度)，底层的硬件如何支持这些状态各不相同但是通常有一个安全机制从用户态转入系统态并转回来，用户态比系统态的权限低了很多， Alpha AXP 处理器，使用 TLT （ Translation Look-aside Table ）或者缓存的页表条目，

　　所有的进程部分运行与用户态，部分运行于系统态。底层的硬件如何支持这些状态各不相同但是通常有一个安全机制从用户态转入系统态并转回来。用户态比系统态的权限低了很多。每一次进程执行一个系统调用，它都从用户态切换到系统态并继续执行。这时让核心执行这个进程。 linux 中，进程不是互相争夺成为当前运行的进程，它们无法停止正在运行的其它进程然后执行自身。每一个进程在它必须等待一些系统事件的时候会放弃 CPU 。例如，一个进程可能不得不等待从一个文件中读取一个字符。这个等待发生在系统态的系统调用中。进程使用了库函数打开并读文件，库函数又执行系统调用从打开的文件中读入字节。这时，等候的进程会被挂起，另一个更加值得的进程将会被选择执行。进程经常调用系统调用，所以经常需要等待。即使进程执行到需要等待也有可能会用去不均衡的 CPU 事件，所以 Linux 使用抢先式的调度。用这种方案，每一个进程答应运行少量一段时间， 200 毫秒，当这个时间过去，选择另一个进程运行，原来的进程等待一段时间直到它又重新运行。这个时间段叫做时间片。

需要调度程序选择系统中所有可以运行的进程中最值得的进程。一个可以运行的进程是一个只等待 CPU 的进程。 Linux 使用合理而简单的基于优先级的调度算法在系统当前的进程中进行选择。当它选择了预备运行的新进程，它就保存当前进程的状态、和处理器相关的寄存器和其他需要保存的上下文信息到进程的 task_strUCt 数据结构中。然后恢复要运行的新的进程的状态（又和处理器相关），把系统的控制交给这个进程。为了公平地在系统中所有可以运行（ runnable ）的进程之间分配 CPU 时间，调度程序在每一个进程的 task_struct 结构中保存了信息：

参见 kernel/sched.c schedule()

policy 进程的调度策略。 Linux 有两种类型的进程：普通和实时。实时进程比所有其它进程的优先级高。假如有一个实时的进程预备运行，那么它总是先被运行。实时进程有两种策略：环或先进先出（ round robin and first in first out ）。在环的调度策略下，每一个实时进程依次运行，而在先进先出的策略下，每一个可以运行的进程按照它在调度队列中的顺序运行，这个顺序不会改变。

PRiority 进程的调度优先级。也是它答应运行的时候可以使用的时间量（ jiffies ）。你可以通过系统调用或者 renice 命令来改变一个进程的优先级。

Rt_priority Linux 支持实时进程。这些进程比系统中其他非实时的进程拥有更高的优先级。这个域答应调度程序赋予每一个实时进程一个相对的优先级。实时进程的优先级可以用系统调用来修改

Coutner 这时进程可以运行的时间量（ jiffies ）。进程启动的时候等于优先级（ priority ），每一次时钟周期递减。

调度程序从核心的多个地方运行。它可以在把当前进程放到等待队列之后运行，也可以在系统调用之后进程从系统态返回进程态之前运行。需要运行调度程序的另一个原因是系统时钟刚好把当前进程的计数器 (counter) 置成了 0 。每一次调度程序运行它做以下工作：

参见 kernel/sched.c schedule()

kernel work 调度程序运行 bottom half handler 并处理系统的调度任务队列。这些轻量级的核心线程在第 11 章具体描述

Current pocess 在选择另一个进程之前必须处理当前进程。

假如当前进程的调度策略是环则它放到运行队列的最后。

假如任务是可中断的而且它上次调度的时候收到过一个信号，它的状态变为 RUNNING

假如当前进程超时，它的状态成为 RUNNING

假如当前进程的状态为 RUNNING 则保持此状态

不是 RUNNING 或者 INTERRUPTIBLE 的进程被从运行队列中删除。这意味着当调度程序查找最值得运行的进程时不会考虑这样的进程。

Process Selection 调度程序查看运行队列中的进程，查找最值得运行的进程。假如有实时的进程（具有实时调度策略），就会比普通进程更重一些。普通进程的重量是它的 counter ，但是对于实时进程则是 counter 加 1000 。这意味着假如系统中存在可运行的实时进程，就总是在任何普通可运行的进程之前运行。当前的进程，因为用掉了一些时间片（它的 counter 减少了），所以假如系统中由其他同等优先级的进程，就会处于不利的位置：这也是应该的。假如几个进程又同样的优先级，最接近运行队列前段的那个就被选中。当前进程被放到运行队列的后面。假如一个平衡的系统，拥有大量相同优先级的进程，那么回按照顺序执行这些进程。这叫做环型调度策略。不过，因为进程需要等待资源，它们的运行顺序可能会变化。

Swap Processes 假如最值得运行的进程不是当前进程，当前进程必须被挂起，运行新的进程。当一个进程运行的时候它使用了 CPU 和系统的寄存器和物理内存。每一次它调用例程都通过寄存器或者堆栈传递参数、保存数值比如调用例程的返回地址等。因此，当调度程序运行的时候它在当前进程的上下文运行。它可能是特权模式：核心态，但是它仍然是当前运行的进程。当这个进程要挂起时，它的所有机器状态，包括程序计数器 (PC) 和所有的处理器寄存器，必须存到进程的 task_struct 数据结构中。然后，必须加载新进程的所有机器状态。这种操作依靠于系统，不同的 CPU 不会完全相同地实现，不过经常都是通过一些硬件的帮助。


交换出去进程的上下文发生在调度的最后。前一个进程存储的上下文，就是当这个进程在调度结束的时候系统的硬件上下文的快照。相同的，当加载新的进程的上下文时，仍然是调度结束时的快照，包括进程的程序计数器和寄存器的内容。

假如前一个进程或者新的当前进程使用虚拟内存，则系统的页表需要更新。同样，这个动作适合体系结构相关。 Alpha AXP 处理器，使用 TLT （ Translation Look-aside Table ）或者缓存的页表条目，必须清除属于前一个进程的缓存的页表条目。