Preemptive Shortest Job First Scheduling

Preemptive Shortest Job First Scheduling is the another technique to schedule process but many students find it difficult to implement when it comes to solve a numerical based on it. But trust me, it is the simplest Scheduling algorithm. I will teach you everything about Preemptive Shortest Job First Scheduling in a very easy and interesting way so that you won't find it confusing.At the end I will also give code to execute Preemptive Shortest Job First Scheduling in C++. So let's start shall we?

In Non-Preemptive Shortest Job First Scheduling a process was executed until its ended and no other process was preempted in between the execution of that process. But in Preemptive Shortest Job First Scheduling a process can preempt a process if its burst time is less than the remaining burst time of a process which is currently being executed. That's why Preemptive Shortest Job First Scheduling is also called as Shortest Remaining Time First Scheduling Algorithm.

Numerical:

Draw the gantt chart for the table of processes given below. Also find the waiting time and turn around time of each process.

I will be taking another table T which will help us in determining the remaining time of a process.
1. P1 has arrival time 0 thus it will be scheduled for 1ms. Now, remaining time for P1 is 6ms and it will be added to T.
2. At arrival time 1, P2 has arrived, but we will select the shortest burst time process among table T and this P2. Clearly, P2 has short burst time than P1 so P2 will be scheduled for 1ms. Now, remaining time for P2 is 4ms and it will be added to T.
3. At arrival time 2, P3 has arrived, but we will select the shortest burst time process among table T and this P3. In table T we have process P1 with burst time 6ms and P2 with burst time 4ms. Clearly, P3 has shortest burst time among P3 and table T so P3 will be scheduled for 1ms. Now, remaining time for P3 is 2ms and it will be added to table T.
4. At arrival time 3, P4 has arrived, but we will select the shortest burst time process among table T and this P4. In table T we have P1 with burst time 6ms ,P2 with burst time 4ms and P3 with burst time 2ms. Clearly, P4 has the shortest burst time among P4 and table T so P4 will be scheduled for 1ms. Now, remaining time for P4 is 0ms hence it has completed execution and it won' t be added to table T.
5. At arrival time 4, P5 has arrived, but we will select the shortest burst time process among table T and this P5. In table T we have P1 with burst time 6ms ,P2 with burst time 4ms and P3 with burst time 2ms. Clearly, P3 and P5 have same burst time 2ms so we have to select the process with lowest arrival time which is P3. Thus P3 will be scheduled for 1ms. Now, remaining time for P3 is 1ms and P5 will be added to table T.
6. At arrival time 5, P6 has arrived, but we will select the shortest burst time process among table T and this P6. In table T we have P1 with burst time 6ms, P2 with burst time 4ms, P3 with burst time 1ms and P5 with burst time 2ms. Clearly, P6 and P3 have same burst time 1ms so we will schedule the process P3 because it has the lowest arrival time. Now, remaining time for P3 is 0ms so it is removed from table T and P6 is added to table T.
7. Since no other process has arrived after P6 thus we can schedule the remaining processes in table T according to non-preemptive SJF.
8. In table T we have P1 with burst time 6ms , P2 with burst time 4ms , P5 with burst time 2ms and P6 with burst time 1ms. Since P6 has shortest burst time so it be scheduled next for 1ms.
9. In table T we have P1 with burst time 6ms , P2 with burst time 4ms and P5 with burst time 2ms. Since P5 has shortest burst time so it be scheduled next for 2ms.
10. In table T we have P1 with burst time 6ms and P2 with burst time 4ms. Since P2 has shortest burst time so it be scheduled next for 4ms.
11. In table T we have P1 only with burst time 6ms.So, P6 will be scheduled for next for 6ms.
Gantt Chart:

Waiting Time for each process

Waiting time is computed by the formula starting execution time - arrival time of a process.
Process Starting execution time - arrival time Waiting time
P1 19 - 7 12
P2 12 - 5 7
P3 4 - 3 1
P4 1 - 1 0
P5 5 - 2 3
P6 2 - 1 1

Turn around Time for each Process

Turn around time is computed by the formula completion time - arrival time of a process.
Process Completion time - arrival time Waiting time
P1 19 - 0 19
P2 13 - 1 12
P3 6 - 2 4
P4 4 - 3 1
P5 9 - 4 5
P6 7 - 5 2

Implementation in C++

// C++ program to implement Shortest Remaining Time First 
// Shortest Remaining Time First (SRTF) 

#include <bits/stdc++.h> 
using namespace std; 

struct Process { 
 int pid; // Process ID 
 int bt; // Burst Time 
 int art; // Arrival Time 
}; 

// Function to find the waiting time for all 
// processes 
void findWaitingTime(Process proc[], int n,int wt[]) 
{ 
 int rt[n]; 

 // Copy the burst time into rt[] 
 for (int i = 0; i < n; i++) 
  rt[i] = proc[i].bt; 

 int complete = 0, t = 0, minm = INT_MAX; 
 int shortest = 0, finish_time; 
 bool check = false; 

 // Process until all processes gets 
 // completed 
 while (complete != n) { 

  // Find process with minimum 
  // remaining time among the 
  // processes that arrives till the 
  // current time` 
  for (int j = 0; j < n; j++) { 
   if ((proc[j].art <= t) && 
   (rt[j] < minm) && rt[j] > 0) { 
    minm = rt[j]; 
    shortest = j; 
    check = true; 
   } 
  } 

  if (check == false) { 
   t++; 
   continue; 
  } 

  // Reduce remaining time by one 
  rt[shortest]--; 

  // Update minimum 
  minm = rt[shortest]; 
  if (minm == 0) 
   minm = INT_MAX; 

  // If a process gets completely 
  // executed 
  if (rt[shortest] == 0) { 

   // Increment complete 
   complete++; 
   check = false; 

   // Find finish time of current 
   // process 
   finish_time = t + 1; 

   // Calculate waiting time 
   wt[shortest] = finish_time - 
      proc[shortest].bt - 
      proc[shortest].art; 

   if (wt[shortest] < 0) 
    wt[shortest] = 0; 
  } 
  // Increment time 
  t++; 
 } 
} 

// Function to calculate turn around time 
void findTurnAroundTime(Process proc[], int n,int wt[], int tat[]) 
{ 
 // calculating turnaround time by adding 
 // bt[i] + wt[i] 
 for (int i = 0; i < n; i++) 
  tat[i] = proc[i].bt + wt[i]; 
} 

// Function to calculate average time 
void findavgTime(Process proc[], int n) 
{ 
 int wt[n], tat[n], total_wt = 0, total_tat = 0; 

 // Function to find waiting time of all 
 // processes 
 findWaitingTime(proc, n, wt); 

 // Function to find turn around time for 
 // all processes 
 findTurnAroundTime(proc, n, wt, tat); 

 // Display processes along with all 
 // details 
 cout << "Processes "
  << " Burst time "
  << " Waiting time "
  << " Turn around time\n"; 

 // Calculate total waiting time and 
 // total turnaround time 
 for (int i = 0; i < n; i++) { 
  total_wt = total_wt + wt[i]; 
  total_tat = total_tat + tat[i]; 
  cout << " " << proc[i].pid << "\t\t"
   << proc[i].bt << "\t\t " << wt[i] 
   << "\t\t " << tat[i] << endl; 
 } 

 cout << "\nAverage waiting time = "
  << (float)total_wt / (float)n; 
 cout << "\nAverage turn around time = "
  << (float)total_tat / (float)n; 
} 

// Driver code 
int main() 
{ 
 Process proc[] = { { 1, 6, 1 }, { 2, 8, 1 }, { 3, 7, 2 }, { 4, 3, 3 } }; 
 int n = sizeof(proc) / sizeof(proc[0]); 

 findavgTime(proc, n); 
 return 0; 
}

OUTPUT:

Preemptive Shortest Job First Scheduling

Contact Form