Where Priority Queues Are Used

job               priority   wait, first come   wait, priority
batch report             5                  0                0
user click               1                  9                9
backup                   5                  9               10
user typing              1                 16                8
index rebuild            5                 16               16

the two interactive jobs waited 9 and 16 units under first come first served,
and 9 and 8 under priority scheduling.

The interactive jobs waited 9 and 16 units under first come first served, and 9 and 8 under priority scheduling. The improvement is real and smaller than one might expect, and the reason is worth reading off the table: the batch report was already running when the first user click arrived at time 1, and this scheduler does not interrupt it. The second interactive job gained, from 16 to 8; the first gained nothing, because nothing could be done for it.

That limit has a name: this is non-preemptive scheduling. A preemptive scheduler would stop the batch job mid-way, and operating systems do, which is outside this paper but worth the sentence.

Event-driven simulation, run

import heapq
import random

random.seed(2)

# A single counter. Customers arrive, queue, and are served.
events = []          # (time, sequence, kind, customer)
sequence = 0


def schedule(time, kind, customer):
    global sequence
    heapq.heappush(events, (time, sequence, kind, customer))
    sequence += 1


arrival_time = 0
for customer in range(1, 9):
    arrival_time += random.randint(1, 4)
    schedule(arrival_time, "arrive", customer)

waiting, busy_until, served = [], 0, []

while events:
    time, _, kind, customer = heapq.heappop(events)
    if kind == "arrive":
        if time >= busy_until:
            busy_until = time + 3
            schedule(busy_until, "finish", customer)
            served.append((customer, time, 0))
        else:
            waiting.append((customer, time))
    else:
        if waiting:
            next_customer, arrived = waiting.pop(0)
            start = max(time, arrived)
            busy_until = start + 3
            schedule(busy_until, "finish", next_customer)
            served.append((next_customer, arrived, start - arrived))

print("one counter, service takes 3 units, customers arrive at random")
print()
print("%10s %9s %8s" % ("customer", "arrived", "waited"))
for customer, arrived, waited in sorted(served):
    print("%10d %9d %8d" % (customer, arrived, waited))

total_wait = sum(w for _, _, w in served)
print()
print("customers served :", len(served))
print("total waiting    :", total_wait)
print("average wait     : %.2f units" % (total_wait / len(served)))
print()
print("every step of that simulation came out of a priority queue ordered by TIME.")

one counter, service takes 3 units, customers arrive at random

  customer   arrived   waited
         1         1        0
         2         2        2
         3         3        4
         4         6        4
         5         8        5
         6        11        5
         7        14        5
         8        16        0

customers served : 8
total waiting    : 25
average wait     : 3.12 units

every step of that simulation came out of a priority queue ordered by TIME.

The whole simulation is a loop over a priority queue: take the earliest event, handle it, and schedule whatever it causes. The priority is the clock, and that is the pattern behind every discrete event simulator.

The pattern to recognise

An examiner may describe a problem and ask what structure fits. The signs of a priority queue:

• the next item to handle is chosen by a value, not by arrival or recency
• items keep arriving while others are being handled
• only the best item is ever needed, never the second best, and never a search
• the collection does not need to be read in order

If the last point fails, that is, if the whole collection must be listed in order, then it is a search tree and not a heap.

Quick revision

• A priority queue is used wherever the next item is chosen by importance rather than arrival.
• Inside this paper: Huffman coding, Dijkstra's algorithm, and heap sort.
• Outside it: process scheduling (with ageing against starvation), hospital triage, network packet

queues, event-driven simulation, and A-star search.

• Event-driven simulation is the pattern worth knowing: the priority is a timestamp, and handling the

earliest event may schedule more.

• The signs of a priority queue problem: the next item is chosen by value; items keep arriving; only the

best is ever needed; and the collection need not be readable in order.

• If the collection must be listed in order, a search tree is wanted, not a heap.

Test yourself

1. Name the three uses inside this paper. Huffman coding, which repeatedly needs the two least frequent items; Dijkstra's algorithm, which needs the nearest unvisited vertex; and heap sort.

2. What is the priority in an event-driven simulation? The time at which the event happens. The loop repeatedly takes the earliest event, handles it, and schedules any events that result.

3. In the scheduling run, one interactive job gained nothing. Why? Because the scheduler is non-preemptive and the long batch job was already running when that job arrived, so nothing could be done for it. The second interactive job gained, from 16 units to 8. A preemptive scheduler would interrupt the batch job and help both.

4. What prevents starvation in a priority scheduler? Ageing: an item's priority is raised the longer it waits, so anything waiting long enough eventually becomes urgent.

5. Give the four signs that a problem wants a priority queue. The next item is chosen by a value rather than by arrival; items keep arriving while others are handled; only the best item is ever needed; and the collection does not have to be read in order.

6. Which of those signs, if it fails, points to a different structure? The last. If the whole collection must be listed in order, a binary search tree is wanted rather than a heap.