进程调度

基本概念

进程调度是操作系统的核心功能之一，负责动态分配处理机（CPU）资源给就绪队列中的进程，确保系统高效运行。其主要功能包括：

记录进程状态：通过进程控制块（PCB）跟踪进程的执行情况（如运行态、就绪态、等待态）。
选择进程：根据调度算法从就绪队列中选出下一个占用CPU的进程。
上下文切换：保存当前进程的寄存器状态并加载新进程的上下文，实现CPU控制权转移。

进程调度的三个层次

高级调度

alt text

高级调度（作业调度）：按一定规则从外存调入作业后备队列中挑选一个作业调入内存，并创建进程。每个作业只调入一次，调出一次。作业调入时会建立PCB。调出时才撤销PCB。

==高级调度本质就是选择一个作业从外存调入内存。==

低级调度

alt text

低级调度（进程调度/处理机调度）：按照某种策略从就绪队列中选取一个进程，将处理分配给他。

==进程调度是操作系统中最基本的调度。本质是选择一个进程上处理机运行。==

中级调度

alt text

内存不够时，可将某些进程的数据调出外存。等内存空闲或者进程需要运行时在重新调入内存。

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

中级调度（内存调度）：按照某种策略决定将哪个处于挂起状态的进程重新调入内存。一个进程可能会被多次调出，调入内存，因此中级调度发生的频率要比高级调度更高。

==中级调度本质就是选择一个进程调入/调出内存。==

进程挂起态与七状态模型

alt text

三层调度的关系对比

alt text

进程调度指标

CPU利用率

指CPU忙碌时间占总时间比例：

$$利用率 = \frac{忙碌的时间}{总时间}$$

系统吞吐量

单位时间内完成作业的数量

$$利用率 = \frac{总共完成了多少道作业}{总共花的时间}$$

周转时间

作业被系统提交给系统开始，到作业完成为止的这段时间间隔。它包括四个部分：

作业从外存后备队列上等待作业调度的时间
进程在就绪队列上等待进程调度的时间
进程在CPU上执行的数据
进程等待I/O操作完成的时间。

对于用户操作来说，更关心自己的单个作业的周转时间

$$周转时间 = 作业完成时间 - 作业提交时间$$

对于操作系统来说，更关心的是系统的整体表现。

$$平均周转时间 = \frac{各作业周转时间和}{作业数}$$

$$带权周转时间 = \frac{作业周转时间}{作业实际运行时间}= \frac{作业完成时间 - 作业提交时间}{作业实际运行时间}$$

$$平均带权周转时间 = \frac{各作业带权周转时间之和}{作业数}$$

等待时间

计算机用户希望自己的作业尽可能少的等待处理机。等待事件，指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低。

alt text

对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待I/O完成的期间起始进程也是被服务的，所以不计入等待时间。
对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中的等待时间。

一个作业总共需要被CPU服务多久，被I/O设备服务多久一般是确定不变的。调度算法只会影响作业/进程的等待时间。

响应时间

对于计算机用户来说，会希望自己的提交的请求（比如通过键盘输入了一个调试命令）尽早地开始被系统服务、回应。

响应时间：从用户提交请求到首次产生响应所用的时间。

调度器/调度程序

线程在就绪态和运行态之间的切换由调度程序引起，调度程序决定。

调度时机：

创建新进程
进程退出
运行进程阻塞
I/O中断发送

调度策略：

非抢占式调度策略：只有在运行进程阻塞或退出才触发调度程序工作。
抢占式调度策略：每个时钟中断或K个时钟中断会触发调度程序工作。

alt text

闲逛进程

调度程序永远的备胎，没有其他就绪进程时，运行闲逛进程。

闲逛进程特性：

优先级最低
可以是0地址指令，占一个完整的指令周期（指令周期例行检查中断）
能耗低

进程调度算法

先来先服务算法(FCFS)

算法规则：按照到达的先后顺序调度，事实上就是等待时间越久的越优先得到服务。
用于作业/进程调度：用于进程调度时，考虑的是哪个作业先到达后备队列；用于进程调度时，考虑的哪个进程先到达就绪队列
是否可抢占：非抢占式算法
是否会导致饥饿（某进程/作业长期得不到服务）：不会（作业依次进行处理）
优点：公平，算法实现简单
缺点：

排在后面的队列有等待很长时间，带权周转时间大，对短作业用户体验不好。
FCFS算法对长作业有利，对短作业不利。

举例：各进程到达就绪队列的时间、需要的运行时间如下表所示。使用先来先服务调度算法，计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

alt text

$$周转时间 = 完成时间 - 到达时间$$

$P1 = 7 - 0 = 7$
$P2 = 11 - 2 = 9$
$P3 = 12 - 4 = 8$
$P4 = 16 - 5 = 11$

$$带权周转时间 = \frac{周转时间}{运行时间} $$

$P1 = \frac{7}{7} = 1$
$P2 = \frac{9}{4} = 2.25$
$P3 = \frac{8}{1} = 8$
$P4 = \frac{11}{4} = 2.75$

$$等待时间 = 周转时间 - 运行时间$$

$P1 = 7 - 7 = 0$
$P2 = 9 - 4 = 5$
$P3 = 8 - 1 = 7$
$P4 = 11 - 4 = 7$

$$平均周转时间 = \frac{周转时间和}{任务数} = \frac{7 + 8 + 9 + 11}{4} = 8.75$$

$$平均带权周转时间 = \frac{带权周转时间和}{任务数} = \frac{1 + 2.25 + 8 + 2.75}{4} = 3.5$$

$$平均等待时间 = \frac{等待时间和}{任务数} = \frac{0 + 5 + 7 + 7}{4} = 4.75$$

短作业优先算法

非抢占式短作业/进程优先算法(SJF/SPF)

算法规则：每次调度选择当前已到达且运行时间最短的作业/进程
用于作业/进程调度：即可用于作业调度，也可用于进程调度。用于进程调度时称为短进程优先算法(SPF, Shortest Process First)
是否可抢占：SJF和SPF是非抢占式的算法。但是也有抢占式的版本——最短剩余时间优先算法(SRTN, Shortest Remaining Time Next)

alt text

$$周转时间 = 完成时间 - 到达时间$$

$P1 = 7 - 0 = 7$
$P3 = 8 - 4 = 4$
$P2 = 12 - 2 = 10$
$P4 = 16 - 5 = 11$

$$带权周转时间 = \frac{周转时间}{运行时间} $$

$P1 = \frac{7}{7} = 1$
$P3 = \frac{4}{1} = 4$
$P2 = \frac{10}{4} = 2.5$
$P4 = \frac{11}{4} = 2.75$

$$等待时间 = 周转时间 - 运行时间$$

$P1 = 7 - 7 = 0$
$P3 = 4 - 1 = 3$
$P2 = 10 - 4 = 6$
$P4 = 11 - 4 = 7$

$$平均周转时间 = \frac{周转时间和}{任务数} = \frac{7 + 4 + 10 + 11}{4} = 8$$

$$平均带权周转时间 = \frac{带权周转时间和}{任务数} = \frac{1 + 4 + 2.25 + 2.75}{4} = 2.56$$

$$平均等待时间 = \frac{等待时间和}{任务数} = \frac{0 + 3 + 6 + 7}{4} = 4$$

抢占式短作业/进程优先算法(SRTN)

算法规则：每当有进程加入就绪队列改变时就要发生调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度。
优点：“最短的”平均等待时间、平均周转时间
缺点：不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先
是否会导致饥饿：会。如果源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生饥饿现象。如果一直得不到服务，则称为饿死。
用于作业/进程调度：即可用于作业调度，也可用于进程调度。用于进程调度时称为短进程优先算法(SPF, Shortest Process First)

alt text

$$周转时间 = 完成时间 - 到达时间$$

$P1 = 16 - 0 = 16$
$P2 = 7 - 2 = 5$
$P3 = 5 - 4 = 1$
$P4 = 11 - 5 = 6$

$$带权周转时间 = \frac{周转时间}{运行时间}$$

$P1 = \frac{16}{7} = 2.28$
$P2 = \frac{5}{4} = 1.25$
$P3 = \frac{1}{1} = 1$
$P4 = \frac{6}{4} = 1.5$

$$等待时间 = 周转时间 - 运行时间$$

$P1 = 16 - 7 = 9$
$P2 = 5 - 4 = 1$
$P3 = 1 - 1 = 0$
$P4 = 6 - 4 = 2$

$$平均周转时间 = \frac{周转时间和}{任务数} = \frac{16 + 5 + 1 + 6}{4} = 7$$

$$平均带权周转时间 = \frac{带权周转时间和}{任务数} = \frac{2.28 + 1.25 + 1 + 1.5}{4} = 1.50$$

$$平均等待时间 = \frac{等待时间和}{任务数} = \frac{9 + 1 + 0 + 2}{4} = 3$$

注意事项

如果题目中没有明确说明，短作业优先调度算法默认是非抢占式的。
在所有进程同时可运行时、所有进程都几乎同时到达时，采用SJF调度算法的平均等待事件、平均周转时间最少。相比于其他算法（如FCFS）SJF依然可以或者较少的平均等待时间。
如果选择题中出现了平均等待事件、平均周转时间最少的选项。最后看看其他选项有没有明显的错误。

高响应比优先算法

算法规则：每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务。
用于作业/进程调度：即可用于作业调度，也可用于进程调度。
是否可抢占：非抢占式算法。
优缺点：综合考虑了等待时间和运行时间（要求服务时间），等待时间相同时，要求服务时间短的优先（SJF 的优点），要求服务时间相同时，等待时间长的优先（FCFS 的优点），对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题。
是否会导致饥饿：不会。

例题：各进程到达就绪队列的时间、需要的运行时间如下表所示。使用高响应比优先调度算法，计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

alt text

$$响应比 = \frac{等待时间 + 要求服务时间}{要求服务时间}$$

0时刻：进程P1上处理机运行。
2时刻：进程P2到达，等待进程P1运行结束。
4时刻：进程P3到达，等待进程P1运行结束。
7时刻：进程P1运行结束，CPU准备调度另外一个进程上处理机运行。此时进程P2响应比：$\frac{5 + 4}{4} = 2.25$。进程P3的响应比：$\frac{3 + 1}{1} = 3$。进程P4的响应比：$\frac{2 + 4}{2} = 1.5$。其中P3的响应比最高，选择P3上处理机运行。
8时刻：进程P3运行结束，CPU准备调度另外一个进程上处理机运行。此时进程P3响应比：$\frac{6 + 4}{4} = 2.5$。进程P4的响应比：$\frac{4 + 1}{4} = 1.75$。其中P3的响应比最高，选择P3上处理机运行。
12时刻：进程P2运行结束，CPU调度P4上处理机运行

时间片轮转调度算法

算法思想：公平地，轮流地为各个进程服务。让每个进程在一定时间间隔内都可以得到响应。
算法规则：按照各进程到达的就绪队列的顺序，轮流让各个进程执行一个事件片100ms。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾进行重新排队。
用于作业/进程调度：即可用于作业调度，也可用于进程调度。
是否可抢占：若进程未在时间片内运行完，将被强行剥夺CPU使用权。时间片轮转算法属于抢占式算法。由时钟装置发出时钟中断来通知来通知CPU时间片已到。
时间片的大小影响：

如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。
另一方面，进程调度、切换是有时间代价的（保存、恢复运行环境），因此如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比
一般来说，设计时间片要让切换进程开销占比不超过1%。

是否会导致饥饿：不会。

各进程到达就绪队列的时间、需要的运行时间如下表所示。使用时间片轮转调度算法，分析时间片大小分别是2、5时的进程运行情况。

时间片为2时

alt text

0时刻（就绪队列：头 -> P1 -> 尾）：进程P1到达，此时就绪队列只有P1，调度P1上处理机运行。
2时刻（就绪队列：头 -> P2 -> P1 -> 尾）：进程P2到达，此时P1进程没有运行完，进程P2抢占上处理机运行。
4时刻（就绪队列：头 -> P1 -> P3 -> P2 -> 尾）：进程P3到达，挂到就绪队列等待，从就绪队列中选取进程P1上处理机运行。进程P2的时间片用完，挂到就绪队列等待。
5时刻（就绪队列：头 -> P1 -> P3 -> P2 -> P4 -> 尾）：进程P4到达，挂到就绪队列等待。
6时刻（就绪队列：头 -> P3 -> P2 -> P4 -> P1 -> 尾）：进程P1的时间片用完，挂到就绪队列等待，从就绪队列中选取进程P3上处理机运行。
7时刻（就绪队列：头 -> P2 -> P4 -> P1 -> 尾）：进程P3运行结束，从就绪队列中选取P2上处理机运行。
9时刻（就绪队列：头 -> P4 -> P1 -> 尾）：进程P2运行结束，从就绪队列中选取P4上处理机运行。
11时刻（就绪队列：头 -> P1 -> P4 -> 尾）：进程P4的时间片用完，挂到就绪队列等待，从就绪队列中选取进程P1上处理机运行。
12时刻（就绪队列：头 -> P4 -> 尾）：进程P1运行结束，从就绪队列中选取P4上处理机运行。
16时刻（就绪队列：头 -> 尾）：进程P4运行结束。

时间片为5时

alt text

0时刻（就绪队列：头 -> P1 -> 尾）：进程P1到达，此时就绪队列只有P1，调度P1上处理机运行。
2时刻（就绪队列：头 -> P1 -> P2 -> 尾）：进程P2到达，进程P1的时间片没用完，挂到就绪队列等待。
4时刻（就绪队列：头 -> P1 -> P2 -> P3 -> 尾）：进程P3到达，进程P1的时间片没用完，挂到就绪队列等待。
5时刻（就绪队列：头 -> P2 -> P3 -> P4 -> 尾）：进程P4到达，挂到就绪队列等待。进程P1运行结束，从就绪队列中选取进程P2上处理机运行。
9时刻（就绪队列：头 -> P3 -> P4 -> 尾）：进程P2运行结束，从就绪队列中选取进程P3上处理机运行。
10时刻（就绪队列：头 -> P4 -> 尾）：进程P3运行结束，从就绪队列中选取进程P4上处理机运行。
16时刻（就绪队列：头 -> 尾）：进程P4运行结束。

优先级调度算法

算法思想：随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序。
算法规则：每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程。
作业调度/进程调度：既可用于作业调度，也可用于进程调度。甚至，还会用于在之后会学习的I/O调度中
是否可抢占：抢占式、非抢占式都有。做题时的区别在于：非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占。
优先级分类：根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级两种。

静态优先级：创建进程时确定，之后一直不变。
- 系统进程优先级高于用户进程
- 前台进程优先级高于后台进程
- 操作系统更偏好I/O型进程（或称I/O繁忙型进程）I/O设备和CPU可以并行工作。如果优先让I/O繁忙型进程优先运行的话，则越有可能让I/O设备尽早地投入工作，则资源利用率、系统吞吐量都会得到提升
- 注：与I/O型进程相对的是计算型进程（或称CPU繁忙型进程）
动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级。可以从追求公平、提升资源利用率等角度考虑
- 如果某进程在就绪队列中等待了很长时间，则可以适当提升其优先级
- 如果某进程占用处理机运行了很长时间，则可适当降低其优先级
- 如果发现一个进程频繁地进行I/O操作，则可适当提升其优先级

优缺点：

优点：用优先级区分紧急程度，重要程度。适用于实时操作系统。可以灵活的调整对各种作业/进程的偏好程度。
缺点：若源源不断的有高优先级进程到来，则可能导致饥饿。

是否会导致饥饿：会。

例题：各进程到达就绪队列的时间、需要的运行时间、进程优先数如下表所示。使用非抢占式的优先级调度算法，分析进程运行情况。（注：优先数越大，优先级越高）

alt text

0时刻（就绪队列：头 -> P1 -> 尾）：进程P1到达，上处理机行。
2时刻（就绪队列：头 -> P1 -> P2 -> 尾）：进程P2到达，此时P1还未运行结束，挂到就绪队列等待。
4时刻（就绪队列：头 -> P1 -> P2 -> P3 -> 尾）：进程P3到达，此时P1还未运行结束，挂到就绪队列等待。
5时刻（就绪队列：头 -> P1 -> P2 -> P3 -> P4 -> 尾）：进程P4到达，此时P1还未运行结束，挂到就绪队列等待。
7时刻（就绪队列：头 -> P2 -> P3 -> P4 -> 尾）：进程P1运行结束，选择优先级最高的进程P3上处理机运行。
8时刻（就绪队列：头 -> P2 -> P4 -> 尾）：进程P3运行结束，选择优先级最高的并且在就绪中靠前的P2进程上处理机运行。
12时刻（就绪队列：头 -> P4 -> 尾）：进程P2运行结束，选择优先级最高的P4进程上处理机运行。
16时刻（就绪队列：头 -> 尾）：进程P4运行结束。

各进程到达就绪队列的时间、需要的运行时间、进程优先数如下表所示。使用抢占式的优先级调度算法，分析进程运行情况。（注：优先数越大，优先级越高）

alt text

0时刻（就绪队列：头 -> P1 -> 尾）：进程P1到达，上处理机行。
2时刻（就绪队列：头 -> P1 -> P2 -> 尾）：进程P2到达，P2优先级比P1高，P2上处理就运行。
4时刻（就绪队列：头 -> P1 -> P2 -> P3 -> 尾）：进程P3到达，P3优先级比P2高，P3上处理就运行。
5时刻（就绪队列：头 -> P1 -> P2 -> P3 -> 尾）：进程P4到达，挂到就绪队列等待。进程P3运行结束，选择优先级最高的并且在就绪中靠前的P2进程上处理机运行。
7时刻（就绪队列：头 -> P1 -> P3 -> 尾）：进程P2运行结束，选择优先级最高的P3进程上处理机运行。
11时刻（就绪队列：头 -> P1 -> 尾）：进程P3运行结束，选择P1进程上处理机运行。
16时刻（就绪队列：头 -> 尾）：进程P1运行结束。

反馈队列调度算法

算法思想：对其他调度算法的这种权衡。
算法规则：

设置多级优先队列，各级队列优先级从高到低，时间片从小到大。
新进程到达时先进入第一级就绪队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级队列，则重新返回到该队列队尾。
只有第k级队列为空时，才会为k+1级队头的进程分配时间片。

是否用于作业/进程调度：用于进程调度。
优缺点：

对各类型进程相对公平（FCFS的优点）
每个新到达的进程都可以很快就得到响应（RR的优点）
短进程只用较少的时间就可完成（SPF的优点）
不必实现估计进程的运行时间（避免用户造假）
可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、I/O密集型进程（拓展：可以将因I/O而阻塞的进程重新放回原队列，这样I/O型进程就可以保持较高优先级）

是否会导致饥饿：会。

alt text