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.

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.

Frequently Asked Questions