Priority Scheduling Algorithms

The Story That Explains Priority Scheduling

In an operating system, hundreds of processes compete for a single CPU. Some are critical (a system daemon handling network packets), others are trivial (a background spellchecker). Priority Scheduling — one of the most studied algorithms in Galvin's Operating System Concepts — assigns each process a priority and lets the CPU always execute the highest-priority process first.

The Two Flavours — Preemptive vs Non-Preemptive

Priority Scheduling exists in two forms. The difference is what happens when a new higher-priority process arrives while a lower-priority one is running.

Key Terms You Must Know

Numerical 1 — Non-Preemptive Priority Scheduling

Let's solve a complete Galvin-style problem step by step. Convention: lower number = higher priority.

Step-by-Step Execution Trace

Animated Gantt Chart — Step Reveal

Calculating CT, TAT, and WT

Numerical 2 — Preemptive Priority Scheduling

Now let's solve the same processes but with preemption enabled. The moment a higher-priority process arrives, the CPU is snatched away from the currently running process.

Preemption Trace — Every Time-Unit Decision

Animated Preemptive Gantt Chart

Final Table — Preemptive Version

Numerical 3 — Preemption Actually Happens

Now a case where preemption changes the outcome. Same idea, but P5 arrives earlier with a higher-priority than the process currently running.

Animated Gantt Chart with Real Preemptions

Final Metrics Table

Internal vs External Priorities

Where does the priority number come from? Galvin classifies the source into two categories.

The Starvation Problem

The Solution — Aging

Aging gradually increases the priority of processes that have been waiting in the ready queue for a long time. Eventually even the lowest-priority process becomes the highest-priority and gets scheduled. Simple, elegant, effective.

Aging Illustrated as a Pipeline

Python Implementation — Both Variants

Non-Preemptive Priority Scheduling

# Non-Preemptive Priority Scheduling — Galvin convention (low number = high priority)

def non_preemptive_priority(processes):
    # processes: list of dicts { 'pid', 'at', 'bt', 'pr' }
    n = len(processes)
    completed = []
    ready  = []
    t      = 0
    remaining = sorted(processes, key=lambda p: p['at'])

    while remaining or ready:
        # Move all arrived processes into ready queue
        while remaining and remaining[0]['at'] <= t:
            ready.append(remaining.pop(0))

        if not ready:
            t = remaining[0]['at']      # CPU idle → jump to next arrival
            continue

        # Pick process with SMALLEST priority number
        ready.sort(key=lambda p: p['pr'])
        p = ready.pop(0)

        start = t
        t    += p['bt']                    # Runs to completion
        p['ct']  = t
        p['tat'] = p['ct'] - p['at']
        p['wt']  = p['tat'] - p['bt']
        completed.append(p)

    return completed


procs = [
    {'pid': 'P1', 'at': 0, 'bt': 4, 'pr': 2},
    {'pid': 'P2', 'at': 1, 'bt': 3, 'pr': 3},
    {'pid': 'P3', 'at': 2, 'bt': 1, 'pr': 4},
    {'pid': 'P4', 'at': 3, 'bt': 5, 'pr': 5},
    {'pid': 'P5', 'at': 4, 'bt': 2, 'pr': 1},
]

result = non_preemptive_priority(procs)
print("PID  AT  BT  PR  CT  TAT  WT")
for p in sorted(result, key=lambda x: x['pid']):
    print(f"{p['pid']:3} {p['at']:3} {p['bt']:3} {p['pr']:3} {p['ct']:3} {p['tat']:4} {p['wt']:3}")

avg_tat = sum(p['tat'] for p in result) / len(result)
avg_wt  = sum(p['wt']  for p in result) / len(result)
print(f"\nAvg TAT = {avg_tat:.2f}, Avg WT = {avg_wt:.2f}")

Preemptive Priority Scheduling

# Preemptive Priority Scheduling — recheck priorities at every time unit

def preemptive_priority(processes):
    n         = len(processes)
    remaining = {p['pid']: p['bt'] for p in processes}
    completed = {}
    t         = 0
    # Precompute total burst so we know when to stop
    total_bt  = sum(p['bt'] for p in processes)

    while len(completed) < n:
        # Which processes have arrived by time t and still have BT left?
        available = [p for p in processes
                     if p['at'] <= t and remaining[p['pid']] > 0]

        if not available:
            t += 1                                # CPU idle
            continue

        # Choose highest priority (smallest pr number)
        curr = min(available, key=lambda p: p['pr'])
        remaining[curr['pid']] -= 1
        t += 1

        if remaining[curr['pid']] == 0:
            completed[curr['pid']] = {
                'ct':  t,
                'tat': t - curr['at'],
                'wt':  (t - curr['at']) - curr['bt'],
            }

    return completed


procs = [
    {'pid': 'P1', 'at': 0, 'bt': 6, 'pr': 4},
    {'pid': 'P2', 'at': 1, 'bt': 4, 'pr': 2},
    {'pid': 'P3', 'at': 3, 'bt': 3, 'pr': 1},
    {'pid': 'P4', 'at': 5, 'bt': 2, 'pr': 3},
]
res = preemptive_priority(procs)
for pid, m in sorted(res.items()):
    print(f"{pid}: CT={m['ct']}, TAT={m['tat']}, WT={m['wt']}")

Comparison with Other Scheduling Algorithms

Advantages & Disadvantages

Real-World Applications

Priority Inversion — A Cautionary Tale

Golden Rules — Priority Scheduling