Scheduling and task queues

intermediateCommon atAnthropicGoogleAmazonStripeRead firstHeapsQueues and dequesEvent-driven simulationPractise in the Sandbox →

A scheduler is a policy plus a data structure: FIFO is a queue, priority and earliest-deadline-first are a heap keyed on (priority or deadline, arrival order), round robin is a queue you re-append to. Each pick is O(1) or O(log n). A reliable task queue adds a lease: a worker takes a job for a limited time, and if it doesn’t ack before the lease runs out the job comes back, after a growing backoff, until a retry limit sends it to a dead-letter queue. That gives at-least-once delivery, so the work itself must be idempotent.

The idea in plain words

A scheduler answers one question, over and over: of the jobs that are ready right now, which one gets the worker next?

Think of a hospital emergency room with one doctor:

• FIFO (first in, first out): see patients in arrival order. Fair and simple, but a 3-hour case blocks everyone behind it. This is the convoy effect.
• Priority: see the most urgent first. Great for urgent cases, but a sprained ankle may wait forever if critical cases keep arriving. This is starvation.
• Round robin: give everyone 10 minutes, then move to the next person and come back. Nobody waits long for a first look, but everyone finishes later.
• Earliest deadline first (EDF): see whoever must be treated soonest. On one worker, if any order meets every deadline, EDF does.

A task queue is the same question asked by many workers in a distributed system, plus a harder one: what if a worker takes a job and then dies? The answer is a lease. The worker doesn’t remove the job, it borrows it for, say, 30 seconds. Finish and ack in time, and the job is gone. Go silent, and the job reappears for someone else.

See it

Five jobs, one worker, four policies running side by side. Each job has an arrival tick, a duration, a priority (higher = more urgent) and a deadline. Run the clock and watch job A, the long one: under FIFO it blocks B, C and D and they all miss their deadlines. Change the round-robin quantum, or edit the jobs (try giving everything priority 1, or adding a very long job at tick 0).

Four policies, one worker

simulate

jobs: name arrival duration priority deadline

round-robin quantum q = 2 ticks

A: at 0, 6 long, prio 1, due 14B: at 1, 2 long, prio 3, due 5C: at 2, 3 long, prio 2, due 9D: at 3, 1 long, prio 1, due 6E: at 5, 2 long, prio 3, due 12

0

1

2

3

4

5

6

7

8

9

10

11

12

13

FIFO

Priority

Round robin

EDF

policy	waiting at t = 0	done	avg wait	missed deadlines	max lateness
FIFO	–	0/5	–	0	0
Priority	–	0/5	–	0	0
Round robin	–	0/5	–	0	0
EDF	–	0/5	–	0	0

Tick 0 (A arrives): FIFO runs A · Priority runs A · Round robin runs A · EDF runs A.

Higher priority number = more urgent. A red outline marks a job that finished after its deadline. Wait = finish − arrival − duration.

↺◀▶ Run▶tick 0 / 14

What to notice:

• FIFO misses the most deadlines (4 of 5) because the long job arrived first and everything queued behind it.
• Priority serves B and E quickly but D, the low-priority short job, waits behind everything and ends up the latest of all (8 ticks). Raise every job’s priority except one and watch that one starve.
• Round robin with q = 1 maximises interleaving: good response time, poor completion time. A large q turns it back into FIFO.
• EDF meets every deadline in the default input. It is optimal for minimising the worst lateness on one worker.

When to reach for it

The problem says…	Why this fits
“process in the order received”	FIFO queue. Ask what happens to a very slow item.
“urgent jobs first”, “higher priority wins”	A heap keyed on priority, with a tie-breaker (arrival sequence) so equal priorities stay FIFO.
“each tenant gets a fair share”, “don’t let one user hog the worker”	Round robin across per-tenant queues, or weighted fair queuing.
“must finish by”, “deadline”, “SLA”	EDF: a heap keyed on deadline.
“workers can crash”, “at least once”, “visibility timeout”	Leases with expiry, retry counts and a dead-letter queue.
“retry failed calls”, “the service is overloaded”	Exponential backoff with a cap and jitter.
“run later”, “delay”, “schedule at time T”	Delayed queue: a heap keyed on run-at time; items become ready when the clock passes it. See event-driven simulation.

How it works

Picking the next job

Policy	Data structure	Key	Pick cost	Preempts?
FIFO	queue / deque	arrival order	O(1)	no
Priority	min-heap	(-priority, seq)	O(log n)	optional
Round robin	queue, re-append after q ticks	arrival order	O(1)	yes, at quantum end
EDF	min-heap	(deadline, seq)	O(log n)	usually yes
Shortest job first	min-heap	(duration, seq)	O(log n)	optional (SRTF if so)

seq is a counter you increment on every insert. Heaps are not stable, so without it two equal-priority jobs can come out in either order. Python’s heapq compares tuples left to right (put seq before the job object so it never compares jobs), .NET’s PriorityQueue<TElement, TPriority> makes no ordering promise for equal priorities, and TypeScript has no built-in heap at all.

1. Sort the jobs by deadline, keeping input order for ties.
2. Run them back to back and track finish − deadline for each. The largest is the maximum lateness.
3. If the EDF order is late, every order is: swapping any two out-of-deadline-order jobs never makes the worst lateness better (an exchange argument).

Python

edf_order + max_lateness.py

"""Earliest deadline first on one machine (Jackson's rule): minimises the maximum lateness."""
from typing import NamedTuple


class Job(NamedTuple):
    name: str
    duration: int
    deadline: int


def edf_order(jobs: list[Job]) -> list[Job]:
    # 1. sort by deadline; Python's sort is stable, so equal deadlines keep their input order
    return sorted(jobs, key=lambda j: j.deadline)


def max_lateness(order: list[Job]) -> int:
    """2. Run jobs back to back from t = 0; lateness = finish - deadline (negative = early)."""
    t, worst = 0, float("-inf")
    for j in order:
        t += j.duration
        worst = max(worst, t - j.deadline)
    return int(worst) if order else 0


def feasible(jobs: list[Job]) -> bool:
    # 3. if EDF misses a deadline, every order does (exchange argument)
    return max_lateness(edf_order(jobs)) <= 0


if __name__ == "__main__":
    jobs = [Job("report", 3, 9), Job("email", 1, 2), Job("deploy", 2, 4), Job("backup", 4, 14)]
    assert [j.name for j in edf_order(jobs)] == ["email", "deploy", "report", "backup"]
    assert max_lateness(edf_order(jobs)) == -1  # every job finishes at least 1 early
    assert max_lateness(jobs) == 2  # input order: email finishes at 4, due 2
    assert feasible(jobs)
    assert not feasible([Job("a", 3, 2), Job("b", 1, 10)])
    print("ok")

TypeScript

edf_order + max_lateness.ts

import assert from "node:assert/strict";

/** Earliest deadline first on one machine (Jackson's rule): minimises the maximum lateness. */
interface Job { name: string; duration: number; deadline: number }

export function edfOrder(jobs: readonly Job[]): Job[] {
  // 1. sort by deadline; Array.prototype.sort is stable (ES2019), so ties keep input order
  return [...jobs].sort((a, b) => a.deadline - b.deadline);
}

/** 2. Run jobs back to back from t = 0; lateness = finish - deadline (negative = early). */
export function maxLateness(order: readonly Job[]): number {
  let t = 0, worst = -Infinity;
  for (const j of order) {
    t += j.duration;
    worst = Math.max(worst, t - j.deadline);
  }
  return order.length ? worst : 0;
}

// 3. if EDF misses a deadline, every order does (exchange argument)
export const feasible = (jobs: readonly Job[]): boolean => maxLateness(edfOrder(jobs)) <= 0;

const job = (name: string, duration: number, deadline: number): Job => ({ name, duration, deadline });
const jobs = [job("report", 3, 9), job("email", 1, 2), job("deploy", 2, 4), job("backup", 4, 14)];
assert.deepEqual(edfOrder(jobs).map((j) => j.name), ["email", "deploy", "report", "backup"]);
assert.equal(maxLateness(edfOrder(jobs)), -1); // every job finishes at least 1 early
assert.equal(maxLateness(jobs), 2); // input order: email finishes at 4, due 2
assert.ok(feasible(jobs));
assert.ok(!feasible([job("a", 3, 2), job("b", 1, 10)]));
console.log("ok");

C#

edf_order + max_lateness.cs

// Earliest deadline first on one machine (Jackson's rule): minimises the maximum lateness.

Job[] jobs = [new("report", 3, 9), new("email", 1, 2), new("deploy", 2, 4), new("backup", 4, 14)];
var order = Edf.Order(jobs);
if (string.Join(",", order.Select(j => j.Name)) != "email,deploy,report,backup") throw new Exception("wrong order");
if (Edf.MaxLateness(order) != -1) throw new Exception("every job should finish at least 1 early");
if (Edf.MaxLateness(jobs) != 2) throw new Exception("input order: email finishes at 4, due 2");
if (!Edf.Feasible(jobs)) throw new Exception("should be feasible");
if (Edf.Feasible([new("a", 3, 2), new("b", 1, 10)])) throw new Exception("should be infeasible");
Console.WriteLine("ok");

record Job(string Name, int Duration, int Deadline);

static class Edf
{
    // 1. sort by deadline; LINQ OrderBy is stable, so ties keep input order
    public static List<Job> Order(IEnumerable<Job> jobs) => jobs.OrderBy(j => j.Deadline).ToList();

    // 2. Run jobs back to back from t = 0; lateness = finish - deadline (negative = early).
    public static int MaxLateness(IReadOnlyList<Job> order)
    {
        if (order.Count == 0) return 0;
        int t = 0, worst = int.MinValue;
        foreach (var j in order) { t += j.Duration; worst = Math.Max(worst, t - j.Deadline); }
        return worst;
    }

    // 3. if EDF misses a deadline, every order does (exchange argument)
    public static bool Feasible(IEnumerable<Job> jobs) => MaxLateness(Order(jobs)) <= 0;
}

Leases, retries and dead letters

A plain queue’s pop loses the job if the worker crashes after popping. A lease-based queue (SQS calls the lease a visibility timeout; Google Pub/Sub calls it an ack deadline) makes delivery survive crashes. Pick a scenario and step through it:

Leases, retries and the dead-letter queue

step through

0

1

2

3

4

5

6

7

8

message

L

worker W1

worker W2

worker W3

t0

lease4 ticks

attempt1 / 3

backoff1·2^(n−1)

stateleased

leased (invisible)backoffworker busyackedcrash / late ack / DLQ

W1 leases the message (attempt 1). It is invisible to others until t = 4.

↺◀▶ Play▶1 / 9

1. Lease. A worker takes a ready job; the queue records who holds it and when the lease expires. The job is invisible to other workers until then.
2. Ack. If the holder acks before expiry, the job is done and deleted. An ack from anyone else, or after expiry, is rejected.
3. Heartbeat. A slow but healthy worker extends its lease before it runs out. Without this, long jobs get duplicated.
4. Expiry. No ack in time counts as a failed attempt. The job becomes ready again, often after a backoff delay.
5. Dead letter. After max_attempts failures the job moves to a dead-letter queue instead of retrying forever. One bad “poison” message can’t block the system.

At-least-once means duplicates

In the slow worker scenario both W1 and W2 do the work. The queue rejected W1’s late ack, but W1’s side effects (an email sent, a card charged) already happened. Leases give at-least-once delivery. Exactly-once effects need idempotent handlers, for example a dedupe key stored with the result. See idempotency.

Backoff and jitter

When a dependency fails, retrying immediately makes things worse. Back off: wait base × 2^attempt, capped at some maximum. But if a thousand clients failed at the same moment, they all compute the same delay and retry together. Add jitter, a random part of the delay:

Retry storms and jitter

drag the sliders

clients failing at t=0 = 30retries per client = 5

retries in 40 s150

peak per second30

cap32s

Every client computes the same delay, so all 30 retries land in the same second: a spike that can knock the recovering service over again.

1. The ceiling grows exponentially, base × 2^attempt, clamped to cap (and computed so a huge attempt number can’t overflow).
2. Full jitter: wait a uniform random time in [0, ceiling). AWS’s measurements found this gives the least total work and the lowest peaks.
3. Retry times are the running sum of the delays.

Python

backoff_delay (full jitter).py

"""Exponential backoff with a cap and full jitter. The random source is injected for testing."""
import random
from collections.abc import Callable


def backoff_delay(attempt: int, base: float, cap: float, rand: Callable[[], float] = random.random) -> float:
    """Seconds to wait before retry number `attempt` (0 = first retry)."""
    if attempt < 0:
        raise ValueError("attempt must be >= 0")
    # 1. exponential growth: base, 2*base, 4*base, ... computed with min() first so huge attempts can't overflow
    ceiling = min(cap, base * 2 ** min(attempt, 62))
    # 2. full jitter: pick uniformly in [0, ceiling) so clients that failed together retry apart
    return rand() * ceiling


def retry_schedule(attempts: int, base: float, cap: float, rand: Callable[[], float]) -> list[float]:
    """3. Absolute retry times, starting from a failure at t = 0."""
    t, out = 0.0, []
    for a in range(attempts):
        t += backoff_delay(a, base, cap, rand)
        out.append(t)
    return out


if __name__ == "__main__":
    top = lambda: 0.999999  # worst case: jitter picks (almost) the full ceiling
    assert [round(backoff_delay(a, 0.1, 10, top), 3) for a in range(8)] == [0.1, 0.2, 0.4, 0.8, 1.6, 3.2, 6.4, 10.0]
    assert backoff_delay(10_000, 0.1, 10, top) < 10  # capped, no overflow
    assert backoff_delay(3, 1, 30, lambda: 0.0) == 0.0  # full jitter may retry immediately
    rng = random.Random(7)
    times = retry_schedule(5, 1, 30, rng.random)
    assert times == sorted(times) and len(times) == 5
    print("ok")

TypeScript

backoff_delay (full jitter).ts

import assert from "node:assert/strict";

/** Exponential backoff with a cap and full jitter. The random source is injected for testing. */
export function backoffDelay(attempt: number, base: number, cap: number, rand: () => number = Math.random): number {
  if (!Number.isInteger(attempt) || attempt < 0) throw new RangeError("attempt must be an integer >= 0");
  // 1. exponential growth: base, 2*base, 4*base, ... clamped so huge attempts can't overflow to Infinity
  const ceiling = Math.min(cap, base * 2 ** Math.min(attempt, 62));
  // 2. full jitter: pick uniformly in [0, ceiling) so clients that failed together retry apart
  return rand() * ceiling;
}

/** 3. Absolute retry times, starting from a failure at t = 0. */
export function retrySchedule(attempts: number, base: number, cap: number, rand: () => number): number[] {
  const out: number[] = [];
  let t = 0;
  for (let a = 0; a < attempts; a++) {
    t += backoffDelay(a, base, cap, rand);
    out.push(t);
  }
  return out;
}

const top = () => 0.999999; // worst case: jitter picks (almost) the full ceiling
const r3 = (x: number) => Math.round(x * 1000) / 1000;
assert.deepEqual([0, 1, 2, 3, 4, 5, 6, 7].map((a) => r3(backoffDelay(a, 0.1, 10, top))), [0.1, 0.2, 0.4, 0.8, 1.6, 3.2, 6.4, 10]);
assert.ok(backoffDelay(10_000, 0.1, 10, top) < 10); // capped, no overflow
assert.equal(backoffDelay(3, 1, 30, () => 0), 0); // full jitter may retry immediately
let seed = 7;
const lcg = () => ((seed = (seed * 1103515245 + 12345) % 2 ** 31) / 2 ** 31);
const times = retrySchedule(5, 1, 30, lcg);
assert.deepEqual(times, [...times].sort((a, b) => a - b));
console.log("ok");

C#

backoff_delay (full jitter).cs

// Exponential backoff with a cap and full jitter. The random source is injected for testing.

Func<double> top = () => 0.999999; // worst case: jitter picks (almost) the full ceiling
double[] expected = [0.1, 0.2, 0.4, 0.8, 1.6, 3.2, 6.4, 10.0];
for (int a = 0; a < expected.Length; a++)
    if (Math.Round(Backoff.Delay(a, 0.1, 10, top), 3) != expected[a]) throw new Exception($"attempt {a}");
if (Backoff.Delay(10_000, 0.1, 10, top) >= 10) throw new Exception("must be capped");
if (Backoff.Delay(3, 1, 30, () => 0.0) != 0) throw new Exception("full jitter may retry immediately");
var rng = new Random(7);
var times = Backoff.Schedule(5, 1, 30, rng.NextDouble);
if (!times.SequenceEqual(times.Order())) throw new Exception("retry times must increase");
Console.WriteLine("ok");

static class Backoff
{
    // Seconds to wait before retry number `attempt` (0 = first retry).
    public static double Delay(int attempt, double baseDelay, double cap, Func<double> rand)
    {
        ArgumentOutOfRangeException.ThrowIfNegative(attempt);
        // 1. exponential growth, clamped so huge attempts can't overflow to infinity
        double ceiling = Math.Min(cap, baseDelay * Math.Pow(2, Math.Min(attempt, 62)));
        // 2. full jitter: uniform in [0, ceiling) so clients that failed together retry apart
        return rand() * ceiling;
    }

    // 3. Absolute retry times, starting from a failure at t = 0.
    public static List<double> Schedule(int attempts, double baseDelay, double cap, Func<double> rand)
    {
        var output = new List<double>();
        double t = 0;
        for (int a = 0; a < attempts; a++) { t += Delay(a, baseDelay, cap, rand); output.Add(t); }
        return output;
    }
}

What it costs

Operation	FIFO / RR	Priority / EDF heap	Delayed queue (heap on run-at)
enqueue	O(1)	O(log n)	O(log n)
pick next	O(1)	O(log n)	O(log n), plus moving due items to ready
cancel / change priority	O(n) scan, or O(1) lazy delete	O(n) find, or lazy deletion: mark it dead and skip it on pop	same

Lease expiry has its own cost. You can scan all leases on every call (O(leases)), or keep leases in a heap by expiry time and pop only the expired ones (O(log n) each). Using a heap, an expired lease is found exactly when its time comes, and each lease is pushed and popped once.

The metrics you trade between:

• Throughput: jobs per unit time. Context switches (preemptions) cost throughput.
• Turnaround (finish − arrival) and waiting time (turnaround − duration). Shortest-job-first minimises average waiting time; round robin is bad at it.
• Response time (first run − arrival). Round robin is good at it.
• Fairness / starvation. Strict priority can starve; aging (bump a job’s priority the longer it waits) fixes it.
• Lateness against deadlines. EDF minimises the maximum.

Variations you’ll meet

• Multi-level feedback queue (MLFQ). Several round-robin queues of decreasing priority; jobs that use their whole quantum drop a level. Approximates shortest-job-first without knowing durations. Operating systems use variants of this.
• Weighted fair queuing / deficit round robin. Each tenant gets a share proportional to its weight, even when job sizes differ.
• Multiple workers. “Pick next” becomes “pick next for each idle worker”. With dependencies between jobs it becomes dependency resolution plus a scheduler.
• Cooldowns and rate-limited queues. A job type can’t run again until some time has passed; keep a “not yet ready” heap keyed on ready time.
• Batching. Instead of one job per pick, admit as many as fit under a capacity limit. See resource allocation.
• Visibility vs delay. A delayed job is not ready until run_at; a leased job is not visible until its lease expires. Both are “a heap of future times” under the hood.

Pitfalls

• No tie-breaker in the heap. Equal priorities come out in arbitrary order, tests become flaky, and in Python comparing two job objects can raise TypeError.
• Inclusive vs exclusive expiry. Is a lease taken at t with length 30 still held at t + 30? Write the inequality down and test that exact tick.
• Acks from the wrong worker. Check that the acking worker holds the current lease, not an older expired one.
• Retrying forever. A poison message burns capacity endlessly. Cap attempts and dead-letter.
• Retrying in lock-step. Backoff without jitter turns one outage into periodic retry spikes.
• Starvation under strict priority. Mention aging or a fairness share.
• Mutating priority inside a heap without re-heapifying. Use lazy deletion and re-insert instead.

In the interview

• Ask: one worker or many? Preemptive or run-to-completion? What breaks ties? Can jobs be cancelled or re-prioritised? Is time passed in? What counts as a failure, and how many retries?
• Name the structure and the key out loud: “A min-heap on (deadline, seq); seq keeps ties FIFO and makes the order deterministic.”
• For queues with leases, say the delivery guarantee: “This is at-least-once. A slow worker can finish after its lease expired, so the handler must be idempotent.”
• Expect follow-ups: add priorities, add delayed jobs, add heartbeats, add a dead-letter queue, then “what changes with 100 workers on different machines?” (a shared store, atomic lease acquisition, clock skew).

Check yourself

Check yourself

pick one

A queue uses 30-second leases. A worker takes a job, then pauses for 45 seconds in a garbage-collection stall, then finishes and acks. Meanwhile another worker took the job at t = 30 and acked at t = 40. What happened?

AThe job ran once; the second worker was blocked until the first ackedBThe job ran twice; the late ack is rejected, but its side effects already happenedCThe job ran once; the first worker's ack wins because it leased firstDThe queue deadlocks because two workers hold the same lease

Check yourself

pick one

You keep ready jobs in a binary heap keyed only on priority. Two jobs with priority 5 are enqueued, X then Y. Which comes out first?

AAlways XBAlways YCEither; a binary heap is not stable, so you need a sequence number in the keyDNeither until a higher priority arrives

Check yourself

pick one

1,000 clients lose their connection at the same moment and retry with exponential backoff (1 s, 2 s, 4 s…) but no jitter. What does the server see?

AA steady 1,000 requests spread over the next minuteBSpikes of about 1,000 requests at t = 1, 3, 7, 15 s…CFewer requests each time because backoff reduces loadDNo retries until the cap is reached

Practice on your own

These are classic exercises, not gym questions:

• Simulate shortest-remaining-time-first on a list of (arrival, duration) jobs and report average waiting time; compare with FIFO.
• Implement a multi-level feedback queue with three levels and a periodic priority boost; show a CPU-bound job sinks and an interactive one stays on top.
• Build a delayed job queue on a heap keyed by run-at time, with cancellation by lazy deletion.
• Write deficit round robin over per-tenant queues whose jobs have different sizes, and check each tenant’s share converges to its weight.

Go deeper

• OSTEP, ch. 7-8: Scheduling and the multi-level feedback queue, free textbook chapters on FIFO, SJF, round robin and MLFQ.
• AWS Architecture Blog: Exponential backoff and jitter, the simulation behind “full jitter”.
• Amazon SQS: visibility timeout and dead-letter queues, leases in a production queue.
• Kleinberg and Tardos, Algorithm Design, §4.2 “Scheduling to minimize lateness”, the exchange-argument proof that EDF is optimal.

Related

HeapsThe structure behind priority, EDF and delayed queues.

Event-driven simulationAdvance a clock through a heap of future events.

Dependency resolutionScheduling when jobs wait on other jobs.

Rate limitingThe other side of overload: refusing work politely.