Round Robin调度IDLE场景下平均等待/周转时间计算错误修复

问题描述 #

• 实现RR调度算法时，无就绪进程触发CPU IDLE空闲状态的场景下，平均等待时间、平均周转时间计算结果存在偏差
• 复现测试用例（共4个进程，第一列为到达时间Arrival Time，第二列为运行时间Burst Time）：

0 3
0 5
9 8
10 6

• 该用例正确结果为平均等待时间3.5、平均周转时间9，原代码运行输出为平均等待时间5、平均周转时间10。原代码已标注IDLE逻辑位置，最初尝试通过扣减save变量值修正统计，但未解决核心逻辑错误。
• 原问题实现代码如下：

#include <stdio.h>
int main()
{
   int i, total = 0, x, limit, counter = 0, t_quantum;
   int wait_time = 0, turnaround_time = 0, arrival_time[10], burst_time[10], temp[10];

   float average_wait_time, average_turnaround_time;

   printf("\nEnter Total Number of Processes: ");
   scanf("%d", &limit);
   x = limit;

   for (i = 0; i < limit; i++)
   {
      printf("\nProvide the details for Process[%d]\n", i + 1);
      printf("Arrival Time:\t");
      scanf("%d", &arrival_time[i]);
      printf("Burst Time:\t");
      scanf("%d", &burst_time[i]);
      temp[i] = burst_time[i];
   }

   printf("\nEnter Time Quantum:\t");
   scanf("%d", &t_quantum);
        int save = 0;
   printf("\nProcess ID\t\tBurst Time\t Turnaround Time\t Waiting Time\n");
   for (total = 0, i = 0; x != 0;)
   {
      if (temp[i] <= t_quantum && temp[i] > 0)
      {
         total = total + temp[i];
         temp[i] = 0;
         counter = 1;
      }
      else if (temp[i] > 0)
      {
         temp[i] = temp[i] - t_quantum;
         total = total + t_quantum;
      }

      if (temp[i] == 0 && counter == 1)
      {
         x--;
         printf("\nProcess[%d]\t\t%d\t\t %d\t\t\t %d", i + 1, burst_time[i], total - arrival_time[i], total - arrival_time[i] - burst_time[i]);
         wait_time = wait_time + total - arrival_time[i] - burst_time[i];
         save = total - arrival_time[i] - burst_time[i];
         turnaround_time = turnaround_time + total - arrival_time[i];
         counter = 0;
      }

      if (i == limit - 1)
      {
         i = 0;
      }
      else if (arrival_time[i + 1] <= total)
      {
         i++;
      }
      else
      {
         // IDLE when temp[i] == 0
         i++;
      }
   }

   average_wait_time = wait_time *1.0 / limit;
   average_turnaround_time = turnaround_time *1.0 / limit;
 

   printf("\n\nAverage Waiting Time:\t%f", average_wait_time);
   printf("\nAvg Turnaround Time:\t%f\n", average_turnaround_time);

   return 0;
}

错误根因 #

1. 缺少进程到达校验：执行进程前没有判断进程是否已经到达，当CPU进入IDLE状态、代码遍历到未到达的进程时，会直接为该进程累加执行时间、推进系统时间，把IDLE时间段错误算入进程运行周期
2. IDLE逻辑缺失：没有处理空闲时间跳跃逻辑，当所有已到达进程执行完毕后，代码不会直接跳转到下一个进程的到达时间，反而空转遍历甚至执行未到达进程
3. 修复思路偏差：已完成进程的等待、周转时间在进程终止时已经计算完成，IDLE时段与已完成进程无关，扣减save变量存储的已完成进程统计值属于错误方向

修复后代码 #

#include <stdio.h>
#include <limits.h>
int main()
{
   int i, total = 0, x, limit, counter = 0, t_quantum;
   int wait_time = 0, turnaround_time = 0, arrival_time[10], burst_time[10], temp[10];
   float average_wait_time, average_turnaround_time;

   printf("\nEnter Total Number of Processes: ");
   scanf("%d", &limit);
   x = limit;

   for (i = 0; i < limit; i++)
   {
      printf("\nProvide the details for Process[%d]\n", i + 1);
      printf("Arrival Time:\t");
      scanf("%d", &arrival_time[i]);
      printf("Burst Time:\t");
      scanf("%d", &burst_time[i]);
      temp[i] = burst_time[i];
   }

   printf("\nEnter Time Quantum:\t");
   scanf("%d", &t_quantum);
   printf("\nProcess ID\t\tBurst Time\t Turnaround Time\t Waiting Time\n");
   
   for (total = 0, i = 0; x != 0;)
   {
      int is_idle = 1;
      // 检查当前是否存在就绪进程
      for(int j = 0; j < limit; j++){
          if(temp[j] > 0 && arrival_time[j] <= total){
              is_idle = 0;
              break;
          }
      }
      // IDLE状态直接跳转到最近未完成进程的到达时间
      if(is_idle){
          int next_arrive = INT_MAX;
          for(int j = 0; j < limit; j++){
              if(temp[j] > 0 && arrival_time[j] < next_arrive){
                  next_arrive = arrival_time[j];
              }
          }
          total = next_arrive;
      }

      // 跳过已完成、未到达的无效进程
      if(temp[i] == 0 || arrival_time[i] > total){
          i = (i + 1) % limit;
          continue;
      }

      if (temp[i] <= t_quantum && temp[i] > 0)
      {
         total += temp[i];
         temp[i] = 0;
         counter = 1;
      }
      else if (temp[i] > 0)
      {
         temp[i] -= t_quantum;
         total += t_quantum;
      }

      if (temp[i] == 0 && counter == 1)
      {
         x--;
         int proc_turnaround = total - arrival_time[i];
         int proc_wait = proc_turnaround - burst_time[i];
         printf("\nProcess[%d]\t\t%d\t\t %d\t\t\t %d", i + 1, burst_time[i], proc_turnaround, proc_wait);
         wait_time += proc_wait;
         turnaround_time += proc_turnaround;
         counter = 0;
      }
      i = (i + 1) % limit;
   }

   average_wait_time = wait_time * 1.0 / limit;
   average_turnaround_time = turnaround_time * 1.0 / limit;

   printf("\n\nAverage Waiting Time:\t%f", average_wait_time);
   printf("\nAvg Turnaround Time:\t%f\n", average_turnaround_time);

   return 0;
}

修复说明 #

• 每次调度前先校验全局就绪状态，IDLE时直接将系统时间跳转到最早的未完成进程到达点，完全跳过空闲时段，避免无效时间被计入进程统计
• 调整进程索引轮转逻辑，用模运算实现环形遍历，自动跳过已完成、未到达的进程，执行进程前增加到达校验，杜绝未到达进程被提前调度的问题
• 删除无效的save变量相关逻辑，进程终止时直接计算准确的等待、周转时间，无需后续二次扣减
• 传入测试用例、设置时间片为3运行修复后代码，可输出平均等待时间3.5、平均周转时间9的正确结果

内容的提问来源于stack exchange，提问作者markio