Priority Scheduling — Step-by-Step With Animated Numericals

The Story That Explains Priority Scheduling

The Two Flavours

Non-Preemptive Priority

Preemptive — But Nothing Preempts

Preemption in Action

The Preemption Timeline

Where Do Priorities Come From?

The Starvation Problem

The Solution — Aging

Priority vs FCFS vs SJF vs Round Robin

Advantages, Disadvantages & Uses

Priority Inversion — A Cautionary Tale

Seven Rules for Priority Scheduling

Priority Scheduling — Mastered

🏅

Give the CPU to the most important job first. Both flavours — non-preemptive and preemptive — solved with animated Gantt charts, plus starvation, aging, and the famous priority-inversion bug that hit Mars.

Highest Priority First Gantt Charts Aging Priority Inversion

Press Next → or use ← → arrow keys

Section 01

🚑 ANALOGY · THE EMERGENCY ROOM TRIAGE

Four patients arrive: a child with a fever, an elderly man with chest pain, a teenager with a sprain, a woman who is bleeding. The triage nurse does not treat them in arrival order — she assigns each an urgency, and the doctor sees the most urgent first.

That is priority scheduling: every process carries a priority number, and the CPU always goes to the most important ready job — not the first to arrive.

🔢

Convention: Lower Number = Higher Priority

Following Galvin, a smaller priority number means higher priority — priority 1 beats priority 5. (Some systems flip this, so always check the question's convention.) Fun fact: SJF is just priority scheduling where the priority is the next CPU burst.

Section 02

🛑

Non-Preemptive

run to completion

Once the CPU is allocated, the process runs to the end. A higher-priority arrival must wait in the ready queue until the current job finishes.

⚡

Preemptive

interrupt on arrival

A higher-priority arrival immediately preempts the running job, which returns to the queue with its remaining burst time.

📐

Same Metrics

CT · TAT · WT · RT

TAT = CT − AT, WT = TAT − BT, RT = start − AT. Only the selection rule — highest priority — is new.

🔑

Key Terms

AT arrival, BT burst, CT completion, TAT turnaround, WT waiting, PR priority number. In a preemptive tie between equal priorities, fall back to arrival order (FCFS).

Numerical 1

🧮

P1 Finishes, Then the Best Priority Wins

P1 runs 0→4 (it was alone). At t=4 the ready set is {P2·3, P3·4, P4·5, P5·1} — P5 has the best priority (1), so it runs next, then P2, P3, P4. Avg WT = 3.80 ms.

Numerical 2

🤔

Why the Result Is Identical to Numerical 1

Same data, now preemptive — yet the chart is unchanged. The reason: the only high-priority job, P5 (priority 1), arrives at t=4 — exactly when P1 finishes. There's nothing to interrupt, so no preemption ever fires. A great reminder that "preemptive" describes the rule, not a guarantee that preemption happens. Avg WT = 3.80 ms.

Numerical 3

⚡

P1 Preempted, Then P2 Preempted

P2 (pr 2) preempts P1 (pr 4) at t=1; then P3 (pr 1, the best) preempts P2 at t=3. P3 finishes, P2 resumes, P4 runs, and the low-priority P1 finally completes last. Avg WT = 3.75 ms.

Numerical 3 · Trace

🔍 Decision at every arrival & completion (lower PR wins)

t=0

P1 alone (pr 4) → run P1.

t=1

P2 arrives (pr 2) → 2 < 4, preempt P1 (5 left), run P2.

t=3

P3 arrives (pr 1) → 1 < 2, preempt P2 (2 left), run P3.

t=5

P4 arrives (pr 3) → 3 > 1, P3 keeps running.

t=6

P3 completes → best available is P2 (pr 2) → P2 resumes.

t=8

P2 completes → P4 (pr 3) beats P1 (pr 4) → run P4.

t=10

P4 completes → only P1 left → P1 resumes, finishing its 5 units at t=15.

💡

The Low-Priority Job Pays

Notice P1 — the lowest priority — arrived first yet finished last, waiting 9 units. That asymmetry is exactly what leads to the starvation problem next.

Section 07

	Internal Priority	External Priority
Set by	The OS, automatically	A system administrator / policy
Based on	Measurable quantities — memory needs, time limits, open files, I/O-to-CPU ratio	Importance of the user, payment tier, department, politics
Nature	Objective & dynamic	Subjective & static

⚖️

Most Systems Blend Both

A scheduler often combines an internal component the OS computes from resource usage with an external component reflecting business importance — a paid job may outrank a free one even with identical resource profiles.

Section 08

🕰️ TRUE STORY · MIT's IBM 7094

When MIT shut down its IBM 7094 mainframe at the end of 1973, engineers found a low-priority job that had been submitted in 1967 and had never run — a higher-priority job had always jumped ahead. Six years of waiting, and it never got a single cycle.

🍽️

Pure Priority Scheduling's Fatal Flaw

If a steady stream of high-priority jobs keeps arriving, a low-priority process can wait forever — this is starvation. It's the same danger SJF and SRTF face for long jobs, and it needs the same cure.

Section 09

⏳

Reward Patience

Aging gradually raises the priority of a waiting process — e.g. improve its number by one every few time units. Eventually even the lowest-priority job climbs high enough to be scheduled, so nothing starves. It's the standard fix, and it preserves priority scheduling's responsiveness for important jobs.

Section 11

Feature	Priority	FCFS	SJF	Round Robin
Selection rule	Highest priority	First arrived	Shortest burst	Time-slice rotation
Preemption	Either variant	No	Either (SJF/SRTF)	Always
Starvation	Yes (fix: aging)	No	Yes (long jobs)	No
Overhead	Medium	Lowest	Needs burst prediction	Switch per slice
Real-time fit	Excellent	Poor	Poor	Good (soft RT)
Special case of	—	Priority = arrival	Priority = burst	—

🧩

Priority Is the General Case

FCFS is priority scheduling with priority = arrival time; SJF is priority scheduling with priority = burst. Priority scheduling is the umbrella they both live under.

Section 12–13

✅

Importance-Aware

Critical work runs first — ideal for real-time and mixed-criticality systems.

✅

Flexible

Priorities can be internal, external or a blend — tune it to any policy.

✅

General Model

FCFS and SJF are special cases, so one engine covers many behaviours.

❌

Starvation

Low-priority jobs can wait forever without aging.

❌

Priority Inversion

A high-priority job can stall behind a low-priority one holding a lock.

🌍

Real-World

OS kernels, real-time systems, network QoS, print & batch queues, task schedulers.

Section 14

🚀

Mars Pathfinder, July 1997

On Mars, a high-priority bus task blocked waiting for a lock held by a low-priority task — while a medium-priority task ran freely and never let the low one release it. The watchdog thought the system had hung and kept rebooting the rover. JPL fixed it remotely with priority inheritance: the lock-holder temporarily inherits the waiter's high priority.

Section 15

🏅 PRIORITY SCHEDULING · CHECKLIST

1

State the convention first — usually lower number = higher priority.

2

At each decision, pick the best-priority arrived process; break ties by arrival, then PID.

3

Non-preemptive runs to completion; preemptive re-checks at every arrival and can interrupt.

4

A preempted job returns to the queue with its remaining burst.

5

"Preemptive" is a rule, not a promise — if no better job arrives mid-run, nothing preempts.

6

Pure priority scheduling starves low-priority jobs — cure it with aging.

7

Beware priority inversion with shared locks — fix it with priority inheritance.

FINAL

Averages →

2Flavours

3.80N1 avg WT (ms)

3.75N3 avg WT (ms)

6 yrsThe 1967 starved job

1997Mars inversion bug

🎯

You Can Now Solve Any Priority Problem

Pick the best priority, draw the Gantt chart (marking preemptions), and compute the metrics. You've seen non-preemptive, "preemptive but nothing preempts," and real mid-execution preemption — plus starvation, aging, and priority inversion.

📚

Where To Go Next

The last big single-queue algorithm is Round Robin (fair time-slicing), and then Multilevel Queue and Multilevel Feedback Queue combine priority with round-robin for real production schedulers.

🏅 End of tutorial · Press ← to review, or click Restart