Implementation of Non-Preemptive Shortest Job First using Priority Queue
Read here for Shortest Job First Scheduling algorithm for same arrival times.
Shortest job first (SJF) or shortest job next, is a scheduling policy that selects the waiting process with the smallest execution time to execute next.
In this article, we will implement the Shortest Job First Scheduling algorithm (SJF) using a priority queue, so that we can handle processes at different arrival time.
Examples:
Input: The processes are Process id Arrival time Burst time p1 4 3 p2 0 8 p3 5 4 p4 9 2 Output: Process scheduling according to SJF is Process id Arrival time Burst time p2 0 8 p1 4 3 p4 9 2 p3 5 4 Input: The processes are Process id Arrival time Burst time p1 0 3 p2 0 8 p3 5 4 p4 9 2 Output: Process scheduling according to SJF is Process id Arrival time Burst time p1 0 3 p2 0 8 p4 9 2 p3 5 4
In this program, the task is to schedule the processes according to SJF scheduling algorithm, which states that the process with minimum burst time will be given priority, which can simply be implemented by sorting the burst time of the processes in ascending order. The problem arises when we have to handle the processes at different arrival time, then we simply can’t sort the processes according to burst time as we need to consider the arrival time of the process so that the processor doesn’t stay idle.
Example:
If a process with more burst time arrives before a process with less burst time, then we have to allow the processor time to the process that arrived first so that the processor doesn’t stay idle.
Approach:
To handle processes with a different arrival time in case of SJF scheduling:
- First, sort the processes according to the arrival time.
- Maintain a wait queue, which keeps the process with minimum burst time at the top.
- Maintain the current run time, that is the sum of burst times of the executed processes.
- A process enters the wait queue according to it’s arrival time if a new process has arrival time less than
equal to the current running time, it is pushed in the wait queue. - A process is popped from the wait queue when it is to be executed. It’s burst time is added to the current run time, it’s arrival time is updated to -1 so that it doesn’t enter the wait queue again.
- A process enters the wait queue according to it’s arrival time if a new process has arrival time less than
Below is the implementation of the above approach:
CPP
// C++ implementation of SJF #include <bits/stdc++.h> using namespace std; // number of process #define SIZE 4 // Structure to store the // process information typedef struct proinfo { string pname; // process name int atime; // arrival time int btime; // burst time } proinfo; // This structure maintains the // wait queue, using burst // time to compare. typedef struct cmpBtime { int operator()( const proinfo& a, const proinfo& b) { return a.btime > b.btime; } } cmpBtime; // This function schedules the // process according to the SJF // scheduling algorithm. void sjfNonpremetive(proinfo* arr) { // Used to sort the processes // according to arrival time int index = 0; for ( int i = 0; i < SIZE - 1; i++) { index = i; for ( int j = i + 1; j < SIZE; j++) { if (arr[j].atime < arr[index].atime) { index = j; } } swap(arr[i], arr[index]); } // ctime stores the current run time int ctime = arr[0].atime; // priority queue, wait, is used // to store all the processes that // arrive <= ctime (current run time) // this is a minimum priority queue // that arranges values according to // the burst time of the processes. priority_queue<proinfo, vector<proinfo>, cmpBtime> wait; int temp = arr[0].atime; // The first process is // pushed in the wait queue. wait.push(arr[0]); arr[0].atime = -1; cout << "Process id" << "\t" ; cout << "Arrival time" << "\t" ; cout << "Burst time" << "\t" ; cout << endl; while (!wait.empty()) { cout << "\t" ; cout << wait.top().pname << "\t\t" ; cout << wait.top().atime << "\t\t" ; cout << wait.top().btime << "\t\t" ; cout << endl; // ctime is increased with // the burst time of the // currently executed process. ctime += wait.top().btime; // The executed process is // removed from the wait queue. wait.pop(); for ( int i = 0; i < SIZE; i++) { if (arr[i].atime <= ctime && arr[i].atime != -1) { wait.push(arr[i]); // When the process once // enters the wait queue // its arrival time is // assigned to -1 so that // it doesn't enter again // int the wait queue. arr[i].atime = -1; } } } } // Driver Code int main() { // an array of process info structures. proinfo arr[SIZE]; arr[0] = { "p1" , 4, 3 }; arr[1] = { "p2" , 0, 8 }; arr[2] = { "p3" , 5, 4 }; arr[3] = { "p4" , 9, 2 }; cout << "Process scheduling " ; cout << "according to SJF is: \n" << endl; sjfNonpremetive(arr); } |
Java
// Java implementation of SJF import java.util.*; class GFG { // number of process static int SIZE = 4 ; // A class to represent the // process information static class proinfo { String pname; // process name int atime; // arrival time int btime; // burst time proinfo(String pname, int atime, int btime) { this .pname = pname; this .atime = atime; this .btime = btime; } } static void swap( int i, int idx, proinfo[] arr) { proinfo tmp = arr[i]; arr[i] = arr[idx]; arr[idx] = tmp; } // This function schedules the // process according to the SJF // scheduling algorithm. static void sjfNonpremetive(proinfo[] arr) { // Used to sort the processes // according to arrival time int index = 0 ; for ( int i = 0 ; i < SIZE - 1 ; i++) { index = i; for ( int j = i + 1 ; j < SIZE; j++) { if (arr[j].atime < arr[index].atime) { index = j; } } swap(i, index, arr); } // ctime stores the current run time int ctime = arr[ 0 ].atime; // priority queue, wait, is used // to store all the processes that // arrive <= ctime (current run time) // this is a minimum priority queue // that arranges values according to // the burst time of the processes. PriorityQueue<proinfo> wait = new PriorityQueue<proinfo>( (a, b) -> { return a.btime - b.btime; }); // The first process is // pushed in the wait queue. wait.add( new proinfo(arr[ 0 ].pname, arr[ 0 ].atime, arr[ 0 ].btime)); arr[ 0 ].atime = - 1 ; System.out.print( "Process id" + "\t" ); System.out.print( "Arrival time" + "\t" ); System.out.println( "Burst time\t" ); while (!wait.isEmpty()) { System.out.print( "\t" ); System.out.print(wait.peek().pname + "\t\t" ); System.out.print(wait.peek().atime + "\t\t" ); System.out.println(wait.peek().btime + "\t\t" ); // ctime is increased with // the burst time of the // currently executed process. ctime += wait.peek().btime; // The executed process is // removed from the wait queue. wait.remove(); for ( int i = 0 ; i < SIZE; i++) { if (arr[i].atime <= ctime && arr[i].atime != - 1 ) { wait.add( new proinfo(arr[i].pname, arr[i].atime, arr[i].btime)); // When the process once // enters the wait queue // its arrival time is // assigned to -1 so that // it doesn't enter again // int the wait queue. arr[i].atime = - 1 ; } } } } // Driver Code public static void main(String[] args) { // an array of process info structures. proinfo[] arr = new proinfo[SIZE]; arr[ 0 ] = new proinfo( "p1" , 4 , 3 ); arr[ 1 ] = new proinfo( "p2" , 0 , 8 ); arr[ 2 ] = new proinfo( "p3" , 5 , 4 ); arr[ 3 ] = new proinfo( "p4" , 9 , 2 ); System.out.print( "Process scheduling " ); System.out.println( "according to SJF is: \n" ); sjfNonpremetive(arr); } } // This code is contributed by Karandeep Singh |
Python3
# Python 3 implementation of SJF import heapq as hq # number of process SIZE = 4 # This function schedules the # process according to the SJF # scheduling algorithm. def sjfNonpremetive(arr): # Used to sort the processes # according to arrival time index = 0 for i in range (SIZE - 1 ): index = i for j in range (i + 1 , SIZE) : if (arr[j][ 1 ] < arr[index][ 1 ]) : index = j arr[i], arr[index] = arr[index],arr[i] # ctime stores the current run time ctime = arr[ 0 ][ 1 ] # priority queue, wait, is used # to store all the processes that # arrive <= ctime (current run time) # this is a minimum priority queue # that arranges values according to # the burst time of the processes. wait = [] temp = arr[ 0 ][ 1 ] # The first process is # pushed in the wait queue. hq.heappush(wait,arr[ 0 ].copy()) arr[ 0 ][ 1 ] = - 1 print ( "Process id" ,end = "\t" ) print ( "Arrival time" ,end = "\t" ) print ( "Burst time" ,end = "\t" ) print () while (wait) : print (end = "\t" ) print (wait[ 0 ][ 2 ],end = "\t\t" ) print (wait[ 0 ][ 1 ],end = "\t\t" ) print (wait[ 0 ][ 0 ],end = "\t\t" ) print () # ctime is increased with # the burst time of the # currently executed process. ctime + = wait[ 0 ][ 0 ] # The executed process is # removed from the wait queue. hq.heappop(wait) for i in range (SIZE): if (arr[i][ 1 ] < = ctime and arr[i][ 1 ] ! = - 1 ) : hq.heappush(wait,arr[i].copy()) # When the process once # enters the wait queue # its arrival time is # assigned to -1 so that # it doesn't enter again # int the wait queue. arr[i][ 1 ] = - 1 # Driver Code if __name__ = = '__main__' : # an array of process info structures. arr = [ None ] * SIZE arr[ 0 ] = [ 3 , 4 , "p1" ] arr[ 1 ] = [ 8 , 0 , "p2" ] arr[ 2 ] = [ 4 , 5 , "p3" ] arr[ 3 ] = [ 2 , 9 , "p4" ] print ( "Process scheduling according to SJF is: \n" ) sjfNonpremetive(arr) |
Javascript
// JavaScript implementation of SJF // number of process const SIZE = 4; // A class to represent the // process information class ProInfo { constructor(pname, atime, btime) { this .pname = pname; this .atime = atime; this .btime = btime; } } const swap = (i, idx, arr) => { const tmp = arr[i]; arr[i] = arr[idx]; arr[idx] = tmp; }; // This function schedules the // process according to the SJF // scheduling algorithm. const sjfNonPremetive = arr => { // Used to sort the processes // according to arrival time let index = 0; for (let i = 0; i < SIZE - 1; i++) { index = i; for (let j = i + 1; j < SIZE; j++) { if (arr[j].atime < arr[index].atime) { index = j; } } swap(i, index, arr); } // ctime stores the current run time let ctime = arr[0].atime; // wait is used to store all the processes that // arrive <= ctime (current run time) // this is an array that arranges values according to // the burst time of the processes. let wait = []; // The first process is // pushed in the wait queue. wait.push( new ProInfo(arr[0].pname, arr[0].atime, arr[0].btime)); arr[0].atime = -1; console.log( "Process\tArrival\tBurst\t" ); while (wait.length > 0) { wait.sort((a, b) => a.btime - b.btime); const process = wait.shift(); console.log(`\t${process.pname}\t\t${process.atime}\t\t${process.btime}\t\t`); // ctime is increased with // the burst time of the // currently executed process. ctime += process.btime; for (let i = 0; i < SIZE; i++) { if (arr[i].atime <= ctime && arr[i].atime !== -1) { wait.push( new ProInfo(arr[i].pname, arr[i].atime, arr[i].btime)); // When the process once // enters the wait queue // its arrival time is // assigned to -1 so that // it doesn't enter again // int the wait queue. arr[i].atime = -1; } } } }; // Driver Code console.log( "Process scheduling according to SJF is: \n" ); const arr = [ new ProInfo( "p1" , 4, 3), new ProInfo( "p2" , 0, 8), new ProInfo( "p3" , 5, 4), new ProInfo( "p4" , 9, 2)]; console.log( "Process scheduling " ); console.log( "According to SJF is: \n" ); sjfNonPremetive(arr); // This code is contributed by anskalyan3 |
C#
// C# implementation of SJF using System; using System.Collections.Generic; namespace SJF { // Structure to store the process information public struct proinfo { public string pname; // process name public int atime; // arrival time public int btime; // burst time } // This structure maintains the wait queue, using burst // time to compare. public class cmpBtime : IComparer<proinfo> { public int Compare(proinfo a, proinfo b) { return a.btime.CompareTo(b.btime); } } class Program { // number of processes const int SIZE = 4; // This function schedules the process according to the SJF scheduling algorithm. static void sjfNonpremetive(proinfo[] arr) { // Used to sort the processes according to arrival time int index; for ( int i = 0; i < SIZE - 1; i++) { index = i; for ( int j = i + 1; j < SIZE; j++) { if (arr[j].atime < arr[index].atime) { index = j; } } Swap( ref arr[i], ref arr[index]); } // ctime stores the current run time int ctime = arr[0].atime; // priority queue, wait, is used to store all the processes that arrive <= ctime (current run time) // this is a minimum priority queue that arranges values according to the burst time of the processes. var wait = new SortedSet<proinfo>( new cmpBtime()); int temp = arr[0].atime; // The first process is pushed in the wait queue. wait.Add(arr[0]); arr[0].atime = -1; Console.WriteLine( "Process id\tArrival time\tBurst time\n" ); while (wait.Count > 0) { Console.Write( "\t" ); Console.Write(wait.Min.pname + "\t\t" ); Console.Write(wait.Min.atime + "\t\t" ); Console.Write(wait.Min.btime + "\t\t" ); Console.WriteLine(); // ctime is increased with the burst time of the currently executed process. ctime += wait.Min.btime; // The executed process is removed from the wait queue. wait.Remove(wait.Min); for ( int i = 0; i < SIZE; i++) { if (arr[i].atime <= ctime && arr[i].atime != -1) { wait.Add(arr[i]); // When the process once enters the wait queue its arrival time is // assigned to -1 so that it doesn't enter again in the wait queue. arr[i].atime = -1; } } } } // Helper method to swap two Proinfo elements in an array private static void Swap( ref proinfo a, ref proinfo b) { proinfo temp = a; a = b; b = temp; } static void Main( string [] args) { // an array of process info structures. proinfo[] arr = new proinfo[SIZE]; arr[0] = new proinfo { pname = "p1" , atime = 4, btime = 3 }; arr[1] = new proinfo { pname = "p2" , atime = 0, btime = 8 }; arr[2] = new proinfo { pname = "p3" , atime = 5, btime = 4 }; arr[3] = new proinfo { pname = "p4" , atime = 9, btime = 2 }; Console.Write( "Process scheduling " ); Console.Write( "according to SJF is: \n" ); sjfNonpremetive(arr); } } } |
Process scheduling according to SJF is: Process id Arrival time Burst time p2 0 8 p1 4 3 p4 9 2 p3 5 4
Time Complexity: O(N^2).
Auxiliary Space: O(N).
Contact Us