Java Shortest Job First Example

Program for Shortest Job First (SJF) scheduling | Set 2 (Preemptive)

In previous post, we have discussed Set 1 of SJF i.e. non-preemptive. In this post we will discuss the preemptive version of SJF known as Shortest Remaining Time First (SRTF).

In this scheduling algorithm, the process with the smallest amount of time remaining until completion is selected to execute. Since the currently executing process is the one with the shortest amount of time remaining by definition, and since that time should only reduce as execution progresses, processes will always run until they complete or a new process is added that requires a smaller amount of time.

Preemptive SJF: Example

Process	Duration	Order	Arrival Time
P1	9	1	0
P2	2	2	2

P1 waiting time: 4-2 = 2
P2 waiting time: 0
The average waiting time(AWT): (0 + 2) / 2 = 1

Advantage:
1- Short processes are handled very quickly.
2- The system also requires very little overhead since it only makes a decision when a process completes or a new process is added.
3- When a new process is added the algorithm only needs to compare the currently executing process with the new process, ignoring all other processes currently waiting to execute.

Disadvantage:
1- Like shortest job first, it has the potential for process starvation.
2- Long processes may be held off indefinitely if short processes are continually added.

Source:Wiki

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

                Implementation:                1- Traverse until all process gets completely    executed.    a) Find process with minimum remaining time at      every single time lap.    b) Reduce its time by 1.    c) Check if its remaining time becomes 0     d) Increment the counter of process completion.    e) Completion time of current process =       current_time +1;    e) Calculate waiting time for each completed       process.    wt[i]= Completion time - arrival_time-burst_time    f)Increment time lap by one. 2- Find turnaround time (waiting_time+burst_time).              

C/C++

#include <bits/stdc++.h>

using namespace std;

struct Process {

int pid;

int bt;

int art;

};

void findWaitingTime(Process proc[], int n,

int wt[])

{

int rt[n];

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 ;

while (complete != n) {

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 ;

}

rt[shortest]--;

minm = rt[shortest];

if (minm == 0)

minm = INT_MAX;

if (rt[shortest] == 0) {

complete++;

check = false ;

finish_time = t + 1;

wt[shortest] = finish_time -

proc[shortest].bt -

proc[shortest].art;

if (wt[shortest] < 0)

wt[shortest] = 0;

}

t++;

}

}

void findTurnAroundTime(Process proc[], int n,

int wt[], int tat[])

{

for ( int i = 0; i < n; i++)

tat[i] = proc[i].bt + wt[i];

}

void findavgTime(Process proc[], int n)

{

int wt[n], tat[n], total_wt = 0,

total_tat = 0;

findWaitingTime(proc, n, wt);

findTurnAroundTime(proc, n, wt, tat);

cout << "Processes "

<< " Burst time "

<< " Waiting time "

<< " Turn around time " ;

for ( int i = 0; i < n; i++) {

total_wt = total_wt + wt[i];

total_tat = total_tat + tat[i];

cout << " " << proc[i].pid << " "

<< proc[i].bt << " " << wt[i]

<< " " << tat[i] << endl;

}

cout << " Average waiting time = "

<< ( float )total_wt / ( float )n;

cout << " Average turn around time = "

<< ( float )total_tat / ( float )n;

}

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;

}

Java

class Process

{

int pid;

int bt;

int art;

public Process( int pid, int bt, int art)

{

this .pid = pid;

this .bt = bt;

this .art = art;

}

}

public class GFG

{

static void findWaitingTime(Process proc[], int n,

int wt[])

{

int rt[] = new int [n];

for ( int i = 0 ; i < n; i++)

rt[i] = proc[i].bt;

int complete = 0 , t = 0 , minm = Integer.MAX_VALUE;

int shortest = 0 , finish_time;

boolean check = false ;

while (complete != n) {

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 ;

}

rt[shortest]--;

minm = rt[shortest];

if (minm == 0 )

minm = Integer.MAX_VALUE;

if (rt[shortest] == 0 ) {

complete++;

check = false ;

finish_time = t + 1 ;

wt[shortest] = finish_time -

proc[shortest].bt -

proc[shortest].art;

if (wt[shortest] < 0 )

wt[shortest] = 0 ;

}

t++;

}

}

static void findTurnAroundTime(Process proc[], int n,

int wt[], int tat[])

{

for ( int i = 0 ; i < n; i++)

tat[i] = proc[i].bt + wt[i];

}

static void findavgTime(Process proc[], int n)

{

int wt[] = new int [n], tat[] = new int [n];

int total_wt = 0 , total_tat = 0 ;

findWaitingTime(proc, n, wt);

findTurnAroundTime(proc, n, wt, tat);

System.out.println( "Processes " +

" Burst time " +

" Waiting time " +

" Turn around time" );

for ( int i = 0 ; i < n; i++) {

total_wt = total_wt + wt[i];

total_tat = total_tat + tat[i];

System.out.println( " " + proc[i].pid + " "

+ proc[i].bt + " " + wt[i]

+ " " + tat[i]);

}

System.out.println( "Average waiting time = " +

( float )total_wt / ( float )n);

System.out.println( "Average turn around time = " +

( float )total_tat / ( float )n);

}

public static void main(String[] args)

{

Process proc[] = { new Process( 1 , 6 , 1 ),

new Process( 2 , 8 , 1 ),

new Process( 3 , 7 , 2 ),

new Process( 4 , 3 , 3 )};

findavgTime(proc, proc.length);

}

}

Python3

def findWaitingTime(processes, n, wt):

rt = [ 0 ] * n

for i in range (n):

rt[i] = processes[i][ 1 ]

complete = 0

t = 0

minm = 999999999

short = 0

check = False

while (complete ! = n):

for j in range (n):

if ((processes[j][ 2 ] < = t) and

(rt[j] < minm) and rt[j] > 0 ):

minm = rt[j]

short = j

check = True

if (check = = False ):

t + = 1

continue

rt[short] - = 1

minm = rt[short]

if (minm = = 0 ):

minm = 999999999

if (rt[short] = = 0 ):

complete + = 1

check = False

fint = t + 1

wt[short] = (fint - proc[short][ 1 ] -

proc[short][ 2 ])

if (wt[short] < 0 ):

wt[short] = 0

t + = 1

def findTurnAroundTime(processes, n, wt, tat):

for i in range (n):

tat[i] = processes[i][ 1 ] + wt[i]

def findavgTime(processes, n):

wt = [ 0 ] * n

tat = [ 0 ] * n

findWaitingTime(processes, n, wt)

findTurnAroundTime(processes, n, wt, tat)

print ( "Processes    Burst Time     Waiting" ,

"Time     Turn-Around Time" )

total_wt = 0

total_tat = 0

for i in range (n):

total_wt = total_wt + wt[i]

total_tat = total_tat + tat[i]

print ( " " , processes[i][ 0 ], " " ,

processes[i][ 1 ], " " ,

wt[i], " " , tat[i])

print ( " Average waiting time = %.5f " % (total_wt / n) )

print ( "Average turn around time = " , total_tat / n)

if __name__ = = "__main__" :

proc = [[ 1 , 6 , 1 ], [ 2 , 8 , 1 ],

[ 3 , 7 , 2 ], [ 4 , 3 , 3 ]]

n = 4

findavgTime(proc, n)

C#

using System;

public class Process

{

public int pid;

public int bt;

public int art;

public Process( int pid, int bt, int art)

{

this .pid = pid;

this .bt = bt;

this .art = art;

}

}

public class GFG

{

static void findWaitingTime(Process []proc, int n,

int []wt)

{

int []rt = new int [n];

for ( int i = 0; i < n; i++)

rt[i] = proc[i].bt;

int complete = 0, t = 0, minm = int .MaxValue;

int shortest = 0, finish_time;

bool check = false ;

while (complete != n)

{

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 ;

}

rt[shortest]--;

minm = rt[shortest];

if (minm == 0)

minm = int .MaxValue;

if (rt[shortest] == 0)

{

complete++;

check = false ;

finish_time = t + 1;

wt[shortest] = finish_time -

proc[shortest].bt -

proc[shortest].art;

if (wt[shortest] < 0)

wt[shortest] = 0;

}

t++;

}

}

static void findTurnAroundTime(Process []proc, int n,

int []wt, int []tat)

{

for ( int i = 0; i < n; i++)

tat[i] = proc[i].bt + wt[i];

}

static void findavgTime(Process []proc, int n)

{

int []wt = new int [n]; int []tat = new int [n];

int total_wt = 0, total_tat = 0;

findWaitingTime(proc, n, wt);

findTurnAroundTime(proc, n, wt, tat);

Console.WriteLine( "Processes " +

" Burst time " +

" Waiting time " +

" Turn around time" );

for ( int i = 0; i < n; i++)

{

total_wt = total_wt + wt[i];

total_tat = total_tat + tat[i];

Console.WriteLine( " " + proc[i].pid + " "

+ proc[i].bt + " " + wt[i]

+ " " + tat[i]);

}

Console.WriteLine( "Average waiting time = " +

( float )total_wt / ( float )n);

Console.WriteLine( "Average turn around time = " +

( float )total_tat / ( float )n);

}

public static void Main(String[] args)

{

Process []proc = { new Process(1, 6, 1),

new Process(2, 8, 1),

new Process(3, 7, 2),

new Process(4, 3, 3)};

findavgTime(proc, proc.Length);

}

}

Output:

Processes  Burst time  Waiting time  Turn around time  1        6         3        9  2        8         16        24  3        7         8        15  4        3         0        3 Average waiting time = 6.75 Average turn around time = 12.75              

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

0 1

You Might Also Like

Subscribe to Our Newsletter

schwartzharioned1941.blogspot.com

Source: https://tutorialspoint.dev/computer-science/operating-systems/program-shortest-job-first-scheduling-set-2srtf-make-changesdoneplease-review

Share this post