Shortest Job First ( or SJF ) CPU Scheduling Non | C ++ implementation of shortest job first using the concept of segment tree ; Process ID ; Arrival time ; Burst time ; Completion time ; Turnaround time ; Waiting time ; Array to store all the process information by implementing the above struct util ; Process id ; burst time ; Segment tree array to process the queries in nlogn ; To keep an account of where a particular process_id is in the segment tree base array ; Comparator function to sort the struct array according to arrival time ; Function to update the burst time and process id in the segment tree ; Function to return the range minimum of the burst time of all the arrived processes using segment tree ; Function to perform non_preemptive shortest job first and return the completion time , turn around time and waiting time for the given processes ; To store the number of processes that have been completed ; To keep an account of the number of processes that have been arrived ; Current running time ; To find the list of processes whose arrival time is less than or equal to the current time ; To find the minimum of all the running times from the set of processes whose arrival time is less than or equal to the current time ; Checking if the process has already been executed ; Calculating and updating the array with the current time , turn around time and waiting time ; Update the process burst time with infinity when the process is executed ; Function to call the functions and perform shortest job first operation ; Sort the array based on the arrival times ; Calling the function to perform non - premptive - sjf ; Function to print the required values after performing shortest job first ; Driver code ; Number of processes ; Initializing the process id and burst time ; Arrival time , Burst time and ID of the processes on which SJF needs to be performed ; Print the calculated time
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long NEW_LINE #define z  1000000007 NEW_LINE #define sh  100000 NEW_LINE #define pb  push_back NEW_LINE #define pr ( x )  printf("%d ", x) NEW_LINE struct util { int id ; int at ; int bt ; int ct ; int tat ; int wt ; } ar [ sh + 1 ] ; struct util1 { int p_id ; int bt1 ; } ; util1 range ; util1 tr [ 4 * sh + 5 ] ; int mp [ sh + 1 ] ; bool cmp ( util a , util b ) { if ( a . at == b . at ) return a . id < b . id ; return a . at < b . at ; } void update ( int node , int st , int end , int ind , int id1 , int b_t ) { if ( st == end ) { tr [ node ] . p_id = id1 ; tr [ node ] . bt1 = b_t ; return ; } int mid = ( st + end ) / 2 ; if ( ind <= mid ) update ( 2 * node , st , mid , ind , id1 , b_t ) ; else update ( 2 * node + 1 , mid + 1 , end , ind , id1 , b_t ) ; if ( tr [ 2 * node ] . bt1 < tr [ 2 * node + 1 ] . bt1 ) { tr [ node ] . bt1 = tr [ 2 * node ] . bt1 ; tr [ node ] . p_id = tr [ 2 * node ] . p_id ; } else { tr [ node ] . bt1 = tr [ 2 * node + 1 ] . bt1 ; tr [ node ] . p_id = tr [ 2 * node + 1 ] . p_id ; } } util1 query ( int node , int st , int end , int lt , int rt ) { if ( end < lt st > rt ) return range ; if ( st >= lt && end <= rt ) return tr [ node ] ; int mid = ( st + end ) / 2 ; util1 lm = query ( 2 * node , st , mid , lt , rt ) ; util1 rm = query ( 2 * node + 1 , mid + 1 , end , lt , rt ) ; if ( lm . bt1 < rm . bt1 ) return lm ; return rm ; } void non_preemptive_sjf ( int n ) { int counter = n ; int upper_range = 0 ; int tm = min ( INT_MAX , ar [ upper_range + 1 ] . at ) ; while ( counter ) { for ( ; upper_range <= n ; ) { upper_range ++ ; if ( ar [ upper_range ] . at > tm upper_range > n ) { upper_range -- ; break ; } update ( 1 , 1 , n , upper_range , ar [ upper_range ] . id , ar [ upper_range ] . bt ) ; } util1 res = query ( 1 , 1 , n , 1 , upper_range ) ; if ( res . bt1 != INT_MAX ) { counter -- ; int index = mp [ res . p_id ] ; tm += ( res . bt1 ) ; ar [ index ] . ct = tm ; ar [ index ] . tat = ar [ index ] . ct - ar [ index ] . at ; ar [ index ] . wt = ar [ index ] . tat - ar [ index ] . bt ; update ( 1 , 1 , n , index , INT_MAX , INT_MAX ) ; } else { tm = ar [ upper_range + 1 ] . at ; } } } void execute ( int n ) { sort ( ar + 1 , ar + n + 1 , cmp ) ; for ( int i = 1 ; i <= n ; i ++ ) mp [ ar [ i ] . id ] = i ; non_premptive_sjf ( n ) ; } void print ( int n ) { cout << " ProcessId ▁ " << " Arrival ▁ Time ▁ " << " Burst ▁ Time ▁ " << " Completion ▁ Time ▁ " << " Turn ▁ Around ▁ Time ▁ " << " Waiting ▁ Time STRNEWLINE " ; for ( int i = 1 ; i <= n ; i ++ ) { cout << ar [ i ] . id << " ▁ TABSYMBOL TABSYMBOL ▁ " << ar [ i ] . at << " ▁ TABSYMBOL TABSYMBOL ▁ " << ar [ i ] . bt << " ▁ TABSYMBOL TABSYMBOL ▁ " << ar [ i ] . ct << " ▁ TABSYMBOL TABSYMBOL ▁ " << ar [ i ] . tat << " ▁ TABSYMBOL TABSYMBOL ▁ " << ar [ i ] . wt << " ▁ STRNEWLINE " ; } } int main ( ) { int n = 5 ; range . p_id = INT_MAX ; range . bt1 = INT_MAX ; for ( int i = 1 ; i <= 4 * sh + 1 ; i ++ ) { tr [ i ] . p_id = INT_MAX ; tr [ i ] . bt1 = INT_MAX ; } ar [ 1 ] . at = 1 ; ar [ 1 ] . bt = 7 ; ar [ 1 ] . id = 1 ; ar [ 2 ] . at = 2 ; ar [ 2 ] . bt = 5 ; ar [ 2 ] . id = 2 ; ar [ 3 ] . at = 3 ; ar [ 3 ] . bt = 1 ; ar [ 3 ] . id = 3 ; ar [ 4 ] . at = 4 ; ar [ 4 ] . bt = 2 ; ar [ 4 ] . id = 4 ; ar [ 5 ] . at = 5 ; ar [ 5 ] . bt = 8 ; ar [ 5 ] . id = 5 ; execute ( n ) ; print ( n ) ; }