# 进程调度
CPU调度是多道程序操作系统的基础。通过在进程间切换CPU，操作系统可以使得计算机更加高效。
对于支持线程的操作系统，操作系统实际调度的是内核级线程而非进程。不过，术语 进程调度（process scheduling）和线程调度（thread scheduling）经常交替使用。
进程调度方案分为抢占式和非抢占式。
- 在非抢占式下，进程调度只能在进程中止或者切换到等待状态（例如，I/O 请求，或 wait() 调用等）
- 在抢占式下，除了以上两种情况，还有当进程从运行状态切换到就绪状态（例如出现中断）或者进程由等待状态切换到就绪状态时（例如 I/O 完成）时，都可以发生调度。
Windows 3.x 使用了非抢占调度；Windows 95 开始引入抢占式调度，所有之后的 Windows 都是抢占式调度。Mac OS X 采用抢占调度。
# 调度算法
介绍常用的进程调度算法。
# 1. 先来先服务调度
FCFS 调度算法最简单，先请求CPU的进程首先分配到CPU，是非抢占式的。实现简单，但是缺点不少。
FCFS往往会导致平均等待时间很长，尤其是当运行时间很长的进程先到达时，会拖慢后面所有进程的时间。
# 2. 最短作业优先调度
最短作业优先调度（Shortest Job First，SJF）调度算法将每个进程与下次CPU执行时间关联起来。当CPU变为空闲时，它会被赋予具有最短CPU运行时长的进程。 注意这里更为恰当的说法是 最短下次CPU执行，因为调度取决于进程下次CPU执行的时间，而不是总的CPU执行时间。
可以证明 SJF 算法是最优的，因为其平均等待时间最小。SJF 算法的真正困难是如何直到下次CPU执行的长度。
SJF 算法既可以是非抢占的也可以是抢占的。当一个新进程到达就绪队列而以前的进程还在被执行时，就需要考虑是否需要抢占了。抢占SJF调度有时被称为最短剩余时间优先（Shortest Remaining Time First）。
# 3. 优先级调度
在优先级调度中，每个进程会被赋予一个优先级，具有最高优先级的进程会被分配到CPU。
SJF 算法可以理解为优先级调度的一个特例，其中下次CPU执行时间的倒数就是优先级）
优先级的定义既可以是内部的，也可以是外部的。内部定义的优先级一般采用一些测量数据来计算进程优先级，例如时限，内存要求，打开文件数量，平均I/O时间与平均CPU时间之比 等。外部定义的优先级则采用操作系统以外的准则，例如进程重要性，赞助部门，其他因素（政治等）。
与 SJF 类似，优先调度可以是抢占的，也可以是非抢占的。
优先级调度算法的一个主要问题是无穷阻塞或饥饿，因为低优先级进程可能会无穷等待CPU。解决无穷等待问题的解决方案之一是 老化（aging）。老化逐渐增加在系统中等待很长时间的进程的优先级，例如每隔一定时间增加等待进程的优先级。
# 4. 轮转调度
轮转（Round-Robin，RR）调度算法是专门为分时系统设计的。它类似于 FCFS 的设计，但是增加了抢占以切换进程。定义一个时间片（例如10ms ~ 100ms）。就绪队列作为循环队列，为每个进程分配不超过一个时间片的CPU。
RR算法的性能很大程度取决于时间片大小。在一种极端情况下，时间片很大，那么 RR 就退化成了 FCFS。相反，如果时间片过小，则会导致大量的上下文切换开销。
一般来说，如果大多数进程能在一个时间片内完成，那么平均等待时间会有所改善。这也是设计时间片大小的关键。根据经验，80%的CPU执行应该小于时间片。
# 5. 多级反馈队列调度
多级反馈队列（Multilevel Feedback Queue）是一种多级队列调度，这种算法允许进程在队列之间迁移。这里的想法是根据不同CPU执行的特点来区分进程。如果进程使用较多的CPU时间，就把它移到更低的优先级队列。 这种方法将 I/O 密集型和交互性进程放到更高优先级队列上。此外，在较低优先级队列中等待过长的进程会被移动到较高优先级队列，这种形式的老化阻止了饥饿的发生。
通常，多级反馈队列调度程序可以由下列参数来定义：
- 队列数量。
- 每个队列的调度算法。
- 用以确定何时升级到更高优先级队列的方法。
- 用以确定何时降级到更低优先级队列的方法。
- 用以确定进程在需要服务时会进入哪个队列的方法。
以上五种调度算法都是单处理器系统的CPU调度算法。如果有多个CPU，则负载分配成为可能，但是调度问题就更加复杂。
# Linux 调度
Linux 采用的是 完全公平调度程序（Completely Fair Scheduler，CFS），比较复杂，以后再说...
多级反馈队列调度是最通用的CPU调度算法。通过配置，它能适应所设计的特定系统。遗憾的是，由于需要一些方法来选择参数以定义最佳的调度程序，所以它也是最复杂的算法。