C++: Shortest Job First Preemptive CPU Scheduling Algorithm

Shortest job first (SJF), also known as shortest job next (SJN) or shortest process next (SPN), is a scheduling policy that selects for execution the waiting process with the smallest execution time. SJN is a non-preemptive algorithm. Shortest remaining time is a preemptive variant of SJN.

Shortest job next is advantageous because of its simplicity and because it minimizes the average amount of time each process has to wait until its execution is complete. However, it has the potential for process starvation for processes which will require a long time to complete if short processes are continually added. Highest response ratio next is similar but provides a solution to this problem using a technique called aging.

Another disadvantage of using shortest job next is that the total execution time of a job must be known before execution. While it is impossible to predict execution time perfectly, several methods can be used to estimate it, such as a weighted average of previous execution times.

Shortest job next can be effectively used with interactive processes which generally follow a pattern of alternating between waiting for a command and executing it. If the execution burst of a process is regarded as a separate "job", past behaviour can indicate which process to run next, based on an estimate of its running time.

Shortest job next is used in specialized environments where accurate estimates of running time are available. [Wikipedia]

Here we have used some features of C++11. Algorithm Library will help to understand them.


This program also uses the concept of Inheritance.

Data members and member functions which are common to all scheduling algorithm are declared in scheduling.h and member functions are declared in scheduling.cpp . virtual keyword is used before calcEndTime() because each scheduling algorithm has different algorithm to calculate end time.

Turnaround time and waiting time are calculated using these formulas.


turnAroundTime = endTime - arrivalTime
waitingTime = turnAroundTime - burstTime

Here is the C++ implementation




You can compile with this command in Linux g++ -std=c++11 shortestjobfirst.cpp scheduling.cpp 

Output
Shortest Job First Preemptive

                                                                  
                                                                  
Reference:
 

Other CPU Scheduling Algorithms 
C++: Priority Preemptive CPU Scheduling Algorithm 
C++: Round Robin CPU Scheduling Algorithm 

Comments