软件工程师的发展：深入理解CPU调度原理

前言

软件工程师一直习惯把OS当作可靠的操作系统。我们只将程序送到您的家中。它运行在操作系统上，但很少深入了解操作系统是如何工作的。

事实上，操作系统作为一个通用的软件系统，在大多数情况下表现都相当不错。但还是会有特殊的场景，需要我们对操作系统进行各种修改，以便业务系统能够更高效地执行任务。

这需要对操作系统原理有深入的了解，不仅要会使用管家，还要知道如何更好的配合管家。

OS是一个非常庞大的软件系统。本文主要探讨冰山一角：CPU调度原理。

说到CPU调度原理，很多人的第一反应就是基于时隙的调度，即每个进程都有一个时隙，分配CPU来运行。时隙用完后，将CPU交给其他进程。 。

至于操作系统如何判断某个时间片何时用完、如何切换到另一个进程等更深层次的原理，似乎了解的人不多。

事实上，基于时间片的调度只是众多CPU调度算法中的一种。本文从最基本的调度算法入手，一一分解不同常见调度算法的原理，让大家一起探索CPU调度的奥秘。 。

CPU上下文切换

在学习CPU调度的基本原理之前，我们首先了解一下CPU上下文切换，它是CPU调度的基础。

当今的操作系统几乎都支持远大于CPU数量的任务“同时”运行，操作系统依次分配CPU。

这需要操作系统知道在哪里加载任务以及加载后从哪里开始运行。该信息存储在CPU寄存器中，其中保存了下一条要执行的指令的地址。在特殊寄存器程序计数器（PC）上。 这个寄存器信息称为CPU上下文，也称为硬件上下文。当

OS切换正在运行的任务时，保存上一个任务的上下文，并将下一个任务的上下文加载到CPU寄存器中。这个操作称为CPU上下文切换。

CPU 环境是进程环境的一部分。我们常说的进程上下文由以下两部分组成：

• 用户级上下文：包含进程的运行时堆栈、数据块、代码块等信息。
• 系统级上下文：包含进程标识信息、进程位置信息（CPU上下文）、进程控制信息等信息。

这包括两个问题：（1）如何保存上一个任务的CPU环境？ (2)什么时候应该进行上下文切换？

问题1：如何保存上一个任务的CPU环境？ CPU环境

保存在进程内核区（内核区）中。当操作系统为每个进程分配虚拟内存空间时，也就分配了内核空间。这部分内存只能由内核代码访问。

在切换CPU环境之前，操作系统首先将当前CPU的通用寄存器、PC等进程场景信息保存到进程的内核空间中。在下一次切换时，它被取出并重新加载到CPU中以重置任务。跑步。

2。问题：环境改变什么时候实施？

如果操作系统想要进行任务上下文切换，就必须预留CPU来执行切换逻辑。然而，当用户程序运行时，CPU被用户程序占用，这意味着操作系统当前没有运行，当然无法进行环境切换。这个问题有两种解决方案，合作策略和预防策略。

合作策略依赖于用户程序主动放弃CPU，例如执行系统调用或被零除等异常。然而，这种策略并不可靠。如果用户程序主动不让出CPU，甚至制造恶意死循环，程序就会一直抢占CPU，唯一的恢复方法就是系统重启。

预防策略依赖于硬件定时器中断机制（Timer Interrupt）。在初始化期间，操作系统向硬件注册中断处理回调（Interrupt Handler）。当硬件产生中断时，硬件将CPU的处理能力转移给OS，OS可以实现CPU上下文切换来回调中断。

调度衡量指标

CPU调度算法的好坏通常通过以下两个指标来衡量：

• Lead time （从任务到达到任务完成之间的前置时间），即
• 响应时间（响应时间），是指从任务到达到任务第一次调度所经过的时间，即

这两个指标在一定程度上矛盾，要求很高。提前期不可避免地会缩短平均响应时间。具体遵循的指标与任务类型相关。例如，程序翻译任务需要较短的周转时间，并尽快完成翻译；用户交互任务要求响应时间短，以免影响用户体验。

工作负载假设

操作系统上的负载（即各种任务的运行状态）总是在不断变化的。为了更好地理解不同CPU调度算法的原理，我们首先做出以下负载假设：

• 假设1：所有任务运行相同的时间。
• 2。假设：所有任务都有相同的开始时间
• 3。假设：当任务启动时，它会一直运行直到任务完成。
• 4。假设：所有任务仅使用CPU资源（例如，不发生I/O操作）。
• 5。假设：每个任务的运行时间是预先已知的。

准备工作已经完成，现在我们进入CPU调度算法的奇妙世界。

FIFO：先进先出

FIFO（First In First Out，先进先出）调度算法以其原理简单、易于实现而闻名。 首先安排第一个任务直到结束，然后安排下一个任务，依此类推。如果多个任务同时到达，系统会随机选择一个。

在我们假设的负载条件下，FIFO 的效率很好。例如，有满足上述负载假设的三个作业 A、B、C。每个任务运行 10 秒并在时间 t=0 时到达。那么任务调度情况如下：

根据先进先出调度原则，A、B、C 分别用了 10、20、30 小时完成了任务，平均周转时间为 20 秒（ ），并且效果非常好。

然而，现实总是残酷的。如果违反假设 1，例如A的运行时间为100秒，B和C的运行时间仍为10秒，则调度情况为：时间，B和C无法长时间安排，因此平均交货时间恶化为 110 ( )。

因此，在任务运行时间相差较大的场景下，的调度策略容易导致任务饿死！

对于这个问题，如果B和C先安排一个较短的运行时间，问题就可以解决。这就是SJF调度算法背后的思想。

SJF：最短作业优先

SJF（最短作业优先，最短作业优先） 从多个到达时间相同的作业中选择运行时间最短的作业进行调度，然后调度第二短的任务。任务等等。

对于上一节的工作负载，使用SJF调度的情况如下。周转时间将为 50 秒 ( )，是 FIFO 110 秒的两倍多。

我们分手吧。而 C 在 A 之后到达，必须等待 A 运行完毕才有机会进行调度，即使 A 运行时间很长。周转时间恶化至103.33秒()，任务饥饿问题再次出现！

STCF：首次完成的最短时间

为了解决SJF的任务饥饿问题，我们需要打破假设3可以中断，可以在运行时中断。如果B和C立即到达，问题就解决了。

这是一个先发制人的时间表。原理在CPU上下文切换中提到。中断定时器到来后，操作系统完成任务A和B的上下文切换。

在协同调度SJF算法和预防性调度算法的基础上，我们发展成了STCF算法（最短完成时间优先）。调度原则： 如果运行时间较短的任务到达，则当前任务被中断，运行时间较短的任务优先。

使用STCF算法进行工作负载调度的情况如下。周转时间优化为50秒（），再次解决任务饥饿问题！

到目前为止我们只处理了前置时间指标，那么 FIFO、SJF 和 STCF 调度算法的响应时间是多少？

假设A、B、C三个任务都在t=0时刻到达，运行时间为5s。那么这三种算法的调度如下，平均响应时间为5s()：

更糟糕的是，随着任务运行时间的增加，平均响应时间也随之增加，这对于交互来说将是灾难性的任务并认真。影响用户体验。

问题的根源在于，当所有任务同时到达并且具有相同的运行时间时，最后一个任务必须等待所有其他任务完成才能开始调度。

为了优化响应时间，出现了我们熟悉的基于时间片的调度。

RR：基于时隙的查询调度

RR（Round Robin，轮转训练）算法为每个任务分配一个时隙。当任务的时隙用完时，调度程序将中止当前任务并切换到下一个任务，依此类推。

注意时间片长度设置必须是中断定时器的整数倍。例如，如果中断定时器的时长为2ms，则任务时隙可以设置为2ms、4ms、6ms……否则，即使任务时隙用完后，调度的不会发生中断。发生并且操作系统无法切换任务。

现在使用 RR 来调度并为 A、B 和 C 分配 1 秒的时隙。调度情况如下，平均响应时间为1s()：

根据RR的调度原理，我们可以发现，时隙设置越小，平均响应时间越小。然而，随着时隙的减少，任务切换的次数也会增加，这意味着上下文切换的消耗增加。

因此，设置时隙的大小是一个折中的过程。不能盲目追随响应时间而忽视CPU上下文切换带来的消耗。

CPU环境切换消耗不仅仅是保存和恢复寄存器带来的消耗。随着程序的运行，它会逐渐在CPU缓存、TLB、分支预测器和其他硬件的各个级别创建自己的缓存数据。任务切换意味着必须重新预热缓存，这会带来巨大的消耗。

另外，RR调度算法的周转时间为14s()，比FIFO、SJF和STCF的10s()差很多。

这也印证了之前所说的，周转时间和响应时间在一定程度上是相反的。如果想优化周转时间，建议使用SJF和STCF；如果想优化响应时间，建议使用RR。

I/O 操作对调度的影响

到目前为止，我们还没有考虑 I/O 操作。我们知道，当I/O操作开始时，进程并不占用CPU，而是阻塞等待I/O操作完成。

现在我们打破假设4。假设任务 A 和 B 均在时间 t=0 时到达，并且运行时间均为 50 ms，但 A 执行的 I/O 操作每 10 ms 阻塞 10 ms。 B 没有 I/O。

使用STCF进行调度时，调度情况如下：

如上图所示，任务A和B的总调度时间达到140ms，比实际全运行时间长了100ms。而且A在I/O操作过程中被阻塞，调度器不会切换到B，导致CPU空闲！

为了解决这个问题，使用RR调度算法，为任务A和B分配10ms的时隙，这样当A在I/O操作中阻塞时，B可以得到调度，B使用该时隙后，恰巧A也从I/O阻塞中返回等等，总调度时间优化为100ms。

这个调度方案是基于 5的假设，这意味着调度器需要提前知道A和B的运行时间、I/O操作时间长等信息。以充分利用CPU。

然而，实际情况比这复杂得多。每次的I/O阻塞时间不会相同，调度器无法准确知道A和B的运行信息。如果假设 5也失败，那么调度器应该如何实现才能保证最高的CPU利用率和调度合理性？

然后，我们提出了一种 CPU 调度算法，即使在违反所有负载假设的情况下也能表现良好，并且被许多现代操作系统使用，即 MLFQ。 †

从前面的分析中我们知道，为了优化前置时间，可以优先处理前置时间较短的任务（如SJF和STCF的做法）；使用类似于 RR 的基于时间片的计划来优化响应时间。然而，这两个目标似乎是矛盾的，减少响应时间必然会增加交付时间。

所以MLFQ需要解决以下两个问题：

1. 如何在事先不知道任务的运行时信息（包括运行时、I/O操作等）的情况下考虑前置时间和响应时间。 ）？
2. 我们如何从历史时间表中学习，以便在未来做出更好的决策？

任务优先级划分

MLFQ和上面介绍的众多调度算法最显着的特点是增加了一个新的优先级队列来存储不同优先级的任务，并设置了以下两条规则：

• 规则1 ：如果优先级（A）>优先级（B），则调度A
• 规则2：如果优先级（A）=优先级（B），则根据RR算法的音调

C调度A和B。优先级

MLFQ应考虑更改任务的优先级，否则根据规则1和根据上图C中的规则2，在图C之前和C的末尾，C没有机会运行，所以C的响应时间会很长。因此，可以设置以下优先级修改规则：

• 3。规则：当有新任务到达时，将其放入最高优先级队列
• 4a规则：如果任务对A进行切片一段时间而没有主动让出CPU（例如I/O操作），优先级降低一级。优先级不变

规则 3 主要认为可以对新添加的任务进行调度，避免任务中断的问题

规则 4a 和 4b 主要认为交互任务大多是短期的，经常会废弃 CPU，所以为了为了保证响应时间，必须保持现有的优先级； CPU密集型任务往往不太注重响应时间，因此优先级可能较低。

根据上述规则，当一个长时间运行的任务A到达时，调度情况如下：

如果当任务A运行在t=100时，一个短时间运行的任务B到达，那么调度情况如下：

从上面的调度情况可以看出，MLFQ具有STCF的优点，即可以优先调度短期任务，缩短前置时间。

如果任务 A 在 t=100 运行，交互任务 C 到来，调度情况如下：

MLFQ 在任务阻塞时按照优先级顺序选择其他任务运行，避免 CPU 闲置 ‿‿。因此，上图中，当任务C处于I/O阻塞状态时，任务A获得运行时切片，当任务C从I/O阻塞状态返回时，A再次被挂起，以此类推。

另外，由于任务C在时隙内主动让出CPU，因此C的优先级保持不变，有效提升了交互任务的用户体验。

CPU 密集型任务饥饿问题

到目前为止，MLFQ 似乎能够同时考虑交互式任务的周转时间和响应时间。真的很完美吗？

考虑以下场景。当任务A运行到t=100时，交互任务C和D同时到达。那么调度情况会是这样的：

可以看出，如果当前系统上交互任务较多，那么CPU密集型任务就有饥饿的可能！

为了解决这个问题，可以设置以下规则：

• 5。规则：系统运行S时间后，所有任务都按照最高优先级排队（♿优先级提升