CODEWITHSUNDEEP
cscheduling
Brian Brown
Brian Brown

Reputation: 4311

How to calculate average waiting time in round robin?

Watching this: https://www.youtube.com/watch?v=GjrxO-PDPdk video on YouTube has inspired me to implement the Round Robin algorithm in C:

#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;
}

This is my very first approach to scheduling, and it seems it works as needed (is it?). However, I have some troubles calculating average waiting time. I got:

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

instead of:

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

Upvotes: 2

Views: 2627

Answers (1)

chux
chux

Reputation: 153338

Code could record when each process stopped and note when it started. It is this difference that is the wait.
Further, when a fraction of time quanta is used, only accumulate that portion.

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;
}

Code could be run with unsigned time values rather than int. There is no negative accumulation nor elapsed time.

Note: Code could initialize t with the current time and get the same results. (time types should then be time_t)

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

Upvotes: 1

Related Questions