Explain Shortest Job First (SJF) scheduling algorithms with proper examples.

Question

Aryan Kumar · Answer

Shortest Job First (SJF) is a scheduling algorithm in which the process with the shortest burst time is scheduled first. This algorithm is a type of non-preemptive scheduling, which means that once a process is scheduled, it will continue to execute until it completes its job or is blocked by an I/O operation.
The advantage of the SJF algorithm is that it minimizes the average waiting time of processes and gives priority to short jobs. However, it can lead to starvation of long processes if many short processes are continually entering the system.

It is worth noting that there is a variant of SJF called Shortest Remaining Time First (SRTF) which is preemptive, meaning that it can interrupt an already running process if a new process with a shorter burst time arrives.

Consider the following set of processes with their burst times:

Process	Burst Time
P1	6
P2	8
P3	7
P4	3
P5	4

Using SJF, the processes will be scheduled in the following order:

Time	Process
0	P4
3	P5
7	P1
13	P3
20	P2

Krishnapriya Rajeev · Answer

Shortest Job First (SJF) is a CPU scheduling algorithm that selects the waiting process with the smallest execution time to execute next. In other words, the process with the shortest estimated processing time is executed first. In SJF, the processes in the ready queue are sorted in ascending order of their expected execution time and we execute the process with the shortest execution time. It can be both preemptive and non-preemptive in nature.

If a new process arrives while a process is executing, compare the expected execution time of the new process with the remaining execution time of the executing process. If the new process has a shorter expected execution time, preempt the executing process and start executing the new process.

Repeat the process until all processes have been executed.

The SJF scheduling algorithm can be visualized using a Gantt chart, which shows the timeline of each process's execution. Here is an example of a preemptive SJF scheduling algorithm with four processes, where the expected execution time of each process is given in milliseconds:

Process	Arrival Time	Burst Time
P1	0	8
P2	1	4
P3	2	9
P4	3	5

At the initial time of arrival (time 0), the only process in the ready queue is P1, which begins its execution. During P1's execution, another process, P2, arrives in the queue at time 2 with a shorter burst time than P1's remaining execution time (which is 7). As a result, P2 begins its execution. Once P2 has finished its execution, three processes are remaining in the queue. The process with the least execution time remaining (i.e. P4) is selected to execute next. After P4 completes its execution, P1 and P3 complete their execution in that order.

In this way, all the processes get executed and the Gantt chart is as follows:

	P1		P2		P4		P1		P3		
__________________________________________
0		1		5		10		17		26

SJF scheduling algorithm can minimize the average waiting time for the processes, as it selects the shortest job first. However, it requires knowledge of the expected execution time of each process, which may not be available in practice.

forum

Explain Shortest Job First (SJF) scheduling algorithms with proper examples.

Can you answer this question?

2 Answers