C 语言轮询程序及输出

轮循调度是一种CPU调度算法，它以循环方式为每个进程分配相等的资源份额，并处理所有进程而没有优先级。在轮循调度中，每个进程获得一个固定的时间片段来利用资源或执行其任务，称为时间量或时间片。一些轮循进程如果在一个给定的时间段内执行了，它们会被抢占，而其余进程则返回就绪队列，并在调度的时间段内以循环顺序等待运行，直到它们完成任务。它通过对CPU进行适当的分区，消除了每个进程的饥饿现象，以实现CPU调度。

轮循CPU调度算法

步骤 1: 按照到达时间将所有进程组织到就绪队列中。就绪队列的队列结构基于FIFO结构来执行所有CPU进程。

步骤 2: 现在，我们将就绪队列中的第一个进程推送到执行其任务，时长为固定的时间，该时间由进入队列的每个进程分配。

步骤 3: 如果进程无法在定义的时段或时间片内完成其任务，因为它被另一个从就绪队列中推出的进程抢占以执行其任务，因为下一个进程的到达时间已到。因此，CPU保存了进程的先前状态，这有助于从中断点恢复。（如果进程的突发时间还剩余，则将进程推送到就绪队列的末尾）。

步骤 4: 同样，调度程序从就绪队列中选择另一个进程来执行其任务。当一个进程在时间片内完成其任务时，该进程将不再继续执行，因为该进程的突发时间已结束。

步骤 5: 同样，我们重复所有步骤来执行进程，直到工作完成。

轮循的特点

1. 它是一种抢占式算法。
2. 它在所有进程之间分配相等的时间间隔以完成其任务。
3. 它是一种无饥饿的CPU调度算法。因此，它被称为最公平和简单的算法。

优点

1. 它不面临任何饥饿问题或合集效应。
2. 每个进程在CPU公平分配中获得相同的优先级。
3. CPU调度算法易于实现。
4. 每个新进程在下一个进程的到达时间到达时被添加到就绪队列的末尾。
5. 每个进程都以循环顺序执行，分配固定的时间片或时间量子。
6. 在轮循调度算法中，每个进程都有机会在给定的时间量子周期后重新调度。

缺点

1. 如果时间量子较低，则在进程之间的上下文切换上花费的时间更多。
2. 它不为执行最重要的进程提供任何特殊优先级。
3. 由于时间片短，大进程的等待时间较长。
4. 算法的性能取决于时间量子。
5. 由于时间量子较大的时间片，进程的响应时间较长。
6. 在轮循算法中，为所有进程获得正确的时间片或时间量子非常困难。

轮循CPU调度示例

让我们通过一个例子来理解轮循的概念。假设我们有五个进程 P1、P2、P3、P4 和 P5。每个进程的到达时间和突发时间在下表中给出。时间量子是三个单位。

现在我们需要为轮循CPU调度程序创建就绪队列和甘特图。

就绪队列: P1, P3, P1, P2, P4, P3, P5, P1, P3, P5

这是甘特图

步骤 1: 时间 0 时，进程 P1 进入就绪队列并开始执行，时长为指定的时间片 3。在 3 个时间片的期间，另一个进程 P3 进入就绪队列，因为它的到达时间是 1。

步骤 2: 现在，进程 P3 开始执行，时间片为 3 个单位，而进程 P1 需要等待。进程 P3 执行完毕后，进程 P1 再次恢复执行，时长为时间片 3。

步骤 3: 在进程 P1 执行期间，另外两个进程 P2 和 P4 进入就绪队列开始执行。由于进程 P2 先到达，它将执行时间量子 2 个单位，然后 P4 执行。

步骤 4: 在此，P4 已执行时间片 3 个单位，并且其任务已完成，因为 BT (突发时间) 为 2。因此，它不会进入就绪队列。

步骤 5: 之后，进程 P3 从就绪队列执行，时间片为 3，然后进程 P5 到达，时间片为 3。

步骤 6: 在此期间，进程 P5 执行时，进程 P1 和 P3 需要在就绪队列中等待。

步骤 7: 现在进程 P1 从就绪队列中提取出来，并开始执行，时长为 2，因为它只需要 2 个 BT 即可完成任务。因此，它不会进入就绪队列进行进一步执行。

步骤 8: 现在，进程 P3 以 1 个 BT 来完成任务，因为它只需要 1 个 BT 来完成其任务。

步骤 9: 最后一个进程 P5 执行时长为 2，因为它只需要 2 个 BT 即可完成其任务。

以下是确定完成时间、周转时间 (TAT)、响应时间 (RT) 和等待时间 (WT) 的重要术语。

1. 完成时间: 它定义了进程完成其执行的时间。
2. 周转时间: 它定义了完成时间 (CT) 和到达时间 (AT) 之间的时间差。
   周转时间 (TAT) = 完成时间 (CT) - 到达时间 (AT)
3. 等待时间: 它定义了请求操作与获得资源之间的总时间。
   等待时间 (WT) = 周转时间 (TAT) - 突发时间 (BT)
4. 响应时间: 这是定义系统响应进程的时间。

进程 P1 的完成时间 = 22，P2 = 11，P3 = 23，P4 = 14，P5 = 25。

P1 的周转时间 = 完成时间 (CT) - 到达时间 (AT)
                          22 - 0 = 22
P2 的周转时间 = 11 - 5 = 6
P3 的周转时间 = 23 - 1 = 22
P4 的周转时间 = 14 - 6 = 8
P5 的周转时间 = 25 - 8 = 17

P1 的等待时间 = 周转时间 (TAT) - 突发时间 (BT)
                        22 - 8 = 14
P2 的等待时间 = 6 - 2 = 4
P3 的等待时间 = 22 - 7 = 15
P4 的等待时间 = 8 - 3 = 5
P5 的等待时间 = 17 - 5 = 12

平均等待时间 = (14 + 4 + 15 + 5 + 12)/5 = 50/5 = 10

平均周转时间 = (22+6+22+8+17)/5= 75/5 = 15

具有顺序到达时间的轮循CPU调度示例

让我们通过另一个具有顺序到达时间的轮循例子来理解。这里我们有四个进程 P1、P2、P3 和 P4。每个进程的到达时间和突发时间如下表所示。时间量子是6个单位。

这是甘特图

步骤 1: 时间 0 时，进程 P1 进入就绪队列并执行其任务，时长为时间量子 6 个单位。在 6 个时间片的期间，另一个进程 P2、P3 和 P4 进入就绪队列。之后，进程 P1 将返回就绪队列的末尾等待其执行。

步骤 2: 现在，进程 P2 开始执行，时长为 5 个单位，因为突发时间 (BT) 是 5，并且它不会进入就绪队列进行进一步执行。

步骤 3: 之后，进程 P3 将开始执行，其突发时间为 10，但时间量子为 6 个单位。因此，它执行其任务直到定义的时间限制，并被添加到就绪队列的末尾。

步骤 4: 之后，进程 P4 开始执行，其突发时间为 11，但时间量子为 6 个单位。它只执行 6 秒的任务，然后添加到就绪队列的末尾。

步骤 5: P4 执行完毕后，现在 P1 将再次执行 2 个单位或秒，并且进程 P1 终止或结束。同样，在 P1 完全执行后，P3 开始其剩余的突发时间 4 的执行，进程完成。

步骤 6: P3 完全执行后，现在进程 P4 执行剩余的时间片，即 5，并且进程完成。

现在我们找出完成时间、周转时间、等待时间以及平均TAT和等待时间。

P1 的完成时间是：25
P2 的完成时间是：11
P3 的完成时间是：29
P4 的完成时间是：34

周转时间: 完成时间 (CT) - 到达时间 (AT)
对于进程 P1: 25 - 0 = 25
对于进程 P2: 11 -1 = 10
对于进程 P3: 29 - 2 = 27
对于进程 P4: 34 - 3 = 31
平均周转时间是: (25+10+27+31)/4 = 23.25

进程等待时间

P1 = 25-8 =17
P2 = 10-5 =5
P3 = 27-10= 17
P4 = 31-11=20
平均等待时间是 (17+5+17+20)/4 = 59/4 = 14.75

用C语言编写轮循CPU调度程序。

输出