Priority Scheduling and Aging — Preventing Starvation
- Priority scheduling: always run the highest-priority ready process.
- Lower priority number conventionally means higher priority (like OS nice values).
- Starvation: low-priority processes may never execute — solved by aging.
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
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']}")
P2: priority=1, WT=9, TAT=10
P3: priority=4, WT=17, TAT=19
P4: priority=5, WT=19, TAT=20
P5: priority=2, WT=7, TAT=12
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.
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)
t= 0: priority=10
t= 5: priority=9
t= 10: priority=8
t= 15: priority=7
t= 20: priority=6
t= 25: priority=5
t= 30: priority=4
t= 35: priority=3
t= 40: priority=2
t= 45: priority=1
t= 50: 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.
Multilevel Feedback Queue (MLFQ) allows processes to move between queues based on behaviour — CPU-bound processes move to lower priority queues, I/O-bound processes stay at high priority. This is what most real OS schedulers implement.
🎯 Key Takeaways
- Priority scheduling: always run the highest-priority ready process.
- Lower priority number conventionally means higher priority (like OS nice values).
- Starvation: low-priority processes may never execute — solved by aging.
- Aging: increase priority by 1 every T wait units — guarantees eventual execution.
- MLFQ (Multilevel Feedback Queue) combines priority with dynamic adjustment based on behaviour.
Interview Questions on This Topic
- QWhat is starvation in priority scheduling and how does aging solve it?
- QCompare preemptive vs non-preemptive priority scheduling.
- QWhat is Multilevel Feedback Queue scheduling?
- QIn Linux, what do negative nice values indicate?
Frequently Asked Questions
What is the difference between priority scheduling and SJF?
SJF is actually a special case of priority scheduling where the priority is the inverse of burst time (shorter burst = higher priority). The starvation problem also applies to SJF for the same reason.
Developer and founder of TheCodeForge. I built this site because I was tired of tutorials that explain what to type without explaining why it works. Every article here is written to make concepts actually click.