进程调度算法详解

创作时间:

作者:

@小白创作中心

进程调度算法详解

引用

CSDN

https://blog.csdn.net/icefast/article/details/145754543

进程调度算法

这里首先要提及衡量进程调度算法的指标，毕竟很多算法的出现都与这些指标的需求息息相关

调度指标

1. 周转时间（Turnaround Time, TAT）

定义：一个进程从提交（Arrival）到完成（Completion）所经历的时间。
计算方式： Turnaround Time=Completion Time−Arrival Time\text{Turnaround Time} = \text{Completion Time} - \text{Arrival Time}Turnaround Time=Completion Time−Arrival Time
目标：希望尽可能小，让进程尽快完成。

2. 响应时间（Response Time, RT）

定义：一个进程提交后（Arrival），直到首次被 CPU 调度执行（First Run）之间的时间。
计算方式： Response Time=First Run Time−Arrival Time\text{Response Time} = \text{First Run Time} - \text{Arrival Time}Response Time=First Run Time−Arrival Time
目标：希望尽可能小，让进程尽快得到响应（特别适用于交互式系统）。

3. 等待时间（Waiting Time, WT）

定义：进程在就绪队列（Ready Queue）中等待 CPU 的时间总和（不包括执行时间）。
计算方式： Waiting Time=Turnaround Time−Burst Time\text{Waiting Time} = \text{Turnaround Time} - \text{Burst Time}Waiting Time=Turnaround Time−Burst Time 其中Burst Time是进程真正需要的 CPU 执行时间。
目标：希望尽可能小，减少 CPU 资源的浪费，提高吞吐量。

4. 吞吐量（Throughput）

定义：单位时间内 CPU 处理的进程数量。
计算方式： Throughput=完成的进程数总时间\text{Throughput} = \frac{\text{完成的进程数}}{\text{总时间}}Throughput=总时间完成的进程数
目标：希望尽可能大，提高系统整体效率。

5. CPU 利用率（CPU Utilization）

定义：CPU 实际用于执行进程的时间占总时间的比例。
计算方式： CPU Utilization=CPU 执行时间总时间×100%\text{CPU Utilization} = \frac{\text{CPU 执行时间}}{\text{总时间}} \times 100%CPU Utilization=总时间CPU 执行时间×100%
目标：希望尽可能高，但通常不会达到 100%，否则可能会导致过载。

调度算法

1.FIFO

该算法如其名，first in first out，与队列的先进先出一样，先提交的进程优先进行调度，执行完一个再调度下一个。
当进程的执行时间都很短时，FIFO的平均周转时间表现很好
但是当先提交的进程的执行时间很长时，FIFO的平均周转时间表现很差，因为长任务会阻塞住短任务
而不论什么情况，FIFO的平均响应时间表现都很差，因为该算法要求一个进程完成后才能调度下一个

2.SJF（Shortest Job First）

SJF算法优先调度执行时间最短的进程，这样就能改善平均周转时间的表现，但是平均响应时间依然表现很差，而且最重要的问题是操作系统如何得知哪个进程的执行时间最短，以及如何保证执行时间长的进程不挨饿
解决问题：
1.操作系统往往使用预测算法来估算任务的执行时间，但往往这种估算不太准确
2.只使用SJF本体难以保证长任务不挨饿，必须结合其他策略和算法如多级反馈调节，老化等等
两种变体
1.非抢占式SJF
此变体在有新任务提交时，不会抢占原有正在执行的任务
但是这种算法如果有更短时间的任务提交，可能会降低平均周转时间和平均响应时间
但是这种算法仍然无法保证长任务不挨饿
2.抢占式SJF（又名SRTF，Shortest Remaining Time First）（还叫STCF Shortest Time-to-Completion First）
此变体在有新任务提交时，会比较新任务和正在进行的任务的剩余完成时间，哪个短就调度谁。
这种算法在有频繁更短新任务提交的时候，可能会一直由新任务抢占旧任务，从而使得任务难以完成，使得平均周转时间表现变差，而且抢占引起的上下文切换也会带来时间开销，使得吞吐量降低，并且长任务挨饿的问题依旧得不到解决

3.RR(Round Robin)时间片轮转

为了解决响应时间的问题，又发明出了RR算法，设置时间片长度，每个时间片轮转（在循环队列中 FIFO）调度不同的任务，
这样可以保证每个任务的响应时间短，但是平均周转时间会大打折扣
这种算法特别适合响应式的软件，如果用以上其他算法，导致一个任务长时间得不到相应，那就很难受
但是任务的频繁切换会导致上下文的切换的开销，故此种算法完成任务的时间一般要比非抢占式的算法更久
如果时间片设置得过短，那么上下文切换的时间可能等同于或超过任务的执行时间
如果时间片设置得过长，那么该算法可能趋向变成FIFO算法，导致响应时间降低
故折中一下，一般将时间片设置为CPU Burst（进程在 CPU 上连续运行的一段时间，直到发生 I/O 或被调度切换）的80%

4.多级反馈队列（MLFQ）

为了平衡周转时间，响应时间和吞吐量，多级反馈队列算法出现了。
多级反馈队列设置了多个优先级队列，若是当前任务的运行时间超出了当前优先级限定的时间片，就会将其降级，这样短任务就会快速完成，而长任务也会随着执行时间增长而降低优先级，且高优先级任务可以随时抢占低优先级任务，但是当运行久了之后，长任务岂不是会挨饿，于是MLFQ在一段时间之后会重置优先级，以便长任务不会挨饿
但是若是任务执行一段时间就进行I/O阻塞住，且每次执行的时间都不超出当前优先级队列限定的时间片，岂不是会一直留在高优先级队列，”欺骗“过了算法
为了解决这一问题，多级反馈队列被如此改进：
当前任务的总执行时间超出了当前优先级队列限定的时间片，就降低优先级
那么又有一个问题，在重置优先级之前，难道低优先级队列中的任务就没有机会被执行了吗？
那肯定是不会的，低优先级队列中的任务在以下情况下有机会被执行：
高优先级队列为空，或高优先级任务阻塞后队列为空，或低优先级任务时间片没有被用完
此时低优先级任务可以正常执行，但是可以随时被高优先级队列中的任务抢占
优先级重置策略
1.全局重置
每隔一段时间重置所有任务的优先级
使得所有任务都有机会执行
2.Aging（老化）
任务在等待队列中停留的时间越长，它的优先级就越高
防止单一任务挨饿