Shortest Job First Scheduling Algorithm in C issues

Question

I have created a C Program to simulate the Non-Preemptive Shortest Job First Algorithm but it has bugs with certain inputs. The shortest job first algorithm program takes in inputs for the arrival and burst times of the required number of processes and arranges the processes in 2 phases. The first phase involves arranging the program by arrival times and the 2nd phase arranges them by burst times given that their arrival times are lower than the time for the previous process to complete. This is all then compiled in the end and shown.

#include <stdio.h>

// n - total processes
// p - process no. array
// bt - burst time array
// at - arrival time array
// wt - the time taken for the process to start from it's arrival time array
// tat - time spent by process in cpu array
int i, n, j, m, min, sum = 0, x = 1, btTally = 0, p[20], bt[20], at[20], wt[20], tat[20], ta = 0;
float tatTally = 0, wtTally = 0;

//function grabs arrival and burst times of each process and stores it in its respective array
void getInput(){
    printf("\nEnter the total number of processes: ");
    scanf("%d", & n);

    // For Loop for user to input info about the processes
    for (i = 0; i < n; i++) {
        p[i] = i + 1;
        printf("\nEnter the arrival time of process %d: ", p[i]);
        scanf(" %d", & at[i]);
        printf("\nEnter the burst time of process %d: ", p[i]);
        scanf(" %d", & bt[i]);
    }
}

//Function arranges processes according to their arrival times
void arrangePhase1(){
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (at[j] > at[i]) {
                m = p[j];
                p[j] = p[i];
                p[i] = m;

                m = at[j];
                at[j] = at[i];
                at[i] = m;

                m = bt[j];
                bt[j] = bt[i];
                bt[i] = m;
            }
        }
    }
}

//Function arranges the processes according to Burst time
void arrangePhase2(){
    for (i = 0; i < n; i++) {
        btTally = btTally + bt[i];
        min = bt[x];
        for (j = x; j < n; j++) {
            if (bt[j] < min && btTally >= at[j]) {
                m = p[x];
                p[x] = p[j];
                p[j] = m;

                m = at[x];
                at[x] = at[j];
                at[j] = m;

                m = bt[x];
                bt[x] = bt[j];
                bt[j] = m;
            }
        }
        x++;
    }
}

//Function calculates the tallies of turnaround time and waiting time
void calcTallies(){
    for (i = 0; i < n; i++) {
        ta = ta + bt[i];
        tat[i] = ta - at[i];
        tatTally = tatTally + tat[i];
    }

    wt[0] = 0;
    for (i = 1; i < n; i++) {
        sum = sum + bt[i - 1];
        wt[i] = sum - at[i];
        wtTally = wtTally + wt[i];
    }

}

//Function displays all of the information about the algorithm running
void showFinal(){
    printf("\nProcess\t Arrival Time\t Burst Time\t Waiting Time\t Turnaround Time");
    for (i = 0; i < n; i++) {
        printf("\n p%d\t %d\t\t %d\t\t %d\t\t %d", p[i], at[i], bt[i], wt[i], tat[i]);
    }

    printf("\nAverage Waiting Time: %.2f", (wtTally / n));
    printf("\nAverage Turn Around Time: %.2f", (tatTally / n));
}

int main() {
    getInput();
    arrangePhase1();
    arrangePhase2();
    arrangePhase2();
    calcTallies();
    showFinal();
    return 0;
}

These are the expected results:

These are the results I get with my programme:

Any help would really be appreciated. Thanks!

Answer 1

I ... rearrange your program a bit ...

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

typedef struct {
  int p, at, bt, wt, tat;
} Job;
#define maxN (20)
Job jobs[maxN ];
int n, btTally = 0, sum = 0, ta = 0;
float tatTally = 0, wtTally = 0;

#define TestSize (5)
Job Test[TestSize] = {
  { 1, 2, 1, 0, 0 },
  { 2, 1, 5, 0, 0 },
  { 3, 4, 1, 0, 0 },
  { 4, 0, 6, 0, 0 },
  { 5, 2, 3, 0, 0 }
};

void getInput(){
    int i;
    printf("\nEnter the total number of processes: ");
    scanf("%d", & n);

    if (n == 0) {
      for (i = 0; i < TestSize; ++i)
        jobs[i] = Test[i];
      n = TestSize;
      return;
    }

    // For Loop for user to input info about the processes
    for (i = 0; i < n; i++) {
        jobs[i].p = i + 1;
        printf("\nEnter the arrival time of process %d: ", jobs[i].p);
        scanf(" %d", & jobs[i].at);
        printf("\nEnter the burst time of process %d: ", jobs[i].p);
        scanf(" %d", & jobs[i].bt);
    }
}

int compareAT (const void * a, const void * b) {
  Job *jobA = (Job *)a;
  Job *jobB = (Job *)b;

  return ( jobA->at - jobB->at );
}

void arrangePhase1(){
  qsort (jobs, n, sizeof(Job), compareAT);
}

void Swap(int i, int j) {
  Job m = jobs[i];
  jobs[i] = jobs[j];
  jobs[j] = m;
}



void calcTallies(){
    int i;
    for (i = 0; i < n; i++) {
        ta = ta + jobs[i].bt;
        jobs[i].tat = ta - jobs[i].at;
        tatTally = tatTally + jobs[i].tat;
    }

    jobs[0].wt = 0;
    for (i = 1; i < n; i++) {
        sum = sum + jobs[i - 1].bt;
        jobs[i].wt = sum - jobs[i].at;
        wtTally = wtTally + jobs[i].wt;
    }
}

void showFinal(){
    int i;
    printf("\nProcess\t Arrival Time\t Burst Time\t Waiting Time\t Turnaround Time");
    for (i = 0; i < n; i++) {
        printf("\n p%d\t %d\t\t %d\t\t %d\t\t %d", jobs[i].p, jobs[i].at, jobs[i].bt, jobs[i].wt, jobs[i].tat);
    }

    printf("\nAverage Waiting Time: %.2f", (wtTally / n));
    printf("\nAverage Turn Around Time: %.2f", (tatTally / n));
}

void arrangePhase2() {
    int i, j, min, x = 1;

    for (i = 0; i < n; i++) {
        btTally = btTally + jobs[i].bt;
        min = jobs[x].bt;
        for (j = x; j < n; j++) {
            if (jobs[j].bt < min && btTally >= jobs[j].at) {
              Swap(x, j);
              min = jobs[x].bt;
              showFinal();
            }
        }
        x++;
    }
}

int main() {
    getInput();
    arrangePhase1();
    showFinal();
    arrangePhase2();
//    arrangePhase2();
    calcTallies();
    showFinal();
    return 0;
}

And left some test and prints in it.

The main problem is that the min is not updated. Try to add the update to your original program and see if it works. Next is to move the int i,j; to the functions, does it work now? (it wont work without this if you just add the showFinal(); test to your code).

Now the code I made is not the one true truth, it is just an example from someone who hasn't programmed C in decades.

Short code review. Using globals are bad in C, you easily gets a problem with your loops if you use globals for loop control, here i,j is reused a lot.

You could use structs more, at least for the 3 main values, makes some of the sorting a bit easier. In either case having a Swap function makes the code easier to check and understand.

void SwapInt(int *i, int *j) {
  int m = *i;
  *i = *j;
  *j = m;
}

SwapInt(&at[i], &at[j]); // example of calling swapping

The 2nd call to arrangePhase2(); doesn't do anything.