c - 如何计算循环法中的平均等待时间？

Question

正在观看:https://www.youtube.com/watch?v=GjrxO-PDPdk YouTube 上的视频启发了我用 C 语言实现 Round Robin 算法:

#include <stdio.h>
#include <stdlib.h>

int check_if_done(int processes[], int n)
{
    int i;
    for(i=0; i<n; i++)
        if(processes[i] > 0)
            return 0;
    return 1;
}

int main()
{
    int processes[5];
    int waiting_times[5];

    processes[0] = 6;
    processes[1] = 5;
    processes[2] = 2;
    processes[3] = 3;
    processes[4] = 7;

    int tq = 2;
    int i = 0, j, n = 5;

    for(j=0; j<n; j++)
        waiting_times[j] = 0;

    while(1)
    {
        if(check_if_done(processes, n))
            break;

        if(processes[i] > 0)
        {
            printf("P%d = %d\n", i+1, processes[i]);
            waiting_times[i] += processes[i];
            processes[i] -= tq;
        }
        i ++;
        if(i == n)
        {
            printf("\n");
            i = 0;
        }
    }

    printf("\n");
    for(i=0; i<n; i++)
    {
        printf("P%d waiting time = %d\n", (i+1), waiting_times[i]);
    }

    return 0;
}

这是我的第一个日程安排方法，它似乎可以按需工作(是吗？)。但是，我在计算平均等待时间时遇到了一些麻烦。我得到了:

P1 waiting time = 12
P2 waiting time = 9
P3 waiting time = 2
P4 waiting time = 4
P5 waiting time = 16

代替:

P1 waiting time = 13
P2 waiting time = 15
P3 waiting time = 4
P4 waiting time = 12
P5 waiting time = 16

Answer 1

代码可以记录每个进程何时停止并记录何时开始。 等待就是这个区别。
此外，当使用一小部分时间量子时，仅累积该部分。

int main(void) {
  int last_run[5];
  int processes[5];
  int waiting_times[5];

  processes[0] = 6;
  processes[1] = 5;
  processes[2] = 2;
  processes[3] = 3;
  processes[4] = 7;

  int tq = 2;
  int i = 0, j, n = 5;

  int t = 0;  // cumulative time.
  for (j = 0; j < n; j++) {
    last_run[j] = t;  // All processes scheduled at t = 0
    waiting_times[j] = 0;
  }

  while (!check_if_done(processes, n)) {
    if (processes[i] > 0) {
      printf("P%d = %d\n", i + 1, processes[i]);
      waiting_times[i] += t - last_run[i];  // now - last runtime
      int t_used = processes[i];
      if (t_used > tq)   // If time needed more than tq ...
        t_used = tq;  
      processes[i] -= t_used;
      t += t_used;  // update now
      last_run[i] = t;
    }
    i = (i + 1) % n;
  }

  printf("\n");
  for (i = 0; i < n; i++) {
    printf("P%d waiting time = %d\n", (i + 1), waiting_times[i]);
  }

  return 0;
}

代码可以使用 unsigned 时间值而不是 int 运行。没有负积累，也没有流逝的时间。

注意:代码可以用当前时间初始化 t 并得到相同的结果。 (时间类型应该是 time_t)

  // int t = 0;  // cumulative time.
  int t = time(0);