Shortest Job First ( or SJF ) CPU Scheduling Non | Java 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 ; 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
import java . util . * ; class GFG { static int z = 1000000007 ; static int sh = 100000 ; static class util { int id ; int at ; int bt ; int ct ; int tat ; int wt ; } static util [ ] ar = new util [ sh + 1 ] ; static { for ( int i = 0 ; i < sh + 1 ; i ++ ) { ar [ i ] = new util ( ) ; } } static class util1 { int p_id ; int bt1 ; } ; static util1 range = new util1 ( ) ; static util1 [ ] tr = new util1 [ 4 * sh + 5 ] ; static { for ( int i = 0 ; i < 4 * sh + 5 ; i ++ ) { tr [ i ] = new util1 ( ) ; } } static int [ ] mp = new int [ sh + 1 ] ; static 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 ; } } static 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 ; } static void non_premptive_sjf ( int n ) { int counter = n ; int upper_range = 0 ; int tm = Math . min ( Integer . MAX_VALUE , ar [ upper_range + 1 ] . at ) ; while ( counter != 0 ) { 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 != Integer . MAX_VALUE ) { 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 , Integer . MAX_VALUE , Integer . MAX_VALUE ) ; } else { tm = ar [ upper_range + 1 ] . at ; } } } static void execute ( int n ) { Arrays . sort ( ar , 1 , n , new Comparator < util > ( ) { public int compare ( util a , util b ) { if ( a . at == b . at ) return a . id - b . id ; return a . at - b . at ; } } ) ; for ( int i = 1 ; i <= n ; i ++ ) mp [ ar [ i ] . id ] = i ; non_premptive_sjf ( n ) ; } static void print ( int n ) { System . out . println ( " ProcessId ▁ Arrival ▁ Time ▁ Burst ▁ Time " + " ▁ Completion ▁ Time ▁ Turn ▁ Around ▁ Time ▁ Waiting ▁ Time " ) ; for ( int i = 1 ; i <= n ; i ++ ) { System . out . printf ( "%d		%d		%d		%d		%d		%dNEW_LINE", ar[i].id, ar[i].at, ar[i].bt, ar[i].ct, ar[i].tat, ar[i].wt); } } public static void main ( String [ ] args ) { int n = 5 ; range . p_id = Integer . MAX_VALUE ; range . bt1 = Integer . MAX_VALUE ; for ( int i = 1 ; i <= 4 * sh + 1 ; i ++ ) { tr [ i ] . p_id = Integer . MAX_VALUE ; tr [ i ] . bt1 = Integer . MAX_VALUE ; } 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 ) ; } }