Scheduling Algorithms — 2ms Quantum Context-Switch Storm

package io.thecodeforge.scheduler;

import java.util.ArrayList;
import java.util.List;

/**
 * Small foundation model shared by the scheduler examples.
 *
 * This is intentionally simple: one CPU, one ready queue, integer time units.
 * Real kernels have multiple cores, I/O waits, wakeup latency, NUMA effects,
 * interrupt handling, cache affinity, and priority classes — but you need a
 * clean model first before adding that complexity.
 */
public class SchedulingPrimer {

    static class Process {
        String name;
        int arrivalTime;
        int burstTime;
        int remainingBurst;
        int priority;
        int waitingTime;
        int turnaroundTime;
        int responseTime = -1;   // first time scheduled - arrivalTime
        int completionTime;

        Process(String name, int arrivalTime, int burstTime) {
            this(name, arrivalTime, burstTime, 0);
        }

        Process(String name, int arrivalTime, int burstTime, int priority) {
            this.name = name;
            this.arrivalTime = arrivalTime;
            this.burstTime = burstTime;
            this.remainingBurst = burstTime;
            this.priority = priority;
        }

        Process copy() {
            return new Process(name, arrivalTime, burstTime, priority);
        }
    }

    public static void main(String[] args) {
        List<Process> workload = new ArrayList<>();
        workload.add(new Process("P1", 0, 6));
        workload.add(new Process("P2", 2, 3));
        workload.add(new Process("P3", 4, 1));

        System.out.println("Scheduling workload loaded:");
        for (Process p : workload) {
            System.out.println("  " + p.name
                + " arrival=" + p.arrivalTime
                + " burst=" + p.burstTime
                + " priority=" + p.priority);
        }

        System.out.println("\nMetrics to watch: waiting time, turnaround time, response time, throughput.");
        System.out.println("A scheduler's job is to optimize some of these without destroying the others.");
    }
}

package io.thecodeforge.scheduler;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class FCFSScheduler {

    static class Process {
        String name;
        int arrivalTime;
        int burstTime;
        int waitingTime;
        int turnaroundTime;
        int responseTime = -1;
        int completionTime;

        Process(String name, int arrivalTime, int burstTime) {
            this.name = name;
            this.arrivalTime = arrivalTime;
            this.burstTime = burstTime;
        }
    }

    public static void simulate(List<Process> processes) {
        // FCFS must respect arrival order. If input is unsorted, sort by arrival time.
        processes.sort(Comparator.comparingInt(p -> p.arrivalTime));

        int currentTime = 0;
        for (Process p : processes) {
            // CPU sits idle if nothing has arrived yet.
            if (currentTime < p.arrivalTime) {
                currentTime = p.arrivalTime;
            }

            p.responseTime = currentTime - p.arrivalTime;
            p.waitingTime = currentTime - p.arrivalTime;
            currentTime += p.burstTime;
            p.completionTime = currentTime;
            p.turnaroundTime = p.completionTime - p.arrivalTime;
        }
    }

    public static void main(String[] args) {
        List<Process> processes = new ArrayList<>();
        processes.add(new Process("P1", 0, 24));
        processes.add(new Process("P2", 0, 3));
        processes.add(new Process("P3", 0, 3));

        simulate(processes);

        int totalWait = 0, totalTurn = 0;
        for (Process p : processes) {
            totalWait += p.waitingTime;
            totalTurn += p.turnaroundTime;
            System.out.println(p.name
                + ": completion=" + p.completionTime
                + " turnaround=" + p.turnaroundTime
                + " waiting=" + p.waitingTime
                + " response=" + p.responseTime);
        }

        System.out.printf("Average waiting time: %.2f%n", (double) totalWait / processes.size());
        System.out.printf("Average turnaround time: %.2f%n", (double) totalTurn / processes.size());
    }
}

package io.thecodeforge.scheduler;

import java.util.ArrayList;
import java.util.List;

public class SJFScheduler {

    static class Process {
        String name;
        int arrivalTime;
        int burstTime;
        int remainingBurst;
        int waitingTime;
        int turnaroundTime;
        int responseTime = -1;
        int completionTime;

        Process(String name, int arrivalTime, int burstTime) {
            this.name = name;
            this.arrivalTime = arrivalTime;
            this.burstTime = burstTime;
            this.remainingBurst = burstTime;
        }

        Process copy() {
            return new Process(name, arrivalTime, burstTime);
        }
    }

    public static void simulate(List<Process> processes, boolean preemptive) {
        if (preemptive) {
            simulateSRTF(processes);
        } else {
            simulateNonPreemptive(processes);
        }
    }

    private static void simulateNonPreemptive(List<Process> processes) {
        int n = processes.size();
        boolean[] done = new boolean[n];
        int completed = 0;
        int currentTime = 0;

        while (completed < n) {
            int idx = -1;
            int minBurst = Integer.MAX_VALUE;

            for (int i = 0; i < n; i++) {
                Process p = processes.get(i);
                if (!done[i] && p.arrivalTime <= currentTime && p.burstTime < minBurst) {
                    minBurst = p.burstTime;
                    idx = i;
                }
            }

            if (idx == -1) {
                currentTime++;
                continue;
            }

            Process p = processes.get(idx);
            p.responseTime = currentTime - p.arrivalTime;
            p.waitingTime = currentTime - p.arrivalTime;
            currentTime += p.burstTime;
            p.completionTime = currentTime;
            p.turnaroundTime = p.completionTime - p.arrivalTime;
            done[idx] = true;
            completed++;
        }
    }

    private static void simulateSRTF(List<Process> processes) {
        int n = processes.size();
        int completed = 0;
        int currentTime = 0;

        while (completed < n) {
            int idx = -1;
            int minRemaining = Integer.MAX_VALUE;

            for (int i = 0; i < n; i++) {
                Process p = processes.get(i);
                if (p.arrivalTime <= currentTime && p.remainingBurst > 0 && p.remainingBurst < minRemaining) {
                    minRemaining = p.remainingBurst;
                    idx = i;
                }
            }

            if (idx == -1) {
                currentTime++;
                continue;
            }

            Process p = processes.get(idx);
            if (p.responseTime == -1) {
                p.responseTime = currentTime - p.arrivalTime;
            }

            p.remainingBurst--; // run for one time unit
            currentTime++;

            if (p.remainingBurst == 0) {
                p.completionTime = currentTime;
                p.turnaroundTime = p.completionTime - p.arrivalTime;
                p.waitingTime = p.turnaroundTime - p.burstTime;
                completed++;
            }
        }
    }

    public static void main(String[] args) {
        List<Process> base = List.of(
            new Process("P1", 0, 6),
            new Process("P2", 2, 8),
            new Process("P3", 1, 3),
            new Process("P4", 4, 4)
        );

        List<Process> nonPreemptive = new ArrayList<>();
        List<Process> preemptive = new ArrayList<>();
        for (Process p : base) {
            nonPreemptive.add(p.copy());
            preemptive.add(p.copy());
        }

        simulate(nonPreemptive, false);
        System.out.println("=== Non-preemptive SJF ===");
        for (Process p : nonPreemptive) {
            System.out.println(p.name + ": completion=" + p.completionTime
                + " turnaround=" + p.turnaroundTime
                + " waiting=" + p.waitingTime
                + " response=" + p.responseTime);
        }

        simulate(preemptive, true);
        System.out.println("\n=== Preemptive SRTF ===");
        for (Process p : preemptive) {
            System.out.println(p.name + ": completion=" + p.completionTime
                + " turnaround=" + p.turnaroundTime
                + " waiting=" + p.waitingTime
                + " response=" + p.responseTime);
        }
    }
}

package io.thecodeforge.scheduler;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Queue;

public class RoundRobinScheduler {

    static class Process {
        String name;
        int arrivalTime;
        int burstTime;
        int remainingBurst;
        int turnaroundTime;
        int waitingTime;
        int responseTime = -1;
        int completionTime;

        Process(String name, int arrivalTime, int burstTime) {
            this.name = name;
            this.arrivalTime = arrivalTime;
            this.burstTime = burstTime;
            this.remainingBurst = burstTime;
        }
    }

    public static void simulate(List<Process> processes, int quantum) {
        processes.sort(Comparator.comparingInt(p -> p.arrivalTime));

        Queue<Process> readyQueue = new ArrayDeque<>();
        int currentTime = 0;
        int completed = 0;
        int nextArrival = 0;
        int n = processes.size();

        while (completed < n) {
            // Add all processes that have arrived by currentTime
            while (nextArrival < n && processes.get(nextArrival).arrivalTime <= currentTime) {
                readyQueue.add(processes.get(nextArrival));
                nextArrival++;
            }

            // If nothing is ready, jump time to the next arrival
            if (readyQueue.isEmpty()) {
                currentTime = processes.get(nextArrival).arrivalTime;
                continue;
            }

            Process p = readyQueue.poll();

            if (p.responseTime == -1) {
                p.responseTime = currentTime - p.arrivalTime;
            }

            int execute = Math.min(quantum, p.remainingBurst);
            p.remainingBurst -= execute;
            currentTime += execute;

            // Add newly arrived processes that appeared during this quantum
            while (nextArrival < n && processes.get(nextArrival).arrivalTime <= currentTime) {
                readyQueue.add(processes.get(nextArrival));
                nextArrival++;
            }

            if (p.remainingBurst > 0) {
                readyQueue.add(p);
            } else {
                p.completionTime = currentTime;
                p.turnaroundTime = p.completionTime - p.arrivalTime;
                p.waitingTime = p.turnaroundTime - p.burstTime;
                completed++;
            }
        }
    }

    public static void main(String[] args) {
        int quantum = 4;
        List<Process> processes = new ArrayList<>();
        processes.add(new Process("P1", 0, 24));
        processes.add(new Process("P2", 0, 3));
        processes.add(new Process("P3", 0, 3));

        simulate(processes, quantum);

        for (Process p : processes) {
            System.out.println(p.name
                + ": completion=" + p.completionTime
                + " turnaround=" + p.turnaroundTime
                + " waiting=" + p.waitingTime
                + " response=" + p.responseTime);
        }
    }
}

package io.thecodeforge.scheduler;

import java.util.ArrayList;
import java.util.List;

public class PriorityScheduler {

    static class Process {
        String name;
        int arrivalTime;
        int burstTime;
        int remainingBurst;
        int basePriority;      // lower number = higher priority
        int effectivePriority; // changes with aging
        int waitingTime;
        int turnaroundTime;
        int responseTime = -1;
        int completionTime;

        Process(String name, int arrivalTime, int burstTime, int priority) {
            this.name = name;
            this.arrivalTime = arrivalTime;
            this.burstTime = burstTime;
            this.remainingBurst = burstTime;
            this.basePriority = priority;
            this.effectivePriority = priority;
        }
    }

    /**
     * Simulate preemptive priority scheduling with simple aging.
     * agingInterval = every N time units of waiting, improve effective priority by 1.
     */
    public static void simulate(List<Process> processes, int agingInterval) {
        int n = processes.size();
        int completed = 0;
        int currentTime = 0;

        while (completed < n) {
            Process chosen = null;

            // Update effective priorities based on wait time (aging)
            for (Process p : processes) {
                if (p.arrivalTime <= currentTime && p.remainingBurst > 0) {
                    int waited = currentTime - p.arrivalTime;
                    int ageBoost = agingInterval > 0 ? waited / agingInterval : 0;
                    p.effectivePriority = Math.max(0, p.basePriority - ageBoost);
                }
            }

            // Pick highest effective priority among arrived runnable tasks
            for (Process p : processes) {
                if (p.arrivalTime <= currentTime && p.remainingBurst > 0) {
                    if (chosen == null
                            || p.effectivePriority < chosen.effectivePriority
                            || (p.effectivePriority == chosen.effectivePriority
                                && p.arrivalTime < chosen.arrivalTime)) {
                        chosen = p;
                    }
                }
            }

            if (chosen == null) {
                currentTime++;
                continue;
            }

            if (chosen.responseTime == -1) {
                chosen.responseTime = currentTime - chosen.arrivalTime;
            }

            // Preemptive: run for one time unit, then re-evaluate priorities
            chosen.remainingBurst--;
            currentTime++;

            if (chosen.remainingBurst == 0) {
                chosen.completionTime = currentTime;
                chosen.turnaroundTime = chosen.completionTime - chosen.arrivalTime;
                chosen.waitingTime = chosen.turnaroundTime - chosen.burstTime;
                completed++;
            }
        }
    }

    public static void main(String[] args) {
        List<Process> processes = new ArrayList<>();
        processes.add(new Process("P1", 0, 10, 2));
        processes.add(new Process("P2", 0, 5, 1));
        processes.add(new Process("P3", 0, 3, 5));

        simulate(processes, 5); // every 5 time units of waiting, improve priority by 1

        for (Process p : processes) {
            System.out.println(p.name
                + ": completion=" + p.completionTime
                + " turnaround=" + p.turnaroundTime
                + " waiting=" + p.waitingTime
                + " response=" + p.responseTime
                + " finalEffectivePriority=" + p.effectivePriority);
        }
    }
}

package io.thecodeforge.scheduler;

import java.util.ArrayList;
import java.util.List;

public class SchedulingMetrics {

    static class Result {
        String name;
        int waitingTime;
        int turnaroundTime;
        int responseTime;

        Result(String name, int waitingTime, int turnaroundTime, int responseTime) {
            this.name = name;
            this.waitingTime = waitingTime;
            this.turnaroundTime = turnaroundTime;
            this.responseTime = responseTime;
        }
    }

    public static double avgTurnaround(List<Result> processes) {
        return processes.stream().mapToInt(p -> p.turnaroundTime).average().orElse(0.0);
    }

    public static double avgWaiting(List<Result> processes) {
        return processes.stream().mapToInt(p -> p.waitingTime).average().orElse(0.0);
    }

    public static double avgResponse(List<Result> processes) {
        return processes.stream().mapToInt(p -> p.responseTime).average().orElse(0.0);
    }

    public static double throughput(int processCount, int totalTime) {
        return totalTime == 0 ? 0.0 : (double) processCount / totalTime;
    }

    public static void main(String[] args) {
        // Same workload, hypothetical outcomes under different schedulers.
        // In production you would feed these from actual simulation results.

        List<Result> fcfs = new ArrayList<>();
        fcfs.add(new Result("P1", 0, 24, 0));
        fcfs.add(new Result("P2", 24, 27, 24));
        fcfs.add(new Result("P3", 27, 30, 27));

        List<Result> rr = new ArrayList<>();
        rr.add(new Result("P1", 6, 30, 0));
        rr.add(new Result("P2", 4, 7, 4));
        rr.add(new Result("P3", 7, 10, 7));

        System.out.println("=== FCFS Metrics ===");
        System.out.printf("Avg waiting    : %.2f%n", avgWaiting(fcfs));
        System.out.printf("Avg turnaround : %.2f%n", avgTurnaround(fcfs));
        System.out.printf("Avg response   : %.2f%n", avgResponse(fcfs));
        System.out.printf("Throughput     : %.3f processes/unit%n", throughput(fcfs.size(), 30));

        System.out.println("\n=== Round Robin Metrics ===");
        System.out.printf("Avg waiting    : %.2f%n", avgWaiting(rr));
        System.out.printf("Avg turnaround : %.2f%n", avgTurnaround(rr));
        System.out.printf("Avg response   : %.2f%n", avgResponse(rr));
        System.out.printf("Throughput     : %.3f processes/unit%n", throughput(rr.size(), 30));
    }
}

#!/bin/bash
# Check current scheduling policy and context switch information for a process.
# Requires chrt from util-linux. Replace 1234 with an actual PID on your system.

PID="$1"

if [ -z "$PID" ]; then
  echo "Usage: $0 <PID>"
  exit 1
fi

if [ ! -d "/proc/$PID" ]; then
  echo "PID $PID does not exist"
  exit 1
fi

echo "Process $PID scheduling info:"

# Example chrt output format:
# pid 1234's current scheduling policy: SCHED_OTHER
# pid 1234's current scheduling priority: 0
chrt -p "$PID" || echo "chrt not available or insufficient permissions"

echo
cat "/proc/$PID/status" | grep -E '^State:'
echo
cat "/proc/$PID/status" | grep -E '^(voluntary|nonvoluntary)_ctxt_switches'

echo
if [ -f /sys/fs/cgroup/cpu.stat ]; then
  echo "cgroup cpu.stat:"
  cat /sys/fs/cgroup/cpu.stat
fi

#define _GNU_SOURCE
#include <pthread.h>
#include <sched.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

/*
 * Minimal demonstration of priority inheritance setup.
 * This example configures different real-time priorities so that
 * inheritance is meaningful. On Linux this usually requires root
 * privileges or CAP_SYS_NICE.
 */

pthread_mutex_t mutex;

static void set_fifo_priority(pthread_t thread, int priority) {
    struct sched_param param;
    memset(&param, 0, sizeof(param));
    param.sched_priority = priority;
    if (pthread_setschedparam(thread, SCHED_FIFO, &param) != 0) {
        perror("pthread_setschedparam");
        fprintf(stderr, "Hint: run as root or grant CAP_SYS_NICE for real RT priorities.\n");
    }
}

void* low_priority_work(void* arg) {
    pthread_mutex_lock(&mutex);
    printf("Low-priority thread acquired lock\n");
    sleep(2); // simulate slow work while holding the lock
    printf("Low-priority thread releasing lock\n");
    pthread_mutex_unlock(&mutex);
    return NULL;
}

void* high_priority_work(void* arg) {
    usleep(200000); // small delay so low-priority thread acquires lock first
    printf("High-priority thread attempting to acquire lock\n");
    pthread_mutex_lock(&mutex);
    printf("High-priority thread acquired lock\n");
    pthread_mutex_unlock(&mutex);
    return NULL;
}

int main() {
    pthread_mutexattr_t attr;
    pthread_mutexattr_init(&attr);
    pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT);
    pthread_mutex_init(&mutex, &attr);

    pthread_t low, high;
    pthread_create(&low, NULL, low_priority_work, NULL);
    pthread_create(&high, NULL, high_priority_work, NULL);

    // Different priorities are what make inversion and inheritance meaningful.
    // High thread should outrank low thread under SCHED_FIFO.
    set_fifo_priority(low, 10);
    set_fifo_priority(high, 20);

    pthread_join(low, NULL);
    pthread_join(high, NULL);

    pthread_mutex_destroy(&mutex);
    pthread_mutexattr_destroy(&attr);
    return 0;
}