🚀 Operating Systems Interview Prep: Shortest Remaining Time First (SRTF) Scheduling Algorithm
Imagine you're managing a restaurant.
Three customers place orders:
- One needs 10 minutes.
- Another needs 4 minutes.
- Another needs just 2 minutes.
Would you finish the longest order first, or prioritize the one that can be completed quickly?
Shortest Remaining Time First (SRTF) follows a similar idea when allocating CPU time to processes.
It prioritizes the process that needs the least remaining CPU execution time.
If you're preparing for a Software Engineering interview as a fresher, understanding SRTF is important because it tests your knowledge of CPU scheduling, preemption, process execution, and scheduling calculations.
Let's understand it step by step.
1. What is CPU Scheduling?
Before understanding SRTF, understand one basic concept.
A computer can have multiple processes waiting for CPU execution, but a CPU core can execute only one process at a time.
The operating system uses a CPU Scheduler to select which ready process gets the CPU next.
Important terminology:
- Process: A program currently being executed.
- Ready Queue: Processes waiting for CPU allocation.
- CPU Burst Time: Time a process needs on the CPU.
- Preemption: Interrupting a running process to give the CPU to another process.
2. What is SRTF Scheduling?
SRTF stands for Shortest Remaining Time First.
It is the preemptive version of Shortest Job First (SJF).
Definition:
SRTF is a preemptive CPU scheduling algorithm that selects the process with the shortest remaining CPU burst time for execution.
If a newly arrived process has a shorter burst time than the remaining time of the currently running process, the operating system preempts the current process.
How does it work?
- Select the process with the shortest remaining time.
- Allocate the CPU to that process.
- When a new process arrives, compare its burst time with the currently running process's remaining time.
- If the new process has a shorter remaining time, preempt the current process.
- Otherwise, continue executing the current process.
- Repeat until all processes complete.
Remember: SRTF compares remaining execution time, NOT the original burst time of a process that has already started executing.
3. Understand the Important Terminologies
Before solving numerical questions, understand these six terms.
| Term | Meaning |
|---|---|
| AT | Arrival Time |
| BT | Burst Time |
| CT | Completion Time |
| TAT | Turnaround Time |
| WT | Waiting Time |
| RT | Response Time |
Important formulas
1. Completion Time (CT)
The time at which a process finishes execution.
2. Turnaround Time (TAT)
Total time between process arrival and completion.
TAT = CT - AT
3. Waiting Time (WT)
Total time a process spends waiting in the ready queue.
WT = TAT - BT
4. Response Time (RT)
Time between process arrival and its first CPU allocation.
RT = First CPU Start Time - AT
What should you memorize?
These three formulas are particularly important:
TAT = CT - ATWT = TAT - BTRT = First Start Time - AT
4. Solve Your First SRTF Numerical Problem
This is where you should spend most of your preparation time.
Consider the following processes:
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0 ms | 6 ms |
| P2 | 1 ms | 3 ms |
| P3 | 2 ms | 7 ms |
Let's execute them step by step.
Step 1: Time = 0
Only P1 has arrived.
Therefore, P1 starts execution.
Remaining time of P1 = 6 ms.
Step 2: Time = 1
P2 arrives.
Compare:
- P1 remaining time = 5 ms.
- P2 burst time = 3 ms.
P2 needs less CPU time.
Therefore, P1 is preempted and P2 starts executing.
Step 3: Time = 2
P3 arrives.
Compare:
- P2 remaining time = 2 ms.
- P3 burst time = 7 ms.
P2 still has the shortest remaining time.
Therefore, P2 continues executing.
Step 4: Time = 4
P2 completes.
Compare:
- P1 remaining time = 5 ms.
- P3 remaining time = 7 ms.
P1 has the shortest remaining time.
Therefore, P1 starts executing again.
Step 5: Time = 9
P1 completes.
Only P3 remains, so P3 executes until completion at time 16.
Final Gantt Chart
0 1 4 9 16
| P1 | P2 | P1 | P3 |
Calculate Completion Time
| Process | CT |
|---|---|
| P1 | 9 |
| P2 | 4 |
| P3 | 16 |
Calculate TAT and WT
| Process | AT | BT | CT | TAT | WT |
|---|---|---|---|---|---|
| P1 | 0 | 6 | 9 | 9 | 3 |
| P2 | 1 | 3 | 4 | 3 | 0 |
| P3 | 2 | 7 | 16 | 14 | 7 |
Average Turnaround Time:
(9 + 3 + 14) / 3 = 8.67 ms
Average Waiting Time:
(3 + 0 + 7) / 3 = 3.33 ms
Interview takeaway: Always construct the Gantt chart first. Calculate CT, TAT, and WT afterward.
5. SJF vs SRTF: What's the Difference?
This is one of the most important theoretical interview questions.
| SJF | SRTF |
|---|---|
| Shortest Job First | Shortest Remaining Time First |
| Non-preemptive | Preemptive |
| Selects shortest burst time | Selects shortest remaining time |
| Running process normally continues until completion or blocking | Running process can be interrupted |
| No preemption-based context switching | Preemption may cause context switching |
Remember:
SJF selects the shortest job, whereas SRTF selects the process with the shortest remaining execution time.
6. Advantages and Disadvantages
Advantages
- Low Average Waiting Time: Under ideal assumptions, SRTF minimizes average waiting time when CPU burst times are known.
- Faster Short Jobs: Short processes can complete quickly.
- Better Responsiveness for Short Processes: Newly arriving short processes can receive CPU time earlier.
Disadvantages
- Starvation: Long processes may wait indefinitely if shorter processes keep arriving.
- Burst Time Prediction: The OS generally cannot know the exact future CPU burst time in advance.
- Context Switching Overhead: Frequent preemption can introduce performance overhead.
- Implementation Complexity: It requires tracking and comparing remaining execution times.
What is Starvation?
Imagine a process requires 20 ms of CPU time.
However, shorter processes continuously arrive and get selected before it.
The longer process may keep waiting without getting sufficient CPU execution.
This situation is called Starvation.
7. Important Implementation Logic
You don't necessarily need to memorize the entire C++ implementation for an OS theory interview.
However, understand the algorithm's execution logic.
Pseudocode:
Initialize remaining_time = burst_time for every process
current_time = 0
completed = 0
WHILE completed < total_processes:
Find the arrived process with:
remaining_time > 0
shortest remaining_time
IF a process is found:
Execute it for 1 time unit
Decrease its remaining_time by 1
Increase current_time by 1
IF remaining_time becomes 0:
completion_time = current_time
turnaround_time = completion_time - arrival_time
waiting_time = turnaround_time - burst_time
completed += 1
ELSE:
Increase current_time by 1
Calculate average waiting time and turnaround time
Important implementation details:
- Initialize remaining time with burst time.
- Consider only processes whose arrival time is less than or equal to current time.
- Ignore processes that have already completed.
- Select the process with the minimum remaining time.
- Handle CPU idle time when no process is available.
- Handle equal remaining times using a consistent tie-breaking rule.
- Validate that the number of processes is greater than zero before calculating averages.
C++ interview follow-up: Understand why remainingTime-- is performed after selecting a process and why completion time is recorded immediately when remaining time reaches zero.
8. Must-Prepare Interview Questions with Expected Answers
These are the questions I recommend preparing before moving to another CPU scheduling algorithm.
Q1. What is SRTF scheduling?
Expected answer:
SRTF is a preemptive CPU scheduling algorithm that selects the process with the shortest remaining CPU burst time. A running process can be interrupted if a newly arrived process has a shorter remaining time.
Q2. Why is SRTF called preemptive SJF?
Expected answer:
Because it is the preemptive version of Shortest Job First. Unlike non-preemptive SJF, SRTF can interrupt a running process when a shorter job arrives.
Q3. What is the difference between burst time and remaining time?
Expected answer:
Burst time is the total CPU time required by a process, whereas remaining time is the CPU time still needed after some execution has already occurred.
Q4. Does SRTF guarantee minimum average waiting time?
Expected answer:
Under ideal single-CPU scheduling assumptions, with known CPU burst times and no scheduling overhead, SRTF produces minimum average waiting time.
Q5. Can starvation occur in SRTF?
Expected answer:
Yes. Long processes may experience starvation if shorter processes continuously arrive and get CPU priority.
Q6. What is context switching?
Expected answer:
Context switching is the process of saving the state of the currently running process and restoring the state of another process so the CPU can switch execution.
Q7. What happens if two processes have equal remaining time?
Expected answer:
The scheduler follows a tie-breaking policy, such as FCFS or continuing the currently running process. The question's specified policy should always be followed.
Q8. What happens if all processes arrive at the same time?
Expected answer:
SRTF effectively behaves like non-preemptive SJF because there are no later arrivals to trigger preemption. Processes execute in ascending order of burst time, assuming no ties.
Q9. What happens when no process is available?
Expected answer:
The CPU remains idle until a process arrives.
Q10. What is the biggest disadvantage of SRTF?
Expected answer:
Starvation of longer processes, difficulty predicting CPU burst times, and context-switching overhead.
9. Test Your Understanding: Interview Quiz
Don't just read the answers. Try solving these questions yourself.
Question 1: Conceptual
Which scheduling algorithm is the preemptive version of SJF?
A. FCFS
B. Round Robin
C. SRTF
D. Priority Scheduling
Question 2: Conceptual
A process is currently executing with 6 ms remaining time. A new process arrives with a burst time of 3 ms.
What will SRTF do?
A. Continue the current process
B. Preempt the current process
C. Terminate both processes
D. Put the new process into the blocked queue
Question 3: Numerical
Consider the following processes:
| Process | AT | BT |
|---|---|---|
| P1 | 0 | 5 |
| P2 | 1 | 2 |
| P3 | 2 | 4 |
What is the completion time of P2?
A. 2
B. 3
C. 4
D. 5
Question 4: Numerical
Using the same processes, what is the waiting time of P1?
A. 0
B. 1
C. 2
D. 3
Question 5: Interview-level
Why can starvation occur in SRTF?
A. Because longer processes always execute first.
B. Because shorter processes may continuously arrive and receive CPU priority.
C. Because CPU burst time is always zero.
D. Because all processes arrive simultaneously.
Question 6: Tricky
If all processes arrive at time 0, how does SRTF behave?
A. Like FCFS
B. Like Round Robin
C. Like non-preemptive SJF
D. Like Priority Scheduling
Answer Key
Click to reveal answers and explanations
- C — SRTF. It is the preemptive version of SJF.
- B — Preempt the current process. The newly arrived process has less remaining time.
- C — 4. P1 executes from 0–1, P2 from 1–3? Check the arrival at time 2: P2 has 1 ms remaining, so it continues until time 3. Its completion time is 3. Therefore, the correct option is B — 3.
- B — 1. P1 executes from 0–1, resumes at 3, and completes at 7. Its turnaround time is 7 and waiting time is 2. Therefore, the correct option is C — 2.
- B — Shorter processes may continuously arrive and receive priority.
- C — Non-preemptive SJF. No later arrivals exist to trigger preemption.
10. Final Interview Preparation Checklist
Before considering SRTF complete, make sure you can:
- [ ] Explain CPU scheduling.
- [ ] Define SRTF and its relationship with SJF.
- [ ] Explain preemptive vs non-preemptive scheduling.
- [ ] Understand AT, BT, CT, TAT, WT and RT.
- [ ] Memorize the three important formulas.
- [ ] Construct a Gantt chart independently.
- [ ] Solve numerical problems involving multiple preemptions.
- [ ] Calculate average waiting and turnaround times.
- [ ] Explain starvation and context switching.
- [ ] Differentiate SJF, SRTF, FCFS and Round Robin.
- [ ] Answer the interview questions above.
My advice: Don't move to another scheduling algorithm until you can solve at least three different SRTF numerical problems without looking at the solution.
Understanding one algorithm properly is more valuable than memorizing ten algorithms superficially.
What's Next?
After SRTF, prepare these CPU scheduling algorithms in this order:
- First Come First Serve (FCFS)
- Shortest Job First (SJF)
- Priority Scheduling (Preemptive and Non-Preemptive)
- Round Robin Scheduling
Together, these will give you a strong foundation for CPU Scheduling interview questions.
If you're preparing for an SWE interview, save this article, solve the quiz, and practice the numerical examples yourself.
Happy Learning! 🚀
Top comments (0)