循环调度算法示例

什么是循环调度？

该算法的名称来自循环原则，即每个人轮流获得相等份额的东西。它是最古老、最简单的调度算法，主要用于多任务处理。

在轮询调度算法中，每个就绪任务依次在循环队列中运行，且每次运行的时间片都是有限的。该算法还能确保进程执行过程中不会出现饥饿现象。

循环调度的特点

以下是循环调度的重要特征：

• 轮询算法是一种抢占式算法。
• CPU 会在经过一段固定的时间间隔后切换到下一个进程，这段时间间隔称为时间片/时间片。
• 被抢占的进程被添加到队列末尾。
• 循环赛是一种由时钟驱动的混合模型。
• 时间片应尽可能小，并分配给需要处理的特定任务。但是，不同操作系统的时间片可能有所不同。
• 它是一种实时算法，能够在特定的时间限制内对事件做出响应。
• 循环赛制是最古老、最公平、最简单的算法之一。
• 它是传统操作系统中广泛使用的一种调度方法。

循环调度示例

请考虑以下三个过程：

步骤1） 执行从进程 P1 开始，其突发时间为 4。此时，每个进程执行 2 秒。P2 和 P3 仍在等待队列中。

步骤2） 在时间 = 2 时，P1 被添加到队列的末尾，P2 开始执行。

步骤3） 在时间 4 时，P2 被抢占并添加到队列末尾。P3 开始执行。

步骤4） 在时间 6 时，P3 被抢占并添加到队列末尾。P1 开始执行。

步骤5） 在时间 8 时，P1 的执行时间为 4，执行完毕。P2 开始执行。

步骤6） P2 的执行时间为 3。它已经执行了 2 个时间间隔。在时间 9 时，P2 执行完毕。然后，P3 开始执行，直到执行完毕。

步骤7） 让我们来计算一下上述例子的平均等待时间。

Wait time
P1 = 0 + 4 = 4
P2 = 2 + 4 = 6
P3 = 4 + 3 = 7

循环调度法的优势

以下是轮询调度方法的优点/益处：

• 它不会面临饥荒或护航效应的问题。
• 所有作业都获得公平的 CPU 分配。
• 它处理所有流程，不设优先级。
• 如果您知道运行队列中的进程总数，那么您还可以假设同一进程的最坏情况响应时间。
• 这种调度方法不依赖于运行时间，因此很容易在系统中实现。
• 一旦某个进程在特定时间段内执行完毕，该进程就会被抢占，而另一个进程则会在给定的时间段内执行。
• 允许操作系统使用上下文切换方法来保存被抢占进程的状态。
• 就平均响应时间而言，它提供了最佳的性能。

循环调度的缺点

以下是使用轮询调度算法的缺点/不足之处：

• 如果操作系统的切片时间较短，则处理器输出会降低。
• 这种方法会花费更多时间在上下文切换上。
• 其性能很大程度上取决于时间量。
• 无法为进程设置优先级。
• 轮询调度不会优先处理更重要的任务。
• 它会降低理解能力。
• 时间片越小，系统上下文切换开销就越大。
• 在这个系统中，找到正确的时间量子是一项相当困难的任务。

最坏情况延迟

该术语用于表示执行所有任务所需的最大时间。

• dt = 表示将任务添加到列表中的检测时间
• st = 表示从一个任务切换到另一个任务的时间
• et = 表示任务执行时间

分子式：

Tworst = {(dti+ sti + eti ), + (dti+ sti + eti )2 +...+ (dti+ sti + eti )N., + (dti+ sti + eti  + eti) N} + tISR
tISR = sum of all execution times

常见问题