1. 为什么需要调度

进程调度的概念比较简单，我们假设在一个单核处理器的系统中，同一时刻只有一个进程可以拥有处理器资源，那么其他的进程只能在就绪队列中等待，等到处理器空闲之后才有计划获得处理器资源来运行。在这种场景下，操作系统就需要从众多的就绪进程中选择一个 最合适的进程 来运行，这个就是调度器需要做的事情。

作为一个通用的操作系统，需要兼顾各种类型的进程，包括交互式进程、批处理进程、实时进程等。其特征如下：

• 交互式进程： 与人机交互的进程，例如鼠标、键盘、触摸屏等相关的应用，这类进程的特点是系统响应时间越短越好，否则用户就会抱怨系统卡顿
• 批处理进程： 此类进程默默运行，可能会占用比较多的系统资源，对响应时间没有确定的要求
• 实时进程： 有些应用对整体时延有严格的要求，如VR设备，从头部转动到画面显示的间隔时间有明确的要求，否则人的体验不是太好；同时例如工业控制系统，不符合时延可能会导致严重的事故

我们以生活中为例，来看看调度器对我们实际生活的影响，以我们手机上的一个场景为例

如我们手机上运行一个机器学习的程序，大约CPU需要运行30分钟，我们也需要播放音乐

如果没有调度器：

对于手机上运行的学习进程和播放进程，学习进程属于批处理进程，而播放音乐属于实时进程，如果整体播放延时比较大就会出现卡顿的情况，用户体验就会很差。如果没有调度器，对于用户就需要30分钟才能播放音乐，那么它可能等不到30分就会抛弃这个手机。

如果有调度器：调度器让生活更美好

调度器“任性化”将程序切片执行，对于用户就可以边听音乐边等待他的程序运行完，能够完美的实现二者的兼容。

2. 如何设计一个调度器

2.1 什么是调度器

通常来说，操作系统是应用程序和可用资源直接的媒体，CPU是一个重要的资源，调度器可以临时 分配一个任务在CPU上执行 。为了使各个进程间可以公平共享CPU时间，而同时又要考虑不同的任务优先级，所以就需要一个调度器，来保证以下功能

• 有效的分配CPU时间片，根据用户的目标来提供一个很好的用户体验
• 当面对一些互相冲突的目标的时候，提供一个最优化的调度算法，例如既要为关键实时任务最小响应时间，又要最大限度的提高CPU的总体利用率

2. 2 进程分类

如果站在CPU的角度来看进程，有些进程一直占用处理器，有些进程只需要一部分处理器资源即可。所以进程按照这个特性可以分为两类

• CPU消耗型：

CPU消耗型的进程会把 大部分的时间用在运行代码上 ，并且会 一直占用CPU 。一个常见的例子就是while循环的运行，如运行大量计算的程序等。

• IO消耗性：

IO消耗性的进程会把大部分的时间用在提交I/O请求或等待I/O请求，所以这类的进程通常只需要很少的处理器计算资源即可，如需要键盘的输入进程或等待网路I/O的进程。

2.3 调度器目标

知道了进程的分类，那就可以知道哪些场景需要调度来协调，如IO消耗性的，例如磁盘，打印机，网络等场景。调度在不同场景下的目标有

• 高吞吐量： 最大系统利用率(高吞吐量)，对于一些批处理系统中需要考虑
• 低响应时间： 此类进程经常与用户进行交互, 因此需要花费很多时间等待键盘和鼠标操作. 当接受了用户的输入后, 进程必须很快被唤醒, 否则用户会感觉系统反应迟钝，主要用于一些交互式系统需要重点考虑
• 低功耗： 对于目前的移动设备，如何设计一个更优的调度算法，来保证系统的低功耗也需要重点考虑
• 实时性： 这些进程由很强的调度需要, 这样的进程绝不会被低优先级的进程阻塞. 并且他们的响应时间要尽可能的短

为了达到一些共有的目标，要达到系统资源的高利用率，多任务公平性，低调度开销，所以需要设计调度器基于以下的场景进行考虑

• 降低周转时间： 任务第一次进入系统到执行结束的时间，使批处理用户等待输出的时间尽可能短
• 降低响应时间： 任务第一次进入系统到第一次给用户输出时间，使交互用户的响应时间尽可能短
• 实时性： 在任务的截止时间内要完成任务
• 公平性： 每个任务都应该有机会执行，不能饿死，保证每个进程得到合理的CPU时间
• 开销低： 调度器是为了优化系统，而非制造性能Bug
• 可扩展性： 随着任务数量不断增加，仍然能正常工作
• 吞吐量： 使单位时间内处理的进程数量尽可能多

2.4 调度策略

确定如何从就绪队列中选择下一个执行的进程进入调度，需要解决以下问题

• 如何挑选就绪队列中的哪一个进程
• 通过什么样的调度准则来选择

2.5 如何设计好的调度算法

调度算法的要求，希望得到**“更快”**服务，那么如何定义什么是更快呢？根据调度器的目标，其可以重点关注：

• 高吞吐量：传输文件时的高带宽
• 低响应延时：玩游戏时的低延迟

调度器的响应目标考虑：

• 减小响应时间：及时处理用户的输入请求，尽快将输出反馈给用户
• 减小平均响应的时间波动：在交互系统中，可预测性比高差异低平均更重要
• 低延迟调度改善了用户的交互体验：如果移动鼠标时，屏幕中的光标没动，那么客户会如何做呢？会不会重启

处理器调度吞吐 量目标考虑

• 增加吞吐量：减小开销，主要是上下文切换的开销，系统资源的高利用(CPU /IO设备)
• 减小等待时间：减小每个进程的等待时间

处理器公平的定义：

• 保证每个进程占用相同的CPU时间
• 保证每个进程的等待时间相同

3 调度算法

3.1 先来先服务算法(First Come First Served, FCFS)

定义

每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行。

依据进程进入就绪队列的先后顺序排列，进程进入等待或者结束状态时，就绪队列中的下一个进程占用CPU，3个进程，计算时间分别为12，3，3，FCFS算法的周转时间，根据任务到达的顺序不同，周转时间不同

结合大家学习中，遇到的实际例子，我们来学习下整个过程，例如该过程中，调度器是我们生活中遇到的学霸，而此时有3个同学想学霸请教问题，其思路如下

该问题对于C同学来说，有一个很大的问题是，我的问题很简单，却需要等那么长的时间，所以对于该算法的特征如下：

优点	缺点
简单	1.平均等待时间波动较大，短进程可能排到长进程后面2.IO资源和CPU资源的利用率较低，对于上面的例子，如果该同学需要查阅相关文档，那么学霸就需要一直等待，浪费学霸的资源

3.2 短进程优先算法(SPN)

定义

它会 优先选择运行时间最短的进程来运行 ，这有助于提高系统的吞吐量。

选择就绪队列中执行时间最短进程占用CPU进入运行状态，就绪队列按预期的执行时间来排序

进程的平均周转时间为：

还是基于刚才学霸解决问题的实例来看看这个算法的执行顺序，首先A同学先执行，当执行到2后，同学B和C都来寻求学霸解决问题，但是此时A占用了学霸，所以当A解决完问题后，发现同学C问题简单，所以就优先解决C的问题

优点	缺点
平均周转时间较短	1.不公平，可能出现导致饥饿，连续的短进程流会使得长进程长时间无法获得CPU资源2.平均响应时间过长3.需要预知未来，需要解决预估下一个CPU计算的持续时间

3.3 时间片轮转算法(RR, Round-Robin)

定义

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

• 如果时间片用完，进程还在运行，那么将会把此进程从 CPU 释放出来，并把 CPU 分配另外一个进程；
• 如果该进程在时间片结束前阻塞或结束，则 CPU 立即进行切换；

通过时间片，分配处理器资源的基本单元，当时间片结束后，按FCFS算法切换到下一个就绪进程，我们还是以刚才例子为例，此时为

但是这种算法也需要重点考虑时间片长度，因为切换进程，需要有额外的上下文切换

时间片太长

• 等待时间过长
• 极限情况下退化成FCFS

时间片太短

• 反应迅速，但产生大量的上下文切换
• 大量上下文切换开销会影响系统的吞吐量

时间片长度选择目标

• 选择一个合适的时间片长度
• 经验规律：维持上下文切换开销处于1%以内

3.4 调度优先级

对于操作系统中的任务是不同的，例如，系统进程和用户进程、前台进程和后台进程，如果不加以区分，那么系统中关键的任务无法及时处理，后台运算导致视频播放卡顿，所以基于此，重要的任务需要被优先调度，就产生了优先级的概念。

3.4.1 多队列调度算法(MQ)

对于该调度算法，就绪队列被划分成多个独立的子队列，如前台(交互)、后台(批处理)，每个队列拥有自己的调度策略，如前台-RR，后台-FCFS，队列间的调度

• **固定优先级：**先处理前台，后处理后台，可能导致饥饿
• **时间片轮转：**每个队列读的到一个确定的能够调度器进程的总时间，如80%CPU时间用于前台，20%CPU时间用于后台

还是以学霸解决问题为例，基于此的算法为：

所以该算法特征为：

• 维护多个优先级队列
• 高优先级的任务优先执行
• 同优先级内使用Round Robin调度

3.4.2 公平共享调度(FSS， Fair Share Scheduling)

公平共享调度控制用户对系统资源的访问

• 一些用户组比其他用户组更重要
• 保证不重要的组无法垄断资源
• 未使用的资源按比例分配
• 没有达到资源使用率目标的组获得更高的优先级

4 调度算法总结

算法	优点	缺点
先来先服务算法	简单	不公平，平均等待时间较差
短进程优先算法	平均周转时间最小	1.不公平，可能导致饥饿2.需要精确预测计算时间
时间片轮转算法	公平	平均等待时间较差
公平共享调度	公平是第一要素
多队列调度算法	多种算法的集成