Preemptive Scheduling Algorithms: SRTF, Round Robin, and Priority

This chapter covers advanced CPU scheduling algorithms in operating systems, focusing on preemptive mechanisms like Shortest Remaining Time First (SRTF), Round Robin (RR), Priority Scheduling, and multi-queue architectures. We examine how these algorithms balance CPU utilization, turnaround time, response time, and the trade-offs between concurrency and overhead.

1. Limitations of Non-Preemptive Scheduling & The Starvation Problem

In non-preemptive scheduling models (such as basic Shortest Job First or First-Come, First-Served), once the CPU is allocated to a process, the process keeps the CPU until it releases it either by terminating or by switching to an I/O wait state. While simple, this approach causes severe performance bottlenecks.

Real-Life Analogy: The Express Checkout Line

Imagine a grocery store checkout lane dedicated to "Items under 5 minutes." If customers with 2-minute items keep arriving back-to-back, a customer with a cartload of groceries (representing a long process) will never get checked out. They are perpetually pushed back because shorter tasks keep seizing the priority.

• The Convoy Effect: In FCFS, if a long CPU-bound process arrives first, shorter I/O-bound processes are forced to wait behind it, resulting in poor CPU and I/O device utilization.
• Starvation (Indefinite Blocking): When short tasks continually arrive, long processes may never get CPU time, leading to starvation.
• Advance Knowledge Requirement: Algorithms like SJF require advance knowledge of the exact CPU burst time, which is practically impossible to predict with 100% accuracy in general-purpose operating systems.

2. Shortest Remaining Time First (SRTF)

Shortest Remaining Time First (SRTF) is the preemptive version of Shortest Job First (SJF). Whenever a new process arrives in the ready queue, its burst time is compared against the remaining execution time of the currently running process.

• Preemptive Nature: If a newly arrived process requires less CPU time than what is left of the current process, the operating system interrupts the current process, pushes its state back to the ready queue, and allocates the CPU to the new process.
• Optimality: SRTF yields the minimum average waiting time for a given set of processes.
• Context Switching Overhead: Because processes can be frequently interrupted and swapped out, SRTF incurs high context-switching overhead. Saving registers, flushing instruction pipelines, and reloading memory maps consume valuable CPU cycles.

3. Context Switching Overhead and Mechanics

A context switch involves storing the context (PCB - Process Control Bureau / Process Control Block) of a currently running process so that execution can be resumed later, and then loading the saved context of the next process.

• Overhead Cost: Every context switch is pure system overhead—no useful user instructions are executed during the switch.
• Impact on SRTF: In systems with high arrival rates of short jobs, SRTF triggers frequent context switches, occasionally wasting more CPU cycles on switching than the actual execution of the tasks.

4. Round Robin (RR) Scheduling Algorithm

Round Robin is designed specifically for time-sharing systems. It assigns a fixed time unit called a Time Quantum ($Q$) to every process in the ready queue in a cyclic order.

• Fixed Time Quantum: Regardless of how large or small a process is, it is permitted to run for at most $Q$ seconds.
• Preemption via Timer Interrupt: A hardware timer generates periodic interrupts after every $Q$ time units. If a process does not finish within its quantum, the OS preempts it and moves it to the back of the ready queue.

Numerical Example ($Q = 2$ seconds)

Consider three processes arriving with varying burst times. With a time quantum of $2$ seconds:

1. Process 1 runs for $2$s and terminates (if its burst was $\le 2$s) or goes to the back.
2. Process 2 runs for $2$s.
3. Process 3 runs for its allocated quantum.
4. The cycle repeats for remaining burst times until all processes finish, resulting in predictable response times and an average waiting time dependent heavily on choice of $Q$.

5. The Impact of Time Quantum ($Q$) Size

The performance of the Round Robin algorithm relies entirely on the configuration of the Time Quantum ($Q$).

6. Priority Scheduling and the Aging Solution

In Priority Scheduling, every process is associated with a priority number (integer). The CPU is allocated to the process with the highest priority.

• Priority Scale Conventions:
  • Low Number = High Priority (e.g., Priority 1 executes before Priority 100).
  • High Number = High Priority (depending on system implementation).
• Execution Mode: Can be implemented as either Preemptive (interrupts current task if a higher-priority task arrives) or Non-Preemptive (waits for current task to complete).

The Starvation Vulnerability & Aging Solution

• The Problem: Low-priority processes can starve indefinitely if a continuous stream of high-priority processes enters the ready queue.
• The Solution — Aging:
  • Aging is a technique where the priority of a waiting process is incrementally increased the longer it stays in the ready queue.
  • Example: If a process sits in the queue waiting, its priority counter is boosted by $+1$ at regular intervals. Eventually, its priority becomes high enough that it outranks incoming tasks and gets executed, completely eliminating starvation.

7. Multi-Level Queue (MLQ) Scheduling

When processes can be easily classified into distinct groups (e.g., interactive system processes, batch processes, background printing jobs), Multi-Level Queue scheduling partitions the ready queue into multiple separate queues.

• Queue-Specific Policies: Each queue can have its own dedicated scheduling algorithm. For instance, foreground interactive queues might use Round Robin, while background batch queues use FCFS.
• Inter-Queue Scheduling: Fixed priority scheduling is typically applied between queues (e.g., Queue 1 must be completely empty before Queue 2 processes can run), or time-slicing can be distributed among queues.

8. Multi-Level Feedback Queue (MLFQ) Scheduling

Multi-Level Feedback Queue is the most flexible and advanced CPU scheduling algorithm, used by modern operating systems like Linux (e.g., Completely Fair Scheduler concepts).

• Dynamic Migration: Unlike standard Multi-Level Queues where processes are permanently assigned to a queue upon entry, MLFQ allows processes to move between queues.
• Combines Learning and Adaptation:
  • If a process uses too much CPU time, it is demoted to a lower-priority queue with a larger time quantum.
  • If a process waits too long or blocks frequently for I/O, it is promoted to a higher-priority queue (incorporating the aging principle).

9. Comprehensive Summary of Scheduling Algorithms

Summary and Key Takeaways

• Preemption allows the operating system to interrupt a currently running process to serve higher-priority or shorter-arriving tasks.
• SRTF minimizes waiting time by always running the process with the shortest remaining burst time, but suffers from high context-switching overhead.
• Starvation occurs when long or low-priority processes are continuously bypassed by shorter or higher-priority arrivals.
• Aging solves starvation by progressively increasing the priority of waiting processes over time.
• Round Robin relies on a Time Quantum ($Q$) to achieve fair CPU sharing; an improper $Q$ degrades performance to either excessive context-switching or FCFS behavior.
• Priority Scheduling assigns rank numbers to execute critical tasks first, vulnerable to starvation unless paired with aging.
• Multi-Level Feedback Queues (MLFQ) represent the peak of scheduling flexibility by allowing processes to migrate between queues based on their CPU-bound or I/O-bound behavior.