Designing a Fair Scheduler for Agent Workloads

Priority queues are easy to build. Fair schedulers are harder. The failure mode appears when the highest-priority class never stops arriving and lower-priority work never receives capacity.

The strict-priority trap

1if critical_queue.not_empty():2run(critical)3elif interactive_queue.not_empty():4run(interactive)5else:6run(background)

This implements priority perfectly and fairness terribly. Under sustained critical traffic, background work can wait forever. That is starvation.

Start from workload SLOs

Priority now has a reason: it exists to protect a workload objective, not just because one queue was named “critical”.

Option A: reserved capacity

100 worker slots

160 critical230 interactive310 background

This gives every class a guaranteed floor. A flexible implementation can lend idle capacity to busy classes and reclaim it when the reserved class needs it.

Option B: weighted fair scheduling

1weights:2critical = 63interactive = 34background = 1

Under sustained demand, service converges toward a 60/30/10 share rather than allowing one class to monopolize execution.

Option C: aging and max-wait promotion

background job arrives at 10:00

110:00 → priority 3210:15 → priority 2310:30 → priority 1

Aging is useful when hard reservations are undesirable. The scheduler increases urgency as queue age grows so old work eventually surfaces.

Fairness usually needs multiple dimensions

• workload class: critical vs interactive vs background
• tenant or department: Sales vs Finance vs Engineering
• user: one user cannot consume all concurrent runs
• tool: constrained CRM activity cannot occupy every worker needed for unrelated tools

1global worker budget: 1002critical max: 703interactive guaranteed min: 204background guaranteed min: 105sales-department max: 406per-user max concurrent: 5

A scheduler sketch

1loop:2update_queue_ages()3promote_jobs_past_max_wait()

1for class in weighted_round_robin():2if class.has_work() and class.within_quota():3dispatch(class.next_job())

borrow_idle_capacity_when_safe()

A production implementation can use separate queues with a scheduler service, separate worker pools with reserved concurrency, or a shared pool with explicit admission tokens. The algorithm matters less than the guarantees: preferential service for important work plus a non-zero path to progress for everything else.

How to detect starvation

• oldest queue age rises while higher-priority throughput remains healthy
• some classes have near-zero dispatch rate under sustained load
• p95/p99 queue time for one class grows without bound
• capacity is repeatedly consumed by the same tenant or workload
• background completion SLOs fail even though the system is technically available