Balancing Fairness and Throughput in Job Scheduling

51 concepts40 papers3 proposals

If you want to minimize the average time jobs spend waiting in a queue, the theoretical recipe is simple: always run the shortest job first. Under policies like Shortest Remaining Processing Time (SRPT), clearing small tasks quickly prevents them from clogging the system, which drastically reduces the average response time.

But this efficiency comes with a severe side effect: starvation. If a system experiences a steady influx of short tasks, a large, computationally intensive job can be pushed to the back of the line indefinitely. This creates a fundamental tension in computer systems: how do we maximize global throughput without subjecting individual long jobs to catastrophic delays?

A growing body of research addresses this challenge by redesigning scheduling objectives and mechanisms. Instead of treating fairness and throughput as mutually exclusive, these approaches use mathematical safeguards to guarantee a baseline level of service for all tasks while preserving the performance gains of size-based scheduling.


The Core Insight: Perceived Fairness and Relative Delay

To fix the fairness problem, we must first define what it means for a schedule to be "fair." Standard performance metrics like mean delay treat a one-minute wait identically, whether it happens to a five-second task or a five-hour task.

As Samuli Aalto et al. point out, absolute delay fails to capture the true impact of waiting on jobs of varying sizes. A fixed delay is disproportionately burdensome for short tasks. To align scheduling with human perception and system utility, researchers use relative waiting time, also known as stretch or slowdown. This metric scales the absolute wait time by the job's expected service duration:

$$\text{Stretch} = \frac{\text{Response Time}}{\text{Service Time}}$$

When fairness is framed around stretch, the scheduling calculus changes. As Yohai Trabelsi demonstrates, optimizing for relative waiting time ensures that shorter tasks are not subjected to disproportionately long delays compared to their processing requirements.

Crucially, prioritizing the worst-case experience for individual tasks does not doom system efficiency. Work by Tianming Zhao et al. shows that minimizing the maximum stretch across a workload can still yield exceptionally low average response times, proving that worst-case fairness and high overall throughput can coexist.


Mathematical Safeguards: Higher-Order Norms

How do we design an objective function that naturally balances the average case (throughput) with the worst case (fairness)? The answer lies in minimizing higher-order $\ell_k$-norms of flow time or stretch.

When a scheduler minimizes standard average flow time ($\ell_1$-norm), it treats two delays of 5 seconds the same as one delay of 10 seconds. However, if we minimize the $\ell_2$-norm (the sum of squares) or higher $\ell_k$-norms, the penalty for extreme delays grows non-linearly.

Delay Profiles:
Profile A: [2s, 2s, 2s, 2s]  -> l1 sum = 8,  l2 sum (squares) = 16
Profile B: [0s, 0s, 0s, 8s]  -> l1 sum = 8,  l2 sum (squares) = 64  <-- Heavily Penalized!

By minimizing the power-of-$k$ sum of job latencies, the scheduler penalizes long wait times aggressively. As Kyle Fox et al. demonstrate, bounding these higher-order norms provides a theoretical safeguard against job starvation in parallel systems. It prevents smaller jobs from indefinitely delaying larger ones because as a large job waits, its individual penalty grows so rapidly that the system is eventually forced to service it.

While Benjamin Moseley et al. proved that exactly minimizing these non-linear $k$-norms is strongly NP-hard, subsequent work by jatin batra et al. showed that we can achieve constant-factor approximations in pseudo-polynomial time, making higher-order norms a practical tool for balancing system efficiency with individual task fairness.


Algorithmic Mechanisms: Head-of-Line Tracking and Virtual Queues

To translate these mathematical insights into running systems, computer scientists employ two primary algorithmic strategies: tracking the age of the oldest jobs and emulating fair-sharing environments.

Head-of-Line (HoL) Waiting Times

Traditional max-weight schedulers allocate resources based on queue lengths—the number of packets or jobs waiting in a line. However, this severely penalizes low-traffic channels, which can sit starved while a high-volume channel dominates the processor.

To counter this, Ping-Chun Hsieh et al. proposed using Head-of-Line (HoL) waiting times—the actual duration the oldest job has been waiting—as the scheduling weight. By shifting the focus from how many jobs are waiting to how long the oldest job has been waiting, the system prevents low-intensity traffic flows from experiencing excessive delays while maintaining optimal total throughput.

Virtual Queue Emulation

Another elegant mechanism is to run a "shadow" or virtual scheduler alongside the real one. Size-based schedulers are highly efficient but prone to starvation; Processor Sharing (PS) models are perfectly fair but slower on average.

Matteo Dell'Amico et al. combined these two ideas by using virtual queue emulation. The system simulates an ideal, fair-sharing environment in the background to calculate when a job should complete under a fair policy. If a large job in the real size-based queue begins to fall too far behind its virtual completion time, the scheduler dynamically adjusts its priority or switches it to a fair-sharing model. This allows the system to reap the throughput benefits of size-based scheduling while guaranteeing that no job falls through the cracks.


Ubiquity Across Modern Domains

The tension between throughput and fairness is not isolated to classic CPU scheduling; it manifests across modern infrastructure:

  • Large Language Model (LLM) Inference: Schedulers like those detailed by Lianmin Zheng et al. and Bronislav Sidik et al. optimize throughput by batching requests that share common text prefixes or prioritizing short queries. To prevent long, complex prompts from being starved by a continuous stream of short interactive queries, they must integrate explicit fairness scoring functions.
  • Hardware Memory Controllers: In multi-core processors, memory-intensive threads can easily monopolize memory controllers. As Yoongu Kim et al. show, memory schedulers must balance raw system throughput with starvation prevention to ensure that less intensive threads are not completely blocked from accessing memory.
  • Autonomous Infrastructure: In autonomous traffic management, prioritizing the main road maximizes vehicle throughput but starves side streets. Tsz-Chiu Au et al. resolve this by introducing batch-processing and locking mechanisms, trading immediate processing for batch-level fairness to guarantee that every vehicle eventually passes through the intersection.

By shifting from naive average-case optimization to structured constraints—whether through relative stretch metrics, higher-order norm penalties, or virtual queue tracking—modern scheduling frameworks prove that systems do not have to choose between running fast and treating users fairly.

Key Foundational Work

Task allocation in a multi-server system (2001) — contributed 1 concept elements to this direction.
Using MEMS-based storage in computer systems - device modeling and management (2006) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_fairness_throughput_tradeoff_e26c7a87,
  title = {fairness-throughput tradeoff},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fairness-throughput-tradeoff/rdr_e26c7a87ff4b4adeb3471fd8182f8b39},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_fairness_throughput_tradeoff_e26c7a87_v1,
  title = {fairness-throughput tradeoff},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fairness-throughput-tradeoff/rdr_e26c7a87ff4b4adeb3471fd8182f8b39/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake