CPU Scheduling Algorithms

[!NOTE] This module explores the core principles of CPU Scheduling Algorithms, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. The Scheduler’s Dilemma

The CPU is a precious resource. The Scheduler decides which process gets to use it next. It must balance conflicting goals:

Maximize Throughput: Complete as many jobs as possible per hour.
Minimize Turnaround Time: Time from submission to completion.
Minimize Response Time: Time from submission to first execution (Crucial for UI).
Fairness: Prevent starvation.

2. Classic Algorithms

1. First-Come, First-Served (FCFS)

The simplest queue (FIFO).

Pros: Simple to implement.
Cons: Convoy Effect. If a CPU-bound job arrives first, all I/O-bound jobs get stuck behind it.

2. Shortest Job First (SJF)

Pick the job with the smallest burst time.

Pros: Mathematically optimal for minimizing average waiting time.
Cons: Impossible to implement perfectly (We don’t know the future!).

3. Round Robin (RR)

Give each process a fixed Time Slice (Quantum) (e.g., 10ms).

Pros: Fair. Good response time.
Cons: Context switching overhead. If quantum is too small, overhead dominates.

4. Multilevel Feedback Queue (MLFQ)

The “Real World” approximation.

Rule 1: If Priority(A) > Priority(B), A runs.
Rule 2: If Priority(A) == Priority(B), Round Robin.
Rule 3: New jobs start at Highest Priority.
Rule 4: If a job uses its full time slice, priority is reduced (It’s CPU-bound).
Rule 5: If a job yields (I/O) before time slice ends, priority stays high (It’s I/O-bound/Interactive).

3. Interactive: Scheduler Arena

See how different algorithms affect the timeline (Gantt Chart).

0ms Timeline (Time Slices) 20ms

Select an algorithm

Avg Wait Time

Context Switches

4. Linux CFS (Completely Fair Scheduler)

Linux doesn’t use simple MLFQ. It uses CFS.

Concept: Model an “Ideal Multi-tasking CPU” where all N processes run in parallel at 1/N speed.
Virtual Runtime (vruntime): Measures how long a task has run.
Structure: Uses a Red-Black Tree (Self-balancing binary search tree) to store processes, sorted by vruntime.
Selection: Always pick the task with the lowest vruntime (leftmost node).
Fairness: If a task sleeps (I/O), its vruntime doesn’t increase, so it stays on the left (High Priority).

5. Code Example: Round Robin Simulation

A simple Go simulator for Round Robin.

```go
package main

import "fmt"

type Process struct {
    ID    string
    Burst int
}

func main() {
    // Queue of processes
    queue := []Process{
        {"A", 10},
        {"B", 4},
        {"C", 2},
    }

    quantum := 2
    time := 0

    fmt.Printf("Time %d: Start\n", time)

    for len(queue) > 0 {
        // Pop first process
        p := queue[0]
        queue = queue[1:]

        // Execute for quantum or burst
        runTime := quantum
        if p.Burst < quantum {
            runTime = p.Burst
        }

        time += runTime
        p.Burst -= runTime

        fmt.Printf("Time %d: Process %s ran for %d (Remaining: %d)\n",
                   time, p.ID, runTime, p.Burst)

        if p.Burst > 0 {
            // Push back to queue
            queue = append(queue, p)
        } else {
            fmt.Printf("Time %d: Process %s Finished\n", time, p.ID)
        }
    }
}
```