Add Priority Scheduling with Aging

Topic Overview

Priority and Starvation

Static priority scheduling runs the highest-priority ready process first. A low-priority task can wait forever if higher-priority work never blocks. That is starvation, and it shows up in production when a background indexer never runs because foreground tabs keep spawning runnable threads.

Aging Fixes the Fairness Gap

Aging raises a waiting process's effective priority over time:

• Base priority: assigned at creation (e.g., interactive = 50, batch = 10)
• Wait counter: increments each tick while ready but not running
• Boost rule: effective priority = base + floor(wait / aging_interval)

For example, a batch job at base priority 10 that waits 200 ticks with aging every 40 ticks gains 5 levels and eventually preempts a sleeping high-priority task.

Why This Matters in Production

Unbounded priority scheduling caused the Mars Pathfinder's real 1997 priority-inversion bug, where a low-priority task holding a mutex blocked a high-priority one until a watchdog reset the system; VxWorks and most RTOS schedulers now ship priority inheritance specifically because of that incident. The aging mechanism you implement here is the same fix Linux's O(1) scheduler and Windows' dynamic priority boost used before CFS replaced them.

Debugging Checklist

Before you call the implementation done, walk failure modes on purpose. Test empty structures, single-element edge cases, maximum concurrency, and errno paths that must not crash the program. OS code usually fails in production when happy-path tests pass but invariants break under contention or memory pressure.

Implementation Notes

Keep structures small and name fields after kernel counterparts when possible. That lets you read man pages and kernel source side by side while you work. Print observable events during development; remove noisy logs once tests pass reliably.

For This Exercise

You will add priority comparison on enqueue and an aging function that prevents indefinite starvation. The task requires you to log preemption decisions so you can see when aging, not raw priority, wins the CPU.

Simulate a preemptive priority scheduler with aging, driven by input.

Input format (whitespace-separated):

• n: number of processes (1..8)
• aging_interval: ticks per aging step (>= 1)
• n lines of: pid arrival burst priority (lower number = higher priority)

Clock ticks are one time unit each. At every tick, each READY process (arrived, not finished, not running this tick) gains one tick of wait credit; its effective priority is priority + (waited_ticks / aging_interval) using integer division. The scheduler runs the READY process with the LOWEST effective priority for one tick, breaking ties by earlier arrival, then by lower input index. Running a process does NOT reset its wait credit (preemptive, per-tick re-evaluation).

Per tick print exactly: "t=%d run PID=%d eff_prio=%ld wait=%ld" After the simulation, for each process in input order print: "PID %d turnaround=%d wait=%d" with turnaround = finish - arrival and wait = turnaround - burst, then "avg_turnaround=%.1f" and "avg_wait=%.1f".

Success Criteria:

• Highest effective priority (lowest number) runs at every tick
• Aging lets low-priority processes eventually preempt high-priority ones
• Correct turnaround/wait per process and correct one-decimal averages