CPU Scheduling Algorithms

At the heart of every modern operating system lies a critical decision-making component: the CPU scheduler. Its job is deceptively simple yet profoundly impacts system performance. It must constantly choose which waiting process gets to use the CPU next, a task that requires balancing competing goals like maximizing overall throughput, minimizing the time individual programs take to complete, and ensuring all tasks get a fair share of resources. Understanding how different schedulers make this choice is key to designing efficient systems and diagnosing performance bottlenecks.

The Scheduler's Core Objectives and Metrics

Before diving into specific algorithms, it’s essential to understand what a scheduler is trying to optimize and how we measure its success. The CPU scheduler operates on the ready queue, a list of processes that are loaded in memory and ready to execute, awaiting their turn on the CPU.

We evaluate schedulers using several key metrics. Turnaround time is the total time from a process's submission to its completion. Waiting time is the total time a process spends in the ready queue, waiting for the CPU. Response time, crucial for interactive systems, is the time from submission until the process gets the CPU for the first time. An ideal scheduler minimizes these times while maximizing throughput, the number of processes completed per unit of time. These metrics are often in tension, and different algorithms make different trade-offs.

First-Come, First-Served (FCFS) Scheduling

First-Come, First-Served (FCFS) is the simplest scheduling algorithm. It executes processes in the exact order they arrive in the ready queue, much like a single-line checkout at a store. It is non-preemptive, meaning once a process starts, it runs until it voluntarily releases the CPU (e.g., for an I/O operation) or finishes.

Consider three processes arriving in order P1 (burst time 24 ms), P2 (burst time 3 ms), and P3 (burst time 3 ms). The Gantt chart for their execution would be:

|----P1----|--P2--|-P3-|
0          24     27    30

To calculate average waiting time:

• P1 waits 0 ms.
• P2 waits 24 ms (for P1 to finish).
• P3 waits 27 ms (for P1 and P2 to finish).

Average waiting time = $(0+24+27)/3=17$ ms.

While simple, FCFS has a major flaw known as the convoy effect. A long process holding the CPU can force many short processes to wait excessively, dramatically increasing average waiting time. As seen in the example, the short processes P2 and P3 suffer because they arrived after the long P1. This leads to poor performance for interactive tasks.

Shortest-Job-First (SJF) Scheduling

Shortest-Job-First (SJF) scheduling aims to minimize average waiting time by always selecting the process with the smallest CPU burst time next. It can be either non-preemptive or preemptive.

In the non-preemptive SJF version, the scheduler chooses the shortest job only when the CPU becomes free. Using the same processes but assuming they all arrive at time 0, the order would be P2 (3 ms), P3 (3 ms), then P1 (24 ms). The Gantt chart is:

|-P2-|-P3-|----P1----|
0    3    6          30

Average waiting time = $((3-0)+(0-0)+(6-0))/3=3$ ms, a significant improvement over FCFS.

The preemptive SJF variant, often called Shortest-Remaining-Time-First (SRTF), can interrupt a running process if a new process arrives with a shorter burst time than the remaining time of the currently executing process. This further optimizes waiting and turnaround times for dynamic arrivals but adds overhead from context switches.

The primary challenge with SJF is practical: the scheduler cannot reliably know the length of a process's next CPU burst. It must use predictive techniques based on past behavior. Furthermore, a steady stream of short jobs can cause starvation, where a long job is indefinitely denied CPU access.

Round Robin (RR) Scheduling

Round Robin (RR) scheduling is specifically designed for time-sharing systems. It is preemptive and uses a small unit of time called a time quantum or time slice. The ready queue is treated as a circular FIFO queue. The scheduler assigns the CPU to the first process for one time quantum. If the process's burst is longer than the quantum, it is preempted and placed at the back of the ready queue.

Consider processes P1 (10 ms), P2 (5 ms), and P3 (8 ms), all arriving at time 0, with a time quantum of 4 ms. The Gantt chart is:

|-P1-|-P2-|-P3-|-P1-|-P2-|-P3-|-P1-|-P3-|
0   4   8   12  14  16  20  22  24  26

Let's compute waiting time. P1 executes at times 0-4, 12-14, and 20-22. It finishes at time 22. Its waiting time is total time not running: $(22-10)=12$ ms. P2 runs at 4-8 and 14-16, finishing at 16. Waiting time = $(16-5)=11$ ms. P3 runs at 8-12, 16-20, and 22-26, finishing at 26. Waiting time = $(26-8)=18$ ms. Average waiting time = $(12+11+18)/3\approx 13.67$ ms.

The performance of RR heavily depends on the time quantum. If the quantum is extremely large, RR degenerates into FCFS. If it is extremely small, overhead from frequent context switches becomes dominant, hurting throughput. The strength of RR is its excellent response time and fairness; no process waits more than $(n-1)\ast q$ time units before running again, where $n$ is the number of processes.

Multilevel Feedback Queue (MLFQ) Scheduling

The Multilevel Feedback Queue (MLFQ) scheduler is a sophisticated, adaptive algorithm used in many modern operating systems (e.g., Linux, Windows). It aims to combine the benefits of several algorithms without requiring prior knowledge of process behavior. It works by maintaining several distinct ready queues, each with a different priority level and potentially a different scheduling algorithm (e.g., RR for high priority, FCFS for low priority).

A new process enters the highest-priority queue. If it uses up its time quantum (suggesting it is a CPU-bound process), it is moved down to a lower-priority queue. Processes in lower-priority queues are given longer time quanta but are serviced less frequently. If a process voluntarily releases the CPU before its quantum expires (suggesting it is an I/O-bound, interactive process), it may stay in or be moved back to a higher-priority queue. This design automatically favors interactive processes (giving them quick response) while still allowing CPU-bound batch jobs to make progress.

The MLFQ must be carefully configured with rules to prevent starvation (e.g., periodically boosting the priority of all processes) and gaming of the system. Its adaptability makes it powerful but complex to tune.

Common Pitfalls

1. Ignoring Arrival Time in Non-Preemptive Schedulers: A common mistake when calculating metrics for FCFS or non-preemptive SJF is to order processes by burst time without considering their arrival sequence. Always schedule based on who is available in the ready queue at the moment the CPU becomes free.
2. Misunderstanding Preemption in SJF vs. RR: Confusing Shortest-Remaining-Time-First (preemptive SJF) with Round Robin is easy. Remember, SRTF preempts based on remaining burst time comparison upon a new arrival. RR preempts based purely on the expiration of a fixed time quantum, regardless of the new process's length.
3. Choosing an Inappropriate Time Quantum in RR: Selecting a poor time quantum is a classic design error. A quantum that is too large harms response time for interactive tasks; one that is too small wastes excessive CPU cycles on context switching overhead. The optimal quantum is typically large enough that most interactive processes will block for I/O before it expires.
4. Overlooking Starvation in Priority-Based Schemes: Both SJF (which implicitly prioritizes short jobs) and explicit priority schedulers can lead to starvation for low-priority or long processes. Any practical implementation must include a mitigation strategy, such as aging, where a process's priority is gradually increased the longer it waits in a queue.

Summary

• The CPU scheduler's role is to select processes from the ready queue to optimize system performance metrics like average waiting time, turnaround time, and response time.
• First-Come, First-Served (FCFS) is simple but suffers from the convoy effect, leading to high average waiting times when long jobs precede short ones.
• Shortest-Job-First (SJF), especially its preemptive variant (SRTF), provides the theoretically minimal average waiting time but requires accurate burst time prediction and risks starvation for long processes.
• Round Robin (RR) uses a time quantum to provide fair, preemptive scheduling with excellent response time for interactive processes; its efficiency depends heavily on choosing an appropriate quantum size.
• The Multilevel Feedback Queue (MLFQ) uses multiple priority queues and feedback mechanisms to automatically adapt to process behavior, favoring interactive I/O-bound processes while not starving CPU-bound ones.