【操作系统】进程调度-阿南达文事网

【操作系统】进程调度

一、调度时机

在进程的⽣命周期中，当进程从⼀个运⾏状态到另外⼀状态变化的时候，其实会触发⼀次调度。
⽐如，以下状态的变化都会触发操作系统的调度：

从就绪态 -> 运⾏态：当进程被创建时，会进⼊到就绪队列，操作系统会从就绪队列选择⼀个进程运⾏；
从运行态 -> 阻塞态：当进程发⽣ I/O 事件⽽阻塞时，操作系统必须另外⼀个进程运⾏；
从运行态 -> 结束态：当进程退出结束后，操作系统得从就绪队列选择另外⼀个进程运⾏；

因为，这些状态变化的时候，操作系统需要考虑是否要让新的进程给 CPU 运⾏，或者是否让当前进程从CPU 上退出来⽽换另⼀个进程运⾏。

另外，如果硬件时钟提供某个频率的周期性中断，那么可以根据如何处理时钟中断
，把调度算法分为两类：

⾮抢占式调度算法：挑选⼀个进程，然后让该进程运⾏直到被阻塞，或者直到该进程退出，才会调⽤另外⼀个进程，也就是说不会理时钟中断这个事情。
抢占式调度算法：挑选⼀个进程，然后让该进程只运⾏某段时间，如果在该时段结束时，该进程仍然在运⾏时，则会把它挂起，接着调度程序从就绪队列挑选另外⼀个进程。这种抢占式调度处理，需要在时间间隔的末端发⽣时钟中断，以便把 CPU 控制返回给调度程序进⾏调度，也就是常说的时间⽚机制。

二、调度原则

CPU 利⽤率：调度程序应确保 CPU 是始终匆忙的状态，这可提⾼ CPU 的利⽤率；
系统吞吐量：吞吐量表示的是单位时间内 CPU 完成进程的数量，⻓作业的进程会占⽤较⻓的 CPU 资源，因此会降低吞吐量，相反，短作业的进程会提升系统吞吐量；
周转时间：周转时间是进程运⾏和阻塞时间总和，⼀个进程的周转时间越⼩越好；
等待时间：这个等待时间不是阻塞状态的时间，⽽是进程处于就绪队列的时间，等待的时间越⻓，⽤户越不满意；
响应时间：⽤户提交请求到系统第⼀次产⽣响应所花费的时间，在交互式系统中，响应时间是衡量调度算法好坏的主要标准。

说⽩了，这么多调度原则，⽬的就是要使得进程要「快」。

三、调度算法

1、先来先服务调度算法

最简单的⼀个调度算法，就是⾮抢占式的先来先服务（First Come First Seved, FCFS）算法了。

顾名思义，先来后到，每次从就绪队列选择最先进⼊队列的进程，然后⼀直运⾏，直到进程退出或被阻塞，才会继续从队列中选择第⼀个进程接着运⾏。

这似乎很公平，但是当⼀个⻓作业先运⾏了，那么后⾯的短作业等待的时间就会很⻓，不利于短作业。FCFS 对⻓作业有利，适⽤于 CPU 繁忙型作业的系统，⽽不适⽤于 I/O 繁忙型作业的系统。

2、最短作业优先调度算法

最短作业优先（Shortest Job First, SJF）调度算法同样也是顾名思义，它会优先选择运⾏时间最短的进程来运⾏，这有助于提⾼系统的吞吐量。

这显然对⻓作业不利，很容易造成⼀种极端现象。

⽐如，⼀个⻓作业在就绪队列等待运⾏，⽽这个就绪队列有⾮常多的短作业，那么就会使得⻓作业不断的往后推，周转时间变⻓，致使⻓作业⻓期不会被运⾏。

3、高响应比优先调度算法

高响应比优先（Highest Response Ratio Next, HRRN）调度算法主要是权衡了短作业和长作业。

每次进⾏进程调度时，先计算「响应⽐优先级」，然后把「响应比优先级」最⾼的进程投⼊运⾏，「响应⽐优先级」的计算公式：

从上⾯的公式，可以发现：

如果两个进程的「等待时间」相同时，「要求的服务时间」越短，「响应⽐」就越⾼，这样短作业的进程容易被选中运⾏；
如果两个进程「要求的服务时间」相同时，「等待时间」越⻓，「响应⽐」就越⾼，这就兼顾到了⻓作业进程，因为进程的响应⽐可以随时间等待的增加⽽提⾼，当其等待时间⾜够⻓时，其响应⽐便可以升到很⾼，从⽽获得运⾏的机会；

举个不好听但是容易理解的例子：

比如我们在大商场上厕所，等待上厕所的时间就是等待时间，要求服务时间就是我们如厕的时长，哈哈哈哈。

4、时间片轮转调度算法

每个进程被分配⼀个时间段，称为时间⽚（Quantum），即允许该进程在该时间段中运⾏。

如果时间⽚⽤完，进程还在运⾏，那么将会把此进程从 CPU 释放出来，并把 CPU 分配给另外⼀个进程；
如果该进程在时间⽚结束前阻塞或结束，则 CPU ⽴即进⾏切换；

另外，时间⽚的⻓度就是⼀个很关键的点：

如果时间⽚设得太短会导致过多的进程上下⽂切换，降低了 CPU 效率；
如果设得太⻓⼜可能引起对短作业进程的响应时间变⻓。

⼀般来说，时间⽚设为 20ms~50ms 通常是⼀个⽐较合理的折中值。

5、最高优先级调度算法

前⾯的「时间⽚轮转算法」做了个假设，即让所有的进程同等重要，也不偏袒谁，⼤家的运⾏时间都⼀样。

但是，对于多⽤户计算机系统就有不同的看法了，它们希望调度是有优先级的，即希望调度程序能从就绪队列中选择最⾼优先级的进程进⾏运⾏，这称为最⾼优先级（Highest Priority First，HPF）调度算法。

进程的优先级可以分为，静态优先级和动态优先级：

静态优先级：创建进程时候，就已经确定了优先级了，然后整个运⾏时间优先级都不会变化；
动态优先级：根据进程的动态变化调整优先级，⽐如如果进程运⾏时间增加，则降低其优先级，如果进程等待时间（就绪队列的等待时间）增加，则升⾼其优先级，也就是随着时间的推移增加等待进程的优先级。

该算法也有两种处理优先级⾼的⽅法，⾮抢占式和抢占式：

⾮抢占式：当就绪队列中出现优先级⾼的进程，运⾏完当前进程，再选择优先级⾼的进程。
抢占式：当就绪队列中出现优先级⾼的进程，当前进程挂起，调度优先级⾼的进程运⾏。

但是依然有缺点，可能会导致低优先级的进程永远不会运⾏。

6、多级反馈队列调度算法

多级反馈队列（Multilevel Feedback Queue）调度算法是「时间⽚轮转算法」和「最⾼优先级算法」的综合和发展。

「多级」表示有多个队列，每个队列优先级从⾼到低，同时优先级越⾼时间⽚越短
「反馈」表示如果有新的进程加⼊优先级⾼的队列时，⽴刻停⽌当前正在运⾏的进程，转⽽去运⾏优先级⾼的队列；

工作流程：

设置了多个队列，赋予每个队列不同的优先级，每个队列优先级从⾼到低，同时优先级越⾼，时间⽚越短；
新的进程会被放⼊到第⼀级队列的末尾，按先来先服务的原则排队等待被调度，如果在第⼀级队列规定的时间⽚没运⾏完成，则将其转⼊到第⼆级队列的末尾，以此类推，直⾄完成；
当较⾼优先级的队列为空，才会调度较低优先级的队列中的进程运⾏。如果进程运⾏时，有新进程进⼊较⾼优先级的队列，则停⽌当前运⾏的进程并将其移⼊到原队列末尾，接着让较⾼优先级的进程运行；

可以发现，对于短作业可能可以在第⼀级队列很快被处理完。对于⻓作业，如果在第⼀级队列处理不完，可以移⼊下次队列等待被执⾏，虽然等待的时间变⻓了，但是运⾏时间也变更⻓了，所以该算法很好的兼顾了⻓短作业，同时有较好的响应时间。

整理自小林coding所著的《图解系统》，仅做学习用，侵删

【操作系统】进程调度