SJF & SRTF
Scenario
Imagine you have one item to buy, and the person in front of you with a full cart says, 'Go ahead, you'll be fast.' That is optimal scheduling.
Mental model
Shortest Job First (SJF) always runs the quickest task next. Shortest Remaining Time First (SRTF) takes it a step further by interrupting a running task if an even quicker one arrives.
SJF is sorting your to-do list from fastest to slowest. SRTF is being halfway through writing an essay (slow), getting a text message (fast), pausing the essay to reply immediately, and then resuming the essay.
Explanation
Shortest Job First (SJF) aims to completely solve the convoy effect by dynamically prioritizing tasks based on their size. When the CPU becomes available, it examines the ready queue and selects the process that has the smallest next CPU burst. By always prioritizing short processes, SJF mathematically guarantees the minimum possible average waiting time for a given set of processes.
SJF operates as a non-preemptive algorithm. Once a process is selected and begins executing, it will run until it finishes its CPU burst, even if a new, much shorter process arrives in the queue while it is running. This non-preemptive nature means a short process arriving late still has to wait for the current long process to finish, which isn't entirely optimal.
To fix this, we introduce the preemptive version of SJF, known as Shortest Remaining Time First (SRTF). In SRTF, the scheduler evaluates the queue every time a new process arrives. If the newly arrived process requires less total CPU time than what is remaining for the currently executing process, the OS violently interrupts the running process and hands the CPU to the newcomer. This ensures that short jobs get immediate attention, further driving down average waiting times.
However, both SJF and SRTF suffer from a massive, fundamental flaw: they require knowing the future. To pick the 'shortest job', the OS must know exactly how long a process's next CPU burst will take before it actually runs. In reality, this is impossible. Operating systems can only guess the future burst time by looking at the process's historical behavior, usually using a technique called exponential averaging to predict the next burst length based on past bursts.
Another critical issue is starvation. Because these algorithms heavily favor short processes, a steady stream of incoming short jobs can cause a long, CPU-heavy process to wait forever at the back of the line. The long process is constantly bypassed by newer, faster jobs, meaning it may never get a chance to execute.
Key points
- SJF (Non-preemptive): Selects the job with the smallest burst time, but won't interrupt a running job.
- SRTF (Preemptive): Will interrupt the current job if a new arrival has a shorter remaining time.
- Optimal Average Waiting Time: SJF provides the theoretically lowest average waiting time of any scheduling algorithm.
- The Prediction Problem: It is impossible to know exactly how long a process will take beforehand; the OS must use history to predict the future.
- Starvation: Long processes might never execute if short processes keep arriving continuously.
Common mistakes
- Believing SJF can be perfectly implemented: Because we cannot predict the exact future execution time of a program, perfect SJF only exists in theory. Real systems can only estimate it.
- Thinking SJF and SRTF are entirely different algorithms: SRTF is literally just SJF with preemption enabled. They use the exact same logic (shortest time wins).
Glossary
- Shortest Job First (SJF)
- A scheduling method where the operating system always chooses to run the shortest, fastest program next to get it out of the way quickly.
- burst time
- The estimated amount of uninterrupted time a program will need to use the CPU before it finishes or needs to wait for something else.
- Shortest Remaining Time First (SRTF)
- An aggressive version of SJF where if a new, super-short program arrives, the operating system will pause the current program to run the shorter one immediately.
Recall questions
- What is the primary difference between SJF and SRTF?
- Why is SJF considered the 'optimal' scheduling algorithm?
- How does an operating system guess the length of the next CPU burst for SJF?
Questions & answers
What happens to a heavy video-rendering process under SRTF if the system is constantly receiving tiny network packets?
The video rendering process will suffer from starvation. The system will constantly preempt it to handle the tiny network packets, preventing it from ever making progress.
Approach: Identify the heavy process as a 'long job' and network packets as 'short jobs'. Apply the SRTF rule to show the long job is perpetually pushed to the back of the line.
Process A (burst 8) arrives at t=0. Process B (burst 4) arrives at t=1. Process C (burst 2) arrives at t=2. Under SRTF, which process finishes first?
Process C
Approach: At t=0, A starts. At t=1, A has 7 left, B has 4. B preempts A. At t=2, B has 3 left, C has 2. C preempts B. C runs to completion.
Continue learning
Previous: Scheduling Criteria