操作系统中的CPU调度算法

CPU调度的类型

有两种调度方法

抢占式调度

在抢占式调度中，任务通常会分配其优先级。有时，即使较低优先级的任务仍在运行，也必须先运行较高优先级的任务。较低优先级的任务会暂停一段时间，并在较高优先级的任务完成执行后恢复。

非抢占式调度

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

何时调度为抢占式或非抢占式？

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

1. 进程从运行状态切换到等待状态。
2. 特定进程从运行状态切换到就绪状态。
3. 特定进程从等待状态切换到就绪状态。
4. 进程完成执行并终止。

只有情况1和4适用时，调度才称为非抢占式。

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

重要的CPU调度术语

• CPU爆发/执行时间：进程完成执行所需的时间。也称为运行时间。
• 到达时间：进程进入就绪状态的时间
• 完成时间：进程完成并退出系统的时间
• 多道程序设计：同时可以驻留在内存中的程序数量。
• 作业：一种没有任何用户交互的程序。
• 用户：一种具有用户交互的程序。
• 进程：这是用于作业和用户的引用。
• CPU/IO爆发周期：进程执行的特征，在CPU和I/O活动之间交替。CPU时间通常比I/O时间短。

CPU调度标准

CPU调度算法试图最大化和最小化以下各项

最大化

CPU利用率：CPU利用率是操作系统需要确保CPU尽可能繁忙的主要任务。它可以从0到100％。但是，对于RTOS，它可以从低级别的40％到高级别的90％。

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

最小化

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

响应时间：从提交请求到生成第一个响应的时间。

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

间隔定时器

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

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

什么是调度程序？

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

调度程序执行的功能

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

CPU调度算法的类型

主要有六种进程调度算法

1. 先来先服务（FCFS）
2. 最短作业优先（SJF）调度
3. 最短剩余时间
4. 优先级调度
5. 轮转调度
6. 多级队列调度

先来先服务

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

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

FCFS方法的特点

• 它提供非抢占式和抢占式调度算法。
• 作业总是按先到先服务的顺序执行
• 易于实现和使用。
• 然而，此方法的性能较差，并且一般等待时间相当长。

最短剩余时间

SRT的全称是Shortest remaining time（最短剩余时间）。它也称为SJF抢占式调度。在此方法中，将进程分配给最接近完成的任务。此方法可防止新进入就绪状态的进程延迟旧进程的完成。

SRT调度方法的特点

• 此方法主要用于批处理环境中，其中需要优先处理短作业。
• 这不是一个理想的实现共享系统的方法，因为其中所需的CPU时间是未知的。
• 将每个进程与其下一次CPU爆发的长度相关联。这样，操作系统就可以利用这些长度，帮助调度具有最短可能时间的进程。

基于优先级的调度

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

优先级调度也有助于操作系统进行优先级分配。应首先执行优先级较高的进程，而具有相同优先级的作业则按轮转或FCFS顺序执行。优先级可以基于内存需求、时间需求等来决定。

轮转调度

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

轮转调度的特点

• 轮转是一种由时钟驱动的混合模型
• 时间片应尽可能短，它分配给特定任务进行处理。但是，对于不同的进程，它可能会有所不同。
• 它是一个实时系统，在特定时间限制内响应事件。

最短作业优先

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

SJF调度的特点

• 它与每个作业相关联，作为一个完成的时间单位。
• 在此方法中，当CPU可用时，将首先执行具有最短完成时间的下一个进程或作业。
• 它使用非抢占式策略实现。
• 这种算法方法适用于批处理类型，在这种类型中，等待作业完成并不重要。
• 它通过提供较短的作业来提高作业吞吐量，这些作业应首先执行，这些作业通常具有较短的周转时间。

多级队列调度

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

但是，它不是独立的调度OS算法，因为它需要使用其他类型的算法来调度作业。

多级队列调度的特点

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

调度算法的目的

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

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

摘要

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