Priority Scheduling
Run the highest-priority ready thread. Starvation and aging come with it.
Level: intermediate
What is it?
Priority scheduling selects the ready task with the best assigned priority. A system may use fixed or dynamic priorities and can be preemptive or non-preemptive. Priority direction is convention-specific: in some systems a lower numeric value means higher priority.
Why does it matter?
The policy is useful when some work is more urgent, such as real-time events or latency-sensitive services. It can also starve low-priority work if high-priority tasks continue arriving.
Mental model
Priority is a fast-pass rule in a queue. It gives important tasks short waits but needs a fairness policy so less urgent tasks do not wait forever.
How it works
- Priority may be based on importance, deadlines, observed behavior, or resource needs.
- Preemptive priority scheduling can interrupt a running lower-priority task.
- Starvation happens when lower-priority work is repeatedly postponed.
- Aging gradually increases waiting tasks' priority to restore progress.
- Priority inversion occurs when a high-priority task waits for a resource held by a lower-priority task; priority inheritance can mitigate it.
Steps
- A low-priority task starts running.
- A higher-priority task becomes ready and preempts it in a preemptive system.
- The higher-priority task finishes or blocks; the scheduler reevaluates the ready queue.
- If this repeats indefinitely, the low-priority task may starve unless aging or another rule intervenes.
Real-world usage
- Scheduling control-plane or real-time workloads.
- Analyzing starvation and priority inversion in concurrent applications.
- Comparing responsiveness with fairness and throughput.
Common mistakes
- Assuming numeric priority values have the same direction in every system.
- Treating priority assignment as a guarantee of deadline completion.
- Ignoring priority inversion when locks connect tasks with different priorities.
Interview questions
What is starvation in priority scheduling?
A ready task waits indefinitely because higher-priority work keeps being selected.
How does aging help?
It increases the effective priority of a task as its wait grows, so long-waiting tasks can eventually compete for the CPU.
What is priority inversion?
A high-priority task is delayed by a lower-priority task holding a needed resource, potentially while medium-priority work keeps the holder from running.