Shortest Job First (SJF) Scheduling Algorithm

SJF - Shortest Job First

SJF scheduling algorithm, execute the process according to their burst time.

In SJF scheduling, out of all available processes in the ready queue, it selects the processes with lowest burst time to execute next.

Two Types

  1. Preemptive (SRTF – Shortest Remaining Time First)
  2. Non-Preemptive (Default)
Shortest Job First (SJF) Scheduling Algorithm

Example
In the following example, there are five jobs named as P1, P2, P3, P4 and P5. Their arrival time and burst time are given in the table below.

ProcessArrival TimeBurst Time
P121
P215
P341
P406
P523

Solution

Step 1: Select One Process with lowest arrival time and add into Gantt chart First. Here Process P4 have 0 arrival time so P4 moved to Gantt Chart first. Remaining Process will go into Ready Queue(P1,P2,P3,P5)

Step 2: Next get process from Ready Queue which has lowest Burst First. In Some case two process same burst time so that time we have apply FCFS Method. Here P1 and P3 have same burst time value as 1. So we added P1 process first in the Gantt Chart and then added P3 Process added.

            

ProcessArrival Time (AT)Burst Time (BT)Completion Time (CT)Turn Around Time
TAT = CT-AT
Waiting Time WT = TAT-BTResponse Time
RT = ST-AT
(Start Time-Arrival Time)
P1217544
P21516151010
P3418433
P4066600
P52311966

  In the above table, we can find the waiting time for the process P1, P2,P3,P4 and P5.          

  Waiting Time for P1 => 4

Waiting Time for P2 => 10

Waiting Time for P3 => 3

Waiting Time for P4 => 0

Waiting Time for P5 => 6

Average Waiting Time(AWT) =(4+10+3+0+6)/5

= 23/5

= 4.6

Advantages of SJF scheduling algorithm

  1. Maximum throughput
  2. Minimum average waiting and turnaround time
  3. Used for long-term scheduling.
  4. Reduces average waiting time.
  5. Helpful for batch-type processing where runtimes are known in advance.
  6. It is necessary to predict the value of the next burst time for Short-Term Scheduling.

Disadvantages of SJF SJF scheduling algorithm

  1. May suffer with the problem of starvation
  2. It is not implementable because the exact Burst time for a process can’t be known in advance
  3. SJF may cause starvation if shorter processes keep coming. This problem is solved by aging.
  4. It cannot be implemented at the level of short-term CPU scheduling.
  5. It is necessary to know the job completion time beforehand as it is hard to predict.
Leave a Reply 0

Your email address will not be published. Required fields are marked *