In SJF(Shortest Job First) scheduling, the process which has the shortest burst time is scheduled first but if two processes have the same burst time then FCFS is used to break the tie. It is a non-preemptive scheduling algorithm.
This article talks about SJF scheduling in detail.
The problem in FCFS scheduling was if there is a job that is CPU bound and it has come first and has been scheduled on CPU, the other jobs which take less time to have to wait for this long job. It decreases throughput and increases average waiting time. The idea of the shortest job first algorithm is to consider the jobs in increasing order of their CPU burst time. This algorithm is non-preemptive. Being a non-preemptive algorithm, the first process assigned to the CPU is executed till completion then the process whose burst time is minimum is assigned next to the CPU and hence it continues.
Let’s understand the following problem :
|PROCESS||ARRIVAL TIME||BURST TIME|
The Gantt chart of the following problem is:
|PROCESS||ARRIVAL TIME||BURST TIME||COMPLETION TIME||TURN AROUND TIME||WAITINGTIME|
* Turn around time = Completion time – Arrival time
*Waiting time = Turn around time – Burst time
So Average turn around time = (5+11+6+17)/4 = 39/4
And average waiting time = (0+7+3+9)/4 = 19/4
Some important points
- This algorithm gives a minimum average waiting time so it is an optimal algorithm.
- It is a greedy algorithm.
- If the shorter processes keep coming one after the other, it may cause starvation. This problem can be solved using the concept of aging.
- This algorithm assumes that the operating system knows the burst time of every process in the ready queue which is an impractical thing because it is not possible to guess the CPU burst time of every job or process.
SJF(Shortest Job first) is a non-preemptive algorithm. In this, the process which has the shortest CPU burst time is scheduled first. This algorithm has the minimum average time among all the scheduling algorithms.