⏱️ Module 03: CPU Scheduling Algorithms

Focus: CPU vs I/O Bursts, Preemptive vs Non-Preemptive, Core Algorithms (FCFS, SJF, SRTF, Round Robin, Priority, HRRN, MLFQ), Linux Completely Fair Scheduler (CFS), Multicore/NUMA Scheduling, and Gantt Chart Numerical Calculations.

📑 Table of Contents

1. CPU and I/O Burst Cycles
2. Preemptive vs Non-Preemptive Scheduling
3. Scheduling Criteria & Core Formulas
4. First-Come, First-Served (FCFS) & The Convoy Effect
5. Shortest Job First (SJF) & Shortest Remaining Time First (SRTF)
6. Round Robin (RR) & Time Quantum Tuning
7. Priority Scheduling & Aging
8. Highest Response Ratio Next (HRRN)
9. Multilevel Queue (MLQ) & Multilevel Feedback Queue (MLFQ)
10. Linux Completely Fair Scheduler (CFS) Under the Hood
11. Multi-Processor & NUMA Scheduling
12. Common Mistakes & Gotchas
13. Step-by-Step Numerical Practice Problems
14. High-Yield Interview Questions & Answers

1. CPU and I/O Burst Cycles

Process execution consists of a cycle of CPU execution (CPU Burst) and I/O wait (I/O Burst):

CPU-Bound vs I/O-Bound Processes:

• CPU-Bound Process: Spends most of its time performing heavy arithmetic computation (e.g., video encoding, machine learning training, scientific simulations). Characteristics: Long CPU bursts, infrequent I/O bursts.
• I/O-Bound Process: Spends most of its time waiting for input/output events (e.g., text editors, web servers, database queries). Characteristics: Short CPU bursts, frequent I/O bursts.

2. Preemptive vs Non-Preemptive Scheduling

Scheduling decisions take place under four conditions:

1. Running $\rightarrow$ Waiting: Process initiates I/O or calls sleep(). (Non-preemptive)
2. Running $\rightarrow$ Ready: Hardware timer interrupt fires or higher priority process arrives. (Preemptive)
3. Waiting $\rightarrow$ Ready: I/O completes or an event occurs. (Preemptive)
4. Running $\rightarrow$ Terminated: Process finishes execution. (Non-preemptive)

3. Scheduling Criteria & Core Formulas

1. Key Timestamps:

• Arrival Time ($AT$): The exact moment a process enters the Ready Queue.
• Burst Time ($BT$): Total CPU time required by the process to finish its current burst.
• Completion Time ($CT$): The moment the process finishes execution.

2. Formulas to Memorize for Interviews:

$$\text{Turnaround Time (TAT)} = CT - AT$$ $$\text{Waiting Time (WT)} = TAT - BT$$ $$\text{Response Time (RT)} = \text{Time of First CPU Allocation} - AT$$

3. Optimization Goals:

• Maximize: CPU Utilization ($70% - 90%$) and Throughput (Number of processes completed per unit time).
• Minimize: Turnaround Time, Waiting Time, and Response Time.

4. First-Come, First-Served (FCFS) & The Convoy Effect

• Type: Non-preemptive.
• Mechanism: The process that requests the CPU first is allocated the CPU first (FIFO Queue).

The Convoy Effect

When a long CPU-bound process holds the CPU, all short I/O-bound processes queue up behind it like small cars behind a slow truck.

5. Shortest Job First (SJF) & Shortest Remaining Time First (SRTF)

1. Non-Preemptive SJF

• Schedules the process with the shortest CPU burst time next.
• Provably Optimal: SJF gives the minimum average waiting time among all non-preemptive algorithms.
• Flaw: Requires knowing future burst times (can only be approximated using exponential smoothing: $\tau_{n+1} = \alpha t_n + (1-\alpha)\tau_n$).

2. Preemptive SJF (SRTF - Shortest Remaining Time First)

• If a new process arrives with a remaining CPU burst shorter than the currently executing process's remaining time, the OS preempts the running process.

6. Round Robin (RR) & Time Quantum Tuning

• Type: Preemptive.
• Mechanism: Each process is given a fixed slice of CPU time called a Time Quantum ($q$). When the quantum expires, the process is preempted and moved to the back of the circular Ready Queue.

7. Priority Scheduling & Aging

• Mechanism: An integer priority is assigned to each process (e.g., in Unix, smaller number = higher priority). The CPU is allocated to the highest priority process.
• Preemptive vs Non-Preemptive variants exist.

The Starvation Problem & Aging Solution

• Starvation (Indefinite Blocking): A low-priority process may sit in the Ready Queue forever if a continuous stream of high-priority processes keeps arriving.
• Aging Solution: Gradually increase the priority of processes that wait in the system for long periods (e.g., increase priority by 1 every 15 minutes of waiting).

8. Highest Response Ratio Next (HRRN)

• Type: Non-preemptive.
• Mechanism: Addresses SJF starvation by factoring in the waiting time of the process.

$$\text{Response Ratio } R = \frac{W + S}{S} = 1 + \frac{W}{S}$$ Where $W = \text{Current Waiting Time}$, $S = \text{Expected Service/Burst Time}$.

• If burst time $S$ is very small $\rightarrow R$ is large (Favors short jobs).
• If waiting time $W$ becomes very large $\rightarrow R$ grows automatically, preventing starvation!

9. Multilevel Queue (MLQ) & Multilevel Feedback Queue (MLFQ)

1. Multilevel Queue (MLQ)

Divides the Ready Queue into separate queues with fixed priorities (e.g., System Processes $>$ Interactive UI $>$ Batch Background). Processes are permanently assigned to one queue.

2. Multilevel Feedback Queue (MLFQ)

The gold standard for general-purpose scheduling. Processes can move between queues dynamically based on their observed runtime behavior.

The 5 Rules of MLFQ (Solaris/FreeBSD/macOS variants):

1. If $\text{Priority}(A) > \text{Priority}(B)$, $A$ runs ($B$ does not).
2. If $\text{Priority}(A) == \text{Priority}(B)$, $A$ and $B$ run in Round Robin.
3. When a job enters the system, it is placed at the highest priority queue.
4. Once a job uses up its time allotment at a given level (regardless of how many times it yielded the CPU), its priority is reduced (moved down one queue).
5. Priority Boost: After some time period $S$, move all jobs in the system to the topmost queue (prevents starvation and adapts to changing process phases).

10. Linux Completely Fair Scheduler (CFS) Under the Hood

The Completely Fair Scheduler (CFS) has been the default Linux CPU scheduler since kernel 2.6.23.

Core CFS Mechanics:

1. Virtual Runtime (vruntime):
   • Measures the amount of CPU execution time a task has consumed, normalized by its priority (nice level from $-20$ to $+19$).
   • High priority tasks (negative nice) accumulate vruntime slowly; low priority tasks accumulate vruntime quickly.
2. Red-Black Tree Data Structure:
   • All runnable tasks are stored in a self-balancing Red-Black Tree keyed on vruntime.
   • The scheduler always picks the leftmost node ($O(1)$ cached pointer / $O(\log N)$ tree update) because it has consumed the least virtual time.
3. No Fixed Time Quantum:
   • CFS dynamically scales time slices based on the Latency Target (e.g., target $6\text{ ms}$, divided among runnable tasks proportional to their weights).

11. Multi-Processor & NUMA Scheduling

Key Multicore Concepts:

1. Processor Affinity:
   • Soft Affinity: OS tries to keep a thread on the same CPU core to preserve warm L1/L2 caches, but may migrate if overloaded.
   • Hard Affinity (sched_setaffinity): Thread is strictly pinned to specific CPU cores.
2. NUMA-Aware Scheduling:
   • Accessing local RAM node takes ~50ns; accessing remote node over interconnect takes ~150ns. The OS scheduler avoids moving threads across NUMA boundaries.
3. Load Balancing:
   • Push Migration: A periodic kernel task checks load and pushes tasks from overloaded cores to idle cores.
   • Pull Migration: An idle core pulls runnable tasks from busy cores' runqueues.

12. Common Mistakes & Gotchas

[!CAUTION]

1. Calculating Waiting Time as CT - AT

$\text{Turnaround Time} = CT - AT$.
$\text{Waiting Time} = \text{Turnaround Time} - \text{Burst Time}$.
Do not forget to subtract the Burst Time!

[!WARNING]

2. Round Robin Arrival vs Preemption Ordering

When a running process's time quantum expires at timestamp $T$, and a new process simultaneously arrives in the system at timestamp $T$:

• Standard convention: Place the newly arrived process in the ready queue before the preempted returning process.

13. Step-by-Step Numerical Practice Problems

Problem 1: Round Robin Calculation ($q = 2$)

Dataset:

Step-by-Step Ready Queue Simulation ($q=2$):

• $t=0$: P1 enters. Queue: [P1]. P1 runs for 2 units (Rem: 3).
• $t=2$: During P1's run, P2 ($t=1$) and P3 ($t=2$) arrived. Preempted P1 goes behind them. Queue: [P2, P3, P1].
• $t=2$: P2 runs for 2 units (Rem: 1). During this, P4 ($t=3$) and P5 ($t=4$) arrived.
• $t=4$: Preempted P2 goes to back. Queue: [P3, P1, P4, P5, P2].
• $t=4$: P3 runs for 1 unit $\rightarrow$ Finishes at $t=5$ (CT=5). Queue: [P1, P4, P5, P2].
• $t=5$: P1 runs for 2 units (Rem: 1). Preempted P1 added to back. Queue: [P4, P5, P2, P1].
• $t=7$: P4 runs for 2 units $\rightarrow$ Finishes at $t=9$ (CT=9). Queue: [P5, P2, P1].
• $t=9$: P5 runs for 2 units (Rem: 1). Preempted P5 added to back. Queue: [P2, P1, P5].
• $t=11$: P2 runs for remaining 1 unit $\rightarrow$ Finishes at $t=12$ (CT=12). Queue: [P1, P5].
• $t=12$: P1 runs for remaining 1 unit $\rightarrow$ Finishes at $t=13$ (CT=13). Queue: [P5].
• $t=13$: P5 runs for remaining 1 unit $\rightarrow$ Finishes at $t=14$ (CT=14).

Gantt Chart:

Final Results Table:

• Average Turnaround Time: $(13 + 11 + 3 + 6 + 10) / 5 = \mathbf{8.60\text{ ms}}$
• Average Waiting Time: $(8 + 8 + 2 + 4 + 7) / 5 = \mathbf{5.80\text{ ms}}$

14. High-Yield Interview Questions & Answers

Q1: Why is Shortest Job First (SJF) provably optimal for minimizing average waiting time, and why is it hard to implement in practice?

Answer: SJF is mathematically optimal because moving a shorter job ahead of a longer job decreases the waiting time of the short job by more than it increases the waiting time of the long job, resulting in a net decrease in total system wait time.
In practice, it is difficult to implement because the OS cannot know the exact duration of a future CPU burst before the process executes. Real-world systems can only approximate burst times using exponential moving averages of past bursts.

Q2: What is the Convoy Effect, which scheduling algorithm suffers from it, and how is it resolved?

Answer: The Convoy Effect occurs in First-Come, First-Served (FCFS) scheduling when a single long, CPU-bound process holds the CPU, forcing numerous short, I/O-bound processes to wait in the Ready Queue. As a result, I/O devices sit completely idle while waiting for the CPU burst to finish.
It is resolved by using Preemptive Scheduling algorithms like Round Robin, SRTF, or MLFQ, which interrupt long bursts and allow I/O-bound tasks to execute their brief CPU bursts and return to their I/O queues immediately.

Q3: How does the Linux CFS scheduler achieve $O(1)$ scheduling decisions and fairness?

Answer: CFS tracks each process's CPU consumption via vruntime (scaled by priority weight). It stores all runnable tasks in a self-balancing Red-Black Tree ordered by vruntime. The task with the least vruntime is always the leftmost node. The Linux kernel maintains a direct cached pointer to this leftmost node, allowing it to select the next process to run in $O(1)$ time. When the task finishes its time slice, updating its vruntime and reinserting it into the Red-Black tree takes $O(\log N)$ time.

Q4: What is the difference between Soft Affinity and Hard Affinity in Multicore systems?

Answer:

• Soft Affinity: The OS scheduler has a policy preference to keep a thread running on the same CPU core to benefit from cache data locality. However, if that core becomes overloaded while other cores are idle, the OS is allowed to migrate the thread.
• Hard Affinity: A strict constraint enforced via system calls (such as sched_setaffinity in Linux). The OS is never permitted to run the thread on any CPU core other than the explicitly specified CPU mask, regardless of system load.

Proceed to Module 04: Synchronization & Concurrency Mastery!