Priority Scheduling

Priority scheduling is a CPU scheduling discipline in which every process (or thread) is assigned a numeric priority, and the scheduler always selects the ready process with the best priority value to run next. Priorities can be assigned statically at creation (fixed for the process's lifetime) or dynamically, recomputed as the system runs. The source of a priority is a policy decision external to the scheduling algorithm itself: it might reflect user-assigned importance (a `nice` value), the process's resource needs (short jobs get high priority, generalizing Shortest-Job-First Scheduling), its type (I/O-bound interactive tasks over CPU-bound batch tasks), or a real-time deadline. The scheduler's job is purely mechanical — always dispatch the extremal-priority ready task — while the meaning of priority is supplied by the system designer. There are two dispatch disciplines. Non-preemptive priority scheduling lets a running process keep the CPU until it voluntarily blocks or terminates, even if a higher-priority process becomes ready in the meantime; the new arrival simply waits in the ready queue. Preemptive priority scheduling immediately suspends the running process and switches to a newly-arrived process if that arrival's priority exceeds the current process's priority; the preempted process returns to the ready queue at its (possibly aged) priority. Preemptive priority scheduling gives much better response time for urgent work but incurs more context-switch overhead and more complex correctness reasoning, since the running process can be interrupted at essentially any instant. Convention matters here: many systems (and this article) use the rule lower numeric value = higher priority, mirroring Unix `nice` values where `-20` is most favored and `19` is least favored. Ties are typically broken by a secondary rule — commonly First-Come First-Served Scheduling order, or round-robin among equal-priority processes — because pure priority comparison alone does not fully order the ready queue when priorities repeat. The central correctness hazard of priority scheduling is starvation (also called indefinite postponement): a process with low priority may never run, because the ready queue is never empty of higher-priority work by the time the scheduler looks. This is not a bug in the implementation — it is the direct, provable consequence of a scheduler that always prefers priority over waiting time. Aging is the standard remedy: the priority of a waiting process is increased as a function of its waiting time, so that no matter how low its initial priority, it eventually surpasses every competitor and gets scheduled.

At its core, priority scheduling replaces the queue-selection rule of a generic scheduling loop with a priority-ordered selection. The surrounding machinery — ready queue management, dispatch, context switch, timers — is the same skeleton used across CPU schedulers.

Data structure. The ready queue is conceptually a priority queue: an implementation might use a binary heap (dispatch in `O(log n)`), or, if the number of distinct priority levels is small and fixed, an array of FIFO queues indexed by priority level (dispatch in `O(1)` amortized, at the cost of `O(k)` to scan `k` levels in the worst case, or `O(1)` with a bitmap of non-empty levels).

Non-preemptive priority scheduling ``` function schedule_nonpreemptive(ready_queue): while system is running: if ready_queue is empty: idle_until_next_arrival() continue

# Select process with best (numerically smallest) priority.

# Ties broken by earliest arrival time (FCFS). p = extract_min(ready_queue, key = (priority, arrival_time)) dispatch(p) # context switch in run_until(p, event = "blocks_or_terminates") if p.terminated: record_completion(p) else:

# p blocked on I/O; it will re-enter ready_queue

# later via an interrupt handler, not here. pass ```

Preemptive priority scheduling ``` function schedule_preemptive(ready_queue): running = null on_event ARRIVAL(p): insert(ready_queue, p) if running is null or p.priority < running.priority: preempt(running) # running (if any) goes back to queue running = dispatch(p) on_event TIMER_TICK or BLOCK or TERMINATE: if running.blocked or running.terminated: if running.terminated: record_completion(running) running = null if running is null and ready_queue is not empty: p = extract_min(ready_queue, key = (priority, arrival_time)) running = dispatch(p) on_event AGING_TICK: # periodic, e.g. every T time units for each p in ready_queue: p.wait_time += T p.priority = max(p.base_priority - floor(p.wait_time / T), MIN_PRIORITY)

# priority number decreases (i.e., importance increases) with wait if running is not null: best = peek_min(ready_queue) if best.priority < running.priority: preempt(running) running = dispatch(best) remove(ready_queue, best) ``` The `AGING_TICK` handler is the mitigation: every fixed interval, every waiting process's effective priority is nudged toward "most important," strictly as a function of accumulated wait time, independent of the arrival of new competitors. Because the aging term grows without bound as `wait_time` grows (until clipped at `MIN_PRIORITY`, the best possible value), no process can be shut out forever — eventually its aged priority beats every freshly-arriving process's base priority.

Time complexity of scheduling decisions. If the ready queue is implemented as a binary min-heap keyed by priority, `insert` and `extract_min` each cost `O(log n)` for `n` ready processes — this is the standard bound for heap operations, since the heap has height `⌈log₂ n⌉` and each operation does at most one root-to-leaf pass of comparisons and swaps. If instead the system uses `k` fixed priority levels, each a FIFO queue, then `insert` is `O(1)` (push onto the appropriate level's queue) and `extract_min` is `O(1)` amortized if a bitmask or pointer tracks the highest non-empty level, or `O(k)` worst case with a naive linear scan over levels. Real operating systems (Linux's older O(1) scheduler, for instance) favor the array-of-queues design precisely to get `O(1)` dispatch when the number of priority levels is bounded (Linux used 140 levels).

Space complexity is `O(n)` for `n` ready processes, regardless of representation — each process needs one queue slot and a constant amount of scheduling metadata (priority, base priority, wait-time counter).

Correctness of the core selection rule is immediate by construction: at every dispatch point the algorithm scans (implicitly, via the priority-queue structure) all ready processes and picks the extremal one, so it trivially satisfies the specification "always run the highest-priority ready process" — this is not something that needs a subtle proof, it is definitional. The interesting correctness question is a liveness property: does every process eventually run?

Claim (starvation without aging). In a preemptive priority scheduler with static priorities and an unbounded, continual arrival stream of processes with priority strictly better than some process `p`, `p` may never be dispatched. Argument. The scheduler's invariant is "the running process is always the best-priority ready process." If at every decision point some process with priority strictly better than `p.priority` is ready, the selection rule never picks `p` — this holds by direct substitution into the dispatch rule, for arbitrarily long (even infinite) time, so `p`'s completion time is unbounded. This shows starvation is not a corner-case implementation flaw; it is a logical consequence of the specification itself when the input distribution is adversarial (or even just realistically bursty, as in a busy interactive system generating many short high-priority tasks).

Claim (bounded wait with aging). Suppose priorities are integers, aging decreases a waiting process's effective priority by at least `δ > 0` per fixed interval `T`, and the best possible priority value is bounded below by `MIN_PRIORITY`. Then every process's dispatch is delayed by at most a computable bound. Argument (invariant + monotonicity). Let `p` have base priority `b` and let the best priority among all other currently-ready or future-arriving processes never exceed some finite floor `b_min` — a floor that exists in any real system since priority values live in a bounded integer range, `[MIN_PRIORITY, MAX_PRIORITY]`. After waiting for time `w`, `p`'s effective priority is at most: ``` effective(p, w) = max(b - floor(w / T) δ, MIN_PRIORITY) ``` This is monotonically non-increasing in `w` (numerically; non-increasing means "improving" under the "smaller = better" convention) and strictly decreases every `T` time units until it hits `MIN_PRIORITY`. Since `MIN_PRIORITY` is by definition at least as good as every other process's priority (the best value in the whole system), there exists a finite `w = T · (b - MIN_PRIORITY) / δ` such that for all `w ≥ w`, `effective(p, w) = MIN_PRIORITY`, which ties for (or beats) every competitor. At that point `p` is selected at the next scheduling decision — because the selection rule always picks a best-or-tied process and ties resolve via FCFS, guaranteeing `p` is chosen no later than one full round of ties ahead of it clears. Hence `p`'s waiting time is bounded above by `w + (\text{one dispatch quantum per tied process ahead of it})`, a finite quantity depending only on system constants, not on the adversarial arrival pattern. This establishes the liveness guarantee that plain priority scheduling lacks. ∎

Tradeoffs, stated honestly.

• Priority scheduling (with correctly assigned priorities) is optimal for minimizing weighted mean completion time — this is the same underlying theorem that makes Shortest-Job-First Scheduling optimal for unweighted mean completion time, generalized by weighting each job's completion time by its priority/importance.
• It is not optimal for fairness or for worst-case wait time; that is the entire reason aging exists as a bolt-on correction rather than being unnecessary.
• Aging trades a small amount of throughput and average-priority adherence (occasionally a "less important" but long-waiting process runs when a fresher, truly more urgent process is ready) for a hard liveness guarantee. This is a genuine tradeoff, not a free lunch.
• Preemptive priority scheduling adds context-switch overhead proportional to the arrival rate of higher-priority processes; in a system dominated by high-priority bursts this overhead can itself hurt throughput.

Consider five processes arriving at a preemptive priority scheduler (lower number = higher priority), with an aging rule that lowers a waiting process's effective priority by 1 for every 5 time units it waits, floored at priority 0.

Trace (preemptive, priority-only, ignoring aging first, to expose the starvation risk):

P1, despite arriving first, waits from `t=1` to `t=19` (18 units) before it even gets to run, because P2, P3, and P4 all carry better base priority. If a sixth process with priority 2 had arrived at `t = 19.5`, P1 would be preempted again right after finally starting — and in an adversarial stream where better-priority work keeps arriving, P1's total wait is unbounded. This is the starvation failure mode made concrete. Now apply the aging rule from the start. At `t = 5` (when P2 finishes), P1 has waited `5 - 1 = 4` units since being preempted at `t=1` — not yet enough to age past level 4 (needs 5 units for -1). By `t = 10`, P1 has waited `10 - 1 = 9` units, so its effective priority is `4 - floor(9/5) = 4 - 1 = 3`, tying it with P3's priority 3; by FCFS tie-break (P1 arrived at 0, P3 at 2), P1 is dispatched at `t = 10` instead of P3, cutting P1's wait from 18 units down to 9. Aging concretely accelerates P1's turnaround at the cost of slightly delaying P3 — the fairness/optimality tradeoff made visible in the trace, not just asserted abstractly.

Priority scheduling, or a close descendant of it, underlies almost every general-purpose and real-time operating system. Windows assigns each thread a priority class combined with a dynamic priority that the scheduler boosts for foreground and I/O-bound threads, aging effectively baked into the dynamic adjustment. Linux's traditional scheduler used static and dynamic priority fields (`nice` values and real-time priorities) before evolving toward the Completely Fair Scheduler, which reframes fairness using virtual runtime rather than raw priority, but real-time Linux tasks (`SCHED_FIFO`, `SCHED_RR`) still use strict priority scheduling directly. Database engines raise the priority of transactions holding contended locks to shrink the window during which other transactions must wait. Real-time embedded systems — automotive control units, avionics, industrial controllers — rely on strict, analyzable priority scheduling (often Rate Monotonic Scheduling, which assigns priority inversely to task period) precisely because priority order gives the deadline guarantees that Real-Time Scheduling formalizes. The starvation-and-aging tension explored here is also the direct motivation for Multilevel Feedback Queue Scheduling, which uses observed behavior (how much CPU a process actually consumes) to move processes between priority levels dynamically, unifying the responsiveness of priority scheduling with an automatic, built-in aging-like mechanism.

Ask the tutor: How does aging interact with preemption thresholds when several processes reach the same aged priority simultaneously?