操作系统原理之 CPU 调度 #

目录 #

CPU 调度 #

对进程 / 工作进行调度是为了按时完成工作。CPU 调度是允许一个进程在另一个进程由于 I / O 等任何资源的不可用而被延迟（处于待机状态）时使用 CPU，从而充分利用 CPU 的过程。CPU 调度的目的是为了使系统更有效、更快速、更公平。

每当 CPU 变得空闲时，操作系统必须选择一个准备启动的进程。选择过程是由一个临时（CPU）调度器完成的。调度器在准备启动的内存进程（memory processes）之间进行选择，并将 CPU 分配给其中一个。

什么是进程？ #

在计算中，进程是一个计算机程序的实例（instance），由一个或多个线程执行。它包含程序代码和它的活动。根据操作系统（OS）的不同，一个进程可能是由多个执行线程（threads of execution）组成的，它们同时执行指令。

进程存储器如何用于高效运行？ #

进程存储器被分为四个部分以实现高效运行：

• 文本类（text category）由集成的程序代码组成，在程序启动时从固定存储器（fixed storage）中读取。
• 数据类（data class）由全局变量和静态变量组成，在主动作（main action）之前分布和执行。
• 堆（heap）用于灵活的、或动态的内存分配，通过调用 new、delete、malloc、free 等来管理。
• 栈（stack）用于局部变量。堆栈中的空间在公布时被保留给局部变量。

什么是进程调度？ #

进程调度（Process Scheduling）是进程管理器（process manager）处理从 CPU 中移除一个活动进程并根据特定策略选择另一个进程的过程。

进程调度是多程序应用（Multi-programming）的一个组成部分。这样的操作系统允许一次加载一个以上的进程到可用的内存中，加载的共享 CPU 进程使用重复的时间。

有三种类型的进程调度器：

• 长期的或工作调度器（Long term or Job Scheduler）
• 短期或 CPU 调度器（Short term or CPU Scheduler）
• 中期调度器（Medium-term Scheduler）

为什么我们需要对进程进行调度？ #

调度（Scheduling）在许多不同的计算机环境中都很重要。其中一个最重要的领域是调度哪些程序将在 CPU 上工作。这项任务是由计算机的操作系统（OS）处理的，我们可以选择许多不同的方式来配置程序。

进程调度允许操作系统为每个进程分配 CPU 时间。使用进程调度系统的另一个重要原因是，它可以使 CPU 一直处于忙碌状态（busy at all times）。这可以使你获得更少的程序响应时间。

考虑到可能有数百个程序需要工作，操作系统必须启动程序，停止程序，切换到另一个程序，等等。操作系统配置另一个进程在 CPU 中运行的方式被称为 "上下文切换"（context switching）。如果操作系统不断地将程序在所提供的 CPU 中进行上下文切换，就会给用户一个感觉，即他可以同时运行任何他想运行的程序。

因此，现在我们知道我们可以在一个给定的 CPU 上运行 1 个程序，而且我们知道我们可以改变操作系统并使用上下文切换删除另一个程序，那么我们如何选择我们需要运行哪些程序，以及与什么程序一起运行？

这就是调度的作用！首先，你要确定指标（metrics），确立一些类似于 "结束时间"。我们将这个度量定义为 "一个函数进入系统到完成的时间间隔"。第二，你决定一个减少度量的度量。我们希望我们的任务能尽快结束。

对 CPU 调度算法的需求是什么？ #

CPU 调度是决定在另一个进程暂停时哪个进程将拥有 CPU 来使用的过程。CPU 调度的主要功能是确保每当 CPU 保持空闲时，操作系统至少选择了一个可用的进程在准备使用的名单中。

在多程序（Multiprogramming）中，如果长期调度器选择了多个 I/O 绑定的进程，那么在大多数时候，CPU 仍然是空闲的。一个有效程序的功能是提高资源利用率。

如果大多数操作系统将其状态从性能（performance）变为等待（waiting），那么系统中可能总是有失败的可能。因此，为了尽量减少这种过剩，操作系统需要安排任务，以便充分利用 CPU，避免出现死锁（deadlock）的可能性。

进程调度算法的目标 #

• 将 CPU 的利用率提高到最高水平。保持 CPU 尽可能的繁忙。
• CPU 的分配应该是公平的。
• 吞吐量（throughput）应该是最大的，即时间单位完成执行的进程数量应该是最大的。
• 最短的周转（turnaround）时间，即一个进程完成执行的时间应该是最少的。
• 应该有最小的等待时间，进程不应该在准备队列中饿死（starve）。
• 最小响应（response）时间。这意味着一个进程产生第一个响应的时间应该尽可能的短。

CPU 调度算法中的术语 #

• 到达时间（Arrival Time）：进程到达准备队列的时间。
• 完成时间（Completion Time）：进程完成其执行的时间。
• 执行时间（Burst Time）：进程在 CPU 执行所需的时间。
• 周转时间（Turn Around Time）：完成时间和到达时间之间的时间差。周转时间 = 完成时间 - 到达时间。
• 等待时间 (Waiting Time)：周转时间和执行时间之间的时间差。等待时间 = 周转时间 - 执行时间。

在设计 CPU 调度算法时需要注意什么？ #

不同的 CPU 调度算法（CPU Scheduling algorithms）有不同的结构（structures），选择一个特定的算法取决于各种因素。许多条件已经被提出来用于比较 CPU 调度算法。这些条件包括以下几个方面：

• CPU 的利用率（CPU utilization）。任何 CPU 算法的主要目的都是为了让 CPU 尽可能的繁忙。理论上，CPU 的使用率可以从 0 到 100，但在实时系统中，根据系统负荷的不同，CPU 的使用率从 40% 到 90% 不等。
• 吞吐量（Throughput）。CPU 的平均性能是在每个单元度量（unit）中执行和完成的进程数量。这就是所谓的吞吐量。吞吐量可能根据进程的长度或持续时间而变化。
• 周转时间（Turn round Time）。对于一个特定的进程，重要的指标是执行该进程需要多长时间。从进程交付的时间到完成的时间被称为转换时间。转换时间是指等待内存访问、排队等待、使用 CPU 和等待 I/O 的时间。
• 等待时间（Waiting Time）：调度算法并不影响进程开始执行后完成所需的时间（执行时间）。它只影响进程的等待时间，即在准备队列中等待进程执行的时间。
• 响应时间（Response Time）：在一个协作系统中，周转时间不是最好的选择。进程可能会提前产生一些计算结果并继续计算新的结果，同时将以前的结果发布给用户。因此，另一种方法是在提交申请后直到发出第一个响应所花费的时间。这种方式被称为响应时间。

CPU 调度算法的类型 #

主要有两种类型的调度方法：

• 抢占式调度（Preemptive Scheduling）。抢占式调度是在进程从运行状态切换到就绪状态或从等待状态切换到就绪状态时使用。
• 非抢占式调度（Non-Preemptive Scheduling）。非抢占式调度是当一个进程终止时，或者当一个进程从运行状态切换到等待状态时使用的。

现在让我们逐一了解一下操作系统中的这些 CPU 调度算法。

先到先服务（First Come First Serve） #

FCFS（First Come First Serve）被认为是所有操作系统调度算法中最简单的一种。先到先服务的调度算法指出，抢先要求使用 CPU 的进程将首先被分配到 CPU，并通过使用先进先出队列（FIFO queue）来实现。

FCFS 的特点：

• FCFS 支持非抢先和抢占式的 CPU 调度算法。
• 任务总是以先到先服务的概念执行。
• FCFS 很容易实现和使用。
• 这种算法在性能上不是很有效，而且等待时间相当长。

FCFS 的优点：

• 容易实现
• 先来后到的方法

FCFS 的劣势：

• FCFS 受到 Convoy 效应（Convoy effect）的影响。
• 平均等待时间比其他算法高得多。
• FCFS 非常简单，容易实现，因此效率不高。

最短作业优先（Shortest Job First） #

最短作业优先（SJF，Shortest Job First）是一种调度算法，它选择执行时间最小的等待进程来执行下一个作业。这种调度方法可能是也可能不是抢占式的。大大减少了其他等待执行的进程的平均等待时间。

SJF 的特点：

• 最短作业优先的优点是在所有操作系统调度算法中具有最小的平均等待时间。
• 它与每个任务都是以时间单元（a unit of time）完成的。
• 如果较短的进程不断出现，它可能会导致饥饿（starvation）。这个问题可以用老龄化（ageing）的概念来解决。

最短作业优先的优点：

• 由于 SJF 减少了平均等待时间，因此它比先来后到（先到先服务）的调度算法更好。
• SJF 一般用于长期的调度。

SJF 的缺点：

• SJF 的缺点之一是容易导致饥饿（starvation）。
• 很多时候，预测即将到来的 CPU 请求的长度（length）变得很复杂。

最长作业优先（Longest Job First） #

最长作业优先 (LJF，Longest Job First) 调度过程与最短作业优先 (SJF) 相反，顾名思义，这种算法是基于具有最大突发时间（burst time）的进程被优先处理的原则。最长作业优先在本质上是非抢先性的。

LJF 的特点：

• 在等待队列中的所有进程中，CPU 总是被分配给具有最大爆发时间的进程。
• 如果两个进程有相同的爆发时间，则使用 FCFS 打破平局，即先到的进程先被处理。
• LJF CPU 调度可以是抢占式和非抢占式两种类型。

LJF 的优点：

• 在最长的工作或进程完全执行之前，没有其他任务会被调度。
• 所有的工作或进程大致在同一时间完成。

LJF 的缺点：

• 一般来说，LJF 算法对一组给定的进程会有非常高的平均等待时间和平均周转时间。
• 这可能会导致车队效应（convoy effect）。

基于优先级调度（Priority Scheduling） #

抢占式优先级 CPU 调度算法（Preemptive Priority CPU Scheduling Algorithm）是一种抢占式的 CPU 调度算法方法，它根据进程的优先级来工作。在这种算法中，编辑者（editor）将功能标记为重要，也就是说，最重要的进程必须先做。在有任何冲突的情况下，即有一个以上的进程具有相同的优先级，那么最主要的 CPU 规划算法将在 FCFS（先到先得）算法的基础上工作。

优先级调度的特点：

• 根据优先级来安排任务。
• 当优先级较高的工作到达时，而优先级较低的任务正在执行，优先级较高的工作就取代了优先级较低的工作，并且后者被暂停，直到前者执行完毕。
• 分配的优先级数字（number）越低，进程的优先级就越高。

优先级调度的优点：

• 平均等待时间比 FCFS 少
• 不太复杂

优先级调度的缺点：

抢占式优先级 CPU 调度算法最常见的缺点之一是饥饿问题。当一个进程必须等待较长的时间才能被调度到 CPU 的问题，这种情况被称为 "饥饿问题"。

循环调度（Round robin） #

循环调度（Round Robin）是一种 CPU 调度算法，每个进程都被循环地分配一个固定的时间段片。它是先到先服务的 CPU 调度算法的抢占性版本。Round Robin CPU 算法一般侧重于时间共享技术（Time Sharing technique）。

循环调度的特点：

• 它很简单，容易使用，而且没有饥饿现象，因为所有进程都能得到均衡的 CPU 分配。
• 是内核（core）的 CPU 调度中最广泛使用的方法之一。
• 它被认为是抢占式（preemptive）的，因为进程被赋予 CPU 的时间非常有限。

循环调度的优点：

• 循环调度似乎是公平的，因为每个进程都共享到同等份额的 CPU。
• 新创建的进程被添加到就绪队列（ready queue）的末端。

最短剩余时间优先（Shortest Remaining Time First） #

最短剩余时间优先（Shortest Remaining Time First，SRTF）是我们前面讨论过的最短工作优先的抢占式版本，即处理器被分配给最接近完成的工作。在 SRTF 中，选择完成前剩余时间最小的进程来执行。

最短剩余时间优先的特点：

• SRTF 算法使作业的处理比 SJF 算法快，因为它的开销不被计算在内。
• 在 SRTF 中，上下文切换的次数比 SJF 多得多，消耗了 CPU 的宝贵处理时间。这增加了它的处理时间，削弱了它快速处理的优势。

SRTF 的优点：

• 在 SRTF 中，短进程（short processes）的处理速度非常快。
• 该系统也只需要很少的开销（overhead），因为它只在一个进程完成或增加一个新的进程时做出决定。

SRTF 的劣势：

• 像最短作业优先一样，它也有可能造成进程饥饿。
• 如果短的进程不断被添加，长的进程可能会被无限期地搁置。

最长剩余时间优先（Longest Remaining Time First） #

最长剩余时间优先（Longest Remaining Time First，LRTF）是最长工作优先调度算法的一个抢占性版本。这种调度算法被操作系统用来对进入的进程进行系统的编程使用。这种算法首先调度那些剩余处理时间最长的进程，以便完成。

最长剩余时间优先的特点：

• 在等待队列中的所有进程中，CPU 总是被分配给具有最大突发时间（burst time）的进程。
• 如果两个进程有相同的突发时间，那么就用 FCFS 打破平局，即先到的进程先被处理。
• LJF CPU 调度可以是抢占式和非抢占式两种类型。

LRTF 的优点：

• 在最长的任务完全执行之前，其他进程不会被执行。
• 所有的工作或进程大约在同一时间完成。

LRTF 的缺点：

• 这种算法对给定的一组进程会有很高的平均等待时间和平均周转时间。
• 这可能导致车队效应。

下一个最高响应比率（Highest Response Ratio Next） #

下一个最高响应比率（Highest Response Ratio Next，HRRN）算法是一种非抢占式的 CPU 调度算法，它被认为是最优化的调度算法之一。这个名字本身就说明，我们需要找到所有可用进程的响应比率（Response Ratio），并选择一个具有最高响应比率的进程。一个进程一旦被选中就会一直运行到完成。

HRRN 特点：

• HRRN 的标准（criteria）是响应率，模式（mode）是非抢占式。
• HRRN 被认为是对最短作业优先的修改，以减少饥饿问题。
• 与 SJF 相比，在 HRRN 调度算法中，CPU 被分配给具有最高响应比率的下一个进程，而不是分配给具有较少突发时间的进程。

HRRN 的优势：

• HRRN 调度算法通常比最短作业优先调度的性能更好。
• 长作业的等待时间减少了，而且它鼓励短作业。

HRRN 的缺点：

• HRRN 调度的实施是不可能的，因为它不可能事先知道每个作业的突发时间。
• 在这种调度中，可能会出现 CPU 过载的情况。

多级队列调度（Multilevel Queue Scheduling） #

准备队列中的进程可以被分为不同的类别，其中每个类别都有自己的调度需求（scheduling needs）。例如，一个常见的划分是前台（互动，foreground (interactive)）进程和后台（批处理，background (batch)）进程。这两个类有不同的调度需求。对于这种情况，可以使用多级队列调度。

上述图表中的过程描述如下：

• 系统进程（System Processes）。CPU 本身有其运行的进程，一般称为系统进程。
• 交互式进程（Interactive Processes）。交互式进程是一种有相同类型的交互的进程。
• 批处理进程（Batch Processes）。批处理是操作系统中的一种技术，它在进程开始之前将程序和数据以批量的形式收集在一起。

多级队列调度的特点：

在多级队列调度算法中，进程在进入系统时被永久地分配到一个队列中，而进程不允许在队列之间移动。由于进程被永久地分配到队列中，这种设置具有低调度开销的优点。但另一方面也有不灵活的缺点。

多级队列调度的优点：

• 多级队列的主要优点是它的调度开销低。

多级队列调度的劣势：

• 饥饿问题
• 本质上是不灵活

多级反馈队列调度（Multilevel Feedback Queue Scheduling） #

多级反馈队列调度（MLFQ，Multilevel Feedback Queue Scheduling）CPU 调度与多级队列调度一样，但在这个过程中可以在队列之间移动。因此，比多级队列调度的效率要高得多。

多级反馈队列调度的特点：

• 由于进程允许在不同队列之间移动，具有一定灵活性，同时增加了部分的调度开销。

多级反馈队列调度的优点：

• 它更灵活
• 它允许不同的进程在不同的队列之间移动。

多级反馈队列调度的缺点：

• 它也会产生 CPU 的开销
• 它是最复杂的算法。

各种 CPU 调度算法之间的比较 #

下面是不同 CPU 调度算法之间的简要比较。

操作系统中的饥饿和老化 #

饥饿现象 #

优先级调度是批处理系统中最常见的调度算法之一。每个进程都被分配了一个优先级，具有最高优先级的进程将被首先执行，以此类推。这里我们将讨论一个与优先级调度有关的主要问题和它的解决方案。

饥饿（Starvation）或无限期阻塞（indefinite blocking）是一种与优先级调度算法有关的现象，在这种情况下，一个准备获得 CPU（资源）的进程可能因为低优先级而无限期地等待运行。在一个高负荷的计算机系统中，源源不断的高优先级进程可以阻止低优先级的进程获得 CPU。有传言说，1967 年优先级调度在麻省理工学院的 IBM 7094 中使用，他们发现一个低优先级的进程，直到 1973 年才被提交。

正如我们在上面的例子中所看到的，比其他进程拥有更高的优先级的进程更早获得 CPU。我们可以考虑这样一种情况，即只有一个进程具有非常低的优先级（例如 127），而我们给其他进程以高优先级，这可能导致具有低优先级的进程无限期地等待获得 CPU，这就导致了饥饿现象。此外，我们将讨论饥饿现象的解决办法。

操作系统中的死锁（Deadlock）和饥饿的区别如下：

• 由于其他进程占用了所需的资源，没有一个进程能够前进，这时就会出现死锁；另一方面，当一个进程无限期地等待获得它所需要的资源时，就会出现饥饿现象。
• 死锁的另一个名称是循环等待（Circular Waiting）。饥饿现象的另一个名字是活锁（Lived lock）。
• 当死锁发生时，任何进程都不能取得进展，而在饥饿状态下，除了受害者进程外，其他进程可以取得进展或进行。

饥饿的解决方案 —— 老化 #

老化（Aging）是一种逐步提高在系统中等待了很长时间的进程的优先级的技术。例如，如果优先级范围从 127（低）到 0（高），我们可以每 15 分钟给等待进程的优先级加 1。最终，即使是一个初始优先级为 127 的进程，也最多不超过 32 个小时的时间，就能使之老化为优先级为 0 的进程。

FCFS 调度 #

FCFS 是先到先服务（First Come First Serve）的意思。在 FCFS 调度算法中，首先到达准备队列（ready queue）的作业被分配到 CPU，然后是第二个到达的作业，以此类推。我们可以说准备队列是一个先进先出（FIFO）队列，因此到达的作业 / 进程被放在队列的最后。

FCFS 是一种非抢占式的调度算法，因为一个进程会占据 CPU，直到它终止或执行 I/O。因此，如果一个较长的作业被分配到 CPU，那么在它之后的许多较短的作业将不得不等待。这种算法在大多数批处理操作系统中使用。

FCFS 特点 #

• 它遵循非抢占式方法，即一旦一个进程控制了 CPU，它就不会被抢占（preempt），直到它终止。
• 选择进程的标准是到达时间（arrival time）。调度器选择就绪队列中的第一个工作，这个工作运行到完成其 CPU 执行（CPU burst）。
• 平均等待时间很高，所以不是最佳选择，因此性能很差。

FCFS 优点 #

• FCFS 算法很简单，容易在任何已有的系统中实现，而且容易理解。
• 由于进程之间不涉及上下文切换，因此更适合于有大量突发时间（large burst time）的进程。
• 它是一种公平的算法，因为不涉及优先级，先到的进程先得到服务。

FCFS 缺点 #

• 会出现队列效应（convoy effect），即所有的小进程都要等待一个大进程离开 CPU。
• 它是非抢占式的，进程在完成其任务并终止之前不会释放 CPU。
• 它不适合于交互式系统，因为它不能保证短的响应时间。
• 平均等待时间很高，周转时间不可预测，导致性能不佳。

FCFS 原理 #

第一个进程的等待时间为 0，因为它首先被执行。接下来的进程的等待时间可以通过以下方式计算： wt[i] = ( at[i - 1] + bt[i - 1] + wt[i - 1] ) - at[i] 。

其中：

• wt[i] = 当前进程的等待时间
• at[i-1] = 前一个进程的到达时间
• bt[i-1] = 前一进程的突发时间
• wt[i-1] = 前一进程的等待时间
• at[i] = 当前进程的到达时间

平均等待时间可以通过以下方式计算：平均等待时间 =（所有等待时间的总和）/（进程数）。

SJF 调度 #

SJF 调度算法是根据进程的突发时间（burst time）来调度的。在 SJF 调度中，在就绪队列中的可用进程列表中，具有最低突发时间的进程将被安排在下一个。然而，预测一个进程所需的突发时间是非常困难的，因此这种算法在系统中很难实现。

SJF 优点 #

• 最大的吞吐量
• 最小的平均等待和周转时间

SJF 缺点 #

• 可能会出现饥饿问题
• 无法实现，因为进程的确切突发时间无法事先知道。（有不同的技术可以用来确定进程的 CPU 突发时间。我们将在后面详细讨论这些技术）。

SRTF 调度 #

这个算法是 SJF 调度的抢占式版本（preemptive version）。在 SRTF 中，进程的执行可以在一定的时间后停止。在每个进程到达时，短期调度器会在可用的进程列表和正在运行的进程中安排剩余突发时间最少的进程进行调度。

一旦所有的进程都在就绪队列中，将不进行抢占，该算法将作为 SJF 调度工作。当进程从执行中移除下一个进程被调度时，进程的上下文被保存在进程控制块（Process Control Block）中。这个 PCB 在这个进程的下一次执行时被访问。

SRTF 示例 #

在这个例子中，有五个工作 P1, P2, P3, P4, P5 和 P6。他们的到达时间和突发时间如下表所示：

平均等待时间 = 24/6

甘特图是根据表格中给出的到达和突发时间编制的。

• 因为在时间 0，唯一可用的进程是 CPU 突发时间为 8 的 P1。这是列表中唯一可用的进程，因此它被安排。
• 下一个进程在时间单元 1 到达。由于我们使用的算法是 SRTF，它是一种抢占式的算法，当前的执行被停止，调度器检查具有最小突发时间的进程。
• 到现在为止，在准备队列中有两个进程。操作系统到现在为止已经执行了 P1 一个单位的时间；P1 的剩余突发时间是 7 个单位。进程 P2 的突发时间是 4 个单位。因此，根据算法，进程 P2 被安排在 CPU 上。
• 下一个进程 P3 在时间单位 2 到达。在这个时候，进程 P3 的执行被停止，并寻找剩余突发时间最少的进程。由于进程 P3 有 2 个单位的突发时间，因此它将被赋予比其他进程更多的优先权。
• 下一个进程 P4 在时间单位 3 到达。在这个时候，调度器将停止 P4 的执行，并检查在可用的进程（P1、P2、P3 和 P4）中哪个进程的突发时间最少。P1 和 P2 分别有 7 个单位和 3 个单位的剩余突发时间。
• P3 和 P4 的剩余突发时间各为 1 个单位。由于两者相等，因此调度将根据他们的到达时间进行。P3 比 P4 早到，因此它将被再次调度。
• 下一个进程 P5 在时间单位 4 到达。直到这个时候，进程 P3 已经完成了它的执行，它已经不在列表中了。调度器将比较所有可用进程的剩余突发时间。由于进程 P4 的突发时间是 1，是所有进程中最少的，因此它将被调度。
• 下一个进程 P6 在时间单元 5 到达，直到这时，进程 P4 已经完成了它的执行。到目前为止，我们有 4 个可用的进程，即 P1（7）、P2（3）、P5（3）和 P6（2）。P6 的突发时间是所有进程中最少的，因此 P6 被安排了。因为现在所有的进程都是可用的，所以现在的算法将与 SJF 一样工作。P6 将被执行，直到其完成，然后剩余时间最少的进程将被安排。

一旦所有进程都到达，就不会有抢占行为，算法将像 SJF 一样工作。

包含 CPU 和 IO 密集时间的 SRTF #

到现在为止，我们只考虑了与 CPU 绑定的作业。然而，进程可能需要一些 IO 操作或一些资源来完成其执行。在本例中，我们考虑的是 IO 绑定的进程。参见：SRTF with Processes contains CPU and IO Time

LRTF 调度 #

最长剩余时间优先（LRTF，Longest Remaining Time First）是最长工作优先（LJF）调度算法的一个抢占性版本。在这种调度算法中，我们找到具有最大剩余时间的进程，然后对其进行处理，即在一定的时间间隔后检查最大剩余时间，以检查是否有另一个具有更多突发时间的进程到达该时间。

LRTF 特点 #

• 在等待队列中的所有进程中，CPU 总是分配给具有最大突发时间的进程。
• 如果两个进程有相同的突发时间，那么就用 FCFS 打破平局，即先到的进程先被处理。
• LJF CPU 调度可以是抢占式和非抢占式的。

LRTF 优点 #

• 在最长的工作或进程完全执行之前，没有其他进程可以执行。
• 所有的工作或进程大约在同一时间完成。

LRTF 缺点 #

• 这种算法对一组给定的进程给出非常高的平均等待时间和平均周转时间。
• 这可能导致车队效应。
• 可能发生的情况是，一个短的进程可能永远不会被执行，而系统一直在执行长的进程。
• 这降低了处理速度，从而降低了系统的效率和利用率。

LRTF 原理 #

• 第 1 步：首先，按照到达时间的递增顺序对进程进行排序。
• 第 2 步：选择到达时间最少但突发时间最多的进程。
• 第 3 步：然后对其进行 1 个时间单元（时间片）的处理。检查是否有其他进程到达该执行时间。
• 第 4 步：重复上述两个步骤，直到执行所有的进程。

RR 调度 #

Round Robin（RR）调度算法是最流行的调度算法之一，实际上可以在大多数操作系统中实现。这是 FCFS 的调度方式的抢占式版本。该算法的重点是时间共享（Time Sharing）。在这个算法中，每个进程都以循环的方式（cyclic way）执行。在系统中定义了一个特定的时间片（time slice），这被称为时间量子（time quantum，TQ）。在准备队列中的每个进程都被分配到该时间量的 CPU，如果该进程的执行在该时间段内完成，那么该进程将被终止，否则该进程将回到准备队列（ready queue）中，等待下一次轮到完成执行。

RR 优点 #

• 它可以在系统中实际执行，因为它不依赖于突发时间。
• 它不存在饥饿或车队效应的问题。
• 所有的工作都能得到 CPU 的分配。

RR 缺点 #

• 时间量子越高，系统的响应时间就越长。
• 时间量子越低，系统中的上下文切换开销就越大。
• 决定一个完美的时间量子在系统中确实是一个非常困难的任务。

自私的 RR 调度 #

在传统的 Round Robin 调度算法中，所有的进程都被平等地对待，进行处理。自私的 Round Robin 的目标是给已经执行了一段时间的进程提供比新来者更好的服务。与普通的 Round Robin 算法相比，它是一个更合理、更优越的实现。

原理：

• 准备好的列表（ready list）中的进程被划分为两个列表。新的（NEW）和已接受的（ACCEPTED）。
• 新进程等待，而已接受的的进程则由 Round Robin 提供服务。
• 一个新进程的优先级以 'a' 的速度增加，而一个已接受的的进程的优先级以 'b' 的速度增加。
• 当一个新进程的优先级达到一个已接受的的进程的优先级时，该新进程被接受。
• 如果所有被接受的进程都完成了，则优先级最高的新进程被接受。

HRRN 调度 #

下一个最高响应率（HRNN，Highest Response Ratio Next）是最优化的调度算法之一。这是一种非抢占式的算法，在这种算法中，调度是基于一个叫做响应比的额外参数进行的。响应比是为每个可用的工作计算的，具有最高响应比的工作被赋予比其他工作更多的优先权。

响应比率是通过给定的公式计算的，即 Response Ratio = (W+S)/S 。其中 W 为等待时间，S 为服务时间或突发时间。如果我们看一下这个公式，我们会注意到，突发时间较短的工作将被优先考虑，但它也包括一个额外的因素，称为等待时间。因此：HRNN 与 W 成正比，与 S 成反比。

这种算法不仅有利于较短的工作，而且也关注较长工作的等待时间。它的模式是非抢占式的，因此在这个算法中上下文切换是最小的。

优先级调度 #

在优先级调度（Priority Scheduling）中，有一个优先级号码分配给每个进程。在一些系统中，数字越小，优先级就越高。而在其他系统中，数字越大，优先级就越高。在可用的进程中具有较高优先级的进程被赋予 CPU。有两种类型的优先级调度算法存在：一种是抢占式优先级调度，另一种是非抢占式优先级调度。

分配给每个进程的优先权号码可能会或也可能不会变化。如果优先权号码在整个过程中不发生变化，它就被称为静态优先权，而如果它在固定的时间段内不断改变自己，它就被称为动态优先权。

非抢占式优先级调度 #

在非抢占式优先级调度（Non Preemptive Priority Scheduling）中，进程是根据分配给它们的优先级编号来调度的。一旦进程被调度，它将一直运行到完成。一般来说，优先级数字越低，进程的优先级就越高。人们可能会对优先级的数字感到困惑，因此在 GATE 中，明确提到了哪一个是最高的优先级，哪一个是最低的。

抢占式优先级调度 #

在抢占式优先级调度（Preemptive Priority Scheduling）中，当一个进程到达就绪队列时，它的优先级将与就绪队列中的其他进程的优先级以及在该时间点正在由 CPU 执行的进程的优先级进行比较。在所有可用的进程中具有最高优先级的进程将被赋予 CPU。

抢占式优先级调度和非抢占式优先级调度的区别在于，在抢占式优先级调度中，正在执行的工作可以在更高优先级的工作到来时被停止。

一旦所有的工作都在准备好的队列中，该算法将表现为非抢占式优先级调度，这意味着安排的工作将运行到完成，不会有抢占的情况发生。

预测进程的 CPU 突发时间 #

SJF 算法是最好的调度算法之一，因为它提供了最大的吞吐量和最小的等待时间，但该算法的问题是，CPU 的爆发时间不能事先知道。但是我们可以对一个进程的 CPU 突发时间进行近似计算。有各种技术可以用来预测一个进程的 CPU 突发时间。

以下是用于预测一个进程的 CPU 突发时间的技术：

静态技术 #

进程大小（Process Size）：

我们可以根据进程的大小来预测它的突发时间。如果我们有两个进程 T_OLD 和 T_New，旧进程的实际突发时间为 20 秒，进程的大小为 20KB。我们知道 P_NEW 的大小是 21KB。那么 P_NEW 的突发时间与 20 秒相似的概率是很大的。因此，在这项技术中，我们实际上是根据与新进程大小相似的旧进程的突发时间来预测新进程的突发时间。

进程类型（Process Type）：

我们还可以根据进程的类型来预测进程的突发时间。一个进程可以有各种类型，定义如下：

• 操作系统进程（OS Process）：一个进程可以是一个操作系统进程，如调度器、编译器、程序管理器和许多其他系统进程。它们的突发时间一般较低，例如，3 到 5 个单位的时间。
• 用户进程（User Process）：由用户发起的进程被称为用户进程。可以有以下三种类型的进程：
  • 交互式进程（Interactive Process）：交互式进程是一种不时与用户互动的进程，其执行完全取决于用户的输入，例如各种游戏就是这样的进程。由于它们不需要大量的 CPU，所以它们的突发时间要低一些，它们主要取决于用户与进程的交互性，因此它们主要是 IO 密集（IO bound）的进程。
  • 前台进程（Foreground process）：前台进程是用户用来执行其需求的进程，如 MS office、Editors、实用软件等。这些类型的进程有较高的突发时间，因为它们是 CPU 和 IO 密集进程的完美结合。
  • 后台进程（Background process）：后台进程支持其他进程的执行。它们以隐藏模式工作（hidden mode）。例如，键盘记录器是记录用户按下的键和用户在系统上的活动的进程。它们主要是 CPU 密集的进程，需要 CPU 的时间比较长。

动态技术 #

简单平均法：

在简单平均法中，有给定的 n 个进程列表 P (i).......P (n)。让 T (i) 表示进程 P (i) 的突发时间。让 τ(n) 表示第 n 个进程的预测突发时间。然后根据简单的平均法，进程 n+1 的预测突发时间将被计算为： τ(n+1)=(1/n)∑T(i) 。其中， 0<=i<=n ， ∑T(i) 是到目前为止所有进程的实际突发时间的总和。

指数平均法或老化法：

Tn 是第 n 个进程的实际爆发时间，τ(n) 是第 n 个进程的预测爆发时间，那么下一个进程（n+1）的 CPU 爆发时间将被计算为： τ(n+1) = α.Tn+(1-α).τ(n) ，其中，α 是平滑度。其值在 0 和 1 之间。