Day 02Part 06- Operating System for Gate – Shortest Job First Scheduling Algorithm

Day 02Part 06- Operating System for Gate – Shortest Job First Scheduling Algorithm

 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:

1. Non-Preemptive SJF – Once a process starts execution, it cannot be interrupted.
2. 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:

1. At t = 0, P1 starts execution (since no other process has arrived).
2. At t = 2, P2 arrives, but P1 is still running.
3. At t = 4, P3 arrives.
4. At t = 7, P3 (Shortest Job: 1) is selected.
5. At t = 8, P2 (Shortest Job: 4) is selected.
6. At t = 12, P4 (Shortest Job: 4) is selected.

Gantt Chart:

Calculation of Waiting Time & Turnaround 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?

Day 02Part 06- Operating System for Gate – Shortest Job First Scheduling Algorithm

Unit IV – CPU Scheduling and Algorithm

OPERATING SYSTEM

Here’s a clear and exam-focused explanation of Shortest Job First (SJF) Scheduling Algorithm – perfect for GATE, B.Tech, or Operating System coursework. This is Day 02 – Part 06 of an OS series.

---

Operating System – Scheduling Algorithms

Day 02, Part 06: Shortest Job First (SJF)

---

What is SJF (Shortest Job First)?

SJF is a CPU scheduling algorithm where the process with the smallest burst time (execution time) is executed first.

It is also known as:

• Shortest Next Job (SNJ)
• A type of non-preemptive scheduling

---

How SJF Works:

• Among all the available processes in the ready queue, the CPU chooses the one with the shortest burst time.
• Once selected, the CPU executes that process till completion (non-preemptive).

---

Characteristics:

Property	Value
Type	Non-preemptive (basic SJF)
Criteria	Shortest burst time
Optimality	Minimum average waiting time
Starvation	Yes (long jobs may wait forever)
Preemptive Version	Yes, called SRTF

---

Example:

Assume 4 processes with the following burst times (all arrive at time 0):

Process	Burst Time
P1	6
P2	8
P3	7
P4	3

Step-by-step Execution:

• At time 0, all processes are available.
• Choose process with shortest burst time = P4 (3)

Execution Order:

P4 → P1 → P3 → P2

---

Calculations:

Completion Time (CT), Turnaround Time (TAT), Waiting Time (WT):

Process	BT	CT	TAT = CT-AT	WT = TAT – BT
P4	3	3	3	0
P1	6	9	9	3
P3	7	16	16	9
P2	8	24	24	16

Averages:

• Average TAT = (3+9+16+24)/4 = 13
• Average WT = (0+3+9+16)/4 = 7

SJF gives the minimum average waiting time among all non-preemptive algorithms.

---

Key Points for GATE:

Concept	Remember
SJF Optimality	Proven optimal for non-preemptive scheduling (shortest WT)
Starvation Possible	Yes, if short jobs keep coming
Preemptive Form	SRTF (Shortest Remaining Time First)
Used Where	Batch systems, predictable jobs

---

MCQ Practice (GATE style):

Q: In SJF scheduling, which of the following is TRUE?
a) Longest job executes first
b) Starvation is not possible
c) Shortest available job executes first
d) SJF always uses priorities

Answer: c) Shortest available job executes first

---

Would you like:

• SRTF (Preemptive SJF) explanation next?
• Python program or Gantt chart for simulation?
• PDF notes + GATE previous questions with solutions?

Just let me know!

Day 02Part 06- Operating System for Gate – Shortest Job First Scheduling Algorithm