操作系统原理之调度算法 #

目录 #

FCFS 和优先级调度的区别 #

先到先服务（FCFS）：先到先服务（FCFS）是最简单的算法类型。它是一种非抢占式算法，即进程一旦开始执行就不能被打断。FCFS 是在 FIFO 队列的帮助下实现的。进程按照其到达时间的顺序被放入准备队列。首先到达的进程成为队列的首部，而其他随后到达的进程则被添加到队列的后面。在先到先服务（FCFS）算法中，先到的进程在 CPU 空闲时被首先送入 CPU 执行。这种算法的主要缺点是，平均等待时间往往相当长。这也导致了车队效应，设备或 CPU 的利用率降低，效率下降。

优先级调度算法：优先级调度算法是根据进程的优先级来执行的。每个进程被分配一个优先级，具有最高优先级的进程被首先执行。优先级可以从内部和外部定义。内部优先级由系统决定，取决于所需资源的数量、所需时间等，而外部优先级则基于工作需要的时间或为所做工作分配的权重或进程的重要性。优先级调度可以是抢占式或非抢占式。

请注意：

• 如果两个进程有相同的优先级，那么就用 FCFS 来打破平局。
• 在抢占式模式下，最高优先级进程的等待时间总是零，而在非抢占式模式下，它可能不是零。

缺点：主要问题是饥饿现象。它可能发生在进程流中，系统一直在执行高优先级的进程，而低优先级的进程从未被执行。解决这个问题的方法是老化。老化是指在一个固定的时间间隔后，逐渐增加系统中等待的进程的优先级，例如每 10 分钟增加 1 个。这将确保低优先级的进程也能随着时间的推移缓慢地被执行。

FCFS 和优先级调度算法之间的区别如下：

抢占式和非抢占式调度的区别 #

在 CPU 调度中，我们有两种类型的调度：

• 抢占式调度（Preemptive Scheduling）。在这种情况下，当一个高优先级的进程进入准备状态时，调度器可以随时抢占一个低优先级的运行进程。当调度来自于以下任何一种情况时，它就是抢占式调度：
  • 当一个进程从运行状态切换到准备状态时（例如，当一个中断发生时）。
  • 当一个进程从等待状态切换到准备状态时（例如，在完成 I/O 之后）。
• 非抢占式调度。在这种情况下，一旦一个进程进入运行状态，它就不能被抢占，直到它完成了它的分配时间。当调度只在以下情况下发生时，我们说这个调度方案是非抢占式或合作式的。
  • 当一个进程从运行状态切换到等待状态时（例如，由于 I/O 请求或调用 wait () 终止一个子进程的结果）。
  • 当一个进程终止时。

让我们看看抢占式调度和非抢占式调度的区别：

不能肯定地说抢占式调度比非抢占式调度更好，反之亦然。这取决于如何调度以使进程的平均等待时间最小化和 CPU 利用率最大化。

中周转时间（TAT）和等待时间（WT）的区别 #

在 CPU 调度中，我们经常需要在到达时间、突发时间和完成时间的帮助下找到平均周转时间和等待时间。让我们来简单了解一下它们。

• 周转时间（TAT，Turnaround Time）：它是指从提交进程到完成进程所需的时间间隔。完成时间和到达时间之间的差异被称为周转时间。即 TAT = CT - AT 。
• 完成时间（CT，Completion Time）：这是进程完成其执行的时间。
• 到达时间（AT，Arrival Time）：这是进程到达准备状态的时间。
• 等待时间（WT，Waiting Time）：进程在准备队列中等待获得 CPU 的时间。Turnaround Time 和 Burst Time 之间的时间差被称为等待时间。即 WT = TAT - BT 。
• 突发时间（BT，Burst Time）：这是进程执行所需的时间。

现在有了等待时间和突发时间，我们还可以通过以下方式计算周转时间： TAT = BT + WT 。

LJF 和 LRJF 调度的区别 #

最长作业优先（LJF）：它是 CPU 调度算法，具有最大突发时间的进程首先被执行。一旦进程进入准备队列，该进程只有在执行完成后才退出，因此它是一个非抢占式的进程。在进程的突发时间相同的情况下，选择总体时间最低的工作。这种 CPU 调度算法导致了系统的低吞吐量。

最长剩余作业优先（LRJF）：它是最长作业优先的 CPU 调度算法的抢占式版本。每秒钟都会选择进程的突发时间最长的工作。如果进程的突发时间相同，则选择总体到达时间较短的工作。由于同时检查进程的剩余 Burst Time，所以会出现饥饿现象。这也被称为 "最长剩余时间优先"（Longest Remaining Time First）算法。

LJF 和 LRJF CPU 调度算法的区别:

SJF 和 SRJF 调度的区别 #

最短作业优先（SJF）：最短作业优先（SJF）是一种调度策略，它选择具有最小执行时间的等待进程来执行下一个作业。它也被称为最短作业优先（SJN，Shortest Job Next）或最短进程优先（SPN，Shortest Process Next）。它是一种非抢占式的调度算法。

最短剩余作业优先（SRTF）：最短剩余作业优先（SRJF）是 SJF 调度的抢占性版本。在这种调度算法中，选择完成前剩余时间最小的进程来执行。具有相同到达时间的进程将把 SRTF 转换为 SJF。

相似性：

• SJF 和 SRJF 实际上都是不可行的，因为不可能预测进程的突发时间。
• SJF 和 SRJF 都可能导致进程饿死，因为如果短的进程不断增加，长的进程可能会被无限期地搁置。
• 一旦所有的进程都在就绪队列中，SJF 和 SRJF 都被认为是相同的。这是因为在进程被添加到就绪队列中后，不会进行抢占。

差异：

FCFS 和 SJF 调度的区别 #

先到先服务（FCFS）和最短作业优先（SJF）调度算法的区别如下：

优先级调度和 RR 调度的区别 #

优先级调度和 Round-Robin（RR）调度算法的区别如下：

EDF 和 LST 调度的区别 #

最早期限优先（EDF） #

在最早期限优先（Earliest Deadline First ）的调度算法中，在每个调度点，具有最短期限的任务被安排执行。它是一种用于实时系统的最佳动态优先级驱动（dynamic priority-driven）的调度算法。它使用任务的优先级来进行调度。在 EDF 中，任务的优先级是根据绝对最后期限分配（absolute deadline）的。具有最短期限的任务得到最高的优先权。

例子：假设这里有两个进程 P1 和 P2。设 P1 的周期（period）为 p1=50；设 P1 的处理时间为 t1=25。设 P2 的周期为 p2=75；让 P2 的处理时间为 t2=30。

解释:

• P1 的最后期限较早，所以 P1 的优先级高于 P2。
• 最初 P1 运行并完成了 25 次的执行。
• 25 次之后，P2 开始执行，直到 50 次，此时 P1 能够执行。
• 现在，比较（P1，P2）=（100，75）的期限，P2 继续执行。
• P2 在时间 55 完成其处理。
• P1 开始执行，直到时间 75，此时 P2 能够执行。
• 现在，再次比较（P1，P2）=（100，150）的期限，P1 继续执行。
• 重复上面的步骤。
• 最后在时间 150，P1 和 P2 都有相同的最后期限，所以 P2 将继续执行，直到其处理时间，之后 P1 开始执行。

最小松弛时间（LST） #

在最小松弛时间（Least Slack Time）调度算法中，在每个调度点，具有最小松弛（minimum laxity）的任务被首先执行。它也是一种用于实时系统的动态优先级驱动的调度算法。它根据系统中所有任务的松弛时间给它们分配一些优先级。拥有最少松弛时间（宽松度）的任务获得最高的优先权。

例子：

• 进程 P1。到达时间 = 0，持续时间 = 10，最后期限 = 33
• 进程 P2。到达时间 = 4，持续时间 = 3，最后期限 = 28
• 进程 P3。到达时间 = 5，持续时间 = 10，最后期限 = 29

解释:

• 在时间 t=0 时：只有进程 P1 已经到达。P1 被执行到时间 t=4。
• 在时间 t=4 时：P2 已经到达。P1 的松弛时间：33-4-6=23；P2 的松弛时间：28-4-3=21。因此 P2 开始执行，直到时间 t=5 时 P3 到达。
• 在时间 t=5 时：P1 的松弛时间：33-5-6=22；P2 的松弛时间：28-5-2=21；P3 的松弛时间：29-5-10=12。因此 P3 开始执行，直到时间 t=13
• 在时间 t=13 时：P1 的松弛时间：33-13-6=14；P2 的松弛时间：28-13-2=13；P3 的松弛时间：29-13-2=14。因此，P2 开始执行，直到时间 t=15
• 在时间 t=15 时：P1 的松弛时间：33-15-6=12；P3 的松弛时间：29-15-2=12；因此 P3 开始执行，直到时间 t=16。
• 在时间 t=16 时：P1 的松弛时间：33-16-6=11；P3 的松弛时间：29-16-=12。因此，P1 开始执行，直到时间 t=18，以此类推。

EDF 和 LST 调度算法的区别:

优先级调度和 SJF 的区别 #

最短作业优先（SJF）和优先调度算法的区别如下：

FCFS 和 RR 调度的区别 #

先到先服务（FCFS）和循环（RR）调度算法的区别如下：

SJF 和 RR 调度的区别 #

最短作业优先（SJF）和循环（RR）调度算法的区别如下：

SRTF 和 LRTF #

最短剩余作业优先（SRJF，SRTF，Shortest remaining job first ）：最短剩余作业优先也叫最短剩余时间优先，是最短作业优先调度算法的抢占式版本。在最短剩余作业优先中，具有最小的运行时间（即剩余时间）的进程被安排在下一个运行，在 SRJF 中，如果一个新的进程到达 CPU 调度器，需要更少的突发时间来执行，一个正在运行的进程将被抢占。

最长剩余作业优先（LRJF，LRTF，Longest remaining job）：最长剩余工作优先也叫最长剩余时间优先，与 SRJF 完全相反。在这种类型的 CPU 调度中，具有最长处理时间的进程被安排在下一个运行，如果一个具有更长突发时间的新进程进入队列，正在运行的进程将被抢占。

差异表:

MLQ 和 MLFQ 区别 #

在多进程环境中，经常发生不止一个进程同时竞争 CPU 资源的情况。如果只有一个 CPU 可用，就必须在下一个运行的进程之间做出选择。操作系统中负责选择进程的部分被称为调度器，它使用的算法被称为调度算法。

多任务（multi programming）的目的是使 CPU 的利用率最大化。像周转时间、响应时间、等待时间、吞吐量这样的标准被建议在此基础上对调度算法进行判断。有许多 CPU 调度算法，其中两个是：

• 多级队列调度
• 多级反馈队列调度

多级队列（MLQ）和多级反馈队列（MLFQ）CPU 调度算法之间的区别：

长期和短期调度的区别 #

长期调度器（Long-Term Scheduler）也被称为工作调度器（Job Scheduler）。长期调度器负责管理被选入系统进行处理的程序。在这个过程中，程序被设置在队列中，并根据要求选择最好的一个工作，并从工作池中获取进程。它规定了多任务的程度（DOM，Degree of Multi-programming）。短期调度器（Short-Term Scheduler）也被称为 CPU 调度器（CPU Scheduler）。短期调度器确保哪个程序是适合或的优先级足够被处理。它调节较少的 DOM。

长期和短期调度器之间的区别：

SJF 和 LJF 的区别 #

CPU 和 GPU 的区别 #

中央处理单元（CPU，Central Processing Unit ）：中央处理器被称为每个集成系统的大脑。中央处理器包括算术逻辑单元（ALU，arithmetic logic unit），用于快速存储信息和进行计算，控制单元（CU，Control Unit）用于执行指令排序和代码分支。CPU 与更多的计算机组件互动，如内存、输入和输出，以执行指令（performing instruction）。

图形处理单元（GPU，Graphics Processing Unit）：GPU 用于提供计算机游戏中的图像计算和渲染。GPU 的速度比 CPU 的速度快，它强调高吞吐量（high throughput）。它通常与电子设备结合在一起，与电子设备（electronic equipment）共享 RAM，这对最重要的计算任务来说是很好的。它比 CPU 包含更多的 ALU 单元。

CPU 和 GPU 之间的基本区别是，CPU 强调的是低延迟。而 GPU 则强调高吞吐量。

让我们来看看 CPU 和 GPU 之间的区别：

抢占式和合作式多任务的区别 #

多任务是指在一段时期内同时执行多个任务或进程的方法。抢占式和合作式多任务是多任务的两种类型。

在抢占式多任务（preemptive multitasking）中，操作系统可以启动从运行中的进程到另一个进程的上下文切换。换句话说，操作系统允许停止当前运行进程的执行，并将 CPU 分配给其他进程。操作系统使用一些标准来决定一个进程应该执行多长时间才允许另一个进程使用 CPU 资源。从一个进程手中夺取操作系统的控制权并将其交给另一个进程的机制被称为抢占或预占（preempting or preemption）。

在合作式多任务（cooperative multitasking）中，操作系统从不启动从运行中的进程到另一个进程的上下文切换。只有当进程定期自愿让出控制权，或在空闲或逻辑上受阻（logically blocked）时才会发生上下文切换，以允许多个应用程序同时执行。另外，在这种多任务处理中，所有的进程都要合作以使调度方案发挥作用。

让我们看看抢占式多任务和合作式多任务之间的区别：

CPU 调度标准 #

不同的 CPU 调度算法有不同的特性，对特定算法的选择取决于各种因素。许多标准已经被建议用于比较 CPU 调度算法：

这些标准包括以下几个方面：

• CPU 的利用率。任何 CPU 调度算法的主要目标都是使 CPU 尽可能的繁忙。理论上，CPU 的利用率可以从 0 到 100，但在一个实时系统中，它从 40% 到 90% 不等，取决于系统的负载。
• 吞吐量（Throughput）：衡量 CPU 所做工作的一个标准是每单位时间内被执行和完成的进程数量。这就是所谓的吞吐量。吞吐量可能根据进程的长度或持续时间而变化。
• 周转时间（Turnaround time）。对于一个特定的进程，一个重要的标准是执行该进程需要多长时间。从提交一个进程到完成的时间被称为周转时间。周转时间是等待进入内存、在准备队列中等待、在 CPU 中执行和等待 I/O 的时间之和。周转时间 = 编译时间 - 到达时间（Turn Around Time = Compilation Time – Arrival Time）。
• 等待时间（Waiting time）。调度算法并不影响进程开始执行后完成所需的时间。它只影响进程的等待时间，即进程在准备队列中等待的时间。等待时间 = 周转时间 - 突发时间（Waiting Time = Turnaround Time – Burst Time）。
• 响应时间（Response time）。在一个交互式系统中，周转时间不是最好的标准。一个进程可能会相当早地产生一些输出，并在将以前的结果输出给用户之后继续计算新的结果。因此，另一个标准是从提交请求的过程到产生第一个响应的时间。这个衡量标准被称为响应时间。响应时间 = CPU 分配时间（当 CPU 首次分配）- 到达时间（Response Time = CPU Allocation Time (when the CPU was allocated for the first) – Arrival Time）。
• 完成时间（Completion time）。这是该进程完成执行的时间。

CPU 调度中的时间切片 #

CPU 的内核并不简单地将我们 PC 的全部资源分配给单个进程或服务。CPU 不断地运行许多进程，这些进程对它的运行至关重要，因此我们的内核需要毫不延迟地管理这些进程。当程序需要运行时，必须为其创建进程。这个进程需要拥有重要的资源，如 RAM 和 CPU。内核为 CPU 安排时间片（time slice），以执行进程中的命令和指令。尽管如此，只有一个 CPU 和众多进程。

CPU 是如何做到无延迟地执行不同的进程的呢？它是通过一个一个地按时间片来执行进程的。时间片是分配给 CPU 执行进程的短暂时间帧（time frame）。

时间片 #

它是在抢占式多任务 CPU 中分配给进程运行的时间帧。调度器在每一个时间片上运行每个进程。每个时间片的周期（period）是非常重要的，对平衡 CPU 的性能（performance）和响应性（responsiveness）至关重要。如果时间片很短，调度器将花费更多的处理时间；相反，如果时间片太长，调度器将再次花费更多的处理时间。

当进程被分配到 CPU 时，时钟定时器（clock timer）被设置为对应的时间片：

• 如果进程在时间片之前完成突发（burst），CPU 就像传统的 FCFS 一样简单地将其换出。
• 如果时间片先结束，CPU 就把它移到正在进行的队列的后面。

正在进行的队列（ongoing queue）是像循环队列（circular queue）一样管理的，所以，在所有进程被执行一次后，调度器会再次执行第一个进程，然后是第二个，依此类推。

参考 #

• 更多调度算法参见：Deadline Monotonic CPU Scheduling