1. Introduction

Shortest Job First (SJF) is a CPU scheduling algorithm that selects the process with the smallest CPU burst time for execution next. Among all processes available in the ready queue, the process requiring the least amount of CPU time is given priority.

The fundamental idea behind SJF is simple:

Execute short processes first and postpone longer processes until later.

This approach significantly reduces the waiting time experienced by short processes and improves overall scheduling efficiency.

SJF is one of the most important scheduling algorithms because it has a remarkable theoretical property:

SJF produces the minimum possible average waiting time among all non-preemptive CPU scheduling algorithms.

For this reason, SJF is often considered the benchmark against which other scheduling algorithms are compared.

However, despite its optimality, SJF has practical limitations because operating systems generally cannot know the exact future CPU burst time of a process.

2. Basic Concept

The SJF algorithm makes scheduling decisions based on:

CPU Burst Time

The CPU burst time represents the amount of CPU execution required by a process before it either terminates or performs an I/O operation.

The scheduler examines all processes in the ready queue and selects:

The process with the shortest burst time.

Scheduling Rule

Ready Queue

P1 = 7
P2 = 3
P3 = 1
P4 = 5

Select → P3

because P3 has the smallest burst time.

Variants of SJF

SJF exists in two forms:

Non-Preemptive SJF

Once a process starts execution:

• It cannot be interrupted.

• It runs until completion.

Preemptive SJF

Known as:

Shortest Remaining Time First (SRTF)

A newly arriving shorter process may preempt the currently running process.

SRTF will be covered separately.

This section focuses only on:

Non-Preemptive SJF

3. Working Mechanism

The SJF scheduler continuously evaluates processes in the ready queue.

Whenever the CPU becomes available:

1. Examine all ready processes.

2. Compare burst times.

3. Select process with smallest burst time.

4. Allocate CPU.

5. Execute until completion.

6. Repeat.

Execution Rule

Select Process
With Minimum Burst Time

Conceptual Example

Suppose the ready queue contains:

P1 = 8
P2 = 2
P3 = 5
P4 = 1

Execution order becomes:

P4 → P2 → P3 → P1

Shortest jobs always execute first.

4. Example (Non-Preemptive SJF)

Consider the following processes:

Step-by-Step Execution

Time = 0

Only P1 has arrived.

Ready Queue

P1

Therefore:

Execute P1

Time = 7

P1 completes.

Now available:

P2 = 4
P3 = 1
P4 = 4

Shortest burst:

P3

Execute P3.

Time = 8

Remaining:

P2 = 4
P4 = 4

Both have equal burst time.

Tie typically broken using arrival order.

Therefore:

P2 → P4

Gantt Chart

0        7      8       12      16

|  P1  | P3 |  P2  |  P4  |

5. Calculations

Completion Time (CT)

P1

CT = 7

P3

CT = 8

P2

CT = 12

P4

CT = 16

Turnaround Time (TAT)

Definition:

Calculations

P1

7 − 0 = 7

P3

8 − 2 = 6

P2

12 − 1 = 11

P4

16 − 3 = 13

Waiting Time (WT)

Definition:

Calculations

P1

7 − 7 = 0

P3

6 − 1 = 5

P2

11 − 4 = 7

P4

13 − 4 = 9

Average Waiting Time

Average WT = 5.25 units

Average Turnaround Time

Average TAT = 9.25 units

6. Key Characteristics

Non-Preemptive

Once execution begins:

• Process cannot be interrupted.

• CPU remains allocated until completion.

Burst-Time Based

Selection depends entirely on:

Shortest CPU Burst

Waiting Time Optimization

Designed specifically to reduce waiting times.

Requires Burst-Time Information

Scheduler must know or estimate:

Future CPU Burst Time

before scheduling.

7. Why SJF is Optimal

One of the most important theoretical results in operating systems is:

SJF minimizes average waiting time among all non-preemptive scheduling algorithms.

Intuition

Suppose:

Long Job = 20 units
Short Job = 2 units

If the long job executes first:

20 → 2

The short job waits:

20 units

However:

2 → 20

The short job completes quickly and the average waiting time decreases.

Key Idea

SJF prevents short jobs from being trapped behind long jobs.

This directly reduces:

• Average waiting time

• Average turnaround time

compared to FCFS.

8. Major Limitation

8.1 Burst Time Prediction Problem

The biggest challenge of SJF is:

The operating system cannot know future CPU burst times exactly.

A process has not yet executed, so its future execution length is unknown.

Example:

Process Arrives
      ↓
Future Burst Unknown

Therefore true SJF cannot be implemented perfectly in real systems.

Burst-Time Estimation

Operating systems estimate future bursts using previous behavior.

A common estimation formula is:

Where:

• τₙ₊₁ = predicted next burst

• tₙ = actual previous burst

• τₙ = previous prediction

• α = weighting factor (0 ≤ α ≤ 1)

Interpretation

Large α

Gives greater importance to recent behavior.

Small α

Relies more heavily on historical averages.

This technique is known as:

Exponential Averaging

9. Starvation Problem

A major drawback of SJF is:

Starvation

What is Starvation?

A process suffers starvation when it waits indefinitely without receiving CPU time.

Example

Suppose:

Long Process = 20

arrives.

Then many short processes arrive continuously:

1,1,2,1,2,1,1,1...

The scheduler always selects shorter jobs.

Result:

Long Process Never Executes

Consequences

• Unfair scheduling

• Unbounded waiting time

• Reduced predictability

Solution

Aging techniques can be used:

Waiting Longer
      ↓
Higher Priority

This reduces starvation risk.

10. Comparison with FCFS

Key Difference

FCFS:

First Arrive
     ↓
First Execute

SJF:

Shortest Burst
      ↓
First Execute

11. When is SJF Suitable?

Although perfect SJF is difficult to implement, it works well in certain environments.

Batch Systems

Jobs are often predictable.

Examples:

• Scientific computation

• Payroll processing

• Offline analytics

Systems with Burst-Time Estimates

If reliable burst predictions exist:

Estimated Burst
      ↓
Efficient Scheduling

SJF becomes practical.

Waiting-Time Sensitive Systems

When minimizing waiting time is the primary objective:

Minimum Average Waiting Time

SJF is often the best theoretical choice.

Performance Summary