3.4 Priority Scheduling & Starvation (Aging Technique)

Back to Operating Systems Notes

📚Module 03: CPU Scheduling AlgorithmsTopic 3.4⏱️13 min read

🎯High-Yield For:Computer Science Foundations • Systems Engineering • Technical Interviews

💡 Core Intuition

🍳 The Everyday Analogy: Airport Boarding & VIP Express Lanes

Imagine an airport boarding gate where a single gate agent (the CPU) validates boarding passes for hundreds of passengers waiting to board an aircraft:

Architecture Flow

The Airport Boarding Priority Pipeline

Mapping boarding class hierarchies to OS Priority CPU scheduling

💡 Hover or click any card for deep-dive operational details

🎫Admission Stage

Passenger Queue

Ready Queue Admissions

Passengers arrive at the gate holding different ticket classes.

→

Priority Scan

🚶Non-Preemptive

Boarding Walkway

Non-Preemptive Gate

Once a passenger steps onto the jet bridge, they board without interruption.

→

Preemption Check

⭐Preemptive / Aging

VIP Jump & Aging

Preemption & Aging

VIP passengers jump the line; delayed passengers receive priority upgrades.

• Priority Assignment: Critical passengers (crew members, medical responders, VIPs) take precedence over general travelers.
• The Starvation Dilemma: If high-priority VIP passengers arrive continuously, economy passengers at the back of the line might miss the flight entirely. The solution is Aging—gradually boosting an economy passenger's priority the longer they stand waiting.

---

💻 Bridging to Computer Science

In operating systems, Priority Scheduling associates a priority rank with each process.

• At any scheduling instant, the Short-Term Scheduler allocates the CPU to the available process with the highest priority.
• If two processes share identical priority values, FCFS order is used to break the tie.
• Systems implement Priority Scheduling in both Non-Preemptive and Preemptive modes.

Priority Numbering Conventions

In academic literature and operating system designs, two opposite numbering conventions exist:

1. Lower Number = Higher Priority: Standard UNIX/Linux nice values, where $0$ is high priority and $20$ is low priority.
2. Higher Number = Higher Priority: Common in real-time kernels and standard university problem sets, where a higher integer (e.g., $8$) denotes superior priority over a smaller integer (e.g., $4$). Always verify the declared convention before solving. In this chapter, we adopt the standard convention: Higher Integer Value = Higher Priority.

---

📑Table of Contents

• 💡 Core Intuition
• 📚 Core Deep-Dive & Concepts
  • 1. Priority Scheduling Architectural Principles
  • 2. Comprehensive Problem: Non-Preemptive Priority Scheduling
  • 3. Preemptive Priority Scheduling Step-by-Step Derivation
  • 4. Advantages, Disadvantages & Starvation
  • 5. Starvation Mitigation: The Aging Technique
• 📐 Architecture / Visual Blueprint
  • Priority Inversion Architecture & Priority Inheritance Solution
• 🏭 In The Real World: Production Case Study
  • The Mars Pathfinder Priority Inversion Glitch (1997)
• 🎯 Exam & Interview Pitfall Check

---

📚 Core Deep-Dive & Concepts

1. Priority Scheduling Architectural Principles

Definition: A priority is associated with each process. At any instance of time out of all available processes, the CPU is allocated to the process that possesses the highest priority. Tie is broken using FCFS order. It supports both non-preemptive and preemptive versions.

Non-Preemptive vs. Preemptive Priority Scheduling

Contrasting cooperative completion against dynamic preemption

Non-Preemptive

Non-Preemptive Priority

🤝

Dominant Architecture / DomainCooperative Priority Allocation

• •Scheduling Trigger: Evaluated only when running task completes or blocks for I/O.
• •Zero Preemption: A running process is never evicted, even if a higher-priority task arrives.
• •Low Context Switching: Eliminates cache invalidation and register thrashing.
• •Bounded Responsiveness: Urgent system alerts must wait until current burst finishes.

"Once allocated, the process keeps the CPU until voluntary release."

Preemptive

Preemptive Priority

⚡

Dominant Architecture / DomainImmediate Preemptive Scheduling

• •Scheduling Trigger: Evaluated immediately whenever a new process enters the Ready Queue.
• •Dynamic Context Switch: Evicts the running process if newcomer has higher priority.
• •Optimal Responsiveness: Mission-critical tasks execute with near-zero latency.
• •Severe Starvation Risk: Low-priority jobs can be frozen indefinitely under heavy loads.

"If a newcomer has higher priority than the running process, the CPU is immediately reassigned."

---

2. Comprehensive Problem: Non-Preemptive Priority Scheduling

Consider six processes with their arrival times, burst times, and priorities (where Higher Number denotes Higher Priority, with $8$ being Highest):

Process ID	Arrival Time ($AT$)	Burst Time ($BT$)	Priority
$P_0$	$1\text{ ms}$	$4\text{ ms}$	$4$
$P_1$	$2\text{ ms}$	$2\text{ ms}$	$5$
$P_2$	$2\text{ ms}$	$3\text{ ms}$	$7$
$P_3$	$3\text{ ms}$	$5\text{ ms}$	$8\text{ (Highest)}$
$P_4$	$3\text{ ms}$	$1\text{ ms}$	$5$
$P_5$	$4\text{ ms}$	$2\text{ ms}$	$6$

Step-by-Step Execution Sequence:

• $[0, 1]$: CPU is idle for $1\text{ ms}$.
• At $t = 1$: Only $P_0$ is present ($AT = 1, \text{Priority} = 4$). Since scheduling is non-preemptive, $P_0$ runs uninterrupted to completion ($t = 1 \to 5$).
• At $t = 5$: $P_0$ completes ($CT = 5$). All other processes ($P_1, P_2, P_3, P_4, P_5$) are now in the Ready Queue:
  • $P_3: \text{Priority} = 8$
  • $P_2: \text{Priority} = 7$
  • $P_5: \text{Priority} = 6$
  • $P_1: \text{Priority} = 5$
  • $P_4: \text{Priority} = 5$
  • The scheduler chooses the highest priority: $P_3$ (Priority 8). $P_3$ executes for $5\text{ ms}$ ($t = 5 \to 10$).
• At $t = 10$: $P_3$ completes ($CT = 10$). Highest available priority is $P_2$ (Priority 7). $P_2$ executes for $3\text{ ms}$ ($t = 10 \to 13$).
• At $t = 13$: $P_2$ completes ($CT = 13$). Highest available priority is $P_5$ (Priority 6). $P_5$ executes for $2\text{ ms}$ ($t = 13 \to 15$).
• At $t = 15$: $P_5$ completes ($CT = 15$). Remaining processes are $P_1$ (Priority 5) and $P_4$ (Priority 5).
  • Tie-Breaking via FCFS: $P_1$ arrived at $t = 2$; $P_4$ arrived at $t = 3$. Therefore, $P_1$ is scheduled first.
  • $P_1$ executes for $2\text{ ms}$ ($t = 15 \to 17$).
• At $t = 17$: $P_1$ completes ($CT = 17$). Only $P_4$ remains. $P_4$ executes for $1\text{ ms}$ ($t = 17 \to 18$).
• At $t = 18$: All processes complete execution.

⏱️

Non-Preemptive Priority Execution Gantt Chart

Timeline showing non-preemptive execution ordered strictly by priority (8 -> 7 -> 6 -> 5 -> 5)

IDLEIdle: 1ms

P0Pri: 4

P3Pri: 8 (H)

P2Pri: 7

P5Pri: 6

P1Pri: 5 (Tie FCFS)

P4Pri: 5

01

5

10

13

15

17

18

Avg Turnaround10.5 ms

Avg Waiting Time7.67 ms

Throughput0.333 jobs/ms

CPU Utilization94.44%

Tabulation of Non-Preemptive Priority Metrics:

Process	$AT$	$BT$	Priority	Completion ($CT$)	Turnaround ($TAT = CT - AT$)	Waiting ($WT = TAT - BT$)	Response ($RT$)
$P_0$	$1$	$4$	$4$	$5$	$5 - 1 = \mathbf{4}$	$4 - 4 = \mathbf{0}$	$1 - 1 = \mathbf{0}$
$P_1$	$2$	$2$	$5$	$17$	$17 - 2 = \mathbf{15}$	$15 - 2 = \mathbf{13}$	$15 - 2 = \mathbf{13}$
$P_2$	$2$	$3$	$7$	$13$	$13 - 2 = \mathbf{11}$	$11 - 3 = \mathbf{8}$	$10 - 2 = \mathbf{8}$
$P_3$	$3$	$5$	$8$	$10$	$10 - 3 = \mathbf{7}$	$7 - 5 = \mathbf{2}$	$5 - 3 = \mathbf{2}$
$P_4$	$3$	$1$	$5$	$18$	$18 - 3 = \mathbf{15}$	$15 - 1 = \mathbf{14}$	$17 - 3 = \mathbf{14}$
$P_5$	$4$	$2$	$6$	$15$	$15 - 4 = \mathbf{11}$	$11 - 2 = \mathbf{9}$	$13 - 4 = \mathbf{9}$

$\overline{TAT} = \frac{4 + 15 + 11 + 7 + 15 + 11}{6} = \frac{63}{6} = \mathbf{10.5\text{ ms}}$ $\overline{WT} = \frac{0 + 13 + 8 + 2 + 14 + 9}{6} = \frac{46}{6} \approx \mathbf{7.67\text{ ms}}$

---

3. Preemptive Priority Scheduling Step-by-Step Derivation

Definition: In Preemptive Priority scheduling, the process with the highest priority is allocated the CPU. If a new process enters the system with a priority strictly higher than the priority of the currently running process, a context switch occurs and the CPU is immediately reassigned to the higher-priority newcomer.

Applying preemption to the exact same six processes:

Chronological Preemption Execution Walkthrough:

• $[0, 1]$: CPU idle.
• At $t = 1$: $P_0$ arrives (Priority 4). Begins executing.
• At $t = 2$: $P_1$ (Priority 5) and $P_2$ (Priority 7) arrive.
  • Running process $P_0$ has Priority 4.
  • Both newcomers have higher priority, and the highest is $P_2$ (Priority 7).
  • $P_2$ preempts $P_0$! $P_0$ has run for $1\text{ ms}$ (remaining: $4 - 1 = 3\text{ ms}$).
  • $P_2$ begins executing ($t = 2 \to 3$).
• At $t = 3$: $P_3$ (Priority 8) and $P_4$ (Priority 5) arrive.
  • Running process $P_2$ has Priority 7.
  • Newcomer $P_3$ has Priority 8, which is strictly higher than 7!
  • $P_3$ preempts $P_2$! $P_2$ has run for $1\text{ ms}$ (remaining: $3 - 1 = 2\text{ ms}$).
  • $P_3$ begins executing ($t = 3 \to 8$).
  • (At $t = 4$, $P_5$ arrives with Priority 6. Since $6 < 8$, $P_3$ continues uninterrupted to completion).
• At $t = 8$: $P_3$ completes ($CT = 8$).
  • Ready Queue candidates: $P_2$ (Priority 7, rem $2$), $P_5$ (Priority 6, rem $2$), $P_1$ (Priority 5, rem $2$), $P_4$ (Priority 5, rem $1$), $P_0$ (Priority 4, rem $3$).
  • Highest priority is $P_2$ (Priority 7). $P_2$ resumes and finishes its remaining $2\text{ ms}$ ($t = 8 \to 10$, $CT = 10$).
• At $t = 10$: $P_2$ completes. Highest available priority is $P_5$ (Priority 6). $P_5$ executes for $2\text{ ms}$ ($t = 10 \to 12$, $CT = 12$).
• At $t = 12$: $P_5$ completes. Candidates are $P_1$ (Priority 5) and $P_4$ (Priority 5).
  • Tie broken by FCFS arrival: $P_1 (AT=2)$ runs before $P_4 (AT=3)$.
  • $P_1$ executes for $2\text{ ms}$ ($t = 12 \to 14$, $CT = 14$).
• At $t = 14$: $P_1$ completes. $P_4$ executes for $1\text{ ms}$ ($t = 14 \to 15$, $CT = 15$).
• At $t = 15$: Only $P_0$ remains (Priority 4). $P_0$ resumes and finishes its remaining $3\text{ ms}$ ($t = 15 \to 18$, $CT = 18$).
• At $t = 18$: All processes complete.

⏱️

Preemptive Priority Execution Gantt Chart

Tracing dynamic preemption points at t = 2 (P2 preempts P0) and t = 3 (P3 preempts P2)

IDLEIdle: 1ms

P0P0 (run 1ms)

P2P2 (run 1ms)

P3P3 finishes

P2P2 finishes

P5P5 finishes

P1P1 finishes

P4P4 finishes

P0P0 finishes

01

2

3

8

10

12

14

15

18

Avg Turnaround10.33 ms

Avg Waiting Time7.5 ms

P3 Waiting Time0.0 ms

CPU Utilization94.44%

Tabulation of Preemptive Priority Metrics:

Process	$AT$	$BT$	Priority	Completion ($CT$)	Turnaround ($TAT = CT - AT$)	Waiting ($WT = TAT - BT$)	Response ($RT$)
$P_0$	$1$	$4$	$4$	$18$	$18 - 1 = \mathbf{17}$	$17 - 4 = \mathbf{13}$	$1 - 1 = \mathbf{0}$
$P_1$	$2$	$2$	$5$	$14$	$14 - 2 = \mathbf{12}$	$12 - 2 = \mathbf{10}$	$12 - 2 = \mathbf{10}$
$P_2$	$2$	$3$	$7$	$10$	$10 - 2 = \mathbf{8}$	$8 - 3 = \mathbf{5}$	$2 - 2 = \mathbf{0}$
$P_3$	$3$	$5$	$8$	$8$	$8 - 3 = \mathbf{5}$	$5 - 5 = \mathbf{0}$	$3 - 3 = \mathbf{0}$
$P_4$	$3$	$1$	$5$	$15$	$15 - 3 = \mathbf{12}$	$12 - 1 = \mathbf{11}$	$14 - 3 = \mathbf{11}$
$P_5$	$4$	$2$	$6$	$12$	$12 - 4 = \mathbf{8}$	$8 - 2 = \mathbf{6}$	$10 - 4 = \mathbf{6}$

$\overline{TAT} = \frac{17 + 12 + 8 + 5 + 12 + 8}{6} = \frac{62}{6} \approx \mathbf{10.33\text{ ms}}$ $\overline{WT} = \frac{13 + 10 + 5 + 0 + 11 + 6}{6} = \frac{45}{6} = \mathbf{7.5\text{ ms}}$

---

4. Advantages, Disadvantages & Starvation

Advantages of Priority Scheduling:

1. Preferential Facility for System Processes: Provides dedicated priority execution to critical kernel daemons, device interrupt services, and audio/graphics drivers.
2. Allows Important Service Execution: Ensures urgent batch or security workloads preempt standard user applications whenever necessary.

Disadvantages of Priority Scheduling:

1. Indefinite Blocking (Starvation): Processes with lower priorities may sit in the Ready Queue forever if higher-priority processes arrive continuously.
2. Unpredictable Latency: No mathematical guarantee on turnaround time or waiting time for lower-tier processes.

---

5. Starvation Mitigation: The Aging Technique

Definition: Aging is a technique of gradually increasing the priority of processes that wait in the system for a long time.

Architecture Flow

The Starvation Elimination Aging Pipeline

How periodic timer-driven priority boosts guarantee progress for low-priority processes

💡 Hover or click any card for deep-dive operational details

⏳Arrival

Low Priority Process

Priority = 1 (Awaiting CPU)

Process enters Ready Queue with lowest initial priority.

→

10 Minutes Elapse

📈Aging Step 1

First Priority Boost

Priority Incremented (+1)

Kernel timer handler detects threshold wait and increments priority.

→

Continued Waiting

⭐Final Promotion

Highest Priority Run

Priority = Highest Tier

Eventually matches highest priority and is guaranteed CPU dispatch.

Aging Mechanics:

• For example, the kernel can increase a waiting process's priority by $1$ every $10\text{ minutes}$ (or every few hundred timer interrupts).
• A process that entered with a minimal priority of $1$ will, after $70\text{ minutes}$ of waiting, reach priority $8$, competing on equal terms with the highest-priority tasks in the system.
• Result: Starvation is mathematically eliminated.

---

📐 Architecture / Visual Blueprint

Priority Inversion Architecture & Priority Inheritance Solution

A critical concurrency flaw in real-time priority systems is Priority Inversion, where a low-priority task holds a lock needed by a high-priority task, while medium-priority tasks prevent the low-priority task from finishing:

The Priority Inversion Problem & Priority Inheritance Fix

Tracing how an un-inverted priority schedule protects high-priority real-time deadlines

High-Priority Task (T_H)

Medium-Priority Task (T_M)

Low-Priority Task (T_L)

Shared Mutex Lock

1

Low-Priority Task (T_L)→Shared Mutex Lock

T_L Acquires Mutex Lock

2

High-Priority Task (T_H)→Shared Mutex Lock

T_H Blocks on Mutex

3

Medium-Priority Task (T_M)→Low-Priority Task (T_L)

Priority Inversion Occurs!

4

High-Priority Task (T_H)→Low-Priority Task (T_L)

Priority Inheritance Protocol Applied

---

🏭 In The Real World: Production Case Study

The Mars Pathfinder Priority Inversion Glitch (1997)

One of the most famous real-world systems software bugs occurred during NASA's Mars Pathfinder mission:

Mars Pathfinder VxWorks Real-Time Thread Hierarchy

The three concurrent threads that triggered the historic 1997 Martian system reset

High Priority Tier

Information Bus Thread (bc_dist)

🚨

Critical spacecraft attitude control thread starved while awaiting the shared bus mutex.

Critical flight telemetry taskBlocked awaiting mutex held by low-priority taskStarvation tripped watchdog timer to reboot spacecraft

↓Blocked on Mutex Held by Low Task

Medium Priority Tier

Communications Thread (ASI/MET)

📡

Long-running radio transmitter tasks that preempted low-priority tasks freely.

No mutex dependencyRan continuously, starving the low-priority threadIndirectly caused high-priority thread starvation

↓Preempts Low Task Indefinitely

Low Priority Tier

Meteorological Sensor Task

🌡️

Background science measurement thread that held the contended shared memory mutex.

Acquired shared information bus lockPreempted by medium tasks before releasing lockResolved permanently via Priority Inheritance Protocol

Incident Breakdown:

1. A low-priority meteorological sensor task acquired an information bus mutex.
2. A high-priority attitude control thread requested the mutex and was blocked.
3. Multiple medium-priority communications tasks arrived and ran uninterrupted, preventing the low-priority task from finishing and releasing the lock.
4. An automated watchdog timer detected that the high-priority attitude task was stalled, assumed total system failure, and triggered a full spacecraft computer reset.
5. The Fix: Engineers uploaded a patch enabling the Priority Inheritance Protocol on the mutex, ensuring any task holding a contended lock temporarily inherits the priority of the highest blocked thread.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: Define Priority Scheduling. Explain the fundamental difference in dispatcher behavior between its non-preemptive and preemptive forms. Answer:

1. Definition: A scheduling scheme where each process is assigned a priority integer, and the Short-Term Scheduler dispatches the available process with the highest priority. FCFS resolves ties.
2. Dispatcher Differences:
   • In Non-Preemptive Priority, when a high-priority process arrives, the dispatcher takes no action; the currently running process retains the CPU until it voluntarily yields or finishes.
   • In Preemptive Priority, the arrival of a higher-priority process triggers an immediate interrupt, saving the running process's registers to its PCB and context-switching to the newcomer.

Question 2: What is Starvation, and how does the Aging technique resolve it? Answer:

1. Starvation: The permanent or indefinite denial of CPU resources to low-priority processes caused by a steady stream of higher-priority arrivals.
2. Aging: The gradual increment of an awaiting process's priority over time (e.g., $+1$ priority every $10\text{ minutes}$). Eventually, every starving process reaches the highest priority tier and executes.

Common Interview Traps

• The Number Direction Trap: Always verify whether $0$ represents the highest or lowest priority before calculating $CT, TAT, WT$. Assuming $0$ is highest when a problem defines higher integers as higher priority inverts the entire Gantt chart.
• Assuming Preemption Happens on Equal Priority: If process $A$ with priority 5 is executing and process $B$ arrives with priority 5, no preemption occurs. Context switching introduces overhead; the running process continues under the FCFS tie-breaking rule.
• Confusing Aging with Dynamic Priority: While aging is a form of dynamic priority adjustment, general dynamic priority may fluctuate based on I/O burst ratios or CPU consumption. Aging strictly moves in the direction that increases dispatch urgency to eliminate starvation.

---

🗺️View Complete Operating Systems Roadmap & Syllabus

← Previous Topic3.3 Shortest Job First (SJF) & SRTFNext Topic →3.5 Round Robin Scheduling & Time Quantum