**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.**