CPU Scheduling Algorithms

Why This Matters

CPU scheduling is how an operating system decides which process gets the CPU and for how long. It's the core mechanism behind process management, and every scheduling algorithm makes tradeoffs between throughput, response time, fairness, and overhead.

Don't just memorize algorithm names. Know why each algorithm exists, what problem it solves, and what new problems it creates. When you see a scheduling question, ask yourself: Is this about minimizing wait time? Preventing starvation? Balancing fairness with efficiency? The algorithm you choose, and how you justify it, shows real understanding.

---

Non-Preemptive Algorithms

These algorithms let a process run until it finishes or voluntarily yields the CPU. Once assigned, the CPU stays assigned. The scheduler only makes decisions when a process terminates or blocks.

First-Come, First-Served (FCFS)

• Simplest scheduling algorithm. Processes execute in arrival order, just like a basic FIFO queue.
• The convoy effect occurs when short processes get stuck behind a long one, which dramatically increases average wait time. Picture five 1-second jobs waiting behind a 100-second job: the average wait time skyrockets compared to running the short jobs first.
• Non-preemptive by nature, making it a poor choice for interactive systems where responsiveness matters.

Shortest Job First (SJF)

• Provably optimal for minimizing average waiting time among non-preemptive algorithms.
• The catch: you need to know burst time in advance. In practice, this is estimated using exponential averaging of past CPU bursts. The formula is $\tau_{n+1} = \alpha \cdot t_n + (1 - \alpha) \cdot \tau_n$, where $t_n$ is the actual last burst, $\tau_n$ is the previous estimate, and $\alpha$ (between 0 and 1) controls how much weight recent history gets.
• Starvation risk for long processes: if short jobs keep arriving, long jobs may wait indefinitely.

Highest Response Ratio Next (HRRN)

• Response ratio formula: $\frac{\text{waiting time} + \text{burst time}}{\text{burst time}}$. The process with the highest ratio gets scheduled next.
• Prevents starvation because as a process waits longer, its ratio grows, eventually pushing it to the front regardless of burst length.
• Balances SJF's efficiency with fairness, though the scheduler must recalculate ratios at each decision point, adding overhead.

---

Preemptive Algorithms

These algorithms can interrupt a running process to give the CPU to another. The scheduler actively reclaims CPU time based on events like new arrivals or timer interrupts.

Shortest Remaining Time First (SRTF)

• Preemptive version of SJF. When a new process arrives with a shorter remaining burst time than the currently running process, it preempts immediately.
• Optimal for minimizing average waiting time among all scheduling algorithms, preemptive or not.
• Context switch overhead and starvation remain real concerns, especially in systems with high process arrival rates.

Round Robin (RR)

• Each process gets a fixed time quantum (time slice). When the quantum expires, the process is preempted and placed at the back of the ready queue.
• Fairness is guaranteed since every process gets equal CPU time slices, making it ideal for time-sharing systems.
• Quantum size is the critical tuning decision:
  • Too small → excessive context switches eat into useful CPU time
  • Too large → processes wait a long time for their turn, and behavior degrades toward FCFS
  • A common rule of thumb: the quantum should be large enough that roughly 80% of CPU bursts finish within a single quantum.

Priority Scheduling

• Each process is assigned a priority value, and the highest-priority process runs first. Convention varies by system: sometimes lower numbers mean higher priority, sometimes the reverse. Always check which convention a problem uses.
• Can be preemptive or non-preemptive. In the preemptive version, a newly arrived higher-priority process immediately displaces the running one.
• The main danger is indefinite blocking (starvation) of low-priority processes. The standard fix is aging: gradually increasing the priority of processes that have been waiting, so they eventually get scheduled.

---

Multi-Queue Algorithms

These algorithms use multiple queues to handle different process types or adapt to process behavior. Complexity increases, but so does flexibility.

Multilevel Queue Scheduling

• Separate queues for process categories, typically foreground (interactive) and background (batch), each with its own scheduling algorithm (e.g., RR for foreground, FCFS for background).
• Queue assignment is fixed. A process stays in its assigned queue for its entire lifetime.
• Inter-queue scheduling is needed to decide how CPU time is divided between queues. Common approaches include absolute priority for the foreground queue, or a weighted time-slice split like 80% foreground / 20% background.

Multilevel Feedback Queue Scheduling

• Processes can migrate between queues based on their CPU burst behavior. A process that uses its full time quantum gets demoted to a lower-priority queue; a process that gives up the CPU early (I/O-bound behavior) gets promoted.
• This makes it a self-adjusting algorithm that automatically distinguishes CPU-bound from I/O-bound processes over time.
• It's the most flexible general-purpose scheduler, but it requires careful tuning of several parameters: number of queues, scheduling algorithm per queue, promotion/demotion criteria, and the time quantum at each level.

---

Fairness-Focused Algorithms

These algorithms prioritize equitable CPU distribution using more sophisticated tracking mechanisms.

Completely Fair Scheduler (CFS)

• Linux's default scheduler since kernel 2.6.23, replacing the earlier O(1) scheduler.
• Tracks virtual runtime (vruntime) for each process. The process with the lowest vruntime (meaning it has received the least CPU time relative to its weight) runs next. Processes are stored in a red-black tree, giving $O(\log n)$ lookup for the next process to schedule.
• No fixed time quantum. Instead, CFS dynamically calculates how long each process should run based on the number of runnable processes and a configurable target latency (the period within which every runnable process should get at least one turn).

Longest Remaining Time First (LRTF)

• Inverse of SRTF — prioritizes the process with the longest remaining burst time.
• Rarely used in practice because it maximizes wait time for short processes, which is the opposite of what most systems want.
• Its value is mostly theoretical: it helps illustrate scheduling tradeoffs and serves as a useful counterexample in algorithm analysis.

---

Quick Reference Table

---

Self-Check Questions

1. Which two algorithms are provably optimal for minimizing average waiting time, and what distinguishes them from each other?

2. A system experiences starvation of long-running processes. Which algorithms could cause this problem, and what mechanism solves it in Priority Scheduling?

3. Compare and contrast Multilevel Queue and Multilevel Feedback Queue scheduling. When would you choose one over the other?

4. If the time quantum in Round Robin is set extremely large, what algorithm does it effectively become? What happens if it's set extremely small?

5. You need to design a scheduler for a system running both interactive terminals and background batch jobs. Which algorithm would you recommend and why? What parameters would you need to specify?