Overview
Shortest Remaining Time First is the preemptive version of shortest-job-first. When a new job arrives, the scheduler compares remaining times and may switch to the shorter job.
CoreSource checked
Shortest Remaining Time First
Preemptively runs the ready job with the smallest remaining processing time.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Scheduling
- Difficulty
- Intermediate
- Family
- CPU Scheduling
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
preemptive schedulingcpu schedulingscheduling
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n log n)
Worst
O(n^2)
Space
O(n)
When to Use
- Use when job duration estimates are available and minimizing average waiting time is important.
- Use when preemption overhead is low enough to justify switching.
When Not to Use
- Avoid when long jobs must receive fairness guarantees.
- Avoid when duration estimates are missing or frequently wrong.
What It Does
- Tracks remaining work for ready jobs
- Preempts longer jobs when a shorter job arrives
- Reduces average waiting time under suitable assumptions
Use Cases
- Interactive workloads where short jobs should finish quickly
- Scheduler simulations with known or estimated processing times
- Comparing latency-oriented policies against fairness-oriented policies
Inputs
- Ready queue of processes with arrival times, burst estimates, and waiting times
- CPU time-slice or preemption policy
Outputs
- Next scheduled process selection
- Updated waiting, turnaround, and response-time statistics
Pseudocode
- 1.Insert newly arrived jobs into a priority queue keyed by remaining time
- 2.Run the job with the smallest remaining time
- 3.When a new job arrives, compare it with the running job
- 4.Preempt if the new job has less remaining time
- 5.Repeat until all jobs complete
Canonical Example
- Input
- A arrives at 0 with 8 units; B arrives at 1 with 2 units
- Output
- A runs 0-1, B runs 1-3, then A resumes
- Explanation
- B preempts A because B's remaining time is shorter when it arrives.
Implementation Notes
- Keep ready jobs in a priority queue keyed by remaining time.
- Update remaining work whenever the running job is preempted.
- Track waiting and turnaround time separately for metrics.
Common Pitfalls
- Long jobs can starve when short jobs keep arriving.
- Using total duration instead of remaining duration turns the policy into a different rule.
- Ignoring context-switch cost can make simulated gains unrealistic.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow always running the job with the least remaining processing time on a small preemptive scheduling example.
Step 1 of 5: Insert newly arrived jobs into a priority queue keyed by remaining time
scheduling-mechanismNotes
SRTF is latency-friendly but can be unfair without aging or admission control.
Sources (1)
What each reference supports for this entry.
Operating System Concepts
BookOperating-systems reference for Shortest Remaining Time First CPU scheduling policy, ready-queue ordering, and preemption behavior.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageVariant ofShortest Job First
SRTF is the preemptive form of shortest-job-first.
Alternative toRound Robin Scheduling
SRTF minimizes short-job latency, while round robin emphasizes time-sliced fairness.
Related Algorithms
Tags
Scheduling