抢占式优先权调度

引言

在实时系统中，抢占式调度是最常用的调度技术。在这里，作业按优先级别排序，CPU 时间分配给所有其他任务中优先级最高的那个任务。当出现优先级比当前正在执行的任务更高的任务时，内核会维护正在运行进程的上下文，并通过加载其上下文来切换到优先级更高的作业。优先级最高的任务通常会持续运行，直到它完成或不再可计算，例如等待某个资源可用或调用函数进行等待或延迟。

什么是“抢占式调度”？

抢占式调度是实时系统中应用最广泛的调度方法。即使低优先级进程已经准备就绪或正在进行传输，抢占式优先权调度方法也会停止它并将其挂起，直到高优先级进程得到处理，如果高优先级进程进入等待队列。最终，高优先级进程获得 CPU 时间。这是抢占式的，因为高优先级进程可以通过中断现有进程来抢占低优先级进程，为其腾出运行空间。循环就绪（RR）、最短剩余时间优先（SRTF）、优先权（抢占式版本）以及其他算法都是抢占式调度算法的例子。

抢占式调度如何工作？

在抢占式优先权调度中，当一个进程到达就绪队列时，它的优先权会与其他在就绪队列中以及当前由 CPU 执行的进程的优先权进行比较。所有可用进程中优先级最高的进程将获得下一个 CPU。

抢占式优先权调度与非抢占式优先权调度的区别在于，在抢占式优先权调度中，正在执行的作业可以在有更高优先级作业到达时被停止。

一旦所有作业都进入就绪队列，该算法将表现得像非抢占式优先权调度一样，这意味着已调度的作业将一直运行到完成，并且不会发生抢占。

示例

有 7 个进程 P1、P2、P3、P4、P5、P6 和 P7。它们各自的优先权、到达时间和执行时间如下表所示。

甘特图准备

在时间 0，P1 到达，执行时间为 1 个单位，优先权为 2。由于没有其他进程可用，因此将调度此进程，直到下一个作业到达或其完成（以较小者为准）。

在时间 1，P2 到达。P1 已完成执行，此时没有其他进程可用，因此操作系统必须调度它，而不管分配给它的优先权。

下一个进程 P3 于时间单位 2 到达，P3 的优先权高于 P2。因此，P2 的执行将被停止，P3 将在 CPU 上被调度。

在 P3 执行期间，另外三个进程 P4、P5 和 P6 也到达了。由于这三个进程的优先权都低于正在执行的进程，因此 PS 无法抢占该进程。P3 将完成其执行，然后将调度 P5，其优先权是可用进程中最高的。

在 P5 执行期间，所有进程都已到达就绪队列。此时，算法将开始像非抢占式优先权调度一样运行。因此，一旦所有进程都进入就绪队列，操作系统将挑选优先级最高的进程并一直执行该进程直到完成。在这种情况下，将调度 P4 并执行直到完成。

由于 P4 已完成，就绪队列中下一个优先级最高的可用进程是 P2。因此，P2 将被调度。

P2 将获得 CPU 直到完成。由于其剩余执行时间为 6 个单位，因此 P7 将在此之后被调度。

唯一剩余的进程是 P6，其优先级别最低。操作系统别无选择，只能执行它。这将最后执行。

每个进程的完成时间是通过甘特图确定的。周转时间和等待时间可以通过以下公式计算。

平均等待时间 = (0+14+0+7+1+25+16)/7 = 63/7 = 9 个单位

抢占式调度的优点

• 通过允许关键进程在进入就绪队列时访问 CPU，抢占式调度提供了灵活性，独立于当前正在执行的作业。
• 在这种情况下，所有正在运行的应用程序将平均使用 CPU，这意味着 CPU 使用率是相同的。此外，抢占式调度被认为是公平的。
• 由于等待时间减少，平均响应时间得到改善。
• 抢占式调度在多道程序设计环境中有益。

抢占式调度的缺点

• 优先级较低的进程可能会出现饿死。
• 调度程序花费更多时间来暂停当前作业、更改上下文以及发送新到达的任务。
• 调度需要大量的处理能力。

总结

如果 CPU 能够在分配进程后将其移走，那么该调度就是抢占式的。抢占式调度包括循环就绪（Round Robin）和最短剩余时间优先（Shortest Remaining Time First）等策略。与其他操作系统调度技术相比，抢占式调度具有多种优势，包括被认为是公平的、灵活的（因为关键进程可以在进入就绪队列时访问 CPU，而无论当前正在执行的任务是什么）、等待时间减少以及与多道程序设计环境兼容。

由于将优先级进程添加到队列中，可能会发生饿死。

常见问题

你能解释一下抢占式优先权调度吗？

一种调度算法，它为每个进程分配一个优先级别，称为抢占式优先权调度。优先级最高的进程获得 CPU。当一个高优先级进程出现而低优先级作业正在进行时，我们抢占低优先级任务，以便它可以立即开始运行。

哪种情况说明了抢占式调度？

当一个高优先级进程（例如实时系统中断）在低优先级进程运行时出现时，这就是抢占式调度的例子。抢占式调度机制将 CPU 时间分配给这个高优先级活动，它会立即阻止低优先级活动。这确保了中断能够被快速处理。

如何解决抢占式优先权调度？

为了解决抢占式优先权调度，必须采取以下步骤：按优先级别对就绪队列中的所有进程进行排序；将 CPU 分配给优先级最高的进程；并根据其紧迫性或重要性为每个进程分配优先级别。如果有优先级高于当前正在运行的进程的新进程出现，那么之前被抢占的进程应在所有低优先级进程完成或更高优先级进程到达后继续运行。继续这样做，直到所有步骤都完成。