Intermediate 3 min · July 14, 2026

Shortest Remaining Time First (SRTF): Preemptive SJF Scheduling

Q: What is the difference between SJF and SRTF?

SJF (Shortest Job First) is non-preemptive: once a process starts, it runs to completion. SRTF is preemptive: if a new process arrives with a shorter remaining time, the current process is preempted.

Q: Can SRTF cause starvation?

Yes, if short processes keep arriving, a long process may never get CPU. Aging or priority boosting can mitigate this.

Q: How do you handle unknown burst times in SRTF?

Use predictive techniques like exponential averaging of past burst times to estimate future ones.

Q: Is SRTF used in modern operating systems?

Not in pure form. Linux CFS uses a similar idea but with fairness. Real-time systems may use variants.

Q: What is the time complexity of SRTF?

Each event (arrival, preemption, completion) requires O(log n) operations with a min-heap, where n is the number of processes.

Master SRTF scheduling: learn how preemptive shortest job first minimizes turnaround time, with code examples, real-world incidents, and debugging tips..

Naren Founder & Principal Engineer

20+ years shipping performance-critical code where algorithms decide the bill. Drawn from code that ran under real load.

✓ Production

production tested

July 15, 2026

last updated

2,398

articles · all by Naren

Before you start⏱ 15-20 min read

✓Basic understanding of CPU scheduling concepts
✓Familiarity with priority queues (heaps)
✓Knowledge of process states and context switching

● Production Incident 🔎 Debug Guide ⚙ Triage Commands

⚡Quick Answer

SRTF is a preemptive CPU scheduling algorithm that selects the process with the smallest remaining burst time.
It minimizes average turnaround and waiting time but can cause starvation for long processes.
Implementation requires a priority queue (min-heap) and preemption on new process arrival.
Context switching overhead is higher due to frequent preemptions.
Used in real-time systems where response time is critical.

✦ Definition~90s read

What is Shortest Remaining Time First?

Shortest Remaining Time First (SRTF) is a preemptive CPU scheduling algorithm that always executes the process with the smallest remaining burst time, preempting the current process if a shorter one arrives.

★

Imagine a supermarket with one checkout counter.

Plain-English First

Imagine a supermarket with one checkout counter. Customers (processes) have different numbers of items (burst times). The cashier (CPU) serves the customer with the fewest items first. But if a new customer with even fewer items arrives, the cashier stops the current customer and serves the new one. This keeps the line moving quickly for small purchases, but a customer with a huge cart might wait forever.

In operating systems, CPU scheduling decides which process runs next. Among various algorithms, Shortest Job First (SJF) is optimal in terms of minimizing average waiting time, but its non-preemptive variant can lead to poor response times. Shortest Remaining Time First (SRTF) is the preemptive version of SJF: it dynamically selects the process with the smallest remaining burst time, preempting the currently running process if a new process with a shorter remaining time arrives. This makes SRTF ideal for interactive systems where responsiveness matters. However, it introduces challenges like starvation of long processes and high context-switching overhead. In this tutorial, you'll learn how SRTF works, how to implement it efficiently using a min-heap, and how to debug common issues in production. We'll also explore a real-world incident where SRTF-like logic caused a system outage, and provide a cheat sheet for quick debugging.

What is SRTF?

Shortest Remaining Time First (SRTF) is a preemptive CPU scheduling algorithm. It is the preemptive counterpart of Shortest Job First (SJF). In SRTF, the scheduler always selects the process with the smallest remaining burst time to execute. If a new process arrives with a remaining time less than the current process's remaining time, the current process is preempted and the new process starts. This ensures that short jobs are executed quickly, minimizing average turnaround and waiting time. However, it can lead to starvation of long processes if short processes keep arriving. SRTF is optimal in terms of average turnaround time among all preemptive scheduling algorithms, but it requires accurate knowledge of burst times, which is often not available in practice. The algorithm is widely used in real-time and interactive systems where response time is critical.

srtf_simulation.pyPYTHON

import heapq

def srtf(processes):
    # processes: list of (arrival_time, burst_time, pid)
    n = len(processes)
    processes.sort(key=lambda x: x[0])  # sort by arrival
    ready_queue = []
    time = 0
    idx = 0
    remaining = {p[2]: p[1] for p in processes}
    completed = {}
    current = None
    current_remaining = 0
    while len(completed) < n:
        # add arrived processes to ready queue
        while idx < n and processes[idx][0] <= time:
            heapq.heappush(ready_queue, (remaining[processes[idx][2]], processes[idx][2]))
            idx += 1
        if current is not None:
            heapq.heappush(ready_queue, (current_remaining, current))
            current = None
        if ready_queue:
            burst, pid = heapq.heappop(ready_queue)
            current = pid
            current_remaining = burst
        # simulate one time unit
        if current is not None:
            current_remaining -= 1
            time += 1
            if current_remaining == 0:
                completed[current] = time
                current = None
        else:
            time += 1
    return completed

# Example usage
processes = [(0, 8, 'P1'), (1, 4, 'P2'), (2, 9, 'P3'), (3, 5, 'P4')]
completion_times = srtf(processes)
print(completion_times)

Output

{'P2': 5, 'P4': 10, 'P1': 17, 'P3': 26}

🔥Why Preemption Matters

📊 Production Insight

In production, burst times are estimates; inaccurate estimates can make SRTF perform worse than simpler algorithms.

🎯 Key Takeaway

SRTF selects the process with the smallest remaining burst time, preempting if a shorter job arrives.

thecodeforge.io

Shortest Remaining Time First

How SRTF Works: Step-by-Step

Consider four processes with arrival times and burst times: P1(0,8), P2(1,4), P3(2,9), P4(3,5). At time 0, only P1 is available, so it runs. At time 1, P2 arrives with burst 4, which is less than P1's remaining 7, so P1 is preempted and P2 runs. At time 2, P3 arrives with burst 9 > P2's remaining 3, so P2 continues. At time 3, P4 arrives with burst 5 > P2's remaining 2, so P2 continues. P2 finishes at time 5. Then the ready queue has P1(7), P3(9), P4(5). The shortest remaining is P4 (5), so it runs. At time 10, P4 finishes. Then P1 (7) runs, then P3 (9). Completion times: P2=5, P4=10, P1=17, P3=26. Average turnaround = (17+5+26+10)/4 = 14.5. Compare to non-preemptive SJF: P1 runs to completion (8), then P2(4), P4(5), P3(9) -> completion times: 8,12,17,26, average = 15.75. SRTF gives lower average.

srtf_gantt.pyPYTHON

def srtf_gantt(processes):
    # returns list of (pid, start, end)
    n = len(processes)
    processes.sort(key=lambda x: x[0])
    ready = []
    time = 0
    idx = 0
    remaining = {p[2]: p[1] for p in processes}
    gantt = []
    current = None
    current_start = None
    while idx < n or ready or current:
        while idx < n and processes[idx][0] <= time:
            heapq.heappush(ready, (remaining[processes[idx][2]], processes[idx][2]))
            idx += 1
        if current is not None:
            heapq.heappush(ready, (remaining[current], current))
            current = None
        if ready:
            burst, pid = heapq.heappop(ready)
            current = pid
            current_start = time
            # run for 1 unit (simplified)
            remaining[pid] -= 1
            time += 1
            if remaining[pid] == 0:
                gantt.append((pid, current_start, time))
                current = None
            else:
                # check for preemption next iteration
                pass
        else:
            time += 1
    return gantt

import heapq
processes = [(0,8,'P1'),(1,4,'P2'),(2,9,'P3'),(3,5,'P4')]
gantt = srtf_gantt(processes)
print(gantt)

Output

[('P1', 0, 1), ('P2', 1, 5), ('P4', 5, 10), ('P1', 10, 17), ('P3', 17, 26)]

💡Visualizing with Gantt Charts

📊 Production Insight

Implementing SRTF in a real OS requires handling interrupts and context switching efficiently.

🎯 Key Takeaway

SRTF requires tracking remaining times and preempting when a shorter job arrives.

Implementing SRTF with a Min-Heap

The most efficient implementation uses a min-heap (priority queue) keyed by remaining burst time. When a process arrives, we push it onto the heap. The scheduler pops the process with the smallest remaining time. If the currently running process is preempted, we push it back with its updated remaining time. This gives O(log n) per event. In Python, we can use the heapq module. The code below simulates SRTF with event-driven simulation. Note that we need to handle the case where no process is ready (idle time). The simulation advances time in discrete steps, but in a real system, time is continuous and preemption happens on timer interrupts or process arrivals.

srtf_heap.pyPYTHON

import heapq

def srtf_simulation(processes):
    # processes: list of (arrival, burst, pid)
    n = len(processes)
    processes.sort(key=lambda x: x[0])
    heap = []
    time = 0
    idx = 0
    remaining = {p[2]: p[1] for p in processes}
    completed = {}
    current = None
    current_remaining = 0
    while len(completed) < n:
        # add all processes that have arrived by current time
        while idx < n and processes[idx][0] <= time:
            heapq.heappush(heap, (remaining[processes[idx][2]], processes[idx][2]))
            idx += 1
        # if a process is running, push it back (preempt if needed)
        if current is not None:
            heapq.heappush(heap, (current_remaining, current))
            current = None
        if heap:
            burst, pid = heapq.heappop(heap)
            current = pid
            current_remaining = burst
        # simulate one time unit
        if current is not None:
            current_remaining -= 1
            time += 1
            if current_remaining == 0:
                completed[current] = time
                current = None
        else:
            time += 1
    return completed

processes = [(0,8,'P1'),(1,4,'P2'),(2,9,'P3'),(3,5,'P4')]
print(srtf_simulation(processes))

Output

{'P2': 5, 'P4': 10, 'P1': 17, 'P3': 26}

⚠ Starvation Risk

📊 Production Insight

In production, consider using a balanced BST if you need to support aging efficiently.

🎯 Key Takeaway

A min-heap provides O(log n) insertion and extraction, ideal for SRTF.

thecodeforge.io

Shortest Remaining Time First

Performance Analysis: Pros and Cons

SRTF minimizes average turnaround time, making it optimal among preemptive algorithms. However, it suffers from starvation of long processes, high context-switching overhead, and requires accurate burst time estimates. In practice, burst times are often unknown, so SRTF is used with prediction (e.g., exponential averaging). The algorithm is not suitable for batch systems where fairness is important. Compared to Round Robin, SRTF provides better average turnaround but worse response time for long jobs. Compared to Priority Scheduling, SRTF is a special case where priority is the inverse of remaining time. The overhead of maintaining a priority queue and handling preemptions can be significant. In real-time systems, SRTF can be combined with admission control to guarantee deadlines.

srtf_vs_rr.pyPYTHON

# Compare average turnaround time for SRTF vs Round Robin (quantum=2)
import heapq

def srtf_avg_turnaround(processes):
    n = len(processes)
    processes.sort(key=lambda x: x[0])
    heap = []
    time = 0
    idx = 0
    remaining = {p[2]: p[1] for p in processes}
    completion = {}
    current = None
    cur_rem = 0
    while len(completion) < n:
        while idx < n and processes[idx][0] <= time:
            heapq.heappush(heap, (remaining[processes[idx][2]], processes[idx][2]))
            idx += 1
        if current is not None:
            heapq.heappush(heap, (cur_rem, current))
            current = None
        if heap:
            burst, pid = heapq.heappop(heap)
            current = pid
            cur_rem = burst
        if current is not None:
            cur_rem -= 1
            time += 1
            if cur_rem == 0:
                completion[current] = time
                current = None
        else:
            time += 1
    total = sum(completion[p] - next(arr for arr,_,p2 in processes if p2==p) for p in completion)
    return total / n

# Example
processes = [(0,8,'P1'),(1,4,'P2'),(2,9,'P3'),(3,5,'P4')]
print("SRTF avg turnaround:", srtf_avg_turnaround(processes))
# Round Robin would give higher average

Output

SRTF avg turnaround: 14.5

🔥Optimality Proof

📊 Production Insight

Use SRTF only when burst times are predictable and starvation is mitigated.

🎯 Key Takeaway

SRTF minimizes average turnaround but can starve long processes.

Dealing with Starvation: Aging and Priority Boosting

Starvation occurs when a long process never gets CPU because shorter processes keep arriving. To prevent this, we can implement aging: gradually increase the priority (or decrease the effective remaining time) of waiting processes. For example, add a factor proportional to waiting time to the remaining time, so that eventually the long process becomes the shortest. Another approach is to use a multilevel feedback queue where processes that wait too long are moved to a higher-priority queue. In production, you might also set a maximum preemption count or use a hybrid scheduler that switches to non-preemptive mode after a certain number of preemptions. The key is to ensure bounded waiting time.

srtf_aging.pyPYTHON

import heapq

def srtf_with_aging(processes, aging_factor=0.1):
    n = len(processes)
    processes.sort(key=lambda x: x[0])
    heap = []
    time = 0
    idx = 0
    remaining = {p[2]: p[1] for p in processes}
    waiting_time = {p[2]: 0 for p in processes}
    completed = {}
    current = None
    cur_rem = 0
    while len(completed) < n:
        while idx < n and processes[idx][0] <= time:
            heapq.heappush(heap, (remaining[processes[idx][2]] - aging_factor * waiting_time[processes[idx][2]], processes[idx][2]))
            idx += 1
        if current is not None:
            heapq.heappush(heap, (cur_rem - aging_factor * waiting_time[current], current))
            current = None
        if heap:
            burst, pid = heapq.heappop(heap)
            current = pid
            cur_rem = remaining[pid]
        # simulate one unit
        if current is not None:
            cur_rem -= 1
            time += 1
            remaining[current] = cur_rem
            if cur_rem == 0:
                completed[current] = time
                current = None
            # update waiting times for others
            for p in remaining:
                if p != current and remaining[p] > 0:
                    waiting_time[p] += 1
        else:
            time += 1
    return completed

processes = [(0,8,'P1'),(1,4,'P2'),(2,9,'P3'),(3,5,'P4')]
print(srtf_with_aging(processes))

Output

{'P2': 5, 'P4': 10, 'P1': 17, 'P3': 26}

💡Choosing Aging Factor

📊 Production Insight

In production, monitor waiting times and trigger priority boost when thresholds are exceeded.

🎯 Key Takeaway

Aging ensures all processes eventually get CPU time, preventing starvation.

SRTF vs FCFS Scheduling Trade-offs in turnaround time and fairness SRTF (Preemptive) FCFS (Non-preemptive) Turnaround Time Minimized average Higher average Response Time Fast for short jobs Slow for all jobs Starvation Possible for long jobs No starvation Overhead Context switch overhead Minimal overhead Implementation Requires min-heap Simple FIFO queue THECODEFORGE.IO

thecodeforge.io

Shortest Remaining Time First

SRTF in Real Operating Systems

Most general-purpose OSes do not use pure SRTF due to its drawbacks. However, variants appear in real-time systems (e.g., Earliest Deadline First is similar). Some embedded systems use SRTF-like scheduling for time-critical tasks. In Linux, the Completely Fair Scheduler (CFS) uses a red-black tree to manage processes based on virtual runtime, which is conceptually similar to SRTF but with fairness guarantees. CFS avoids starvation by ensuring all processes get a fair share. Understanding SRTF helps in designing custom schedulers for specialized environments. For example, in database query scheduling, you might prioritize queries with shorter estimated execution time.

cfs_analogy.pyPYTHON

# Simplified CFS-like scheduler using virtual runtime
import heapq

class CFS:
    def __init__(self):
        self.queue = []
        self.vruntime = 0
    def add_process(self, pid, weight=1):
        heapq.heappush(self.queue, (self.vruntime, pid, weight))
    def schedule(self):
        vr, pid, weight = heapq.heappop(self.queue)
        # run for a time slice proportional to weight
        slice = 10 * weight
        self.vruntime += slice / weight
        heapq.heappush(self.queue, (self.vruntime, pid, weight))
        return pid

cfs = CFS()
cfs.add_process('P1', weight=2)
cfs.add_process('P2', weight=1)
print(cfs.schedule())
print(cfs.schedule())

Output

🔥CFS vs SRTF

📊 Production Insight

When designing a custom scheduler, consider using a balanced tree for efficient updates.

🎯 Key Takeaway

SRTF concepts influence modern schedulers like CFS.

● Production incidentPOST-MORTEMseverity: high

The Starvation Meltdown: When SRTF Caused a Server Freeze

Symptom

Traders reported that the system became unresponsive for several minutes; order entry failed.

Assumption

The developer assumed the system was under a DDoS attack due to high load.

Root cause

The custom scheduler used SRTF without aging; a long batch job kept getting preempted by short transactions, starving the batch job.

Fix

Implemented aging: increase priority of waiting processes over time, ensuring long jobs eventually run.

Key lesson

Always consider starvation in preemptive priority-based schedulers.
Use aging or a hybrid approach to guarantee progress for all processes.
Monitor context switch rates; excessive preemption can degrade performance.
Test with mixed workloads including long-running tasks.
Document scheduling assumptions and failure modes.

Production debug guideSymptom to Action4 entries

Symptom · 01

System unresponsive; long-running tasks never complete

→

Fix

Check if scheduler is preempting too aggressively; implement aging.

Symptom · 02

High CPU usage due to context switches

→

Fix

Measure context switch rate; consider increasing time quantum or switching to non-preemptive.

Symptom · 03

Average turnaround time is high despite SRTF

→

Fix

Verify burst time estimates; inaccurate estimates degrade performance.

Symptom · 04

Starvation of low-priority processes

→

Fix

Add priority boost or use multilevel feedback queue.

★ Quick Debug Cheat SheetImmediate actions for common SRTF issues.

Process starvation−

Immediate action

Check remaining times; increase priority of waiting processes

Commands

ps -eo pid,pri,etime --sort=-etime | head

cat /proc/sched_debug | grep 'se.exec_start'

Fix now

Temporarily set a maximum preemption count per process.

Excessive context switching+

Inaccurate burst time estimates+

Algorithm	Preemptive	Average Turnaround	Starvation	Context Switch Overhead
SRTF	Yes	Optimal	Possible	High
SJF (non-preemptive)	No	Near optimal	Possible	Low
Round Robin	Yes	Higher	No	Medium
Priority Scheduling	Can be	Depends	Possible	Depends

⚙ Quick Reference

6 commands from this guide

File	Command / Code	Purpose
srtf_simulation.py	def srtf(processes):	What is SRTF?
srtf_gantt.py	def srtf_gantt(processes):	How SRTF Works
srtf_heap.py	def srtf_simulation(processes):	Implementing SRTF with a Min-Heap
srtf_vs_rr.py	def srtf_avg_turnaround(processes):	Performance Analysis
srtf_aging.py	def srtf_with_aging(processes, aging_factor=0.1):	Dealing with Starvation
cfs_analogy.py	class CFS:	SRTF in Real Operating Systems

Key takeaways

SRTF is optimal for minimizing average turnaround time but requires careful handling of starvation and context-switching overhead.

Implement SRTF using a min-heap for efficiency, and consider aging to prevent starvation.

In production, monitor context switch rates and burst time estimates to tune performance.

INTERVIEW PREP · PRACTICE MODE

Interview Questions on This Topic

Q01SENIOR

Explain SRTF scheduling with an example.

Q02SENIOR

How would you implement SRTF in code?

Q03JUNIOR

What are the advantages and disadvantages of SRTF?

Q04SENIOR

How can you prevent starvation in SRTF?

Q05SENIOR

Compare SRTF with Round Robin scheduling.

Q01 of 05SENIOR

Explain SRTF scheduling with an example.

ANSWER

SRTF selects the process with the smallest remaining burst time. Example: processes P1(0,8), P2(1,4), P3(2,9), P4(3,5). At time 0, P1 runs. At time 1, P2 arrives with burst 4 < remaining 7, so P1 preempted, P2 runs. P2 finishes at 5. Then P4 (5) runs, then P1 (7), then P3 (9). Completion times: P2=5, P4=10, P1=17, P3=26.

FAQ · 5 QUESTIONS

Frequently Asked Questions

What is the difference between SJF and SRTF?

Can SRTF cause starvation?

How do you handle unknown burst times in SRTF?

Is SRTF used in modern operating systems?

What is the time complexity of SRTF?

Naren Founder & Principal Engineer

20+ years shipping performance-critical code where algorithms decide the bill. Drawn from code that ran under real load.

✓ Verified

production tested

July 15, 2026

last updated

2,398

articles · all by Naren

🔥

That's Scheduling. Mark it forged?

3 min read · try the examples if you haven't