Shortest Job First (SJF): The CPU Scheduling Algorithm Every Software Engineer Should Understand

Code with Obaid | Article 04

Shortest Job First (SJF): The CPU Scheduling Algorithm Every Software Engineer Should Understand

From operating system fundamentals to interview-ready problem solving

Imagine you're standing in a queue at a service counter. One person needs 2 minutes, another needs 20 minutes, and another needs 5 minutes. Would serving the shortest request first help everyone finish earlier? Often, yes. But what happens to the person waiting for 20 minutes if shorter requests keep arriving?

Welcome to Shortest Job First (SJF) - an operating system concept that teaches us something much bigger than CPU scheduling: optimizing one metric can create problems somewhere else.

1. Context: What is SJF, and why does it exist?

Shortest Job First (SJF) is a CPU scheduling algorithm that selects the ready process with the shortest estimated CPU burst time for execution.

Why does it matter? Because a CPU is a shared resource. When multiple processes compete for it, the operating system needs a policy for deciding who runs next. SJF aims to minimize the average waiting time of processes.

This makes it an important concept for operating systems exams, technical interviews, and understanding scheduling trade-offs in real systems.

2. The core concept: Understand it in two ways

The simple explanation

Imagine a restaurant with one chef. Three orders are waiting:

• Order A: 8 minutes
• Order B: 2 minutes
• Order C: 4 minutes

If the chef prepares A, B, C, their waiting times are 0, 8, and 10 minutes. Average waiting time: 6 minutes.

If the chef prepares B, C, A, the waiting times are 0, 2, and 6 minutes. Average waiting time: approximately 2.67 minutes.

Same orders. Same total cooking time. A different schedule produces less waiting.

The technical explanation

In operating systems, SJF chooses the ready process with the smallest next CPU burst. Two variants matter:

• Non-preemptive SJF: Once a process gets the CPU, it continues until its CPU burst finishes or it blocks.
• Shortest Remaining Time First (SRTF): The preemptive counterpart. If a new process arrives with a shorter remaining CPU burst, it can preempt the currently running process.

Important distinction: SJF is a scheduling policy, not a guarantee that the shortest process always finishes first. Arrival times and the current execution state matter.

3. Why does SJF minimize average waiting time?

This is a favorite interview question because it tests whether you understand the reasoning, not just the definition.

Consider two processes ready at the same time: Process A needs 8 ms. Process B needs 3 ms. If A runs first, B waits 8 ms. Their total waiting time is 8 ms. If B runs first, A waits 3 ms. Their total waiting time is 3 ms.

Why? Because when a longer job runs first, every shorter job behind it inherits that delay.

The intuition behind the proof

Suppose two consecutive jobs have burst times (a) and (b), and both are ready before either begins. If A runs before B, B incurs an additional wait of (a). If B runs before A, A incurs an additional wait of (b). The other jobs' waiting-time contributions remain unchanged when we swap these two adjacent jobs.

Therefore, placing the shorter job first cannot increase the combined waiting time of the pair: (b \leq a). Repeatedly swapping any out-of-order pair produces a shortest-first sequence without increasing total waiting time. Hence, sorting jobs by increasing burst length minimizes total and average waiting time.

The crucial assumption: All jobs are available for scheduling together, and their CPU burst times are known. With different arrival times, the scheduler must also respect which jobs are actually ready. SRTF has the corresponding optimality result for minimizing total waiting time when arrival times and burst lengths are known and preemption is allowed.

4. Walk through an interview example

Assume all four processes arrive at time 0.

SJF schedules the processes in ascending order of burst time.

Gantt chart

0 ─ P4 ─ 3 ─ P1 ─ 9 ─ P3 ─ 16 ─ P2 ─ 24

For this example, waiting time is the time a process spends in the ready queue before its first execution.

Average waiting time: [ \frac{0+3+9+16}{4}=\boxed{7\text{ ms}} ]

Under FCFS, the original order P1, P2, P3, P4 gives waiting times of 0, 6, 14, and 21 ms.

[ \frac{0+6+14+21}{4}=10.25\text{ ms} ]

SJF reduces average waiting time from 10.25 ms to 7 ms in this example. Notice what happened: the shortest process finished first, but the longest process waited until the end. That leads us to SJF's biggest weakness.

5. Starvation: When optimization becomes unfair

Starvation occurs when a process waits indefinitely because scheduling decisions repeatedly favor other processes.

Imagine a 30 ms job waiting in the ready queue. New jobs requiring only 1-2 ms keep arriving. If the scheduler always chooses the shortest available job, the long job might never execute. This is especially concerning when short jobs arrive continuously.

How can we address it?

• Aging: Gradually increase a waiting process's priority.
• Priority scheduling with safeguards: Give long-waiting processes a chance to run.
• Round Robin: Give ready processes time slices for better sharing, accepting extra context-switch overhead.
• Maximum-wait policies: Prevent a process from waiting beyond an acceptable threshold.

Aging is a technique, not an automatic property of standard SJF. Adding it changes the scheduling policy and may sacrifice the minimum average waiting time.

6. The catch: How can an OS predict CPU burst time?

Real operating systems generally cannot know exactly how long a process's next CPU burst will last. A process might finish quickly, enter a loop, or wait for I/O. So how can SJF work if its most important input is unknown?

One classical solution is exponential averaging, which estimates the next CPU burst using previous observations.

[ \tau_{n+1}=\alpha t_n+(1-\alpha)\tau_n ]

Where:

• (t_n): Actual duration of the latest CPU burst.
• (\tau_n): Previous burst-time estimate.
• (\tau_{n+1}): New estimate.
• (\alpha): A weighting factor between 0 and 1.

For example, suppose the previous estimate is 10 ms, the latest actual burst is 4 ms, and (\alpha=0.5).

[ \tau_{n+1}=0.5(4)+0.5(10)=7\text{ ms} ]

The estimate moves from 10 ms to 7 ms. A higher alpha gives more weight to recent behavior; a lower alpha preserves more of the previous estimate.

Big-word alert - prediction vs. measurement: An estimate is not a guarantee. If the prediction is inaccurate, the scheduler may choose a process that turns out to be longer than another waiting process.

7. Practical implementation: Write it, then defend it

Here is a small Python implementation for the special case in which all processes arrive at time 0.

def sjf ( processes ):
    # Each process is (process_id, burst_time)
    ordered = sorted ( processes , key = lambda p : p [ 1 ])
    elapsed = 0
    waiting_times = {}
    for process_id , burst_time in ordered :
        waiting_times [ process_id ] = elapsed
        elapsed += burst_time
    average = sum ( waiting_times . values ()) / len ( ordered )
    return ordered , waiting_times , average

processes = [ ( " P1 " , 6 ), ( " P2 " , 8 ), ( " P3 " , 7 ), ( " P4 " , 3 ), ]
order , waiting , average = sjf ( processes )
print ( " Order: " , [ p [ 0 ] for p in order ])
print ( " Waiting times: " , waiting )
print ( " Average waiting time: " , average )

Expected scheduling order: P4, P1, P3, P2. Average waiting time: 7.0 ms.

Production caveat: This implementation is not a complete OS scheduler. It assumes every process is ready from the beginning, knows each burst time, and has only one relevant CPU burst. A more realistic simulation must track arrival times, the ready queue, process states, I/O blocking, and either preemption or non-preemption.

How this connects to production systems

SJF is useful for reasoning about batch workloads where jobs are available together and processing times can be estimated. For example, a batch-processing platform might have small report-generation jobs and large data-processing jobs. Prioritizing short jobs can improve average completion or waiting times, but can also delay large jobs.

Production systems may instead use weighted fair queuing, priority queues, deadlines, resource limits, or multiple scheduling classes. Actual CPU schedulers are more sophisticated than simply sorting processes by their expected burst duration. Do not claim that modern operating systems universally use SJF.

The value of SJF is both theoretical and practical: it helps engineers understand scheduling objectives, estimation, fairness, and trade-offs.

8. Pros, cons, and the professional perspective

A senior engineer asks a question that beginners often miss: “What are we optimizing, and what are we willing to sacrifice?”

SJF optimizes average waiting time under specific assumptions. It does not automatically optimize fairness, response time for every user, deadlines, throughput in every workload, or overall system performance. The right algorithm depends on the service-level objective and workload.

9. Interview questions you should be ready for

Q1. What is the difference between SJF and SRTF?

SJF is conventionally non-preemptive. SRTF allows preemption when a process arrives with a shorter remaining CPU burst.

Q2. Can SJF cause starvation?

Yes. Repeated arrivals of short jobs can keep postponing a long job.

Q3. Why does SJF minimize average waiting time?

For jobs available together, swapping an adjacent longer-before-shorter pair reduces or preserves the sum of waiting times. Sorting by increasing burst length therefore minimizes the average.

Q4. What happens when two processes have the same burst time?

Either may be chosen first under ordinary SJF. A tie-breaking rule, such as FCFS among equal estimates, can make the policy deterministic.

Q5. What if a short job arrives after a long job has already started?

In non-preemptive SJF, the running process continues. In SRTF, the newly arrived job may preempt it if its estimated remaining time is shorter.

Q6. Is SJF always better than FCFS?

Not for every objective or workload. It can minimize average waiting time under its assumptions, but FCFS is simpler and avoids starvation caused by shortest-first selection alone.

Q7. How would you reduce starvation?

Use aging or another policy that explicitly protects long-waiting jobs. Explain the trade-off: improving fairness may increase average waiting time.

Q8. How would you implement SJF efficiently?

For a static batch, sorting is straightforward and takes (O(n\log n)) time. For a dynamic ready queue, a min-heap can select the shortest estimated burst in (O(\log n)) per insertion or removal, provided the scheduler handles arrivals and preemption correctly.

10. How fresh graduates should prepare for algorithm interviews

Don't memorize eight answers and hope the interviewer stops there. Build the ability to reason from first principles.

• Understand the objective. Know what waiting time, turnaround time, response time, and CPU utilization mean.
• Draw the schedule. Use a Gantt chart before doing calculations.
• Solve by hand. Calculate waiting time and average waiting time for FCFS, SJF, and SRTF.
• Change one assumption. Introduce different arrival times, equal burst lengths, or continuous short-job arrivals.
• Implement it. Write a simple simulator and explain its time complexity.
• Defend the trade-off. Discuss starvation, estimation errors, and fairness.
• Practice follow-ups aloud. Explain why a decision works, when it fails, and what alternative you would choose.

For a fresh graduate, aim to explain the definition, derive the waiting-time result, solve a numerical example, and implement the basic version without help. For a candidate targeting roughly two years of experience, go further: discuss dynamic arrivals, preemption, imperfect estimates, production objectives, and how you would test the scheduler.

Final mental model

Remember these five things:

• SJF: Choose the ready process with the shortest estimated CPU burst.
• Why it works: Short jobs avoid being trapped behind long jobs.
• Why it fails: Continuous short arrivals can starve long jobs.
• What makes it realistic: Burst prediction is an estimate, not perfect knowledge.
• What makes you interview-ready: You can calculate, implement, challenge assumptions, and explain trade-offs.

The real lesson isn't “shortest is always best.” It's that good engineering starts by identifying what you want to optimize - and understanding what that optimization costs.

Test yourself: SJF interview challenge

Try these questions before checking your notes. Answers are intentionally withheld so you can share your solutions in the comments and revisit the article tomorrow.

• Q1 - Fundamentals: Define SJF and explain its main objective in one or two sentences.
• Q2 - Calculation: Three processes arrive at time 0 with CPU bursts P1 = 5 ms, P2 = 2 ms, and P3 = 4 ms. Find the SJF execution order, each process's waiting time, and the average waiting time.
• Q3 - Proof: Why does placing the shorter of two adjacent jobs first reduce or preserve total waiting time?
• Q4 - Scenario: A long-running process has waited for several seconds, but short jobs keep arriving. What problem is occurring, and name one possible solution.
• Q5 - Prediction: The previous CPU burst estimate is 12 ms, the latest actual burst is 4 ms, and alpha is 0.25. Calculate the new estimate using exponential averaging.
• Q6 - Scheduling decision: A 10 ms process is running. A new process arrives with an estimated CPU burst of 3 ms. What happens under non-preemptive SJF? What could happen under SRTF?
• Q7 - Implementa