Priority Scheduling — Mars Pathfinder Inversion

Priority scheduling is what your OS uses right now. Linux's nice values (-20 to +19), Windows' priority classes (0-31), Java's Thread.setPriority() — all are implementations of priority scheduling. The starvation problem is real: in early Unix systems before aging was implemented, background processes at low priority could wait hours or days before getting CPU time if the system was heavily loaded.

The solution — aging — is an example of a general algorithm design principle: make greedy choices less greedy over time by adjusting inputs. A low-priority process that has waited long enough becomes a high-priority process. The invariant being maintained is that no process waits forever, even if it regularly loses to higher-priority work.

Why Priority Scheduling Nearly Killed a Mars Rover

Priority scheduling assigns each process a numeric priority; the scheduler always runs the highest-priority ready process. The core mechanic is simple — but the consequences are not. In the Mars Pathfinder mission, a lower-priority data bus task was preempted by a higher-priority weather task, which in turn blocked on a mutex held by the data task. The result: a priority inversion that triggered a system reset.

Preemptive priority scheduling means a running process can be interrupted at any instant by a higher-priority process. This gives low latency for critical tasks but introduces starvation: low-priority processes may never run if higher-priority work keeps arriving. Priority inversion occurs when a high-priority task waits on a resource held by a low-priority task that is preempted by a medium-priority task — the high-priority task effectively inherits the low-priority task's place in line.

Use priority scheduling when you have clear urgency tiers — real-time control, audio processing, or interrupt handlers. But never deploy it without priority inheritance or a ceiling protocol. The Mars Pathfinder bug was fixed by enabling the priority inheritance protocol in the VxWorks kernel, a one-line change that prevented the inversion. Without that, the rover would have reset every few hours.

Priority Scheduling Implementation

The non-preemptive priority scheduler implemented here picks the highest-priority ready process (lower numeric value = higher priority). It uses a min-heap to manage ready processes efficiently. Processes are sorted by arrival time first; then at each tick, all processes that have arrived are pushed onto the heap. The scheduler always runs the process with smallest priority number. This is a classic batch-oriented approach – suitable when tasks are short and infrequent, but dangerous in interactive systems where unpredictability can cause missed deadlines.

import heapq

def priority_non_preemptive(processes: list[dict]) -> list[dict]:
    """
    processes: {pid, arrival, burst, priority}
    Lower priority number = higher priority (1 = highest).
    """
    procs = sorted(processes, key=lambda p: p['arrival'])
    results = []
    time = 0
    heap = []  # (priority, arrival, process) — min-heap
    i = 0
    while i < len(procs) or heap:
        while i < len(procs) and procs[i]['arrival'] <= time:
            p = procs[i]
            heapq.heappush(heap, (p['priority'], p['arrival'], p))
            i += 1
        if not heap:
            time = procs[i]['arrival']
            continue
        _, _, p = heapq.heappop(heap)
        start = time
        ct  = start + p['burst']
        tat = ct - p['arrival']
        wt  = tat - p['burst']
        time = ct
        results.append({**p, 'start': start, 'ct': ct, 'tat': tat, 'wt': wt})
    return results

processes = [
    {'pid':'P1','arrival':0,'burst':10,'priority':3},
    {'pid':'P2','arrival':1,'burst':1, 'priority':1},
    {'pid':'P3','arrival':2,'burst':2, 'priority':4},
    {'pid':'P4','arrival':3,'burst':1, 'priority':5},
    {'pid':'P5','arrival':4,'burst':5, 'priority':2},
]
results = priority_non_preemptive(processes)
for r in sorted(results, key=lambda x: x['pid']):
    print(f"{r['pid']}: priority={r['priority']}, WT={r['wt']}, TAT={r['tat']}")

Starvation and Aging

Starvation occurs when low-priority processes wait indefinitely because high-priority ones keep arriving.

Aging solution: increase the priority of a process by 1 every T time units it waits. Eventually every process becomes highest priority and executes. The choice of T is critical – too large and starvation persists, too small and the priority system loses its intended differentiation. A common starting point: T = 5 * average burst time of all processes.

def apply_aging(processes: list[dict], time: int, aging_interval: int = 5) -> None:
    """Boost priority of waiting processes every aging_interval time units."""
    for p in processes:
        if p.get('waiting', 0) > 0 and p['waiting'] % aging_interval == 0:
            p['priority'] = max(1, p['priority'] - 1)  # lower number = higher priority

# Demonstration: process stuck at priority 10, aging every 5 time units
print('Priority progression with aging:')
priority = 10
for t in range(0, 51, 5):
    print(f't={t:3}: priority={priority}')
    priority = max(1, priority - 1)

Multilevel Queue Scheduling

Modern OSes use multilevel queues – separate queues for different process types (real-time, interactive, batch), each with its own scheduling algorithm. Processes are permanently assigned to a queue based on their type. Multilevel Feedback Queue (MLFQ) adds mobility: processes move between queues based on behaviour – CPU-bound processes drift to lower priority, I/O-bound stick to higher priority. This is what Linux and Windows implement underneath (with dynamic priority boosts for interactive tasks).

MLFQ prevents starvation by periodically boosting all processes to the top queue (every ~200ms in Linux). This ensures every process gets a time slice eventually.

Preemptive vs Non-Preemptive Priority Scheduling

In non-preemptive priority scheduling, once a process starts running, it continues until it blocks or finishes – even if a higher-priority process arrives in the meantime. This can cause high-priority tasks to miss deadlines. In preemptive priority scheduling, the running process is immediately interrupted when a higher-priority process becomes ready. Preemptive ensures that the highest-priority ready process always runs, but it adds context-switch overhead and requires careful synchronization for shared resources.

Real-time systems (e.g., VxWorks, RT-Linux) use preemptive priority scheduling. General-purpose OSes use a hybrid: preemptive with time quanta, where priority determines the next process but CPU-bound tasks eventually get demoted.

Priority Inversion – The Mars Pathfinder Bug

In 1997, the Mars Pathfinder rover, running VxWorks, experienced repeated system resets. The root cause was priority inversion: a high-priority data bus task blocked waiting for a mutex held by a low-priority meteorological task. A medium-priority communications task ran continuously, preventing the low-priority task from releasing the mutex. The high-priority task starved, causing a hardware watchdog to reset the system.

The fix was to enable priority inheritance on the mutex: when a high-priority task blocks on a lock, the lock-holding low-priority task temporarily inherits the higher priority, allowing it to run and release the lock quickly. This is now standard practice in real-time operating systems.

Priority Scheduling in C – The Brutal Implementation

You want a priority scheduler. Not a textbook diagram, but actual C code that runs. Here's the thing: every production scheduler I've seen wraps this logic in a sorted queue or a heap, not a linear scan. But let's walk the naive path first so you understand the perf trap.

The algorithm is disgusting simple: maintain a queue of process control blocks (PCBs). On each scheduling decision, scan the ready queue for the highest priority process. In non-preemptive mode, you run it to completion. In preemptive, you check after each timer tick whether a higher priority process arrived.

Don't use bubble sort on the queue — that's O(n) per insertion if you keep it sorted. A binary heap gives O(log n) inserts and O(1) peek. Your scheduler will live in the kernel; every microsecond counts. The code below is a stripped-down demo for non-preemptive priority scheduling. It assumes lower number = higher priority because that's what Unix nice values do.

// io.thecodeforge — dsa tutorial

import java.util.*;

class Process {
    int pid, burstTime, priority;
    Process(int pid, int bt, int pri) {
        this.pid = pid; this.burstTime = bt; this.priority = pri;
    }
}

public class PriorityScheduler {
    public static void main(String[] args) {
        List<Process> queue = Arrays.asList(
            new Process(1, 4, 2),
            new Process(2, 2, 1),
            new Process(3, 6, 3)
        );
        // sort by priority (lowest first), then FCFS
        queue.sort(Comparator.comparingInt(p -> p.priority));
        int time = 0;
        for (Process p : queue) {
            System.out.println("Time " + time + ": P" + p.pid + " runs for " + p.burstTime + " units");
            time += p.burstTime;
        }
        System.out.println("Total completion time: " + time);
    }
}

Starvation – The Silent Process Killer

Starvation happens when a low-priority process never gets CPU time because higher-priority processes keep arriving. It's not a bug — it's a design choice until you remember that some processes (like garbage collection, log flushers, or heartbeat monitors) run at low priority and are critical to system health.

The fix is aging: increment a process's priority as it waits. Every scheduler I've deployed adds a boost every N seconds. The Mars Pathfinder used this, but their bug was priority inversion, not starvation. Starvation is more subtle — it's a gradual degradation where your low-priority watchdog timer fires late and the system resets.

Aging doesn't solve priority inversion. But it does guarantee forward progress. Without it, your system will eventually hang on a process that never gets its turn. I've seen this in embedded systems where a background calibration task starves because the main loop never yields. The fix: track wait time and bump priority linearly or exponentially. The code below implements a basic aging simulation: every 3 time units, each waiting process gets its priority decreased (higher priority).

// io.thecodeforge — dsa tutorial

import java.util.*;

class Process {
    int pid, burstTime, priority, waitTime;
    Process(int pid, int bt, int pri) {
        this.pid = pid; this.burstTime = bt; this.priority = pri;
    }
}

public class AgingSimulation {
    public static void main(String[] args) {
        List<Process> queue = new ArrayList<>(Arrays.asList(
            new Process(1, 4, 5), // low priority
            new Process(2, 2, 1),
            new Process(3, 6, 2)
        ));
        int time = 0;
        while (!queue.isEmpty()) {
            // age waiting processes
            for (Process p : queue) {
                p.waitTime++;
                if (p.waitTime % 3 == 0) p.priority--; // boost every 3 units
            }
            queue.sort(Comparator.comparingInt(p -> p.priority));
            Process current = queue.remove(0);
            System.out.println("Time " + time + ": P" + current.pid + " (pri " + current.priority + ") runs");
            time += current.burstTime;
        }
    }
}

Gantt Charts: Why You Can't Trust a Pretty Timeline

Every textbook shows you a Gantt chart like it's a gift from God. Clean blocks, perfect ordering, zero ambiguity. Real systems don't work that way. You need Gantt charts to debug priority scheduling because without a visual timeline, you're guessing at which process starved or why a deadline blew up.

The Gantt chart exposes the truth: context switches are expensive, priority inversions hide in plain sight, and your pretty algorithm degrades under load. When you see a low-priority process getting ten milliseconds after a high-priority process runs for two seconds, you know aging isn't configured or quantum is wrong. The chart forces you to confront the scheduling reality, not the textbook ideal.

Build Gantt charts from your scheduler's event logs. Don't simulate them. Pull real timestamps. That's when you see why your system failed at 3 AM.

// io.thecodeforge — dsa tutorial

import java.util.*;

class Process {
    String name; int burst, priority;
    Process(String n, int b, int p) {
        name = n; burst = b; priority = p;
    }
}

public class GanttPriorityExample {
    public static void main(String[] args) {
        List<Process> proc = Arrays.asList(
            new Process("P1", 8, 2),
            new Process("P2", 3, 1),
            new Process("P3", 5, 3)
        );
        // Non-preemptive priority (lower = higher priority)
        proc.sort(Comparator.comparingInt(p -> p.priority));
        int time = 0;
        System.out.print("Gantt: ");
        for (Process p : proc) {
            System.out.print(p.name + "(" + time + "-" + (time + p.burst) + ") ");
            time += p.burst;
        }
        System.out.println();
    }
}

Priority Inversion: The Bug That Brought Down Mars Pathfinder

In 1997, a $150 million Mars rover nearly died because of priority inversion. A high-priority science task was waiting for a mutex held by a low-priority task, while a medium-priority task preempted the low one. The high-priority thread starved, watchdog kicked, rover reset. That's the production cost of ignoring priority inversion.

The fix isn't more priority levels. It's priority inheritance. When a low-priority thread holds a resource a high-priority thread needs, temporarily boost the low thread's priority to the high thread's level. This blocks the medium-priority thread from sneaking in. Real-time OS kernels like VxWorks and RT-Linux implement this. Your custom scheduler? Probably not. And that's why your robot arm jams.

You don't need a Mars rover to hit this. Any multi-threaded system with shared resources and different priorities will reproduce it. Test for it explicitly.

// io.thecodeforge — dsa tutorial

import java.util.concurrent.locks.*;

class LowTask extends Thread {
    private Lock lock;
    LowTask(Lock l) { this.lock = l; }
    public void run() {
        lock.lock();
        try { sleep(2000); } catch (InterruptedException e) {}
        lock.unlock();
        System.out.println("Low done");
    }
}

class HighTask extends Thread {
    private Lock lock;
    HighTask(Lock l) { this.lock = l; }
    public void run() {
        try { sleep(100); } catch (InterruptedException e) {}
        lock.lock(); // blocked by LowTask, med runs
        lock.unlock();
        System.out.println("High done — inversion?") ;
    }
}

public class PriorityInversionDemo {
    public static void main(String[] args) throws Exception {
        Lock lock = new ReentrantLock();
        new LowTask(lock).start();
        new Thread(() -> { // medium priority flood
            for (int i = 0; i < 100_000_000; i++) Math.sin(i);
            System.out.println("Medium done");
        }).start();
        new HighTask(lock).start();
    }
}