Implementation OF SJF ScheDULing Algorithm

Implementation of SJF ScheDULing algorithm.

Shortest Job First (SJF) is an algorithm in which the process having the smallest execution time is chosen for the next execution. This scheduling method can be preemptive or non-preemptive. It significantly reduces the average waiting time for other processes awaiting execution. The full form of SJF is Shortest Job First.

Non-Preemptive SJF

In non-preemptive scheduling, once the CPU cycle is allocated to process, the process holds it till it reaches a waiting state or is terminated.

Consider the following five processes each having its own unique burst time and arrival time.

Process Queue Burst time Arrival time
P1 6 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4

Step 0) At time=0, P4 arrives and starts execution.

gg

Step 1) At time= 1, Process P3 arrives. But, P4 still needs 2 execution units to complete. It will continue execution.

hh

Step 2) At time =2, process P1 arrives and is added to the waiting queue. P4 will continue execution.

rff

Step 3) At time = 3, process P4 will finish its execution. The burst time of P3 and P1 is compared. Process P1 is executed because its burst time is less compared to P3.

cc

Step 4) At time = 4, process P5 arrives and is added to the waiting queue. P1 will continue execution.

ff

Step 5) At time = 5, process P2 arrives and is added to the waiting queue. P1 will continue execution.

fgfg

Step 6) At time = 9, process P1 will finish its execution. The burst time of P3, P5, and P2 is compared. Process P2 is executed because its burst time is the lowest.

rf

Step 7) At time=10, P2 is executing and P3 and P5 are in the waiting queue.

fg

Step 8) At time = 11, process P2 will finish its execution. The burst time of P3 and P5 is compared. Process P5 is executed because its burst time is lower.

fdf

Step 9) At time = 15, process P5 will finish its execution.

fddrhh

Step 10) At time = 23, process P3 will finish its execution.

htgf

Step 11) Let’s calculate the average waiting time for the above example.

Wait time P4= 0-0=0
P1=  3-2=1
P2= 9-5=4
P5= 11-4=7
P3= 15-1=14
Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2

Preemptive SJF

In Preemptive SJF Scheduling, jobs are put into the ready queue as they come. A process with the shortest burst time begins execution. If a process with even a shorter burst time arrives, the current process is removed or preempted from execution, and the shorter job is allocated CPU cycle.

Consider the following five processes:-

Process Queue Burst time Arrival time
P1 6 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4

Step 0) At time=0, P4 arrives and starts execution.

 

Process Queue Burst time Arrival time
P1 6 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4

re

Step 1) At time= 1, Process P3 arrives. But, P4 has a shorter burst time. It will continue execution.

fvg

Step 2) At time = 2, process P1 arrives with burst time = 6. The burst time is more than that of P4. Hence, P4 will continue execution.

gggh

Step 3) At time = 3, process P4 will finish its execution. The burst time of P3 and P1 is compared. Process P1 is executed because its burst time is lower.

ffdf

Step 4) At time = 4, process P5 will arrive. The burst time of P3, P5, and P1 is compared. Process P5 is executed because its burst time is the lowest. Process P1 is preempted.

Process Queue Burst time Arrival time
P1 5 out of 6 is remaining 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4

fre

Step 5) At time = 5, process P2 will arrive. The burst time of P1, P2, P3, and P5 is compared. Process P2 is executed because its burst time is the least. Process P5 is preempted.

Process Queue Burst time Arrival time
P1 5 out of 6 is remaining 2
P2 2 5
P3 8 1
P4 3 0
P5 3 out of 4 is remaining 4

df

Step 6) At time =6, P2 is executing.

rfd

Step 7) At time =7, P2 finishes its execution. The burst time of P1, P3, and P5 is compared. Process P5 is executed because its burst time is lesser.

Process Queue Burst time Arrival time
P1 5 out of 6 is remaining 2
P2 2 5
P3 8 1
P4 3 0
P5 3 out of 4 is remaining 4

fgiuyt

Step 8) At time =10, P5 will finish its execution. The burst time of P1 and P3 is compared. Process P1 is executed because its burst time is less.

thtr

Step 9) At time =15, P1 finishes its execution. P3 is the only process left. It will start execution.

fgfh

Step 10) At time =23, P3 finishes its execution.

tytryr

Step 11) Let’s calculate the average waiting time for the above example.

Wait time P4= 0-0=0
P1= (3-2) + 6 =7
P2= 5-5 = 0
P5= 4-4+2 =2
P3= 15-1 = 14
Average Waiting Time = 0+7+0+2+14/5 = 23/5 =4.6

Implementation OF FCFS ScheDULing Algorithm ->>click here

1 thought on “Implementation OF SJF ScheDULing Algorithm”

Leave a Comment