Priority Scheduling

Each process carries a priority. When the CPU frees up, the ready process with the best priority runs; ties are broken FCFS. In this course, and in most textbooks, a lower number means a higher priority — priority 1 beats priority 5. (Some real systems invert that, so always check the convention before answering.)

It comes in both flavours. Non-preemptive — the version animated below — lets the running process finish even if something more important arrives. Preemptive takes the CPU away the moment a higher-priority process becomes ready.

SJF *is* priority scheduling, with priority = predicted next burst. Recognising that saves memorising two algorithms.

Internal (computed by the OS)

Measurable quantities: memory footprint, ratio of CPU to I/O usage, time limits, how long it has already waited. The system sets these itself.

External (set from outside)

Policy, not measurement: which user paid, which department owns the job, whether it is a system daemon or a background backup. nice on Unix is the everyday example.

This is the defining problem of priority scheduling: a low-priority process may never run, because higher-priority work keeps arriving. It is not blocked or deadlocked — it is simply always second best. The lore is that when MIT shut down its IBM 7094 in 1973, they found a low-priority job submitted in 1967 that had still never run.

The standard fix is ageing: gradually improve the priority of any process that has been waiting. Raise a job's priority by one step for every 15 minutes it has waited, and even a priority-127 job eventually outranks new arrivals — turning “never” into “eventually”, which is the guarantee a scheduler actually needs.

A related hazard is priority inversion: a high-priority process waits on a lock held by a low-priority one, which is itself never scheduled. The fix is priority inheritance — while it holds the lock, the low-priority process temporarily inherits the waiter's priority.

Arrival time

When the process shows up in the ready queue. The scheduler cannot pick something that has not arrived yet — that single rule decides most exam answers.

Burst time

How long this process needs the CPU for, uninterrupted, before it would block or finish. Also called CPU burst.

Ready queue

Every process that could run right now but does not have the CPU. Scheduling is entirely the question of who gets pulled out of here next.

Preemptive vs non-preemptive

A non-preemptive scheduler cannot take the CPU back — once dispatched, a process runs until it blocks or finishes. A preemptive one can interrupt it mid-burst.

Context switch

Saving one process's registers and loading another's. Pure overhead: real work stops while it happens, typically a few microseconds.

Starvation

A process that stays runnable but never gets picked, because something more attractive keeps arriving. The classic fix is ageing — slowly raising the priority of anything that has waited a long time.

Real systems rarely use one flat priority list. They split the ready queue into several queues — interactive, batch, system — each with its own priority and often its own internal algorithm (Round Robin for the interactive queue, FCFS for the batch one). Multilevel feedback queues go further and move a process between queues based on observed behaviour: use your whole quantum and you drop a level (you look CPU-bound); block early and you rise (you look interactive). That is ageing and burst prediction combined, and it is roughly what Linux, Windows and macOS actually do.