因为有进程间通信，就会涉及到多个进程竞争CPU，操作系统要决定哪一个进程先运行。

调度介绍

我们将进程分为计算密集型（compute-bound）和I/O密集型（I/O-bound），这是通过进程行为进行分类。

如果需要运行I/O密集型进程，那么就应该让它尽快得到机会，以便发出磁盘请求保持磁盘忙碌。

什么时候调度

一定会发生调度：

当一个进程退出时
当一个进程在I/O或信号量阻塞时

可能发生调度：

当一个新进程创建时
当一个I/O中断发生时（意味着I/O设备完成了工作，一些进程可以转变为就绪态）
当一个时钟中断发生时

调度算法目标

为了设计一个调度算法，应该首先明确一个好的调度算法必须做什么。

所有系统都要求

公平

给每个进程公平的CPU份额
策略强制执行

执行所规定的策略
平衡

保持系统所有的部分都忙碌

批处理系统

吞吐量

最大化每小时作业数
周转时间（turnaround time）

最小化从提交到完成的时间间隔（衡量了用户等待一个输出的平均时间），时间越短越好
CPU利用率

保持CPU始终忙碌（并不是一个好的度量参数）

交互式系统

响应时间

快速响应请求
均衡性

满足所有用户需求

实时系统

满足截止时间

避免丢失数据
可预测性

在多媒体系统中避免失真

批处理系统中的调度

先来先服务（FCFS）

non-preemptive scheduler

在这个算法中，进程按照他们请求CPU的顺序使用CPU，维持一个就绪进程的单一队列。

当一个作业从外部进入系统，就马上运行并可以运行任意长时间。当其他作业到来时，就被插入队列尾端。

当运行的进程阻塞时，队列里的第一个进程调度运行，当这个阻塞的进程转为就绪时，再次插入队列尾端。

算法的优点很明显：易于实现。但缺点是在I/O密集型进程和计算密集型进程交替执行时，效率很低（convoy effect）。

最短作业优先（SJF）

preemptive scheduler

这也是很容易想到的贪心算法。当一批作业同时到来时，我们先处理作业最短的。

改善平均周转时间，缩短作业的等待时间。

可以证明，当所有作业同时启动时，最短作业优先算法是最优的。这能够使得平均等待时间最短，最大化吞吐量。

但这种算法也只能在批处理系统中有用。因为在实际的其他系统中，每个作业的到达时间、执行时间都是未知的。

最短剩余时间优先（STCF）

preemptive scheduler

使用这种调度算法，调度器总是挑选其剩余时间最短的那些进程运行，同样，运行时间必须预知。

当一个新作业到来时，它所需的总时间与当前运行进程的剩余时间进行比较，如果新作业需要比当前进程更少的时间完成，那么当前进程被挂起，新作业运行。

这种方式可以使得新到来的短作业得到较好的服务。

最高响应比优先（HRRN）

HRRN是介于FCFS（先来先服务算法）与SJF（短作业优先算法）之间的折中算法，既考虑作业等待时间又考虑作业运行时间，既照顾短作业又不使长作业等待时间过长，改进了调度性能。

响应比 =（等待时间+预估执行时间）/ 预估执行时间

即RR=（w+s）/s=1+w/s，因此响应比一定是大于1的。

CPU每次计算所有作业的响应比，选择最高响应比再进行作业。

三级调度

准入调度器

当作业到来时，首先被放入存储在磁盘上的输入队列中。

准入调度器决定哪些作业允许进入系统，其他作业被选中之前就保存在输入队列中。

一个典型的准入控制算法是找一些计算密集型进程和I/O密集型进程缓和一起运行。
内存调度器

决定哪个进程留在内存而哪个进程换出到磁盘。在内存中保留的进程数称为多道程序的道数。
CPU调度器

实际在内存中选取下一个将要运行的进程。任何合适的抢占式和非抢占式调度算法都可以在CPU调度器中使用。

交互式系统中的调度

在交互式系统中，一般使用两级调度（内存调度和CPU调度），下面将重点介绍CPU调度器和一些常见的调度算法。

时间片轮转调度

每个进程被分配一个时间段，称为它的时间片（Quantum），即该进程允许运行的时间。

时间片轮转调度中最有趣的一点就是时间片的长度。

从一个进程切换到另一个进程需要进行上下文切换（context switch），但这个过程需要overhead，因此，如果时间片设计的过短，单位时间的上下文切换消耗过大。而时间片设置得比平均CPU突发时间长，抢占会很少发生，使得交互请求的相应变差。

注意，在交互式系统中我们注重响应时间，在这种目标下此算法很好，但在周转时间上很差。

因此，时间片过短会导致过多的进程切换，降低了CPU效率；设得过长又可能引起对短的交互请求的相应变差。通常来说时间片设置为20~50ms。

优先级调度

每个进程被赋予优先级，率先运行优先级最高的就绪进程。

我们可以设计多个优先级队列，在同类进程内部采用时间片轮转调度。

最短进程优先

由于最短作业优先在批处理系统中常常伴随产生最短平均相应时间，因此可以用于交互进程。

如何从当前的就绪进程中找出最短的那一个？一种方法是根据进程过去的行为进行推测，并执行估计运行时间最短的那一个。

可以通过将当前测量值和先前估计值进行加权平均得到下一个估计值的技术称为老化。

彩票调度算法

算法为进程发放针对系统各种资源（如CPU时间）的彩票，当调度器需要作出决策时，随机选择一张彩票，持有该彩票的进程将获得系统资源。

如果一个新进程创建并得到一些彩票，则下次抽奖时，它中奖的机会与其持有的彩票成正比。因此，彩票调度的反映非常迅速。

公平分享调度

考虑进程的拥有者是谁，对每个用户赋予不同的CPU时间。

实时系统调度

分为硬实时和软实时。

软实时允许偶尔超过时间限制，而硬实时必须满足时间限制。

按照要响应的时间进一步分为周期性和非周期性。一个系统必须响应多个周期的事件流。

例如，有 $m$ 个周期性的事件，事件 $i$ 的周期为 $P_i$ ，其中每个事件需要 $C_i$ 秒的CPU时间来处理，则必须满足：

$\sum\limits_{i=1}^m\frac {C_i}{P_i} \le 1$

才可能处理所有的负载。满足该条件的实时系统是可调度的（schedulable）。

调度策略与机制

将调度问题分解为调度策略与调度机制
调度机制（scheduling mechanism）
- 将调度算法以某种形式参数化
调度策略（scheduling policy）
- 参数由用户进程依据相应的策略设置
例如，若内核使用优先级调度算法，且提供一条系统调用，则该主进程可以使用它来设置或改变其子进程的优先级。（nice命令）

线程调度

若系统中进程包含多线程，则系统中存在两个层次上的并行性：线程级和进程级。
线程的实现方式决定了线程级的调度模式

用户级线程

只需要几条指令，无须上下文切换、修改内存映射、高速缓存失效等等，时间快
用户级线程阻塞会引起整个进程的阻塞
进程内部的线程调度器决定哪个进程运行，没有时钟中断来打断运行了足够长时间的线程，操作系统按照进程来调度

内核级线程

内核挑选线程运行，不需要考虑这个线程属于哪个进程
线程被赋予时间片，如果线程运行时间超过了这个时间片，将会被强制挂起

区别

主要区别是性能

用户级线程进行线程切换只需要几条指令，而内核级线程需要完整的上下文切换，修改内存映射，使高速缓存失效，这将比用户级线程切换慢几个数量级。
在使用内核线程时，一个线程的阻塞不会导致整个进程阻塞，而如果在用户级线程下则会导致整个进程阻塞。

例如，在忙等待引起的阻塞时，没有办法被系统检测到。（在用户级线程中线程只是一条语句或一个函数，而忙等待则无法执行这条语句）
内核知道从不同进程的线程切换需要更大开销，因此当内核考虑线程切换时，同等重要的情况下，优先考虑同进程的线程。
用户线程可作为特定应用定制的调度器。

参考资料

Operating System:Design and Implementation,Third Edition
操作系统调度算法

进程调度介绍