Pluggable CPU Schedulers for XINU

This repository replaces XINU's default priority scheduler with pluggable policies designed to reduce starvation under mixed workloads. The codebase focuses on scheduler mechanics, queue discipline, timer-driven preemption, and context-switch behavior inside a compact teaching kernel that is still useful as a systems experimentation target.

The implementation adds two schedulers behind the same dispatch path in sys/resched.c, with policy control exposed through sys/scheduling.c and h/sched.h.

Core Features & Architecture

Exponential Distribution Scheduler

The exponential scheduler chooses the next runnable process from the ready queue by sampling a cutoff value from an exponential distribution with lambda = 0.1. The scheduler then selects the first ready process whose priority exceeds that sampled value. If the sample falls below the minimum ready priority, the lowest eligible priority wins; if it exceeds the maximum ready priority, the highest ready priority wins.

The sampling model follows:

$$F(x; \lambda) = 1 - e^{-\lambda x}$$

with samples generated from:

$$x = -\frac{\ln(y)}{\lambda}, \quad y \in (0, 1]$$

XINU does not ship with a standard math runtime, so this repository includes a small math support layer in sys/math.c. It implements log(), pow(), and expdev() from scratch in C. The logarithm path uses Taylor series approximations, which are sufficient for scheduler sampling without adding an external libc dependency.

Linux 2.2-Style Epoch Scheduler

The Linux-style scheduler emulates the epoch-based behavior of the early Linux 2.2 SCHED_OTHER implementation. Each epoch assigns every process a time quantum. A process that fully consumed its previous quantum starts the new epoch with:

quantum = priority

A process that did not exhaust its previous budget carries half of the remainder into the next epoch:

quantum = floor(counter / 2) + priority

Runnable processes are ranked by a dynamic goodness metric:

goodness = counter + priority

Processes with larger goodness values run first. Tasks with the same goodness rotate fairly through queue ordering. Once all runnable processes have exhausted their counters, the scheduler starts a new epoch and recomputes both counter and goodness for each live process.

Implementation Layout

• sys/resched.c: policy-aware dispatch and context-switch entry point
• sys/scheduling.c: scheduler class selection, exponential candidate selection, epoch refresh
• sys/math.c: custom math primitives used by the exponential scheduler
• sys/create.c: initializes epoch accounting for new processes
• sys/insert.c: queue insertion rules that preserve round-robin fairness for equal keys
• h/proc.h: per-process scheduler state (counter, goodness)

Building and Execution

Prerequisites

• gcc with 32-bit support
• binutils (as, ld)
• make
• qemu-system-i386

Build

cd compile
make clean
make

The build emits compile/xinu.elf.

Run in QEMU

cd compile
make run

The provided run target starts qemu-system-i386 in -nographic mode and boots xinu.elf directly as the kernel image.

Debug Session

cd compile
make debug

This launches QEMU with -s -S so a GDB session can attach before the guest begins execution.

Selecting a Scheduler

The sample harness in sys/main.c switches between the exponential and Linux-style schedulers through setschedclass(). Adjust that harness or integrate the scheduler class selection into your own test workload as needed.

License

MIT. See LICENSE.