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
- Preemptive (SRTF – Shortest Remaining Time First)
- Non-Preemptive (Default)
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.
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 2 | 1 |
| P2 | 1 | 5 |
| P3 | 4 | 1 |
| P4 | 0 | 6 |
| P5 | 2 | 3 |
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.
| Process | Arrival Time (AT) | Burst Time (BT) | Completion Time (CT) | Turn Around Time TAT = CT-AT | Waiting Time WT = TAT-BT | Response Time RT = ST-AT (Start Time-Arrival Time) |
|---|---|---|---|---|---|---|
| P1 | 2 | 1 | 7 | 5 | 4 | 4 |
| P2 | 1 | 5 | 16 | 15 | 10 | 10 |
| P3 | 4 | 1 | 8 | 4 | 3 | 3 |
| P4 | 0 | 6 | 6 | 6 | 0 | 0 |
| P5 | 2 | 3 | 11 | 9 | 6 | 6 |
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
- Maximum throughput
- Minimum average waiting and turnaround time
- Used for long-term scheduling.
- Reduces average waiting time.
- Helpful for batch-type processing where runtimes are known in advance.
- It is necessary to predict the value of the next burst time for Short-Term Scheduling.
Disadvantages of SJF SJF scheduling algorithm
- May suffer with the problem of starvation
- It is not implementable because the exact Burst time for a process can’t be known in advance
- SJF may cause starvation if shorter processes keep coming. This problem is solved by aging.
- It cannot be implemented at the level of short-term CPU scheduling.
- It is necessary to know the job completion time beforehand as it is hard to predict.