**SJF Scheduling-**

In SJF Scheduling,

- Out of all the available processes, CPU is assigned to the process having smallest burst time.
- In case of a tie, it is broken by
**FCFS Scheduling**.

- SJF Scheduling can be used in both preemptive and non-preemptive mode.
- Preemptive mode of Shortest Job First is called as
**Shortest Remaining Time First (SRTF)**.

**Advantages-**

- SRTF is optimal and guarantees the minimum average waiting time.
- It provides a standard for other algorithms since no other algorithm performs better than it.

**Disadvantages-**

- It can not be implemented practically since burst time of the processes can not be known in advance.
- It leads to starvation for processes with larger burst time.
- Priorities can not be set for the processes.
- Processes with larger burst time have poor response time.

**PRACTICE PROBLEMS BASED ON SJF SCHEDULING-**

**Problem-01:**

Consider the set of 5 processes whose arrival time and burst time are given below-

Process Id | Arrival time | Burst time |

P1 | 3 | 1 |

P2 | 1 | 4 |

P3 | 4 | 2 |

P4 | 0 | 6 |

P5 | 2 | 3 |

If the CPU scheduling policy is SJF non-preemptive, calculate the average waiting time and average turn around time.

**Solution-**

**Gantt Chart-**

Now, we know-

- Turn Around time = Exit time – Arrival time
- Waiting time = Turn Around time – Burst time

**Also read-** **Various Times of Process**

Process Id | Exit time | Turn Around time | Waiting time |

P1 | 7 | 7 – 3 = 4 | 4 – 1 = 3 |

P2 | 16 | 16 – 1 = 15 | 15 – 4 = 11 |

P3 | 9 | 9 – 4 = 5 | 5 – 2 = 3 |

P4 | 6 | 6 – 0 = 6 | 6 – 6 = 0 |

P5 | 12 | 12 – 2 = 10 | 10 – 3 = 7 |

Now,

- Average Turn Around time = (4 + 15 + 5 + 6 + 10) / 5 = 40 / 5 = 8 unit
- Average waiting time = (3 + 11 + 3 + 0 + 7) / 5 = 24 / 5 = 4.8 unit

**Problem-02:**

Consider the set of 5 processes whose arrival time and burst time are given below-

Process Id | Arrival time | Burst time |

P1 | 3 | 1 |

P2 | 1 | 4 |

P3 | 4 | 2 |

P4 | 0 | 6 |

P5 | 2 | 3 |

If the CPU scheduling policy is SJF preemptive, calculate the average waiting time and average turn around time.

**Solution-**

**Gantt Chart-**

Now, we know-

- Turn Around time = Exit time – Arrival time
- Waiting time = Turn Around time – Burst time

Process Id | Exit time | Turn Around time | Waiting time |

P1 | 4 | 4 – 3 = 1 | 1 – 1 = 0 |

P2 | 6 | 6 – 1 = 5 | 5 – 4 = 1 |

P3 | 8 | 8 – 4 = 4 | 4 – 2 = 2 |

P4 | 16 | 16 – 0 = 16 | 16 – 6 = 10 |

P5 | 11 | 11 – 2 = 9 | 9 – 3 = 6 |

Now,

- Average Turn Around time = (1 + 5 + 4 + 16 + 9) / 5 = 35 / 5 = 7 unit
- Average waiting time = (0 + 1 + 2 + 10 + 6) / 5 = 19 / 5 = 3.8 unit

**Problem-03:**

Consider the set of 6 processes whose arrival time and burst time are given below-

Process Id | Arrival time | Burst time |

P1 | 0 | 7 |

P2 | 1 | 5 |

P3 | 2 | 3 |

P4 | 3 | 1 |

P5 | 4 | 2 |

P6 | 5 | 1 |

If the CPU scheduling policy is shortest remaining time first, calculate the average waiting time and average turn around time.

**Solution-**

**Gantt Chart-**

Now, we know-

- Turn Around time = Exit time – Arrival time
- Waiting time = Turn Around time – Burst time

Process Id | Exit time | Turn Around time | Waiting time |

P1 | 19 | 19 – 0 = 19 | 19 – 7 = 12 |

P2 | 13 | 13 – 1 = 12 | 12 – 5 = 7 |

P3 | 6 | 6 – 2 = 4 | 4 – 3 = 1 |

P4 | 4 | 4 – 3 = 1 | 1 – 1 = 0 |

P5 | 9 | 9 – 4 = 5 | 5 – 2 = 3 |

P6 | 7 | 7 – 5 = 2 | 2 – 1 = 1 |

Now,

- Average Turn Around time = (19 + 12 + 4 + 1 + 5 + 2) / 6 = 43 / 6 = 7.17 unit
- Average waiting time = (12 + 7 + 1 + 0 + 3 + 1) / 6 = 24 / 6 = 4 unit

**Problem-04:**

Consider the set of 3 processes whose arrival time and burst time are given below-

Process Id | Arrival time | Burst time |

P1 | 0 | 9 |

P2 | 1 | 4 |

P3 | 2 | 9 |

If the CPU scheduling policy is SRTF, calculate the average waiting time and average turn around time.

**Solution-**

**Gantt Chart-**

Now, we know-

- Turn Around time = Exit time – Arrival time
- Waiting time = Turn Around time – Burst time

Process Id | Exit time | Turn Around time | Waiting time |

P1 | 13 | 13 – 0 = 13 | 13 – 9 = 4 |

P2 | 5 | 5 – 1 = 4 | 4 – 4 = 0 |

P3 | 22 | 22- 2 = 20 | 20 – 9 = 11 |

Now,

- Average Turn Around time = (13 + 4 + 20) / 3 = 37 / 3 = 12.33 unit
- Average waiting time = (4 + 0 + 11) / 3 = 15 / 3 = 5 unit

**Problem-05:**

Consider the set of 4 processes whose arrival time and burst time are given below-

Process Id | Arrival time | Burst time |

P1 | 0 | 20 |

P2 | 15 | 25 |

P3 | 30 | 10 |

P4 | 45 | 15 |

If the CPU scheduling policy is SRTF, calculate the waiting time of process P2.

**Solution-**

**Gantt Chart-**

Now, we know-

- Turn Around time = Exit time – Arrival time
- Waiting time = Turn Around time – Burst time

Thus,

- Turn Around Time of process P2 = 55 – 15 = 40 unit
- Waiting time of process P2 = 40 – 25 = 15 unit

**Implementation of Algorithm-**

- Practically, the algorithm can not be implemented but theoretically it can be implemented.
- Among all the available processes, the process with smallest burst time has to be selected.
- Min heap is a suitable data structure where root element contains the process with least burst time.
- In min heap, each process will be added and deleted exactly once.
- Adding an element takes log(n) time and deleting an element takes log(n) time.
- Thus, for n processes, time complexity = n x 2log(n) = nlog(n)

To gain better understanding about SJF Scheduling,

**Next Article-** **Techniques to Predict Burst Time**

Get more notes and other study material of **Operating System**.

Watch video lectures by visiting our YouTube channel **LearnVidFun.**