Implement a scheduler that admits jobs by priority and preempts lower-priority work when it must. What are the rules?

TL;DR: A heap keyed on (priority, submission sequence) orders the waiting queue, and admission is a loop: while the head of the queue fits in the free capacity, start it. The substance is what happens when it does not fit. Consider only running jobs of strictly lower priority as victims, because allowing equal priority means two jobs at the same level can evict each other indefinitely. Among those, select the minimum set that frees enough capacity, preferring the lowest priority and, within a priority, the most recently started, so that a large arrival does not evict the whole cluster when two jobs would do. Return each victim to the waiting queue with its original sequence number, so it does not lose its place to jobs submitted after it. And say unprompted that this design starves low-priority work under sustained high-priority load, which is fixed by aging: raising a job's effective priority with time waited, so nothing waits forever.

How to approach it

Give the data structure in one line, then move to preemption, because that is the question. Name the three rules with the failure each prevents. Show the code and a worked trace. Close with starvation, since a scheduler that never mentions it is incomplete and the fix is a sentence.

A strong answer

A typical situation: a scheduler admits by priority and preempts whatever is running when a high-priority job arrives. A 4-GPU job arrives, and the scheduler evicts three 8-GPU jobs to make room because it evicts until it has enough and does not check how much it needs. Twenty GPU-hours of work is discarded to place a job that needed four GPUs.

The structure and the three rules:

waiting   a heap of (priority, sequence, job_id, size). Lower priority number is more
          important; the sequence number breaks ties by submission order, so equal
          priorities are first-come first-served
running   job_id -> (priority, sequence, size)

rule 1: strict inequality
  a job may preempt only strictly lower-priority running jobs
  why: with >=, two jobs at the same priority can evict each other forever, each arrival
  displacing the other, and neither makes progress

rule 2: minimum sufficient victim set
  sort candidates by lowest priority first, then most recently started first
  accumulate until the freed capacity plus the free capacity meets the requirement, then stop
  why: evicting more than necessary discards work for nothing, which is the scenario above
  the tie-break on recency means a job that has been running for hours is preferred over a
  job that just started, since the recent one has less to lose

rule 3: victims return with their original sequence number
  the preempted job goes back into the heap with the sequence it was submitted with
  why: re-assigning a new sequence sends it to the back behind everything submitted while it
  was running, which is a second penalty on top of losing its progress

import heapq, itertools

class Scheduler:
    def __init__(self, capacity):
        self.capacity = capacity
        self._waiting = []                       # heap of (priority, seq, job_id, size)
        self._running = {}                       # job_id -> (priority, seq, size)
        self._seq = itertools.count()

    def _used(self):
        return sum(size for _, _, size in self._running.values())

    def submit(self, job_id, priority, size):
        heapq.heappush(self._waiting, (priority, next(self._seq), job_id, size))
        return self._schedule()

    def _schedule(self):
        events = []
        while self._waiting:
            prio, seq, jid, size = self._waiting[0]
            if self._used() + size <= self.capacity:
                heapq.heappop(self._waiting)
                self._running[jid] = (prio, seq, size)
                events.append(("start", jid))
                continue

            # rule 1: strictly lower priority only
            victims = [(p, s, j, sz) for j, (p, s, sz) in self._running.items() if p > prio]
            # rule 2: lowest priority first, then most recently started
            victims.sort(key=lambda x: (-x[0], -x[1]))
            freed, chosen = 0, []
            for p, s, j, sz in victims:
                if self.capacity - self._used() + freed >= size:
                    break                        # stop as soon as it fits
                freed += sz
                chosen.append((p, s, j, sz))

            if chosen and self.capacity - self._used() + freed >= size:
                for p, s, j, sz in chosen:
                    del self._running[j]
                    heapq.heappush(self._waiting, (p, s, j, sz))   # rule 3: original seq
                    events.append(("preempt", j))
                continue                        # loop again; the head now fits
            break                               # cannot place the head, and nothing below it
        return events

A worked trace, capacity 8:

submit low1  priority 5, size 4  -> [('start', 'low1')]
submit low2  priority 5, size 4  -> [('start', 'low2')]
running: {'low1': (5, 4), 'low2': (5, 4)}      capacity full

submit hi    priority 1, size 4  -> [('preempt', 'low2'), ('start', 'hi')]
running: {'low1': (5, 4), 'hi': (1, 4)}
waiting: [(5, 'low2', 4)]
  only one victim was chosen, because evicting low2 alone freed the 4 needed
  low2 was preferred over low1 because it started more recently

submit low3  priority 5, size 4  -> []
running unchanged: ['hi', 'low1']
  low3 cannot preempt low1: equal priority, so rule 1 blocks it and low3 waits

The break at the end of the loop is worth noting: when the head cannot be placed, the loop stops rather than trying the next waiting job. That is strict priority ordering, and it means a large high-priority job blocks smaller ones behind it. The alternative is backfilling, where lower-priority jobs run in the gaps as long as they do not delay the head, which is what a production scheduler does and which needs an estimate of when the head will be able to start. GPU Job Scheduler Design covers backfill and the reservation that makes it safe.

Starvation, which must be raised unprompted:

the problem
  under sustained high-priority load, a low-priority job at the back never runs
  worse, a job that is preempted repeatedly accumulates no progress at all, so it consumes
  cluster time on restarts and produces nothing

aging, the standard fix
  effective_priority = priority - (time_waited / aging_interval)
  a job waiting long enough eventually outranks the class above it
  the aging interval sets the maximum wait: with priorities 1 to 5 and an interval of one
  hour, a priority-5 job reaches effective priority 1 after four hours, so nothing waits
  more than about four hours behind the top class

a second protection: a preemption budget per job
  a job preempted more than N times is marked non-preemptible for a period, so it can make
  progress rather than being repeatedly evicted at the same point
sanity: without aging this scheduler is correct and unusable, because "correct" here means it
        does exactly what the priorities say and what the priorities say is that low-priority
        work never runs

Multi-Tenancy, Quotas and Fair Share covers the fairness layer that usually sits above raw priority.

The reversal condition: preemption assumes the preempted work can be resumed cheaply, which for GPU jobs means a recent checkpoint. Preempting a job that checkpoints every hour discards up to an hour of work, and doing that repeatedly can consume more cluster time than the high-priority job saves. So a production version consults the victim's checkpoint state: prefer victims that checkpointed recently, and consider waiting for a victim's next checkpoint rather than killing it mid-interval. That turns a scheduling decision into a scheduling decision with a cost model, which is what separates this exercise from the real system.

What interviewers probe next

• "Why sort victims by most recently started?" They have the least accumulated work to lose. Preferring the oldest would repeatedly discard the most progress.
• "What if no victim set is sufficient?" The job waits. The code's break handles it, and a production system would report why the job cannot be placed rather than leaving it silently queued.
• "How would you add backfill?" Estimate when the head can start, then admit lower-priority jobs that will finish before then. It needs runtime estimates, which is where the difficulty moves.
• "Is size a single number?" Here yes. Real schedulers place on nodes with topology constraints, so fitting becomes a packing problem rather than a comparison.

Common mistakes

• Allowing equal-priority preemption, which lets two jobs evict each other indefinitely.
• Evicting until capacity is free rather than until the requirement is met, which discards far more than necessary.
• Re-queueing victims with a fresh sequence number, penalizing them twice.
• Never mentioning starvation, leaving a scheduler in which low-priority work never runs.

Key takeaways

• Heap on (priority, sequence); admission is a loop that starts the head while it fits.
• Three rules: strictly lower priority only, the minimum sufficient victim set preferring recently started jobs, and re-queue with the original sequence.
• Strict priority blocks smaller jobs behind a large head; backfill is the fix and needs runtime estimates.
• Aging is not optional: effective priority = priority minus time waited over an aging interval, so with priorities 1 to 5 and a one-hour interval nothing waits more than about four hours.