操作系统中的 CPU 调度算法

在本教程中，我们将学习操作系统中的 CPU 调度算法。这些算法是操作系统中的一个非常重要的话题。这是因为 CPU 调度算法构成了操作系统学科的基础和基石。

操作系统中有很多正在进行的进程。任务是进程的集合。每个任务都由操作系统执行。操作系统将任务划分为许多进程。操作系统的最终目标是完成任务。

但是任务必须遵循某些特定条件。条件是任务必须在操作系统拥有的有限资源内，在最短的时间内完成。这是 CPU 调度算法的主要动机。

CPU 调度

CPU 调度是使用 CPU 资源执行进程的过程。进程也可能由于资源缺失或不可用而等待。这些进程可以充分利用中央处理器。

当 CPU 空闲时，操作系统必须从就绪进程列表中选择一个进程。一个临时（CPU）调度器负责选择。调度器选择一个就绪的内存进程来获取 CPU。

在学习 CPU 调度算法的类型之前，我们将学习我们将要在 CPU 调度算法中遵循和使用的基本术语。

1. 进程 ID

进程 ID 是解决问题时首先要写的东西。进程 ID 就像进程的名称。它通常用数字或带有数字的 P 字母表示。

示例

通常，我们从零开始命名进程。我们也可以从数字 1 开始编号。这取决于我们。

1. 到达时间

进程进入就绪队列所需的时间，或者进程准备好由 CPU 执行的时间。这个到达时间可以简称为 AT。到达时间始终为正数或零。

2. 爆发时间

进程完成过程所需的时间段称为爆发时间。爆发时间可以简称为 BT。进程的爆发时间始终大于零。

3. 完成时间

CPU 完成进程所需总时间称为完成时间。完成时间可以简称为 CT。完成时间始终大于零。

4. 周转时间

CPU 从进程准备好执行开始，或从进程进入就绪队列开始所花费的时间称为周转时间。周转时间可以通过完成时间和到达时间来计算。周转时间可以简称为 TAT。

周转时间是完成时间和到达时间的差值。

公式

此处，CT 为完成时间，AT 为到达时间。

5. 等待时间

进程从分配进程执行开始，等待完成其过程的时间称为等待时间。等待时间可以简称为 WT。等待时间可以通过周转时间和爆发时间来计算。

等待时间是周转时间与爆发时间的差值。

公式

6. 就绪队列

在上一进程执行完毕之前，所有进程都存储在其中的队列。这个就绪队列非常重要，因为当两个相同类型的进程同时执行时，CPU 会出现混乱。

在这种情况下，就绪队列就发挥作用了，并完成了其职责。

7. 甘特图

这是存储所有已执行进程的地方。这对于计算等待时间、完成时间、周转时间非常有用。

CPU 调度算法中的模式

CPU 调度算法有两种模式。它们是

1. 抢占式方法
2. 非抢占式方法

在抢占式方法中，一旦进程开始执行，CPU 就会分配给同一个进程，直到进程完成。中央处理器不会切换进程。整个 CPU 分配给进程，并且在进程完成之前不会改变 CPU 分配。

在非抢占式方法中，一旦进程开始执行，CPU 就不会分配给同一个进程，直到进程完成。中央处理器会切换进程。仅当达到某些必要条件时，整个 CPU 才分配给进程，并且在必要条件出现中断或错误时，CPU 分配会发生更改。

CPU 调度算法的类型

• 先来先服务
• 最短作业优先
• 优先级调度
• 循环调度

先来先服务调度算法

这是第一种 CPU 调度算法。在这里，我们将学习 CPU 如何将资源分配给特定进程。

在这里，在先来先服务 CPU 调度算法中，CPU 按特定顺序分配资源给进程。顺序是串行的。CPU 分配给进程的顺序是它发生的顺序。

我们也可以说先来先服务 CPU 调度算法遵循就绪队列中的先进先出。

先来先服务可以简称为 FCFS。

FCFS（先来先服务）的特点

• 先来先服务可以采用抢占式方法或非抢占式方法执行。
• 进入就绪队列的进程首先被执行。因此，我们说 FCFS 遵循先进先出方法。
• 先来先服务仅在到达时间（AT）大于或等于当前时间时执行。

优点

• CPU 执行起来非常容易。
• 遵循 FIFO 队列方法。

缺点

• 先来先服务效率不高。
• 先来先服务遭受“队列效应”（Convoy Effect）。

示例

现在，我们将应用 FCFS（先来先服务）CPU 调度算法来解决上述问题。

在 FCFS 中，有一个例外，即到达时间不从完成时间中减去。

在这里，在先来先服务中，基本公式不起作用。只有基本公式起作用。

甘特图

平均完成时间 = 完成时间总和除以进程总数称为平均完成时间。

平均完成时间 = ( CT1 + CT2 + CT3 + . . . . . . . . . . . + CTn ) / n

平均完成时间

平均周转时间 = 周转时间总和除以进程总数称为平均周转时间。

平均周转时间 = (TAT1 + TAT2 + TAT3 + . . . . . . . . . . . + TATn ) / n

平均周转时间

平均等待时间 = 等待时间总和除以进程总数称为平均等待时间。

平均等待时间 = (WT1 + WT2 + WT3 + . . . . . . . . . . . + WTn ) / n

平均等待时间

队列效应

示例

平均完成时间是

平均 CT = ( 79 + 81 + 84 + 85 + 110 + 113 ) / 6

平均 CT = 92

平均等待时间是

平均 WT = ( 0 + 79 + 81 + 84 + 85 + 110 ) /6

平均 WT = 73.1666667

平均周转时间是

平均 TAT = ( 78 + 81 + 83 + 85 + 108 +110 ) / 6

平均 TAT = 90.833334

这里最大的问题是完成时间长、等待时间长、周转时间长、效率低。

上述解决方案中的问题可以通过使用一种新的 CPU 调度技术，即“最短作业优先”（SJF）来解决。

最短作业优先 CPU 调度算法

这是另一种 CPU 调度算法。在这里，我们将学习 CPU 如何将资源分配给特定进程。

最短作业优先很大程度上取决于爆发时间。所有 CPU 调度算法都基本取决于到达时间。在这里，在最短作业优先 CPU 调度算法中，CPU 将其资源分配给就绪队列中的进程，以及具有最小爆发时间的进程。

如果我们遇到两个进程都存在于就绪队列中且它们的爆发时间相同的情况，我们可以选择任何一个进程进行执行。在实际的操作系统中，如果我们遇到相同的问题，则会发生顺序资源分配。

最短作业优先可以简称为 SJF。

特性

• SJF（最短作业优先）的平均等待时间最短。这是因为所有耗时的进程都在最后执行。因此，出于这个原因，所有非常小的、小的进程都先执行，并防止小进程饿死。
• 它被用作执行每项活动的衡量标准。
• 如果持续生成较短的进程，可能会导致饿死。可以使用“老化”（aging）的概念来解决这个问题。
• 最短作业可以以抢占式和非抢占式方式执行。

优点

• SJF 被使用是因为它的平均等待时间比其他 CPU 调度算法短。
• SJF 可以被称为长期 CPU 调度算法。

缺点

• 饿死是 SJF（最短作业优先）CPU 调度算法的一个负面特征。
• 通常，很难预测下一个 CPU 请求需要多长时间。

最短作业优先示例

现在，我们将以抢占式和非抢占式两种方式解决这个问题。

我们将首先以非抢占式方式解决这个问题。

在非抢占式方法中，进程一直执行直到完成。

非抢占式最短作业优先 CPU 调度

甘特图

现在让我们找出平均完成时间、平均周转时间、平均等待时间。

平均完成时间

平均等待时间

平均周转时间

抢占式方法

在抢占式方法中，当找到最佳解决方案时，进程就会执行。

甘特图

P4 之后 P5 被执行，仅仅是因为抢占条件。

现在让我们找出平均完成时间、平均周转时间、平均等待时间。

平均完成时间

平均周转时间

平均等待时间

优先级 CPU 调度

这是另一种 CPU 调度算法。在这里，我们将学习 CPU 如何将资源分配给特定进程。

优先级 CPU 调度与其他 CPU 调度算法不同。在这里，每个进程都有一个特定的优先级数字。

有两种类型的优先级值。

• 最高数字被视为最高优先级值。
• 最低数字被视为最低优先级值。

预防优先级 进程的优先级决定了 CPU 调度算法如何运行，这是一种抢占式策略。由于编辑器为该方法中的每个函数分配了相等的权重，因此最关键的步骤必须首先进行。最重要的 CPU 规划算法在出现冲突时（即当有多个优先级相同的处理器时）依赖于 FCFS（先来先服务）方法。

特性

• 优先级 CPU 调度根据重要性组织任务。
• 当一个低优先级的任务正在执行，而一个高优先级的任务到达时，低优先级的任务将被高优先级的任务替换，后者将被挂起直到执行完成。
• 随着分配的数字减少，进程的优先级级别会提高。

优点

• 优先级 CPU 调度的平均等待时间比先来先服务（FCFS）短。
• 处理优先级 CPU 调度更容易。
• 它不那么复杂。

缺点

• 饿死问题是抢占式优先级 CPU 调度算法最普遍的缺陷之一。由于这个问题，进程必须等待更长的时间才能被调度到 CPU。这个问​​题被称为饿死问题或饥饿问题。

示例

现在，让我们通过优先级调度的一个例子来解释这个问题。

在这里，在此问题中，具有最高数字的优先级数字优先级最低。

这意味着 5 的优先级最低，0 的优先级最高。

解决方案

甘特图

平均完成时间

平均等待时间

平均周转时间

轮转 CPU 调度

轮转是一种 CPU 调度机制，它通过为每个任务分配一个特定的时间片来循环。它是具有抢占模式的先来先服务 CPU 调度技术。轮转 CPU 算法经常强调分时方法。

轮转 CPU 调度算法的特点包括

• 由于所有进程都获得均衡的 CPU 分配，因此它简单、易于使用且没有饿死问题。
• 最常用的 CPU 核心调度技术之一。由于进程仅被允许访问 CPU 很短的时间，因此它被视为抢占式的。

轮转 CPU 调度的优点

• 每个进程都获得相等的 CPU 时间，因此轮转看起来是公平的。
• 新创建的进程被添加到就绪队列的末尾。

示例

问题

解决方案

甘特图

平均完成时间 = 7.8

平均周转时间 = 4.8

平均等待时间 = 3

这就是操作系统中 CPU 调度算法的全部内容。