CPU调度 Algorithms in Opera系统

CPU 调度的类型

下面介绍两种Scheduling方法：

抢先调度

在抢占式调度中，任务大多按优先级分配。有时，在运行另一个优先级较低的任务之前运行优先级较高的任务很重要，即使优先级较低的任务仍在运行。优先级较低的任务会保留一段时间，并在优先级较高的任务完成执行后恢复。

非抢占式调度

在这种调度方法中，CPU 已分配给特定进程。保持 CPU 繁忙的进程将通过切换上下文或终止来释放 CPU。这是唯一可用于各种硬件平台的方法。这是因为它不需要像抢占式调度那样的特殊硬件（例如计时器）。

何时调度是抢占式还是非抢占式？

要确定调度是抢占式的还是非抢占式的，请考虑以下四个参数：

1. 进程由运行状态切换到等待状态。
2. 具体进程由运行态转变为就绪态。
3. 从等待状态切换到就绪状态的具体过程。
4. 进程完成执行并终止。

仅满足条件 1 和 4，该调度称为非抢占式。

所有其他调度都是抢占式的。

重要的 CPU 调度术语

• 爆发时间/执行时间： 进程完成执行所需的时间。也称为运行时间。
• 到达时间： 当进程进入就绪状态时
• 完成时间： 当进程完成并退出系统时
• 多道程序设计： 可以同时存在于内存中的多个程序。
• 工作： 它是一种不需要任何用户交互的程序。
• 用户： 它是一种具有用户交互的程序。
• 过程： 它是工作和用户的参考。
• CPU/IO 突发周期： 描述在 CPU 和 I/O 活动之间交替进行的进程执行。CPU 时间通常比 I/O 时间短。

CPU 调度标准

CPU 调度算法试图最大化和最小化以下内容：

生产力

CPU 利用率：CPU 利用率是操作系统需要确保 CPU 尽可能忙碌的主要任务。其范围为 0 到 100%。但是，对于 RTOS，其范围为低级系统的 40% 和高级系统的 90%。

速率： 单位时间内完成执行的进程数称为吞吐量。因此，当 CPU 忙于执行进程时，此时正在执行工作，单位时间内完成的工作称为吞吐量。

最小化

等待的时间： 等待时间是特定进程需要在就绪队列中等待的时间。

响应时间： 这是从提交请求到产生第一个响应的时间量。

周转时间： 周转时间是执行特定进程的时间量。它是等待进入内存、在队列中等待以及在 CPU 上执行所花费的总时间的计算。进程提交到完成之间的时间段就是周转时间。

间隔计时器

定时器中断是一种与抢占密切相关的方法。当某个进程获得 CPU 分配时，可能会将定时器设置为指定的间隔。定时器中断和抢占都会强制进程在其 CPU 突发完成之前返回 CPU。

大多数多程序操作系统都使用某种形式的计时器来防止进程永远占用系统。

Dispatcher 是什么？

它是一个为进程提供 CPU 控制的模块。Dispatcher 应该很快，以便它可以在每次上下文切换时运行。Dispatch 延迟是 CPU 调度程序停止一个进程并启动另一个进程所需的时间。

调度程序执行的功能：

• 上下文切换
• 切换到用户模式
• 移动到新加载的程序中的正确位置。

CPU 调度算法的类型

主要有六种类型 进程调度算法

1. 先到先得 (FCFS)
2. 最短作业优先 (SJF) 调度
3. 最短剩余时间
4. 优先调度
5. 循环调度
6. 多级队列调度

先到先得

先来先服务是 FCFS 的全称。它是最简单、最容易的 CPU 调度算法。在这种类型的算法中，请求 CPU 的进程首先获得 CPU 分配。这种调度方法可以用 FIFO 队列来管理。

当进程进入就绪队列时，其 PCB（进程控制块）与队列尾部相连。因此，当 CPU 空闲时，应将其分配给队列开头的进程。

FCFS 方法的特点

• 它提供非抢占式和抢占式调度算法。
• 工作总是按照先到先得的原则执行
• 它易于实施和使用。
• 但是这种方式性能比较差，一般等待时间比较长。

最短剩余时间

SRT 的全称是“最短剩余时间”。它也被称为 SJF 抢占式调度。在这种方法中，进程将被分配给最接近完成的任务。这种方法可以防止较新的就绪状态进程占用较旧进程的完成时间。

SRT调度方法的特点

• 该方法主要应用于需要优先处理短作业的批处理环境。
• 在所需 CPU 时间未知的共享系统中，这不是实现它的理想方法。
• 与每个进程关联为其下一次 CPU 突发的长度。这样操作系统就可以使用这些长度，从而帮助以最短的时间调度进程。

基于优先级的调度

优先调度 是一种基于优先级的进程调度方法。在此方法中，调度程序根据优先级选择要执行的任务。

优先级调度也有助于操作系统进行优先级分配。优先级较高的进程应首先执行，而优先级相同的作业则以循环或 FCFS 方式执行。优先级可以根据内存需求、时间需求等来决定。

循环调度

循环调度是最古老、最简单的调度算法。该算法的名称来自循环调度原则，即每个人轮流获得相等份额的资源。它主要用于多任务中的调度算法。该算法方法有助于实现无饥饿执行进程。

循环调度的特点

• 循环调度是一种时钟驱动的混合模型
• 时间片应是分配给特定任务处理的最小值。然而，不同的进程可能会有所不同。
• 它是一个实时系统，能够在特定的时间限制内对事件做出响应。

最短工作优先

SJF 是（最短作业优先）的全称，是一种调度算法，其中应选择执行时间最短的进程进行下一步执行。此调度方法可以是抢占式或非抢占式的。它显著减少了等待执行的其他进程的平均等待时间。

SJF调度的特点

• 它与每项工作相关联，作为完成的时间单位。
• 在此方法中，当 CPU 可用时，将首先执行完成时间最短的下一个进程或作业。
• 它是采用非抢占式策略实现的。
• 该算法方法对于批处理很有用，因为等待作业完成并不重要。
• 它通过提供更短的作业来提高作业产量，这些作业应该首先执行，而且通常具有更短的周转时间。

多级队列调度

该算法将就绪队列分成多个单独的队列。在此方法中，进程根据其特定属性（如进程优先级、内存大小等）分配到队列。

然而，这不是一个独立的调度操作系统算法，因为它需要使用其他类型的算法来调度作业。

多级队列调度的特点

• 对于具有某些特征的进程，应该维护多个队列。
• 每个队列可能有其单独的调度算法。
• 每个队列都有优先级。

调度算法的目的

使用调度算法的原因如下：

• CPU 使用调度来提高其效率。
• 它可以帮助您在竞争进程之间分配资源。
• 通过多道程序设计可以获得CPU的最大利用率。
• 即将执行的进程处于就绪队列中。

结语

• CPU 调度是确定哪个进程将拥有 CPU 执行权而另一个进程处于暂停状态的过程。
• 在抢占式调度中，任务大多按其优先级分配。
• 在非抢占式调度方法中，CPU已分配给特定进程。
• 突发时间是进程完成执行所需的时间。它也被称为运行时间。
• CPU 利用率是操作系统需要确保 CPU 尽可能保持繁忙的主要任务。
• 单位时间内完成执行的进程数称为吞吐量。
• 等待时间是特定进程需要在就绪队列中等待的时间。
• 这是从提交请求到产生第一个响应的时间量。
• 周转时间是执行特定过程的时间量。
• 定时器中断是一种与抢占密切相关的方法。
• 调度程序是一个为进程提供 CPU 控制权的模块。
• 六种进程调度算法分别是：先来先服务（FCFS）、2）最短作业优先（SJF）调度、3）最短剩余时间、4）优先级调度、5）循环调度、6）多级队列调度。
• 在 先到先得，请求 CPU 的进程首先获得 CPU 分配。
• 在最短剩余时间内，流程将被分配给最接近完成的任务。
• 在优先级调度中，调度程序根据优先级选择要执行的任务。
• 循环调度 其工作原理是每个人轮流获得平等份额。
• 在最短作业优先原则中，应该选择执行时间最短的作业进行接下来的执行。
• 多级调度方法将就绪队列分成多个单独的队列。在该方法中，进程根据特定属性被分配到队列中。
• CPU 使用调度来提高其效率。