CPU Scheduling — Cheat Sheet

CPU Scheduling Criteria

// Calculating scheduling metrics for 3 processes (non-preemptive)
// Process | Arrival | Burst
//    P1   |    0    |   6
//    P2   |    2    |   3
//    P3   |    4    |   1
// FCFS order: P1, P2, P3

// Gantt chart:
// | P1 (0-6) | P2 (6-9) | P3 (9-10) |
//   0         6          9           10

int[] arrival  = {0, 2, 4};
int[] burst    = {6, 3, 1};
int[] start    = {0, 6, 9};   // when each process first gets CPU
int[] finish   = {6, 9, 10};  // when each process completes

int n = 3;
double totalTurnaround = 0, totalWait = 0;
for (int i = 0; i < n; i++) {
    int turnaround = finish[i] - arrival[i];   // finish - arrival
    int waiting    = turnaround - burst[i];    // turnaround - burst
    System.out.printf("P%d → Turnaround: %d, Waiting: %d%n",
        i + 1, turnaround, waiting);
    totalTurnaround += turnaround;
    totalWait       += waiting;
}
System.out.printf("Avg Turnaround: %.1f%n", totalTurnaround / n);
System.out.printf("Avg Waiting:    %.1f%n", totalWait / n);
// Avg Turnaround: 5.67   Avg Waiting: 2.67

FCFS Scheduling

// FCFS Example:
// Process | Arrival | Burst
//    P1   |    0    |   10   ← long process arrives first (convoy!)
//    P2   |    1    |   2
//    P3   |    2    |   3
//
// Gantt: | P1 (0–10) | P2 (10–12) | P3 (12–15) |
//          0            10           12            15

int[] arrival = {0, 1, 2};
int[] burst   = {10, 2, 3};
int[] finish  = new int[3];
int[] turnaround = new int[3];
int[] waiting    = new int[3];

int currentTime = 0;
for (int i = 0; i < 3; i++) {
    // FCFS: process runs as soon as previous finishes (if arrived)
    currentTime = Math.max(currentTime, arrival[i]);
    currentTime += burst[i];
    finish[i]     = currentTime;
    turnaround[i] = finish[i] - arrival[i];
    waiting[i]    = turnaround[i] - burst[i];
    System.out.printf("P%d: finish=%d, turnaround=%d, waiting=%d%n",
        i+1, finish[i], turnaround[i], waiting[i]);
}
// P1: finish=10, turnaround=10, waiting=0
// P2: finish=12, turnaround=11, waiting=9   ← convoy effect!
// P3: finish=15, turnaround=13, waiting=10
double avgWait = Arrays.stream(waiting).average().orElse(0);
System.out.printf("Average Waiting Time: %.1f%n", avgWait);  // 6.3

SJF & SRTF Scheduling

// Process set for both SJF and SRTF comparison:
// Process | Arrival | Burst
//    P1   |    0    |   8
//    P2   |    1    |   4
//    P3   |    2    |   9
//    P4   |    3    |   5

// Non-preemptive SJF:
// At t=0: only P1 — run P1 (burst=8) → finishes at t=8
// At t=8: P2(4), P3(9), P4(5) all available → pick P2 (shortest)
// At t=12: P3(9), P4(5) → pick P4 → At t=17: pick P3
// Gantt: | P1(0-8) | P2(8-12) | P4(12-17) | P3(17-26) |
// Waiting: P1=0, P2=7, P3=15, P4=9  → Avg = 7.75

// Preemptive SRTF:
// t=0: P1 starts (remaining=8)
// t=1: P2 arrives (burst=4) < P1 remaining (7) → preempt! Run P2
// t=2: P3 arrives (burst=9) > P2 remaining (3) → P2 continues
// t=3: P4 arrives (burst=5) > P2 remaining (2) → P2 continues
// t=5: P2 done → P4(5) vs P1(7) vs P3(9) → run P4
// t=10: P4 done → P1(7) vs P3(9) → run P1
// t=17: P1 done → run P3
// Gantt: |P1(0-1)|P2(1-5)|P4(5-10)|P1(10-17)|P3(17-26)|
// Waiting: P1=9, P2=0, P3=15, P4=2  → Avg = 6.5  ← better than SJF!

int[] arrival = {0, 1, 2, 3};
int[] burst   = {8, 4, 9, 5};
// SRTF avg waiting = 6.5 vs SJF avg waiting = 7.75
System.out.println("SRTF consistently achieves lower or equal avg wait vs SJF");

Round Robin Scheduling

// Round Robin Example with quantum = 2
// Process | Arrival | Burst
//    P1   |    0    |   5
//    P2   |    0    |   3
//    P3   |    0    |   1
//    P4   |    0    |   2
//
// Queue order at start: [P1, P2, P3, P4]
// t=0: P1 runs 2 → remaining=3, queue: [P2, P3, P4, P1]
// t=2: P2 runs 2 → remaining=1, queue: [P3, P4, P1, P2]
// t=4: P3 runs 1 → done!         queue: [P4, P1, P2]
// t=5: P4 runs 2 → done!         queue: [P1, P2]
// t=7: P1 runs 2 → remaining=1,  queue: [P2, P1]
// t=9: P2 runs 1 → done!         queue: [P1]
// t=10:P1 runs 1 → done!
//
// Gantt: |P1|P2|P3|P4|--|P1|P2|P1|
//         0  2  4  5  7  9 10  11
//
// Turnaround: P1=11, P2=10, P3=5, P4=7
// Waiting:    P1=6,  P2=7,  P3=4, P4=5
// Avg Waiting = (6+7+4+5)/4 = 5.5

int quantum = 2;
int[] burst = {5, 3, 1, 2};
int[] remaining = burst.clone();
int n = burst.length;
int[] finish = new int[n];
int time = 0;

Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) queue.add(i);

while (!queue.isEmpty()) {
    int i = queue.poll();
    if (remaining[i] > 0) {
        int run = Math.min(remaining[i], quantum);
        System.out.printf("P%d runs t=%d to t=%d%n", i+1, time, time + run);
        time += run;
        remaining[i] -= run;
        if (remaining[i] > 0) queue.add(i);
        else finish[i] = time;
    }
}
// Print results
for (int i = 0; i < n; i++)
    System.out.printf("P%d finish=%d, turnaround=%d%n", i+1, finish[i], finish[i] - 0);

Priority Scheduling & Starvation

// Priority scheduling with aging to prevent starvation
// Lower number = higher priority (convention)

class Process {
    int id, basePriority, effectivePriority, waitingTime;
    Process(int id, int priority) {
        this.id = id;
        this.basePriority = priority;
        this.effectivePriority = priority;
        this.waitingTime = 0;
    }
}

List<Process> readyQueue = new ArrayList<>();
readyQueue.add(new Process(1, 1));   // high priority
readyQueue.add(new Process(2, 10));  // low priority — risk of starvation
readyQueue.add(new Process(3, 5));   // medium priority

int AGING_INTERVAL = 3;   // boost priority every 3 time units
int agingBoost = 1;       // increase effective priority by 1 per interval

// Simulate aging: every tick, boost waiting processes' effective priority
for (int tick = 0; tick < 15; tick++) {
    for (Process p : readyQueue) {
        p.waitingTime++;
        if (p.waitingTime % AGING_INTERVAL == 0) {
            p.effectivePriority = Math.max(1,
                p.effectivePriority - agingBoost);  // lower number = higher priority
            System.out.printf("Tick %2d: P%d priority boosted to %d%n",
                tick, p.id, p.effectivePriority);
        }
    }
}
// Eventually, low-priority P2 (base=10) ages up to compete with high-priority tasks

Multilevel Queue Scheduling

// Multilevel Queue — two queue levels
// Queue 0 (highest): Interactive/System processes → Round Robin, quantum=4
// Queue 1 (lowest): Batch processes → FCFS

// Queue assignment rule: interactive tasks go to Queue 0, batch to Queue 1
// Scheduler: always drain Queue 0 before touching Queue 1

Queue<String> queue0 = new LinkedList<>();  // interactive (foreground)
Queue<String> queue1 = new LinkedList<>();  // batch (background)

// Simulate adding processes
queue0.add("UI-Render");
queue0.add("API-Request");
queue1.add("Nightly-Backup");
queue1.add("Log-Compression");
queue0.add("DB-Query");   // interactive arrives — preempts batch

System.out.println("=== Scheduling Order ===");
// Scheduler logic: always pick from queue0 first
while (!queue0.isEmpty() || !queue1.isEmpty()) {
    if (!queue0.isEmpty()) {
        System.out.println("Running (foreground): " + queue0.poll());
    } else {
        System.out.println("Running (background): " + queue1.poll());
    }
}
// Nightly-Backup and Log-Compression only run after ALL interactive tasks finish

Preemptive vs Non-Preemptive Scheduling

// Preemption and synchronization — why volatile and synchronized are needed
// Without preemption: single-threaded, no races. With preemption: races everywhere.

// Race condition due to preemptive scheduling:
class Counter {
    private int count = 0;

    // NOT thread-safe: preemption can interrupt between read and write
    public void incrementUnsafe() {
        // These 3 bytecode instructions are NOT atomic:
        // 1. GETFIELD count        (read count into register)
        // ← timer interrupt fires HERE, another thread runs and also increments
        // 2. IADD 1                (add 1 in register)
        // 3. PUTFIELD count        (write back — OVERWRITES other thread's increment)
        count++;
    }

    // Thread-safe: synchronized prevents preemption from causing inconsistency
    public synchronized void incrementSafe() {
        count++;   // only one thread at a time — mutual exclusion
    }

    // Fastest: atomic CAS operation (hardware-level, no lock needed)
    private final AtomicInteger atomicCount = new AtomicInteger(0);
    public void incrementAtomic() {
        atomicCount.incrementAndGet();   // atomic compare-and-swap
    }
}

CPU Scheduling in Java

import java.util.concurrent.*;

// RecursiveTask: parallel merge sort using ForkJoinPool
class MergeSortTask extends RecursiveTask<int[]> {
    private final int[] arr;

    MergeSortTask(int[] arr) { this.arr = arr; }

    @Override
    protected int[] compute() {
        if (arr.length <= 512) {
            // Base case: sort sequentially
            int[] sorted = arr.clone();
            java.util.Arrays.sort(sorted);
            return sorted;
        }
        int mid = arr.length / 2;

        // Fork two sub-tasks — placed on current thread's deque
        MergeSortTask left  = new MergeSortTask(java.util.Arrays.copyOfRange(arr, 0, mid));
        MergeSortTask right = new MergeSortTask(java.util.Arrays.copyOfRange(arr, mid, arr.length));

        left.fork();           // async: placed in work queue, may be stolen
        int[] rightResult = right.compute(); // compute right in current thread
        int[] leftResult  = left.join();     // wait for left (or steal + execute)

        return merge(leftResult, rightResult);
    }

    private int[] merge(int[] a, int[] b) {
        int[] result = new int[a.length + b.length];
        int i = 0, j = 0, k = 0;
        while (i < a.length && j < b.length)
            result[k++] = a[i] <= b[j] ? a[i++] : b[j++];
        while (i < a.length) result[k++] = a[i++];
        while (j < b.length) result[k++] = b[j++];
        return result;
    }
}

// Use custom pool with parallelism = CPU cores
ForkJoinPool pool = new ForkJoinPool(Runtime.getRuntime().availableProcessors());
int[] data = new int[]{5, 3, 8, 1, 9, 2, 7, 4, 6};
int[] sorted = pool.invoke(new MergeSortTask(data));
System.out.println(java.util.Arrays.toString(sorted)); // [1, 2, 3, 4, 5, 6, 7, 8, 9]