循环调度算法及示例

循环调度的特点

以下是循环调度的重要特性

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

循环调度的例子

考虑以下三个进程

进程队列	执行时间
P1	4
P2	3
P3	5

第一步) 执行开始于进程 P1，其执行时间为 4。此处，每个进程执行 2 秒。P2 和 P3 仍在等待队列中。

第二步) 在时间 = 2 时，P1 被添加到队列末尾，P2 开始执行。

第三步) 在时间=4 时，P2 被抢占并添加到队列末尾。P3 开始执行。

第四步) 在时间=6 时，P3 被抢占并添加到队列末尾。P1 开始执行。

第五步) 在时间=8 时，P1 的执行时间为 4。它已完成执行。P2 开始执行。

第六步) P2 的执行时间为 3。它已执行了 2 个时间间隔。在时间=9 时，P2 完成执行。然后，P3 开始执行直到完成。

第七步) 让我们计算以上示例的平均等待时间。

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	
t,SR = sum of all execution times

摘要

• 该算法的名称来源于循环原则，即每个人轮流获得一份平等的份额。
• 循环调度是最古老、最公平、最简单的算法之一，也是传统 操作系统 中广泛使用的调度方法。
• 循环调度是一种抢占式算法
• 循环调度方法最大的优点是：如果您知道运行队列中进程的总数，那么您也可以假设同一进程的最坏情况响应时间。
• 此方法在上下文切换上花费的时间更多。
• 最坏情况延迟是所有任务执行所需的最大时间的术语。