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:

1. Maximize Throughput: Complete as many jobs as possible per hour.
2. Minimize Turnaround Time: Time from submission to completion.
3. Minimize Response Time: Time from submission to first execution (Crucial for UI).
4. 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 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)
        }
    }
}

Java

import java.util.LinkedList;
import java.util.Queue;

class Process {
    String id;
    int burst;

    Process(String id, int burst) {
        this.id = id;
        this.burst = burst;
    }
}

public class Main {
    public static void main(String[] args) {
        Queue<Process> queue = new LinkedList<>();
        queue.add(new Process("A", 10));
        queue.add(new Process("B", 4));
        queue.add(new Process("C", 2));

        int quantum = 2;
        int time = 0;

        System.out.printf("Time %d: Start\n", time);

        while (!queue.isEmpty()) {
            Process p = queue.poll();
            int runTime = Math.min(quantum, p.burst);

            time += runTime;
            p.burst -= runTime;

            System.out.printf("Time %d: Process %s ran for %d (Remaining: %d)\n", time, p.id, runTime, p.burst);

            if (p.burst > 0) {
                queue.add(p);
            } else {
                System.out.printf("Time %d: Process %s Finished\n", time, p.id);
            }
        }
    }
}