Implementing CPU Scheduling Algorithm: Shortest Job First (SJF)

Mode

Non-Preemptive

Selection Criteria

Burst Time

Understanding the Algorithm

Process Id	Arrival Time	Burst Time
P1	0	1
P2	2	3
P3	2	2

After executing P1, we will search for the next process to execute. We can see that both P2 and P3 arrived within 1 unit of time (P1 took 1 unit of time earlier), but since P3 has a smaller burst time, it will be executed first.

We will repeat these steps like this until we have no incomplete processes.

Before we dive into coding, let's understand a few things.

For our convenience, we will create a user-defined data type to store process information using a structure instead of using 2D or 3D arrays, maps or lists (as you will see on most websites).
```
 struct Process {
   int pid;
   int burst_time;
   int arrival_time;
   int waiting_time;
   int turnaround_time;
   bool is_completed;
 };
```
We know that processes are sorted by their arrival time. Therefore, we will create a comparison function to help us sort the processes by arrival time.
```
 bool sort_by_at(Process a, Process b) {
     return a.arrival_time < b.arrival_time;
 }
```
N.B: You can learn more about comparator functions in C++ by checking out various tutorials available on the web.
We will need a loop that runs until all processes have finished executing.
We also need a counter to track the number of completed processes. Since we don't know how long the loop will run, when the counter equals the total number of processes, the loop will break.

Whenever a process finishes, we search for the next process in the ready queue with the shortest burst time.

 for (int i = 0; i < total_processes; ++i) {
   if (!processes[i].is_completed 
    && processes[i].arrival_time <= elapsed_time 
    && processes[i].burst_time < min_burst_time) {
     idx = i;
     min_burst_time = processes[i].burst_time;
   }
 }

After identifying an incomplete process available to run, we will mark it as completed.We will then calculate the turnaround time and waiting time. Finally we will increase the counter for completed processes.

  processes[idx].turnaround_time =
      (elapsed_time + processes[idx].burst_time) -
      (processes[idx].arrival_time);

  processes[idx].waiting_time =
      processes[idx].turnaround_time - processes[idx].burst_time;
  elapsed_time += processes[idx].burst_time;
  processes[idx].is_completed = true;
  completed++;

If we don't get any incomplete process, we will simply increase the system time as the system will be idle.
```
  elapsed_time++;
```

Implementing SJF in C++

It's time to put all the pieces together!

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>

using namespace std;

struct Process {
 public:
  int pid;
  int arrival_time;
  int burst_time;
  int turnaround_time;
  int waiting_time;
  bool is_completed;
};

class SJF {
 public:
  vector<Process> processes;
  float avg_turnaround_time;
  float avg_waiting_time;

  static bool sort_by_at(Process a, Process b) {
    return a.arrival_time < b.arrival_time;
  }

  void calculate() {
    int total_waiting_time = 0;
    int total_turnaround_time = 0;
    int elapsed_time = 0;
    int n = processes.size();

    sort(processes.begin(), processes.end(), this->sort_by_at);

    int completed = 0;
    while (completed < n) {
      int idx = -1;
      int curr_min_burst_time = INT_MAX;

      for (int i = 0; i < n; ++i) {
        if (!processes[i].is_completed &&
            processes[i].arrival_time <= elapsed_time &&
            processes[i].burst_time < curr_min_burst_time) {
          idx = i;
          curr_min_burst_time = processes[i].burst_time;
        }
      }

      if (idx == -1) {
        elapsed_time++;
      } else {
        processes[idx].turnaround_time =
            (elapsed_time + processes[idx].burst_time) -
            (processes[idx].arrival_time);

        processes[idx].waiting_time =
            processes[idx].turnaround_time - processes[idx].burst_time;
        elapsed_time += processes[idx].burst_time;
        processes[idx].is_completed = true;

        total_waiting_time += processes[idx].waiting_time;
        total_turnaround_time += processes[idx].turnaround_time;
        completed++;
      }
    }
    avg_waiting_time = (float)total_waiting_time / n;
    avg_turnaround_time = (float)total_turnaround_time / n;
  }

  void debug() {
    for (auto i : processes)
      printf("%d %d\n", i.turnaround_time, i.waiting_time);
  }

  void input() {
    int n;

    cout << "Enter the number of process:" << endl;
    cin >> n;

    vector<Process> temp(n);

    cout << "Enter the arrival times" << endl;
    for (int i = 0; i < n; ++i) cin >> temp[i].arrival_time;

    cout << "Enter the burst times:" << endl;
    for (int i = 0; i < n; ++i) {
      temp[i].pid = i + 1;
      cin >> temp[i].burst_time;
    }

    this->processes = temp;
  }

  void output() {
    for (auto i : processes) {
      printf("Process %d: Turnaround Time: %d Waiting Time: %d\n", i.pid,
             i.turnaround_time, i.waiting_time);
    }

    printf("Average Waiting time: %.2f\n", avg_waiting_time);
    printf("Average Turnaround time: %.2f", avg_turnaround_time);
  }
};

int main() {
  SJF obj;
  obj.input();
  obj.calculate();
  obj.output();
}

Conclusion

When I first attempted to implement it, it seemed quite tough, but in theory, it looked straightforward. I could easily work it out on paper! After wasting a day and a half, I finally managed to implement the algorithm!

I hope you now understand how to implement SJF. I did my best to make the code as easy and understandable as possible.

Credits

Adeela Mushtaq: for the YouTube video tutorial she did. Her code was the easiest to understand.
Mr. Varun Singla (Gate Smashers): for the YouTube video he did. It helped me to clear out the theoretical part.
Hashnode: for the amazing platform.