Day 02Part 06- Operating System for Gate – Shortest Job First Scheduling Algorithm
Day 02Part 06- Operating System for Gate – Shortest Job First Scheduling Algorithm
Contents [hide]
- 1 Day 02 Part 06 – Operating System for GATE
- 2 Shortest Job First (SJF) Scheduling Algorithm
- 3 What is SJF Scheduling?
- 4 Characteristics of SJF
- 5 Non-Preemptive SJF Example
- 6 Preemptive SJF (SRTF) Example
- 7 Advantages & Disadvantages
- 8 Applications of SJF
- 9 Day 02Part 06- Operating System for Gate – Shortest Job First Scheduling Algorithm
- 10 Unit IV – CPU Scheduling and Algorithm
- 11 OPERATING SYSTEM
Day 02 Part 06 – Operating System for GATE
Shortest Job First (SJF) Scheduling Algorithm
What is SJF Scheduling?
Shortest Job First (SJF) is a CPU scheduling algorithm that selects the process with the smallest burst time for execution next.
It is also known as Shortest Next CPU Burst Scheduling.
There are two types of SJF scheduling:
- Non-Preemptive SJF – Once a process starts execution, it cannot be interrupted.
- Preemptive SJF (Shortest Remaining Time First – SRTF) – The process can be interrupted if a shorter job arrives.
Characteristics of SJF
Optimal in reducing average waiting time
Best case scenario for batch processing
Difficult to implement in real-world OS (because burst time is unknown)
Non-Preemptive SJF Example
Let’s consider 4 processes with the following burst times:
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0 | 7 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 5 | 4 |
Step-by-Step Execution:
- At t = 0, P1 starts execution (since no other process has arrived).
- At t = 2, P2 arrives, but P1 is still running.
- At t = 4, P3 arrives.
- At t = 7, P3 (Shortest Job: 1) is selected.
- At t = 8, P2 (Shortest Job: 4) is selected.
- At t = 12, P4 (Shortest Job: 4) is selected.
Gantt Chart:
Calculation of Waiting Time & Turnaround Time
Waiting Time=Turnaround Time−Burst Time\text{Waiting Time} = \text{Turnaround Time} – \text{Burst Time}
| Process | Arrival Time | Burst Time | Completion Time | Turnaround Time (TAT) | Waiting Time (WT) |
|---|---|---|---|---|---|
| P1 | 0 | 7 | 7 | 7 – 0 = 7 | 0 |
| P2 | 2 | 4 | 12 | 12 – 2 = 10 | 10 – 4 = 6 |
| P3 | 4 | 1 | 8 | 8 – 4 = 4 | 4 – 1 = 3 |
| P4 | 5 | 4 | 16 | 16 – 5 = 11 | 11 – 4 = 7 |
Average Waiting Time (AWT) = (0 + 6 + 3 + 7) / 4 = 4
Average Turnaround Time (ATAT) = (7 + 10 + 4 + 11) / 4 = 8
Preemptive SJF (SRTF) Example
In Shortest Remaining Time First (SRTF), if a new process with a shorter burst time arrives, the CPU switches to that process immediately.
Example: If P1 (10 ms) is running and P2 (3 ms) arrives, P1 is preempted, and P2 executes first.
Advantages & Disadvantages
Pros:
Best for minimizing waiting time
Good for batch processing
Cons:
Difficult to implement (since burst time is not known beforehand)
Starvation issue (Longer processes might never get CPU time)
Applications of SJF
Batch processing systems
Job scheduling in databases
Load balancing in cloud computing
Would you like a Python/C++ program to implement SJF Scheduling?