Priority Scheduling

Introduction

In real life, not all tasks are equally important. When a hospital emergency room receives patients, they do not treat them in arrival order — a heart attack patient gets immediate attention over someone with a sprained ankle, regardless of who arrived first. This is priority scheduling: assigning importance levels to tasks and serving the most important ones first.

Priority scheduling is a CPU scheduling algorithm where each process is assigned a priority number. The CPU is allocated to the process with the highest priority. It can be either preemptive (a higher-priority process interrupts the current one) or non-preemptive (the current process finishes its burst before the higher-priority process runs).

How Priority is Assigned

Priorities can be determined by various factors:

Internal factors (set by OS):

• Memory requirements (less memory = higher priority)
• CPU burst time (shorter burst = higher priority, making it similar to SJF)
• Number of open files
• Ratio of I/O burst to CPU burst

External factors (set by administrator/user):

• Process importance to the organization
• Paid priority (cloud computing tiers)
• Political factors (department importance)
• User preference

Note: In some systems, a lower number means higher priority (Unix/Linux uses 0 = highest), while in others, a higher number means higher priority. Always check the convention being used.

Non-Preemptive Priority Scheduling Example

Gantt Chart (Non-Preemptive)

Since it is non-preemptive, P1 runs to completion first (it started at time 0). Then the scheduler picks from available processes by priority.

After P1 finishes at time 10: Available = P2(pri=1), P3(pri=4), P4(pri=5), P5(pri=2). P2 has highest priority (1), runs next. Then P5 (pri=2), then P3 (pri=4), then P4 (pri=5).

Calculations

Average Waiting Time = (0 + 9 + 14 + 15 + 7) / 5 = 9 ms

Preemptive Priority Scheduling Example

With preemption, a newly arriving higher-priority process immediately takes over the CPU.

Using the same processes:

Gantt Chart (Preemptive)

The Starvation Problem

The biggest issue with priority scheduling is starvation (also called indefinite blocking). A low-priority process may never execute if higher-priority processes keep arriving. Imagine a low-priority print job in a system where interactive processes constantly need the CPU — the print job might wait hours or even days.

A real historical example: when they shut down the IBM 7094 at MIT in 1973, they found a low-priority process that had been submitted in 1967 and never got to run — it starved for 6 years!

Solution: Aging

Aging is the standard solution to starvation. The idea is simple: gradually increase the priority of processes that have been waiting a long time. For example, every 15 minutes of waiting, boost the process's priority by 1 level. Eventually, even the lowest-priority process will have its priority raised high enough to execute.

Priority Inversion Problem

Priority inversion occurs when a high-priority process is indirectly blocked by a low-priority process. This happens when they share a resource:

1. Low-priority process L acquires a lock on resource R
2. High-priority process H arrives and needs resource R
3. H is blocked waiting for L to release R
4. Medium-priority process M arrives and preempts L (since M has higher priority than L)
5. Now H is effectively blocked by M, even though H has higher priority than M

This exact bug caused the Mars Pathfinder mission computer to repeatedly reset in 1997. The solution is priority inheritance: temporarily boost L's priority to H's level while L holds the resource H needs, preventing M from preempting L.

Implementation in C

Advantages and Disadvantages

Advantages

• Handles urgency — Critical processes get immediate attention
• Flexible — Priorities can be assigned based on any criteria
• Good for real-time systems — Time-critical tasks get guaranteed service

Disadvantages

• Starvation — Low-priority processes may never execute (solved by aging)
• Priority inversion — Can cause unpredictable blocking (solved by priority inheritance)
• Difficulty in assigning priorities — Subjective and may lead to gaming the system

Real-World Analogy

Priority scheduling is like an airport with different boarding groups. First-class passengers board first (highest priority), then business class, then economy. If the plane is nearly full and more first-class passengers keep arriving, economy passengers might never board. Aging is like the airline rule that bumped passengers get priority on the next flight — the longer you wait, the higher your priority becomes.

Key Takeaways

• Priority scheduling assigns importance levels and serves highest-priority processes first
• It can be preemptive (interrupt current process) or non-preemptive (wait for current to finish)
• Starvation is the main problem — solved by aging (gradually increasing waiting processes' priority)
• Priority inversion can cause high-priority processes to be blocked by low-priority ones
• Priority inheritance solves inversion by temporarily boosting the blocking process's priority
• Most real OS combine priority scheduling with other algorithms (e.g., Round Robin within each priority level)