Free lesson · Operating Systems

Priority Scheduling

Easy10 min readoperating-systemsosconcurrency

Not All Processes Are Equally Important

In FCFS and Round Robin, every process is treated the same - they all wait in the same queue and get the same time quantum. But in real systems, some processes are more important than others. The process handling a user's keystroke should get CPU time before the process running a nightly backup. The process serving an HTTP request with a 100 ms SLA should run before the process generating weekly reports.

Priority scheduling assigns each process a priority number. The scheduler always picks the process with the highest priority from the ready queue. Higher-priority processes run before lower-priority ones, regardless of arrival order or burst length.

This seems like the obvious approach - of course important things should go first. But priority scheduling introduces a problem that is worse than the convoy effect, worse than suboptimal average waiting time, and one of the most important concepts in OS interviews: starvation.

How Priority Scheduling Works

Each process is assigned a priority when it is created. The priority can be a number (lower numbers mean higher priority in Unix, higher numbers mean higher priority in Windows - the convention varies, so always clarify in an interview). The scheduler maintains the ready queue sorted by priority and always dispatches the highest-priority process.

Priority scheduling can be either preemptive or non-preemptive:

Non-preemptive priority scheduling. Once a process starts running, it keeps the CPU until it finishes or blocks, even if a higher-priority process arrives. The higher-priority process waits until the current process yields.

Preemptive priority scheduling. If a higher-priority process enters the ready queue while a lower-priority process is running, the scheduler immediately preempts the running process and switches to the higher-priority one. This ensures that the highest-priority ready process is always running.

Most real operating systems use preemptive priority scheduling. The rationale is the same as for preemptive scheduling in general: if a high-priority process needs the CPU, it should not wait for a low-priority process to finish.

graph TD
    subgraph QUEUE["Ready Queue (Priority Ordered)"]
        PH["P_high<br/>Priority: 1<br/>(highest)"]
        PM["P_medium<br/>Priority: 5"]
        PL["P_low<br/>Priority: 10<br/>(lowest)"]
    end
    
    PH -->|"always runs first"| CPU["CPU"]
    
    subgraph RESULT["What Happens"]
        R1["P_high runs immediately"]
        R2["P_medium waits for P_high"]
        R3["P_low waits for both"]
    end

This diagram shows priority scheduling with three processes. P_high has the highest priority of 1 and runs first. P_medium has priority 5 and must wait for P_high to finish or block. P_low has priority 10 and must wait for both higher-priority processes. The scheduler always picks the highest-priority process from the ready queue.

A Worked Example

Four processes arrive at time 0 with different priorities and burst times:

Under non-preemptive priority scheduling (lower number = higher priority), the schedule is:

P2 runs first (priority 1, burst 1 ms) → finishes at time 1. P4 runs next (priority 2, burst 5 ms) → finishes at time 6. P1 runs next (priority 3, burst 10 ms) → finishes at time 16. P3 runs last (priority 4, burst 2 ms) → finishes at time 18.

Notice that P3, despite having a burst of only 2 ms, waits 16 ms because it has the lowest priority. In SJF, P3 would have run second (after P2) because it has the second-shortest burst. In priority scheduling, burst length does not matter - only priority does.

The Starvation Problem

Starvation is the defining problem of priority scheduling. A starved process is one that is ready to run but never gets CPU time because higher-priority processes keep arriving and being scheduled first.

Consider a web server with two priority levels: priority 1 for user-facing HTTP requests and priority 2 for background tasks (log rotation, cache cleanup, metric collection). Under preemptive priority scheduling, HTTP requests always preempt background tasks. If HTTP requests arrive continuously (as they do on a busy web server), the background tasks never get CPU time. The log rotation never runs, the cache grows unbounded, and the metric collection stops reporting - all because they are starved of CPU time by the continuous stream of higher-priority work.

Starvation is different from the convoy effect. In the convoy effect (FCFS), a process eventually runs - it just waits a long time behind a slow process. In starvation, a process may never run. If higher-priority processes keep arriving forever, the starved process waits forever. It is not delayed; it is permanently excluded.

This is not a theoretical concern. The Mars Pathfinder rover experienced a real starvation-related bug in 1997. A low-priority data-collection task held a shared mutex that a high-priority bus-management task needed. A medium-priority communication task ran frequently, preventing the low-priority task from releasing the mutex. The high-priority task starved because it was blocked on the mutex, and the low-priority task that held the mutex was starved by the medium-priority task. This is called priority inversion - a form of starvation where a high-priority task effectively runs at the priority of a lower-priority task because of a shared resource.

Priority Inversion in Detail

Priority inversion deserves a deeper explanation because it comes up in interviews and it illustrates a subtle flaw in priority scheduling that is not obvious from the algorithm's definition.

The scenario requires three ingredients: a high-priority task (H), a medium-priority task (M), and a low-priority task (L), plus a shared resource (like a mutex) that both H and L need.

The sequence goes like this. L acquires the mutex and starts its critical section. H arrives and needs the mutex, but L holds it. H blocks, waiting for L to release the mutex. Now M arrives. M has higher priority than L (but lower than H). Since H is blocked on the mutex (not in the ready queue), and M has higher priority than L, the scheduler runs M. M runs for as long as it needs. During this time, L is preempted - it cannot finish its critical section and release the mutex. H is still blocked on the mutex. The result: H (the highest priority) is effectively waiting for M (a lower priority) to finish, even though H and M have no direct dependency. H's effective priority has been inverted to below M's.

This exact scenario caused the Mars Pathfinder reset loop. The system's watchdog timer kept resetting the computer because the high-priority bus-management task could not run. NASA engineers diagnosed the problem remotely and uploaded a fix using priority inheritance.

Priority Inheritance: The Fix

Priority inheritance solves priority inversion by temporarily elevating the priority of the process holding the contested resource. When H blocks on a mutex held by L, the OS raises L's priority to match H's. This prevents M from preempting L, so L finishes its critical section quickly, releases the mutex, and H can run. Once L releases the mutex, its priority returns to its original level.

Priority inheritance does not prevent the initial blocking (H still has to wait for L to release the mutex), but it prevents unbounded blocking - L runs at high priority until it releases the resource, preventing medium-priority tasks from prolonging the inversion.

Most modern operating systems and real-time systems support priority inheritance. Linux's PTHREAD_PRIO_INHERIT flag on mutexes enables it. Java's synchronized blocks do not support priority inheritance, which is one reason that java.util.concurrent.locks.ReentrantLock with fair ordering is sometimes preferred in latency-sensitive Java applications.

sequenceDiagram
    participant LOW as Low Priority<br/>(Background Task)
    participant MED as Medium Priority<br/>(Continuous Stream)
    participant HIGH as High Priority<br/>(User Request)
    participant CPU as CPU
    
    Note over LOW: LOW starts running
    LOW->>CPU: Running...
    
    MED->>CPU: I have higher priority!
    CPU->>LOW: Preempted
    Note over MED: MED runs
    
    MED->>CPU: Done
    
    MED->>CPU: Another MED arrives!
    Note over MED: MED runs again
    
    MED->>CPU: Done
    
    MED->>CPU: Yet another MED arrives!
    Note over MED: MED runs AGAIN
    
    Note over LOW: Still waiting...<br/>never gets CPU time<br/>STARVATION

This sequence diagram shows starvation. A low-priority background task starts running but is preempted by a medium-priority task. After the medium-priority task finishes, another medium-priority task arrives immediately and runs. This keeps happening: new medium-priority tasks arrive continuously, each preempting or preventing the low-priority task from running. The low-priority task is starved - it never gets CPU time because higher-priority tasks keep arriving.

The Solution: Aging

Aging is the standard solution to starvation in priority scheduling. The idea is simple: gradually increase the priority of processes that have been waiting a long time. The longer a process waits in the ready queue, the higher its effective priority becomes. Eventually, even the lowest-priority process gets promoted to the highest priority and runs.

Here is how aging works in practice. Suppose a system uses priorities 0 (highest) through 127 (lowest). A process enters the queue at priority 100. Every second it spends waiting, its priority increases by 1 (numerically decreasing toward 0). After 50 seconds of waiting, its effective priority is 50. After 100 seconds, it is 0 - the highest priority in the system. At that point, it will be the next process to run, regardless of what other processes are in the queue.

Aging prevents starvation because no process can wait forever. Eventually, aging will promote it above all other processes. The rate of aging is a tunable parameter - faster aging means starvation is resolved more quickly but may interfere with the intended priority ordering. Slower aging respects the priority ordering longer but risks longer starvation periods.

Interview: "What is starvation in scheduling, and how do you prevent it?"

"Starvation occurs when a process is ready to run but never gets CPU time because higher-priority processes keep arriving and being scheduled first. The starved process may wait indefinitely.

The standard solution is aging - gradually increasing the priority of waiting processes over time. The longer a process waits, the higher its effective priority becomes. Eventually, even the lowest-priority process is promoted to the highest priority and gets to run. This guarantees that no process waits forever, while still respecting the priority ordering under normal conditions.

A related problem is priority inversion, where a high-priority task is effectively blocked because a low-priority task holds a resource it needs, and medium-priority tasks keep preempting the low-priority task. The solution to priority inversion is priority inheritance - temporarily raising the low-priority task's priority to the level of the high-priority task waiting for the resource, so the low-priority task can finish and release the resource."

How Priorities Are Assigned

Priorities can be assigned in two ways: statically (assigned once when the process is created and never changed) or dynamically (adjusted by the OS based on the process's behavior during execution).

Static Priorities

Static priorities are set by the system administrator or by the process itself. In Unix/Linux, the nice value controls a process's priority. The nice value ranges from -20 (highest priority) to +19 (lowest priority), with 0 as the default. You can start a process with a lower priority using nice -n 10 ./my_program or change a running process's priority with renice.

Static priorities are simple and predictable, but they cannot adapt to changing workloads. If a process that was initially low-priority suddenly becomes urgent (because a deadline is approaching, or because a user is waiting for its output), its static priority does not reflect the change.

Dynamic Priorities

Dynamic priorities are adjusted by the OS based on the process's behavior. The most common adjustments are based on whether the process is CPU-bound or I/O-bound.

I/O-bound processes use the CPU for short bursts, then block on I/O. They should get higher priority because they will run briefly and then release the CPU. Giving them priority keeps them responsive and keeps the I/O devices busy.

CPU-bound processes use the CPU for long continuous stretches. They should get lower priority because they will consume their entire time slice. If they had high priority, they would block I/O-bound processes and hurt responsiveness.

This is exactly the behavior that the Multi-Level Feedback Queue (Topic 07) implements: processes that use their entire time slice (CPU-bound behavior) get demoted to lower-priority queues, while processes that block before their slice expires (I/O-bound behavior) stay at higher-priority queues. MLFQ is essentially priority scheduling with dynamic priorities based on observed behavior.

Priority Scheduling in Real Systems

Linux. Linux supports both real-time priorities (0-99, higher number = higher priority) and normal priorities (managed by the CFS scheduler using nice values). Real-time processes always preempt normal processes. Within the real-time range, Linux supports both FIFO scheduling (run until done or blocked) and Round Robin scheduling (time-sliced within the same priority level).

Windows. Windows uses 32 priority levels (0-31). Levels 16-31 are "real-time" and 1-15 are "dynamic" (normal). Windows adjusts dynamic priorities based on process behavior - foreground applications get a temporary priority boost to improve responsiveness. Background applications have their priorities slightly reduced.

Cloud and container orchestration. Kubernetes uses a priority-based scheduling system for pods. Higher-priority pods can preempt lower-priority pods (evicting them from a node to make room). This is OS-level priority scheduling applied at the container orchestration level, and it introduces the same starvation risks - a continuous stream of high-priority pods can prevent low-priority pods from ever being scheduled.

Pros:
- Ensures important processes get CPU time first
- Flexible - priorities can reflect real business importance
- Preemptive version guarantees highest-priority process always runs
- Can be combined with other algorithms (RR within priority levels)

Cons:
- Starvation - low-priority processes may never run
- Priority inversion - high-priority tasks can be indirectly blocked
- Static priorities cannot adapt to changing workloads
- Choosing the right priority for each process requires domain knowledge
- More complex than FCFS or Round Robin - requires maintaining sorted queue

Exercise: Starter: Given processes P1 (priority=4, burst=5), P2 (priority=1, burst=3), P3 (priority=2, burst=8), P4 (priority=3, burst=2), all arriving at time 0, trace through non-preemptive priority scheduling (lower number = higher priority). Calculate average turnaround time and waiting time.

Intermediate: Modify the exercise to use preemptive priority scheduling. P1 arrives at time 0, P2 at time 1, P3 at time 2, P4 at time 3. Trace through the schedule, noting each preemption. How do the results differ from non-preemptive?

Advanced: Design an aging scheme for a priority scheduler with 8 priority levels (0 = highest, 7 = lowest). Define the aging rate (how quickly a process's priority increases), the aging interval (how often aging is applied), and any constraints (should aging ever promote a process above a certain level?). Then describe a scenario where your aging scheme resolves starvation and calculate how long the starved process must wait before it runs.

Back to Operating Systems