Free lesson · Operating Systems

Demonstrate exponential averaging for burst prediction

Easy11 min readoperating-systemsosconcurrency

What If We Ran the Shortest Job First?

The convoy effect in FCFS happens because a long process runs before short ones, making the short ones wait an unreasonable amount of time. The fix is obvious: run the shortest job first. If you always pick the process with the smallest CPU burst time from the ready queue, short jobs finish quickly and long jobs wait a bit longer, but the average waiting time across all processes is minimized.

This algorithm is called Shortest Job First (SJF), and it has a remarkable theoretical property: among all non-preemptive scheduling algorithms, SJF produces the minimum average waiting time. This is provably optimal - no other non-preemptive algorithm can do better. The proof is intuitive: running a short job before a long one reduces the waiting time of the short job by the length of the long job, while only increasing the long job's waiting time by the length of the short job. Since the short job is shorter, you gain more than you lose.

Despite being optimal in theory, SJF has a critical practical problem: you cannot know the burst time in advance. When a process enters the ready queue, the OS does not know how long it will run before blocking or finishing. It might run for 1 millisecond or 1 second. SJF requires knowledge of the future, which is why it is sometimes called an "oracle algorithm" - perfect in hindsight, impossible to implement exactly.

Understanding SJF matters for interviews because it establishes the theoretical benchmark for scheduling performance. When you discuss any practical scheduling algorithm, you can reference SJF as the ideal: "This algorithm approximates SJF by estimating burst lengths based on historical behavior."

How SJF Works

The algorithm maintains a ready queue sorted by burst time (shortest first). When the CPU becomes free, the scheduler picks the process with the smallest burst time from the ready queue and runs it.

In its non-preemptive form, once a process starts running, it runs to completion (or until it blocks on I/O), even if a shorter process arrives while it is running. In its preemptive form - called Shortest Remaining Time First (SRTF) - if a new process arrives with a shorter burst than the time remaining on the currently running process, the scheduler preempts the running process and switches to the new, shorter one.

Let us see both versions with a worked example. Suppose four processes arrive with these parameters:

Non-Preemptive SJF

At time 0, only P1 is available. P1 runs for 7 ms (it runs to completion since SJF is non-preemptive once started). At time 7, P2 (burst=4), P3 (burst=1), and P4 (burst=4) are all in the ready queue. The shortest is P3 (burst=1), so P3 runs next. Then P2 and P4 tie at burst=4 - break the tie with arrival order, so P2 runs, then P4.

gantt
    title Non-Preemptive SJF
    dateFormat X
    axisFormat %s

    section Schedule
    P1 (burst=7) :p1, 0, 7
    P3 (burst=1) :p3, 7, 8
    P2 (burst=4) :p2, 8, 12
    P4 (burst=4) :p4, 12, 16

This Gantt chart shows non-preemptive SJF scheduling. P1 runs from time 0 to 7 because it is the only process available at time 0. At time 7, three processes are ready. P3 with the shortest burst of 1 runs next from 7 to 8. Then P2 runs from 8 to 12, and P4 from 12 to 16. The average waiting time is 4.0 milliseconds.

Preemptive SJF (Shortest Remaining Time First - SRTF)

Now the same processes, but the scheduler can preempt. At time 0, P1 starts running (it is the only process). At time 2, P2 arrives with burst=4. P1 has 5 ms remaining. Since 4 < 5, P2 is shorter, so the scheduler preempts P1 and runs P2. At time 4, P3 arrives with burst=1. P2 has 2 ms remaining. Since 1 < 2, P3 preempts P2. P3 runs from 4 to 5 (1 ms). At time 5, P4 arrives with burst=4. The remaining times are: P2=2, P1=5, P4=4. P2 has the shortest remaining time, so P2 resumes. P2 finishes at time 7. Then P4 (4 ms remaining) runs from 7 to 11. Then P1 (5 ms remaining) runs from 11 to 16.

SRTF produced a lower average waiting time (3.0 vs 4.0) and lower average turnaround time (7.0 vs 8.0) than non-preemptive SJF. Preemption helps because it lets a newly arrived short job interrupt a long one that still has significant time remaining. The short job finishes quickly, reducing the overall average waiting time.

gantt
    title Preemptive SRTF
    dateFormat X
    axisFormat %s

    section Schedule
    P1 (7-runs 2ms)    :p1a, 0, 2
    P2 (4-runs 2ms)    :p2a, 2, 4
    P3 (1-runs 1ms)    :p3, 4, 5
    P2 (remaining 2ms) :p2b, 5, 7
    P4 (4ms)           :p4, 7, 11
    P1 (remaining 5ms) :p1b, 11, 16

This Gantt chart shows SRTF (preemptive SJF) scheduling. P1 starts at time 0 but is preempted at time 2 when P2 arrives with a shorter remaining time. P2 runs until time 4 when P3 arrives with an even shorter burst. P3 runs for 1 ms and finishes. P2 resumes and finishes at time 7. P4 runs from 7 to 11. P1 finally finishes its remaining 5 ms from 11 to 16. The average waiting time is 3.0 ms - lower than non-preemptive SJF.

Interview: "Explain SJF scheduling. What is its advantage and disadvantage?"

"SJF selects the process with the shortest CPU burst time from the ready queue. It is provably optimal for minimizing average waiting time among non-preemptive algorithms. Its preemptive version, SRTF, extends this to preempt a running process when a shorter one arrives, achieving even lower average waiting times.

The main advantage is optimal average waiting time - no non-preemptive algorithm can do better. The main disadvantage is that it requires knowing the burst time in advance, which is impossible in a general-purpose OS. Additionally, SJF can starve long processes - if short jobs keep arriving, a long job may wait indefinitely."

The Prediction Problem: How Do You Know the Burst Time?

SJF is optimal, but it needs information the OS does not have - how long each process will run before its next block or completion. No process announces "I will use the CPU for exactly 4.7 milliseconds" when it enters the ready queue.

The practical solution is estimation: predict the next CPU burst based on past behavior. If a process's previous CPU bursts were 3, 4, 3, and 5 milliseconds, a reasonable prediction for the next burst is somewhere around 4 milliseconds. The process's history becomes a predictor of its future behavior.

The most common prediction technique is exponential averaging. The predicted next burst τ(n+1) is a weighted combination of the most recent actual burst t(n) and the previous prediction τ(n):

τ(n+1) = α × t(n) + (1 − α) × τ(n)

Where α (alpha) is a parameter between 0 and 1 that controls how much weight to give recent behavior versus historical behavior. A high α (like 0.8) makes the prediction respond quickly to recent changes - good for processes whose behavior varies. A low α (like 0.2) smooths out variations - good for processes with stable behavior. In practice, α = 0.5 is a common default.

Let us trace through an example. Suppose a process has the following actual burst times: 6, 4, 6, 4, 13, 13, 13. With α = 0.5 and an initial prediction τ(0) = 10:

Notice how the prediction gradually tracks the actual behavior. When the burst length jumps from 4 to 13, the prediction takes a few rounds to catch up. The smoothing prevents overreaction to one anomalous burst, but it also means the prediction lags behind sudden changes. This tradeoff - responsiveness versus stability - is inherent in any prediction system.

Tip: For the interview: Exponential averaging appears not just in scheduling but throughout computer science - it is used in TCP congestion control, load balancer health checks, and cache eviction policies. If you can explain exponential averaging once, you can apply it to many different contexts. The core idea is always the same: predict the future as a weighted average of the recent past and the historical trend.

The Starvation Problem in SJF

SJF has a serious fairness problem: starvation. If short processes keep arriving continuously, a long process may never get to run. Consider a process with a burst time of 100 ms. If new 1-ms processes arrive every millisecond, the scheduler will always pick them because they are shorter. The 100-ms process is pushed further and further back in the queue - it is starved of CPU time.

Starvation is not just a theoretical concern. In a web server where most requests take 5 ms to process but some complex requests take 500 ms, a pure SJF scheduler would always prioritize the fast requests. The complex requests would wait indefinitely during busy periods. This violates the reasonable expectation that every request will eventually be served.

The solution to starvation is aging - gradually increasing the priority of processes that have been waiting a long time. If a process has been in the ready queue for 10 seconds, its effective burst-time estimate is reduced (making it more likely to be selected) regardless of its actual burst time. Eventually, even the longest process gets promoted to the front of the queue. We cover aging in detail in Topic 06 (Priority Scheduling).

# Demonstrate exponential averaging for burst prediction
alpha = 0.5
initial_prediction = 10.0
actual_bursts = [6, 4, 6, 4, 13, 13, 13]

prediction = initial_prediction
print(f"Alpha = {alpha}, Initial prediction = {prediction}")
print(f"{'Burst #':<10} {'Actual':<10} {'Predicted':<12} {'Error':<10}")
print("-" * 42)

for i, actual in enumerate(actual_bursts):
    error = abs(actual - prediction)
    print(f"{i+1:<10} {actual:<10} {prediction:<12.1f} {error:<10.1f}")
    prediction = alpha * actual + (1 - alpha) * prediction

print(f"\nFinal prediction for next burst: {prediction:.1f}")

SJF vs FCFS: The Quantitative Comparison

Let us compare SJF and FCFS directly using the convoy effect example from Topic 03:

SJF reduces average waiting time by 96% compared to FCFS on this workload. The improvement is not incremental - it is transformational. This is why SJF is the theoretical gold standard for scheduling performance, even though its practical implementation requires estimation.

Where SJF Ideas Appear in Real Systems

Pure SJF is impractical for OS scheduling because burst times are unknown. But the principle behind SJF - prioritize short tasks over long ones - appears throughout production systems.

Web server request routing. Some load balancers use a variant of SJF called "shortest queue first" or "least connections" - they route new requests to the server with the fewest in-flight requests, which is a proxy for routing to the server that will process the request fastest. This is not exact SJF, but it captures the same intuition: give resources to tasks that will finish quickly.

Database query scheduling. Some database engines prioritize short queries over long ones. PostgreSQL's cost-based optimizer estimates the cost (roughly proportional to execution time) of each query. A sophisticated query scheduler could use these estimates to schedule cheap queries before expensive ones, approximating SJF for database workloads.

Job schedulers in distributed systems. Systems like Apache Spark and Hadoop YARN often implement Fair Scheduler or Capacity Scheduler with small-job-fast configurations that let short jobs run ahead of long batch jobs. This is the SJF principle applied at the distributed computing level - small jobs should not wait behind MapReduce jobs that take hours.

Network packet scheduling. Network routers sometimes use Weighted Fair Queueing (WFQ), which gives smaller packets (and shorter flows) preferential treatment. The same principle: getting short items through the system quickly improves average latency without significantly hurting long items.

The common thread across all these examples is the SJF insight: in a mixed workload, running short tasks first dramatically reduces average waiting time at a modest cost to the long tasks. This insight is one of the most powerful and broadly applicable principles in computer science.

Non-Preemptive vs Preemptive: When Does Preemption Help?

The difference between SJF and SRTF comes down to a question: what happens when a short job arrives while a long job is already running?

In non-preemptive SJF, the long job keeps the CPU. The short job waits until the long job finishes. This means the short job's waiting time includes the remaining duration of the current long job - potentially wasting significant time if the long job has many milliseconds left.

In SRTF, the scheduler compares the new job's burst time to the remaining time of the running job. If the new job is shorter, the running job is preempted. The short job runs immediately, finishes quickly, and the long job resumes afterward. The long job's total completion time increases by the short job's burst time, but the short job's waiting time drops to zero (or near zero).

Preemption always produces lower or equal average waiting time compared to non-preemption for SJF. The mathematical reason is that preemption allows the scheduler to react to new information (a short job arriving) rather than being locked into a decision made when the long job started. However, preemption has costs: each preemption is a context switch, with the associated register-save, TLB-flush, and cache-warmup overhead. In practice, the benefit of lower average waiting time almost always outweighs the cost of occasional context switches, which is why SRTF is preferred over non-preemptive SJF when scheduling is being optimized.

Summary: SJF and SRTF Properties

Pros:
- Optimal average waiting time for non-preemptive algorithms (SJF)
- Even better average waiting time with preemption (SRTF)
- Naturally favors I/O-bound processes (short CPU bursts)
- Provides the theoretical benchmark for scheduling performance
- The SJF principle (short tasks first) applies broadly across systems

Cons:
- Requires knowing burst time in advance (impossible in general)
- Can only be approximated using prediction (exponential averaging)
- Starvation of long processes when short processes keep arriving
- Prediction errors degrade performance - bad estimates produce bad schedules
- Preemptive version (SRTF) adds context switch overhead

Exercise: Starter: Given processes P1 (arrival=0, burst=5), P2 (arrival=1, burst=3), P3 (arrival=2, burst=1), P4 (arrival=3, burst=2), calculate the average waiting time under non-preemptive SJF. Compare it to FCFS. How much improvement does SJF provide?

Intermediate: Repeat the exercise using SRTF (preemptive SJF). Trace through the schedule at each time unit, noting when preemption occurs. Is the average waiting time lower than non-preemptive SJF? By how much?

Advanced: Implement exponential averaging in code. Given a sequence of actual burst times, compute predictions with α = 0.2, 0.5, and 0.8. Plot (or tabulate) how quickly each α value tracks a sudden change in burst length (e.g., from 5 ms bursts to 50 ms bursts). Which α would you choose for a web server where request processing times are highly variable?

Back to Operating Systems