2.4Priority scheduling, starvation and aging
The idea
Priority scheduling runs the highest-priority ready process. It can starve low-priority processes, which aging cures.
Think of it like this: A hospital emergency room: the most serious patient is seen first, so someone with a mild problem may wait all night unless the longer they wait the more urgent they are treated.
Why it exists
Some work really is more important (interrupts, interactive jobs). Priorities encode that, but need a safety valve against starvation.
How it works
- Pick the ready process with the best priority (check whether a low number means high priority).
- Preemptive: a higher-priority arrival takes the CPU now.
- Starvation: a steady stream of better processes means a low one never runs.
- Aging: add to the priority of a process each time unit it waits.
Worked example: Priority inversion
Low holds a lock, High waits for it, Medium keeps preempting Low. High is effectively blocked by Medium. Priority inheritance lets Low run at High's priority until it releases the lock.
Now play with it
- →Run the preemptive priority algorithm on the preset and find where preemption happens.
- →Compare with the non-preemptive version.
| Process | Arrival | Burst | Priority | Completion | Turnaround | Waiting | Response |
|---|---|---|---|---|---|---|---|
| P1 | 0 | 8 | 3 | 17 | 17 | 9 | 0 |
| P2 | 1 | 4 | 1 | 5 | 4 | 0 | 0 |
| P3 | 2 | 9 | 4 | 26 | 24 | 15 | 15 |
| P4 | 3 | 5 | 2 | 10 | 7 | 2 | 2 |
Turnaround = completion − arrival. Waiting = turnaround − burst. Response = first run − arrival. Ties go to the earlier arrival, then the earlier row. In round robin, a process that arrives while another runs joins the queue before the preempted one.
| Problem | What happens | Cure |
|---|---|---|
| Starvation | a low-priority process never gets the CPU | aging: raise the priority as the wait grows |
| Priority inversion | high waits for a lock held by low, while medium keeps preempting low | priority inheritance: low temporarily runs at high priority |
| Preemption cost | more context switches | choose non-preemptive when the load is predictable |
Check yourself
Aging is used to prevent
Exam notes (the dense version)
The CPU goes to the highest-priority ready process (check whether a smaller number means higher priority). Can be preemptive or not. Starvation: low-priority processes may never run. Aging raises the priority of a waiting process over time. Priority inversion: a high-priority process waits for a lock held by a low-priority one that a medium-priority process keeps preempting; fixed by priority inheritance.
Previous year questions: CPU Scheduling (13)
PYQs are grouped by topic, so this is the full set for CPU Scheduling; try the ones that match this subtopic. Open all 13 on the topic page.