操作系统入门（四） 进程调度、中级调度、作业调度和进程调度算法

01 操作系统调度概述

操作系统对进程的调度是一种有分级且有策略的行为。

有分级是指操作系统的调度分为 作业调度（高级调度） ，进程挂起和对换（中级调度）和进程调度 （低级调度）3级 。

有策略是指操作系统会将进程组织成一种或多种数据结构，并按照一定的算法对每个进程做出尽可能兼顾公平和高效的调度。

- 作业调度

作业调度指按策略从作业队列中选一个或多个处于外存的作业（可以简单理解为程序代码）， 给它们分配内存和其他设备资源，并建立相应的进程（建立PCB）
，赋予它们竞争CPU的权利。这里所说的外存我们可以简单的理解为磁盘等非内存的存储空间。

作业调度是程序任务在外存和内存之间的调度，每个作业只调入1次，调出1次。作业调度可以理解为是对某程序的一次执行请求。

- 中级调度

中级调度指在内存紧张时将一些暂时不运行的进程（处于等待状态或就绪状态的进程）从内存换出到外存进行等待（处于外存的进程就不再参与进程调度），当内存有足够空间时再将合适的进程换入内存，参与低级调度。

引入中级调度是为了提高内存使用率（使内存在逻辑上扩大了，能容纳更多进程）和系统吞吐量（吞吐量指单位时间内系统运行完程序的个数），使内存中存放的进程数目不至于太多。

暂时调到外存等待的进程状态称为挂起状态。被挂起的进程PCB会被组织成挂起队列。

挂起状态不是阻塞状态或就绪状态，他们的区别在于，挂起状态的进程是在外存中的（具体来说是将它的程序段、数据段放在外存，但PCB是常驻内存的，因为OS要根据PCB监控和管理进程），阻塞状态和就绪状态下的进程是在内存中的。

在内存不足时，不运行的进程都有概率被换出到外存，也就是说 就绪状态 和 阻塞状态 的进程都可能变成挂起状态，所以有的操作系统将挂起状态分为 就绪挂起 和
阻塞挂起 两种状态。

同理，就绪挂起状态的进程对应就绪挂起队列，阻塞挂起状态的进程对应阻塞挂起队列，就绪挂起队列 / 阻塞挂起队列 和 就绪队列 / 阻塞队列 不是同一种队列。

于是进程的五状态模型演变成七状态模型：

进程被挂起的时机只有1种，就是内存不足的情况下。 一个进程可能被多次调入调出内存，因此中级调度的频率高于高级调度。

- 进程调度

进程调度指根据一定算法将CPU分派给就绪队列中的一个进程，CPU在进程间的切换就是由进程调度实现的。进程调度的频率很高，一般几十毫秒一次。

下面是3级调度的关系图：

三层调度的对比：

02 进程调度的细节

- 进程调度的时机

进程调度的时机其实就是某个正在运行的进程放弃CPU的时机，当一个进程放弃CPU，系统自然会调度另一个就绪进程占有CPU。因此调度的时机分为两种：当前运行进程
主动放弃CPU 和 被动放弃CPU 。

主动放弃CPU的情况有：进程正常终止/发生异常终止，进程进行IO操作而阻塞。

被动放弃CPU的情况有：人为干预终止，时间片用完，有更紧急的事处理（如IO中断）、有优先级更高的进程进入就绪队列。

需要注意，发起IO请求和IO设备完成IO操作都会发生中断，前者是用户进程主动调用系统调用委托操作系统发起IO请求因而发生trap中断，属于内中断；后者是IO设备发出外中断表示事件就绪。这两件事我们可以简单的打个比方，前者是我们主动找快递小哥寄快递，后者是快递小哥通知我快递到了让我去签收，但无论如何前者还是后者，我都不得不先放下手里的工作去找快递小哥或者去签收。

什么情况下不会进行进程调度和切换：

1. 在CPU处理中断时。中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。

2. 进程正在执行的指令在操作系统内核程序临界区中。

3. 在原语执行过程中。

为什么进程在操作系统内核程序临界区中不能进行调度和切换，但在用户程序的临界区中可以呢？

首先临界资源是一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。临界区是访问临界资源的那段代码。

内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列。如果内核临界区访问的临界资源不尽快释放的话可能影响到操作系统内核的其他管理工作，因此在这期间不能进行调度切换。

而占用普通临界区访问的临界资源不会直接影响内核的管理工作。

- 进程调度的方式

有的系统只允许进程主动放弃CPU，不允许它被动放弃，有的系统进程可以主动放弃也可以被动放弃。因此进程调度分为 非抢占方式 和 抢占方式 两种。

非抢占方式是只允许进程主动放弃CPU而触发调度和切换的调度方式。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用CPU，直到该进程终止或主动要求进入阻塞态。
非抢占方式下，进程不会被分配时间片，不存在时间片用完被动让出CPU的说法。

抢占方式是允许进程主动和被动放弃CPU而触发调度和切换的调度方式。如果有一个更重要或更紧迫的进程需要使用CPU，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。也可实现让各进程按时间片轮流执行的功能（通过时钟中断）。

- 进程调度发生了什么

1. 对原来运行进程各种CPU现场数据的保存（保存到PCB）；

2. 对新的进程各种CPU现场数据的恢复（从PCB恢复）；

3. 资源的分配/回收、进程状态的改变，PCB转移到对应队列等；

进程切换是有代价的，因此如果过于频繁的进行进程调度、切换，必然会使整个系统的效率降低，
使系统大部分CPU时间都花在了进程切换上，而真正用于执行进程的时间减少。

这也是为什么中级调度可以提高系统吞吐量的原因，将进程换出到外存后，内存中的进程就少了（参与进程调度的进程少了），切换进程的次数减少，切换进程的时间也会减少。

由于进程调度很频繁，因此，进程调度（切换进程）的速度必须要很快才不至于影响CPU真正处理进程任务的效率，例如每个进程要运行10ms，进程调度程序执行一次平均占1ms，那么CPU有1/11
≈ 9% 的时间花费在进程切换上，91%的时间才是真正处理用户进程或其他正经的系统进程任务。

03 进程调度算法

下面正式介绍各种进程调度算法，需要从下面6个方面思考每种算法：

a. 这种算法的设计出来解决什么问题（算法思想）

b. 算法的规则

c. 这种算法用于作业调度还是进程调度

d. 这种算法是抢占式还是非抢占式

e. 优缺点

f. 是否导致进程饥饿（某个进程长期得不到运行机会）

PS：下面会介绍6种进程调度算法，但最终比较完善的调度算法是第6种算法——“多级反馈队列算法”，如果大家觉得这6种算法一个个介绍很繁琐的话，可以跳过前面5种算法，直接看最后一种算法。

- 调度算法的评价指标

CPU利用率：CPU忙碌的总时间

系统吞吐量：单位时间内总共完成多少道作业/进程

周转时间：一个作业完成的时刻 - 该作业提交的时刻，也等于 作业/进程等待时间 + 作业/进程运行时间。

平均周转时间：各作业周转时间之和 / 作业数

带权周转时间：作业的周转时间 / 作业的实际运行的时间，带权周转时间必定大于1，该值越小越好。

平均带权周转时间：各作业带权周转时间之和 / 作业数

等待时间：进程/作业 处于等待CPU状态的时间之和。等待时间 = 周转时间 - 运行时间。

响应时间：从用户提交作业请求到该作业第一次占有CPU的时间。

- 先来先服务算法 FCFS

算法思想：从公平角度出发而设计出来的算法；

算法规则：按作业/进程的到达的先后顺序进行服务；

用于作业/进程调度：用于作业调度时，先到达作业队列的作业先服务；用于进程调度时，先到达就绪队列的进程先服务；

是否可抢占：非抢占算法（该算法下进程无时间片限制）；

优点：公平且算法简单；

缺点：排在长作业（进程）后面的短作业需要等待很长时间。即 FCFS对长作业有利，对短作业不利
。（试想一下，你去买一杯奶茶，结果发现排在你前面的某个人要买20杯）

是否导致饥饿：不会。任何一个进程都能得到服务，尽管有些进程可能要等很久。

- 短作业优先 SJF/SPF

算法思想：追求最少的平均等待时间 和 带权周转时间（说人话就是先运行工作量较小的进程，使得其他进程等待的时间尽可能少）；

算法规则：所以进程中运行时间（是用户要求的或提供的运行时间）最短的作业/进程先得到服务；

用于作业/进程调度：可用于作业调度 和 进程调度。用于进程调度时 称为“短进程优先（SPF, Shortest Process First）算法”；

是否可抢占：非抢占算法，也有抢占式的版本——最短剩余时间优先算法（SRTN）；

优点：可以获得理论上最短的平均等待时间和平均周转时间；

缺点：不公平，对长作业不利，长作业可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的， 并不一定真实，不一定能做到真正的短作业优先。

是否导致饥饿：会。如果源源不断地有短作业/进程到来，会使长作业/进程长时间得不到服务，产生“饥饿”现象。

- 高响应比优先 HRRN（HRRF）

算法思想：响应是指作业从进入系统到它第一次占有CPU所等的时间，高响应是指尽可能让每个进入系统的作业不一定都尽早的处理完，但要都尽早的持有CPU，让用户感觉自己的进程得到了响应已经在运行了，而不是一动不动。

算法规则：选择响应比高的作业/进程先服务，响应比 = （等待时间 + 要求服务的时间） / 要求服务的时间；

要求服务的时间，即运行时间，占有CPU的时间，但运行时间是用户预估的，提前输入到系统的，因此叫做 要求服务的时间。

用于作业/进程调度：皆可；

是否可抢占：非抢占算法，只有当前运行的作业/进程主动放弃 CPU时（如IO阻塞），才会进行下一次进程调度，在发生调度时才需要计算响应比；

优点：综合考虑了等待时间和运行时间（要求服务时间） 。等待时间相同时，要求服务时间短的优先 ；要求服务时间相同时，等待时间长的优先
。对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，获得被调度的机会也越来越大，从而避免了长作业饥饿的问题；

缺点：没有考虑到作业/进程的紧急程度；而且如果要求服务的时间预估错误，则高响应比算法不再有效。

是否导致饥饿：不会。

这3种算法主要关心对进程的公平性、平均周转时间、平均等待时间等指标，但并不区分任务的紧急程度，因此对于用户来说，交互性很糟糕。

因此这三种算法一般适合用于早期的批处理系统，而不适合交互式系统。不过，FCFS先来先服务算法也常结合其他的算法使用，即使在现在也扮演着很重要的角色。

- 时间片轮转 RR

算法思想：让每个进程公平的、轮流的得到运行机会，每个进程在一定时间间隔内都可以占有CPU运行，相比于先来先服务算法，RR算法除了公平外还考虑到了让每个进程的响应时间尽量短；

算法规则：为每个在就绪队列中的进程分配一个时间片，一开始按照进程进入队列的顺序执行这些进程，如果进程未在一个时间片内执行完，则剥夺该进程对CPU的占有，将该进程重新放到就绪队列队尾排队；

用于作业/进程调度：仅用于进程调度；

是否可抢占：抢占式调度；

优点：公平；每个进程响应快；

缺点：没有考虑到作业/进程的紧急程度；时间片大小的设计需要足够合适，否则会降低进程运行效率。

是否导致饥饿：不会。

如果时间片大小太大，每个进程都能在一个时间片内完成，则RR算法会退化为先来先服务算法，后到达的进程可能要等很久才能开始执行，进程变为串行，降低了并发效率。

如果时间片大小太小，进程频繁发生切换，CPU时间都消耗在进程切换而非处理用户任务，从而降低CPU效率和进程运行效率。切换进程的CPU时间应该小于CPU总运行时间的1%。

- 优先级调度算法

算法思想：根据任务的紧急程度来决定处理顺序；

算法规则：每个作业/进程都会分配到一个的优先级，系统选择优先级最高的 作业/进程 最先运行；

用于作业/进程调度：皆可；

是否可抢占：非抢占式调度和抢占式调度皆可；

优点：区分进程的紧急程度，根据优先级决定调度顺序；也可以灵活设定 CPU密集型 和 IO密集型进程的优先级；

缺点：若源源不断地有高优先级进程到来，就会导致低优先级进程饥饿。

是否导致饥饿：会。

如何实现高优先级进程先运行呢？有两种方式，一种是按照不同优先级划分多个就绪队列；另一种是只有一个就绪队列，但系统会把优先级高的进程排在更接近队头的位置。

根据优先级是否可变，可将优先级分为静态优先级和动态优先级两种。

静态优先级：创建进程时就确定，之后一直不变。

动态优先级：创建进程时有一个初始值，之后根据情况动态调整优先级。

如何合理设置各类进程的优先级？ 通常来说

系统进程优先级 高于 用户进程。

前台进程 高于 后台进程。

IO密集型进程 高于 CPU密集型进程。

原因是IO设备和CPU可以并行工作，优先让IO密集型进程工作可以让IO设备尽早投入工作，并且CPU会在发出IO请求后立刻处理之后的CPU密集型进程，如此一来两种进程并行运行，IO设备处理IO密集型进程的请求，同时CPU也在运行CPU密集型的进程运算，IO设备和CPU都不会闲着。提高了资源利用率，系统吞吐量和并发率。

如果采用动态优先级，什么时候应该调整优先级？（可以从公平、提高资源利用率的角度考虑）

如果某进程在就绪队列等待了很长时间，可以提升其优先级。

如果某进程占用CPU时间很长，可以适当降低其优先级。

如果发现一个进程频繁的发生IO操作，可以提升其优先级。

- 多级反馈队列调度算法

算法思想：对其他调度算法的折中（公平性、每个进程及时响应、区分紧急程度）；

算法规则：

1、设置多级就绪队列，各级队列优先级从高到低，时间片从大到小。

2、新进程到达时先进入第1级队列（最高优先级），分配最长时间片，按先来先服务原则调度。

若进程的时间片用完，该进程就会进入下一级队列的队尾。如果进程已经处于最低级队列，则时间片用完时，重新放到本队列队尾。

3、只有在第k级队列为空时，才会选择调度k+1级队列的进程。只有开始调度某一进程时，才会为这个进程分配时间片。

4、被抢占时，当前进程不降级，放回本队列的队尾。

5、主动让出CPU时，当前进程不降级，例如如果进程因IO阻塞而让出CPU，则放回本队列的队尾，如果多次因IO阻塞让出CPU，说明他是IO密集型进程，还可以被放入上一级队列中提升优先级。

用于作业/进程调度：用于进程调度；

是否可抢占：抢占式。当k级队列的进程在运行时，若更上级的队列进入一个新进程，新进程会抢占CPU，原来的进程会返回k级队列尾部；

优点：该算法同时使用了FCFS、RR、SPF 和
优先级调度算法，也集合了他们的优点，即公平、快速响应、短进程快速完成（他们可能在第一级队列就完成了）、区分进程紧急程度、灵活调整系统对CPU/IO密集型进程的偏好；

缺点：可能导致饥饿。

是否导致饥饿：会，例如不停有新进程进入1级队列，而且这些进程都是短进程，在1个时间片内就可以完成，此时下级队列的进程就一直无法持有CPU。

UNIX系统使用的就是多级反馈队列算法。