Shortest Job First (SJF) Algorithm.

Shortest Job First or SJF is a type of algorithm in which the process with the shortest execution time is selected for execution first. It can be preemptive or non-preemptive. SJF significantly decreases the execution time for other processes that are waiting.

Characteristics of SJF scheduling:

1. SJF improves the process throughput by executing jobs with shorter jobs first, hence providing a shorter turnaround time.
2. SJF scheduling is helpful in batch processing, as waiting for jobs is not critical. 
3. SJF scheduling is associated with each job as a unit of time to complete. 
4. This method improves job output by offering shorter jobs, which are executed first, resulting in a shorter turnaround time.

Preemptive SJF:

In preemptive SJF, if a process with a shorter burst time arrives, then the current process is preempted or removed from execution, and the shorter job is given to the CPU. 

Let’s consider the following five processes:

Step 1. Time=0, P4 arrives and starts the execution.

Step 2. Time=1, P3 arrives. As P4 has a shorter burst time, it will continue with its execution. 

Step 3. Time= 2, P1 arrives. As P4 has a shorter burnt time than P1, P4 continues with the execution.

Step 4. Time=3, P4 finishes the execution. P1 is then executed as it has a shorter burst time than P3. 

Step 5. Time=4, P5 arrives. P5 has a shorter burst time than P1 that was in execution. Process P5 will be executed and P1 will be preempted.

Step 6. Time=5, P2 will arrive and its burst time will be compared with P1, P3, and P5. P2 is then executed, as it has the shortest burst time while P5 is preempted.

Step 7. Time=6, P2 is executing. 

Step 8. Time=7, P2 will finish its execution and process P5 will be executed, as it has the least burst time among P1 and P3.

Step 9. Time=10, P5 will finish its execution. Process P1 will be executed as it has a shorter burst time than P3.

Step 10. Time=15, P1 will finish its execution and P3 will be executed. 

Step 11. Time=23, P3 will finish its execution.

Step 12. We will calculate the average waiting time. 

Wait time: 

P4= 0-0=0

P1=  (3-2) + 6 =7

P2= 5-5 = 0

P5= 4-4+2 =2

P3= 15-1 = 14

Average Waiting Time = 0+7+0+2+14/5 = 23/5 =4.6

Non-preemptive SJF:

In Non-preemptive SJF, a process that has been allocated to the CPU will run in the CPU till it is terminated. 

Let’s consider the following five processes: 

Step 1: Time=0, P4 arrives and starts the execution.

Step 2. Time=1, P3 arrives but P4 continues with its execution. 

Step 3. Time= 2, P1 arrives and is added to the waiting queue as P4 continues with the execution.

Step 4. Time=3, P4 finishes the execution. P1 is then executed as it has a shorter burst time than P3. 

Step 5. Time=4, P5 arrives and is added to the waiting queue.

Step 6. Time=5, P2 arrives and is added to the waiting queue. 

Step 7. Time=9, P1 finishes execution and is followed by P2 as it has a shorter burst time compared to P3 and P5.

Step 8. Time=10, P2 is executing, while P3 and P5 are in the wait.

Step 9. Time=11, P2 finishes its execution. Process P5 is executed as it has a shorter burst time than P3.

Step 10. Time=15, P5 will finish its execution and P3 will be executed. 

Step 11. Time=23, P3 will finish its execution.

Step 12. We will calculate the average waiting time. 

Wait time 

P4= 0-0=0

P1=  3-2=1

P2= 9-5=4

P5= 11-4=7

P3= 15-1=14

Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2

Reference:

SJF Algorithm of Operating System.