自私循环调度 CPU 调度算法

引言

自私轮转 是一种自适应进程调度算法，它修改了传统的轮转调度。在该算法下，进程可以根据每个单独进程的需求调整自身的调度参数。与给予所有进程同等待遇的传统轮转调度不同，自私轮转调度使进程更具自我意识。每个进程都可以动态地调整自己的时间片，并根据需求的紧急程度或优先级来表明偏好。

这个概念的核心在于在 CPU 资源分配中实现公平性和灵活性之间的平衡。现在，进程不再是被动地接收固定时间片的接收者，而是主动参与调度过程。该算法在每个进程执行完毕后重新评估该进程，以便它们能够利用反馈影响未来的调度。它允许用户编写更直接、响应更快的代码，从而降低进程饿死等问题的风险。因此，自私轮转 非常适合进程具有不同特征或优先级的动态计算环境。

引入该算法的原因

展望未来，引入自私轮转算法的原因是，传统的调度算法在面对进程需求和工作负载的变化时存在局限性。在进程具有不同执行特性的情况下，“一刀切”的策略 可能导致效率低下，一些进程不必要地延迟或被饿死。

因此，自私轮转中的每个进程都具有一定的自我意识，并可以根据其需求表达自己的偏好或优先级。由于这种灵活性，关键任务进程可以快速获得所需的资源。结果，整个系统变得更加响应迅速。原因是，如果进程能够在其合理范围内表达自己的偏好，它们应该能够获得更好的整体性能并减少资源竞争。

关键目标和宗旨

自私轮转 CPU 调度的几个关键目标和宗旨如下。

公平与适应性

• 目标： 实现竞争进程之间 CPU 时间的公平分配。
• 理由： 在传统的轮转技术中，通过为每个运行进程分配相等的时间片来保证公平性。自私轮转为 CPU 调度增加了适应性。不仅仅是公平，目标还包括让进程能够动态地表达其偏好，并根据不断变化的工作负载进行调整。这种适应性意味着不同优先级的进程可以共享同一空间并获得公平的时间。

缓解进程饿死

• 目标： 利用需求和优先级解决进程饿死问题。
• 理由： 进程饿死对系统性能有害。针对这个问题，自私轮转提供了一种方法，让进程可以声明其紧急程度或优先级级别。它防止重要任务被无限期推迟，并在需要时分配资源。通过这种方法，该算法保证了一些重要工作不会饿死。

优化吞吐量

• 目标： 最大限度地利用 CPU 时间以实现整体系统吞吐量最大化。
• 理由： 吞吐量是衡量调度算法效率的重要指标。通过动态匹配每个进程的需求，自私轮转是一种系统吞吐量优化机制。因此，该算法通过有效利用 CPU 时间并消除空闲周期来实现这一目标。此目标特别适用于多工作负载环境，其中不同进程需要不等量的 CPU 时间。

响应式资源分配

• 目标： 需要一个灵活的环境，使 CPU 能够快速地达到进程。
• 理由： 对于实时或时间关键型应用程序，响应能力尤为重要。自私轮转使资源具有响应能力，因此进程可以在需要时轻松地获取 CPU。它旨在考虑到不断变化的工作负载性质，以便当进程急需关注时，能够及时分配这些资源。时间关键型任务的这一目标仅仅是减少延迟。

轮转调度与自私轮转调度

循环调度

然而，轮转 (RR) 调度是一种抢占式算法，它在轮转的基础上为每个进程分配固定的时间片。当进程的时间配额用完时，它会被放回队列的末尾，然后继续执行下一个进程。这种方法为每个进程提供了平等的运行机会，但它不考虑不同进程的不同需求或特定进程的优先级。

自私轮转调度

轮转 是自私轮转的基础，并增加了一些灵活的调度功能。两种算法都依赖于基本上相同的概念，即轮流分配时间片给进程，而自私轮转允许指定偏好。每个进程都可以根据任何给定进程的特殊需求调整其在队列中的位置或时间片。

进程偏好和优先级

• 特点： 这种自私轮转为进程建立了偏好和优先级。
• 理由： 与将所有进程视为同等重要和紧急的传统轮转调度不同，自私轮转承认不同进程的优先级可能较高或较低。进程可以向调度器表达其特殊需求，以便它能够按顺序获得 CPU 时间。这种能力有助于在各种工作负载面前实现适应性和响应能力。

动态时间片调整

• 特点： 在这里，时间片可以动态调整。
• 理由： 与自私轮转不同，轮转对进程施加固定的时间片。如果进程计算要求高或任务时间敏感，它们可以请求更长的时间片。如果它们不干扰固定计划，它们将被授予必要的资源。这些动态调整提高了资源利用率的整体效率。

算法分步详解

在此，我们将讨论自私轮转算法的分步解释。

1. 初始化

该算法首先按照进入顺序初始化进程队列。最初，每个进程被分配一个相等的时间片。

2. 进程执行

选择队列末尾的进程。它运行一个时间片。

3. 反馈机制

每次执行周期后，进程都会向调度器反馈其性能和资源需求。反馈可能包括有关紧急程度或优先级的信息，以及进程中对未来资源需求的估计。

4. 动态时间片调整

根据收到的反馈，在该算法下，进程在每个执行周期中都可以动态地更改其时间片。具有更高紧急程度或优先级评分的进程将被推向前，以便在下一个调度周期中获得优先处理。

5. 队列重排

反馈 也会影响进程在队列中的位置。具有更高紧急程度或优先级评分的进程将被推向前，以便在下一个调度周期中获得优先处理。

6. 下一个进程选择

根据轮转原则，从更新后的队列中选择下一个运行的进程。还会考虑对时间片和队列中位置的调整。

7. 执行和迭代

步骤 2 到 6 以周期方式重复。在每个周期迭代中，每个进程都有机会根据其动态调整的时间片和优先级进行执行。

8. 完成和到达处理

已完成执行的进程将从队列中删除，新到达的进程将被添加到末尾。该算法动态适应不断变化的工作负载。

9. 终止条件

该算法一直运行，直到所有进程都完成执行或达到预设的终止条件。

自私轮转 CPU 调度的参数

自私轮转 CPU 调度有几个参数。一些主要的参数如下：

• 队列： 队列数据结构用于根据到达时间存储所有进程，这决定了执行顺序。
• 时间片： 为每个进程分配固定的执行时间片。动态进程反馈允许调整该值。
• 进程反馈： 在每个运行周期后，每个进程都会提供信息，例如分配的空间、执行速度和剩余的运行周期数，这会影响执行顺序。
• 进程执行时间： 进程执行时间是每个进程在一个周期中可用的运行时间长度。
• 进程优先级： 一个表示每个进程优先级的参数。在调度队列中，高优先级进程获得优先权。
• 终止条件： 如果所有进程都已完成执行，则使用此标准来停止分配 CPU 时间。

伪代码

让我们通过一个伪代码来说明自私轮转 CPU 调度的原理。

示例

考虑进程 A、B、C、D 和 E

解决方案

(a=2 且 b=1)

说明

• 当进程 A 在时间 t=0 时出现时，它被接受。因此，它的优先级仅在每秒后增加“b”或“1”。在时间 t=1 时，B 进入并加入等待队列。在时间 t=2 时，它的优先级增加“a”或“2”。现在，优先级 A 等于优先级 B，都等于 2。
• 因此，进程 A 和 B 目前正在以轮转方式执行，并已进入就绪队列。进程 C 在时间 t=3 时加入队列。当进程 C 的优先级在时间 t=6 时等于进程 B 的优先级时，它们开始以轮转方式运行。在时间 t=10 时，当 B 完成执行时，D 会自动移入就绪队列。
• 类似地，当 D 在时间 t=15 时完成执行时，E 会立即移入就绪队列。

自私轮转调度算法的优点

自私轮转调度算法 有许多优点。自私轮转调度算法的一些主要优点如下：

• 改进的资源分配公平性

自私轮转调度通过提高竞争进程之间计算时间的公平分配来带来好处。传统的轮转公平地将时间片平均分配给各个进程，因此具有一定的基本公正性。相比之下，这种方法忽略了存在不同优先级和紧急程度的各种进程的事实。在自私轮转 中，进程可以声明其偏好并以自适应的方式更新时间片。这样可以优先处理各种关键任务或进程，确保每个进程都能公平地获得 CPU 的工作时间。自私轮转在公平性和适应性之间取得了平衡，实现了高效利用，同时又能响应不断变化的需求。

• 增强的响应能力

自私轮转调度的另一个显著好处是提高了系统响应能力。然而，在传统调度中，响应能力常常被牺牲，因为许多进程需要立即处理，但又受限于特定的时间片。自私轮转解决了这个问题，它允许进程调整其时间片。

换句话说，这种时间关键型或敏感型作业可以请求更长的时间段以更快地处理。该算法根据任务的关键程度进行调整，从而降低延迟并提高响应能力。这在具有大量实时处理或对时间要求严格的系统中尤其有用。自私轮转可以在不牺牲公平性的情况下提高系统的响应能力。

• 缓解进程饿死问题

另一方面，传统的调度方法经常遭受进程饿死问题（进程长时间无法使用任何保留的 CPU 容量）。然而，自私轮转通过允许进程根据紧急程度和优先级更改其调度参数，很好地避免了进程饿死问题。需要立即关注的敏感任务可以发出请求并使用优先级调度。

它还防止重要任务被无故推迟，并在队列中等待直到它们获得 CPU 时间。由于自私轮转具有高度适应性，进程不会饿死资源。它能更好地分配负载，使系统性能更稳定。因此，该算法解决了 CPU 调度中的一个长期存在的问题，并有助于使系统性能更具可预测性，以适应不断变化的工作负载。

与其他调度算法的比较

• 先来先服务 (FCFS)

最基本的调度算法是先来先服务 (FCFS)，它只按照进程进入就绪队列的顺序执行。另一方面，虽然 FCFS 简单易行，但它很容易出现“车队效应”，即短进程被长进程阻碍。进程可能很紧急或很重要，但 FCFS 不考虑这些方面。

• 自私轮转 vs. FCFS

公平性和适应性： 它为进程增加了适应性和公平性。这些特性与自私轮转非常契合，因此将其添加为一种新的到达机制。FCFS 在动态环境中不特定于进程。在这种情况下，它可能导致资源分配效率低下。

响应紧急情况： 自私轮转的响应能力得到提高，因为具有更高紧急程度或优先级的进程可以影响其调度参数。FCFS 不提供优先处理紧急或关键任务的灵活性。

• 最短作业优先 (SJN) 调度

SJF，也称为S J N (最短作业优先)，选择就绪队列中最短的作业。它减少了总等待时间并最大化了周转时间。

• 自私轮转 vs. SJN

适应性和公平性： 通过动态调整时间片，自私轮转实现了公平性。SJN 在消除等待时间方面做得很好，但对较长作业可能不太公平。它们可能永远看不到光明。

处理不同工作负载： 自私轮转特别适用于工作负载动态变化且进程特性各异的情况。SJN 在作业长度已知的情况下工作得很好，但在动态条件下运行时可能会遇到问题。

• 与优先级轮转调度的比较

公平性和优先级处理： 优先级轮转调度与自私轮转一样，为进程分配优先级。自私轮转基于动态分配给进程的优先级，而优先级轮转使用分配给所有可用进程的静态优先级。

• 与多级队列调度的比较

复杂性和资源分段： 在多级队列调度中，进程被分为不同的优先级组。通过在一个队列中构建适应性，可以实现这种方法，从而消除了管理多个队列的麻烦。

实施自私轮转的最佳实践

自私轮转算法有一些最佳实践。一些主要的最佳实践如下：

• 动态时间片调整： 设计一个机制，可以根据反馈动态地重新分配每个进程的时间片。紧迫性、优先级和过往表现等属性都是决策者在确定每个进程在给定周期中应花费多长时间时应考虑的因素。
• 队列重排策略： 设计一个快速的程序，按进程优先级和紧急程度对队列进行重新排序。另外，要确保紧急程度或优先级较高的进程排在前面，以便在每个周期中首先调度它们。
• 公平性考虑： 通过限制进程时间片的改变幅度，可以实现公平性和适应性之间的平衡。它可以确保没有任何进程可以占用某些资源并等待分配给其他进程的资源。
• 终止条件： 建立终止条件来结束调度过程。这意味着所有进程都已完成执行或已完成一定数量的周期。精确的终止条件可以减少不必要的计算。
• 优先级和紧急程度缩放： 为优先级或紧急程度设置一个尺度。这意味着进程所做的更改会直接与其调度参数成比例地产生影响。
• 高效数据结构： 为调度队列和进程选择有效的数据结构。这可以最大限度地减少算法的运行时间。数据结构，如链表或优先队列，可以根据具体需求方便实现。
• 反馈处理策略： 应该制定一个处理反馈的策略，特别是当进程之间存在冲突时，或者当你收到太多建议导致频繁调整时。
• 日志记录和监控： 建立完善的日志记录和监控系统，以跟踪自私轮转的有效性。这还包括记录进程支持、调度计划和时间片控制。可以检测性能瓶颈，并且监控工具可以调整算法。

结论

自私轮转 似乎在进程调度方面取得了进步。这种公平性、适应性和响应能力的结合纠正了传统算法的一些缺陷。通过将进程的调度条件置于其自身控制之下，自私轮转在动态计算环境中延伸了每一个环节，并且不像旧方法那样容易遇到诸如进程饿死之类的问题。性能也得到了显著提高。自私轮转是一种有效的 CPU 调度方法，可以适应任何计算环境中的变化。