What is Shortest-Remaining-Time-First (SRTF) Scheduling?
Learn Shortest-Remaining-Time-First scheduling — preemption rules, overhead, and starvation risk — with OS interview questions answered.
Expected Interview Answer
Shortest-Remaining-Time-First (SRTF) is the preemptive version of Shortest-Job-First: whenever a new process arrives, the scheduler compares its burst time to the remaining burst time of the currently running process and immediately switches the CPU to whichever has less work left.
Unlike non-preemptive SJF, which commits to a process once dispatched, SRTF continuously re-evaluates its choice at every arrival event: if the newly arrived process has a shorter total burst time than what is left of the running process, the running process is preempted, its remaining time is tracked, and the new arrival takes over the CPU. This makes SRTF even more effective than SJF at minimizing average waiting time, since it can react immediately to a short job showing up rather than waiting for the current job to finish. The cost is a higher number of context switches compared to non-preemptive SJF, since each preemption incurs the overhead of saving and restoring process state, and the starvation risk for long processes is worse than plain SJF because a long-running process can be interrupted repeatedly by a continuous stream of newer short arrivals. In practice SRTF is mostly a theoretical benchmark for comparing scheduling algorithms, since it shares SJF’s core dependency on knowing burst times in advance.
- Achieves lower average waiting time than non-preemptive SJF
- Reacts immediately to short jobs arriving mid-execution
- Useful as a theoretical optimal-waiting-time benchmark
- Highlights the trade-off between optimality and context-switch overhead
AI Mentor Explanation
SRTF scheduling is like a coach who can pull a batter off strike mid-innings the moment a player with a shorter planned stay arrives at the boundary rope: if the batter already at the crease still needs forty minutes but the new arrival only needs five, the coach swaps them immediately rather than waiting for the current innings to end. This constant re-evaluation minimizes total time batters spend waiting to bat, but every swap costs time changing pads and gloves, mirroring context-switch overhead. A batter with a genuinely long innings planned can be interrupted again and again by a stream of quick arrivals.
Step-by-Step Explanation
Step 1
Track remaining time
The scheduler continuously tracks the remaining burst time of the currently running process.
Step 2
New arrival comparison
When a new process arrives, its total burst time is compared against the running process’s remaining time.
Step 3
Preempt if shorter
If the new arrival needs less time than what is left of the running process, the running process is preempted and its remaining time is saved.
Step 4
Resume or continue
The shorter job runs; the preempted process resumes later from its saved remaining time whenever it is again the shortest choice.
What Interviewer Expects
- Clear articulation that SRTF is the preemptive variant of SJF
- Correct description of the preemption trigger (new arrival with shorter remaining time)
- Recognition of higher context-switch overhead versus non-preemptive SJF
- Awareness that starvation risk for long processes is worse than in SJF
Common Mistakes
- Confusing SRTF with non-preemptive SJF
- Forgetting that SRTF compares against remaining time, not original burst time
- Ignoring the added context-switch overhead from frequent preemption
- Not recognizing the increased starvation risk for long jobs
Best Answer (HR Friendly)
“SRTF is the preemptive cousin of Shortest-Job-First: any time a new job shows up that would finish faster than what is left of the job currently running, the system immediately swaps to the new one. That gives the best possible average wait time in theory, but it means more switching overhead, and a long job can keep getting interrupted if short jobs keep arriving.”
Code Example
struct process {
int pid;
int arrival_time;
int remaining_time;
int completed;
};
int pick_srtf(struct process procs[], int n, int current_time) {
int idx = -1;
int shortest = INT_MAX;
for (int i = 0; i < n; i++) {
if (!procs[i].completed &&
procs[i].arrival_time <= current_time &&
procs[i].remaining_time < shortest) {
shortest = procs[i].remaining_time;
idx = i; /* may preempt whatever is currently running */
}
}
return idx;
}Follow-up Questions
- How does SRTF differ from non-preemptive SJF in terms of overhead?
- Why does SRTF have a worse starvation risk than plain SJF?
- What data structure would you use to efficiently track the shortest remaining time?
- Why is SRTF mostly used as a theoretical benchmark rather than in production schedulers?
MCQ Practice
1. What triggers a preemption under SRTF scheduling?
SRTF preempts the running process specifically when a newly arrived process has less total work than the running process has remaining.
2. Compared to non-preemptive SJF, SRTF typically has?
Because SRTF can preempt on every new arrival, it generally causes more context switches than committing to a job until completion as in SJF.
3. SRTF is best described as?
SRTF extends SJF by allowing the currently running process to be preempted whenever a shorter job becomes available.
Flash Cards
What is SRTF scheduling? — The preemptive variant of SJF, which can interrupt the running process for a shorter new arrival.
When does SRTF preempt? — When a new arrival’s burst time is less than the running process’s remaining time.
What is SRTF’s main cost versus SJF? — More context switches from frequent preemption.
Is starvation risk higher in SRTF or SJF? — Higher in SRTF, since a long process can be repeatedly interrupted by newer short arrivals.