Priority queueing disciplines: Definition & Examples

Priority queueing disciplines are service rules that give some classes of jobs precedence over others, specifying both who is served next and whether a running job can be interrupted. In a shared risk-calculation service, this could let urgent exposure checks move ahead of batch reports. The latency benefit depends on the interruption rule: a high-priority label alone does not make a busy server available.

This is a scheduling choice in queueing theory. A priority queue is the data structure that can select the next item; it does not itself specify what happens to the item already running. Exchange queue priority concerns the allocation of executions under a venue's matching rules, a separate modelling question.

The decision is whether to interrupt

Assume a single server, fixed priority classes and first-come, first-served ordering within each class. Whenever the server becomes free, it chooses the highest-priority class with waiting work.

Discipline	A higher-priority job arrives during lower-priority service	What happens to interrupted work?
Nonpreemptive priority	The running job finishes before the newcomer can start.	No interruption occurs.
Preemptive-resume priority	The newcomer can interrupt the lower-priority job.	Completed work is preserved; the job later continues from that point.
Preemptive-repeat or restart priority	The newcomer can interrupt the lower-priority job.	Service must begin again; the model must specify whether its duration is retained or redrawn.

These rules do not settle ties within a class. Nor does “preemptive” alone specify resume versus restart. MIT's treatment of priority disciplines makes these separate choices explicit.

Same workload, different delays

Consider a fictional risk-compute worker. Time is in seconds, and it starts empty.

Low-priority job L arrives at $t=0$ and requires $4$ seconds of server time.
High-priority job H arrives at $t=1$ and requires $1$ second.
There are no other arrivals, and switching and resuming cost no time.

Under nonpreemptive priority, L runs from

0

4

. H then runs from

4

5

. H waits

4-1=3

seconds and spends

5-1=4

seconds in the system, including service. Being first in the waiting line cannot shorten L's remaining service.

Under preemptive-resume priority, L runs from

0

1

, H runs from

1

2

, and L resumes for its remaining

3

seconds, finishing at

5

. H waits zero seconds and spends

2-1=1

second in the system. L starts immediately under both rules, but its completion moves from

4

5

: measuring only the delay until first service would miss its interruption.

Fictional workload: L arrives at 0 and needs 4 seconds; H arrives at 1 and needs 1 second. Nonpreemptive priority serves H from 4 to 5. Preemptive-resume serves H from 1 to 2 and completes L at 5.

Original deterministic schedule, with one server and no switching cost. The same arrivals and service requirements produce different class delays when interruption is allowed.

Both schedules process $5$ seconds of useful work and finish the workload at $t=5$ . The improvement for H comes from postponing L. This is an exact comparison of two schedules, not an estimate of mean latency under random arrivals.

What changes in a stochastic queue?

In a nonpreemptive M/G/1 queue, even the highest-priority class can encounter the unfinished service of a lower-priority job. Under ideal preemptive-resume service, lower-priority work cannot cause that obstruction; high-priority jobs can still wait behind other high-priority jobs. Modiano's MIT notes, slides 11–13 contrast these delay mechanisms and flag the overhead of practical preemption.

The zero-cost assumption matters. A task that must roll back, reload data or recompute lost work does not follow the timeline above. Restarting can increase the work needed to finish the workload; a non-interruptible operation can postpone even a nominally preemptive handover.

Strict priority also offers no automatic fairness or waiting-time bound. If higher-priority work keeps the server continuously occupied, lower-priority work can be starved. That is a possible workload, not a claim that every stable priority queue starves jobs. Capacity and stability must be assessed for the specified arrival and service processes; changing the order alone does not create processing capacity.

For the implementation side, Heapsort and Priority Queues develops heap-based selection of waiting work. The public page previews the lesson; the full teaching requires membership.

Sources

MIT Urban Operations Research, §4.9.1: Preemptive and Nonpreemptive Priorities — class ordering, within-class discipline, interruption and resumption conventions.
Eytan Modiano, MIT 6.263J, Lectures 10–11, slides 11–13 — residual-service obstruction in nonpreemptive queues, ideal preemptive-resume delay and practical overhead.