SJF(shortest job first)

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. SJN is a non-preemptive algorithm.

  • Shortest Job first has the advantage of having minimum average waiting time among all scheduling algorithms.
  • It is a Greedy Algorithm.
  • It may cause starvation if shorter processes keep coming. This problem can be solved using the concept of aging.
  • It is practically infeasible as Operating System may not know burst time and therefore may not sort them. While it is not possible to predict execution time, several methods can be used to estimate the execution time for a job, such as a weighted average of previous execution times. SJF can be used in specialized environments where accurate estimates of running time are available.

How SJF works?

Shortest Job First scheduling works on the process with the shortest burst time or duration first.

  • This is the best approach to minimize waiting time.
  • This is used in Batch Systems.
  • It is of two types:
    1. Non Pre-emptive
    2. Pre-emptive
  • To successfully implement it, the burst time/duration time of the processes should be known to the processor in advance, which is practically not feasible all the time.
  • This scheduling algorithm is optimal if all the jobs/processes are available at the same time. (either Arrival time is 0 for all, or Arrival time is same for all)

 

As you can see in the GANTT chart above, the process P4 will be picked up first as it has the shortest burst time, then P2, followed by P3 and at last P1.
We scheduled the same set of processes using the First come first serve algorithm , and got average waiting time to be 18.75 ms, whereas with SJF, the average waiting time comes out 4.5 ms.

Algorithm:

1- Sort all the processes in increasing order according to burst time.

2- Then simply, apply FCFS.

[ad type=”banner”]

Shortest Job First (or SJF) scheduling | Set 1 (Non- preemptive)

[ad type=”banner”]

How to compute below times in Round Robin using a program?

  1. Completion Time: Time at which process completes its execution.
  2. Turn Around Time: Time Difference between completion time and arrival time. Turn Around Time = Completion Time – Arrival Time
  3. Waiting Time(W.T): Time Difference between turn around time and burst time.
    Waiting Time = Turn Around Time – Burst Time

C++ Programming:

[pastacode lang=”cpp” manual=”%2F%2F%20C%2B%2B%20program%20to%20implement%20Shortest%20Job%20first%0A%23include%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%20%0Astruct%20Process%0A%7B%0A%20%20%20int%20pid%3B%20%2F%2F%20Process%20ID%0A%20%20%20int%20bt%3B%20%20%2F%2F%20Burst%20Time%0A%7D%3B%0A%20%0A%2F%2F%20This%20function%20is%20used%20for%20sorting%20all%0A%2F%2F%20processes%20in%20increasing%20order%20of%20burst%0A%2F%2F%20time%0Abool%20comparison(Process%20a%2C%20Process%20b)%0A%7B%0A%20%20%20%20%20return%20(a.bt%20%3C%20b.bt)%3B%0A%7D%0A%20%0A%2F%2F%20Function%20to%20find%20the%20waiting%20time%20for%20all%0A%2F%2F%20processes%0Avoid%20findWaitingTime(Process%20proc%5B%5D%2C%20int%20n%2C%20int%20wt%5B%5D)%0A%7B%0A%20%20%20%20%2F%2F%20waiting%20time%20for%20first%20process%20is%200%0A%20%20%20%20wt%5B0%5D%20%3D%200%3B%0A%20%0A%20%20%20%20%2F%2F%20calculating%20waiting%20time%0A%20%20%20%20for%20(int%20i%20%3D%201%3B%20i%20%3C%20n%20%3B%20i%2B%2B%20)%0A%20%20%20%20%20%20%20%20wt%5Bi%5D%20%3D%20proc%5Bi-1%5D.bt%20%2B%20wt%5Bi-1%5D%20%3B%0A%7D%0A%20%0A%2F%2F%20Function%20to%20calculate%20turn%20around%20time%0Avoid%20findTurnAroundTime(Process%20proc%5B%5D%2C%20int%20n%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20wt%5B%5D%2C%20int%20tat%5B%5D)%0A%7B%0A%20%20%20%20%2F%2F%20calculating%20turnaround%20time%20by%20adding%0A%20%20%20%20%2F%2F%20bt%5Bi%5D%20%2B%20wt%5Bi%5D%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20n%20%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20tat%5Bi%5D%20%3D%20proc%5Bi%5D.bt%20%2B%20wt%5Bi%5D%3B%0A%7D%0A%20%0A%2F%2FFunction%20to%20calculate%20average%20time%0Avoid%20findavgTime(Process%20proc%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20int%20wt%5Bn%5D%2C%20tat%5Bn%5D%2C%20total_wt%20%3D%200%2C%20total_tat%20%3D%200%3B%0A%20%0A%20%20%20%20%2F%2F%20Function%20to%20find%20waiting%20time%20of%20all%20processes%0A%20%20%20%20findWaitingTime(proc%2C%20n%2C%20wt)%3B%0A%20%0A%20%20%20%20%2F%2F%20Function%20to%20find%20turn%20around%20time%20for%20all%20processes%0A%20%20%20%20findTurnAroundTime(proc%2C%20n%2C%20wt%2C%20tat)%3B%0A%20%0A%20%20%20%20%2F%2F%20Display%20processes%20along%20with%20all%20details%0A%20%20%20%20cout%20%3C%3C%20%22%5CnProcesses%20%22%3C%3C%20%22%20Burst%20time%20%22%0A%20%20%20%20%20%20%20%20%20%3C%3C%20%22%20Waiting%20time%20%22%20%3C%3C%20%22%20Turn%20around%20time%5Cn%22%3B%0A%20%0A%20%20%20%20%2F%2F%20Calculate%20total%20waiting%20time%20and%20total%20turn%0A%20%20%20%20%2F%2F%20around%20time%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20total_wt%20%3D%20total_wt%20%2B%20wt%5Bi%5D%3B%0A%20%20%20%20%20%20%20%20total_tat%20%3D%20total_tat%20%2B%20tat%5Bi%5D%3B%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20%22%20%22%20%3C%3C%20proc%5Bi%5D.pid%20%3C%3C%20%22%5Ct%5Ct%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%3C%20proc%5Bi%5D.bt%20%3C%3C%20%22%5Ct%20%22%20%3C%3C%20wt%5Bi%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%3C%20%22%5Ct%5Ct%20%22%20%3C%3C%20tat%5Bi%5D%20%3C%3Cendl%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22Average%20waiting%20time%20%3D%20%22%0A%20%20%20%20%20%20%20%20%20%3C%3C%20(float)total_wt%20%2F%20(float)n%3B%0A%20%20%20%20cout%20%3C%3C%20%22%5CnAverage%20turn%20around%20time%20%3D%20%22%0A%20%20%20%20%20%20%20%20%20%3C%3C%20(float)total_tat%20%2F%20(float)n%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20code%0Aint%20main()%0A%7B%0A%20%20%20%20Process%20proc%5B%5D%20%3D%20%7B%7B1%2C%206%7D%2C%20%7B2%2C%208%7D%2C%20%7B3%2C%207%7D%2C%20%7B4%2C%203%7D%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof%20proc%20%2F%20sizeof%20proc%5B0%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20Sorting%20processes%20by%20burst%20time.%0A%20%20%20%20sort(proc%2C%20proc%20%2B%20n%2C%20comparison)%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22Order%20in%20which%20process%20gets%20executed%5Cn%22%3B%0A%20%20%20%20for%20(int%20i%20%3D%200%20%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20proc%5Bi%5D.pid%20%3C%3C%22%20%22%3B%0A%20%0A%20%20%20%20findavgTime(proc%2C%20n)%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”” highlight=”” provider=”manual”/] [ad type=”banner”]

Output:

Order in which process gets executed
4 1 3 2 
Processes  Burst time  Waiting time  Turn around time
 4		3	 0		 3
 1		6	 3		 9
 3		7	 9		 16
 2		8	 16		 24
Average waiting time = 7
Average turn around time = 13
[ad type=”banner”]