# Algorithmic Techniques for GPU Scheduling: A Comprehensive Survey
## 3 Scheduling Algorithms and Their Performance
### Queueing-Theoretic Approaches  
Queueing-theoretic scheduling algorithms draw on analytical results from classical queueing models to assign each job a dynamic priority. Instead of solving a global optimization, these policies maintain a simple \"index\" or rank for every job--based on its service history or statistical characteristics--and always dispatch the job with the highest priority. Below, we outline four influential families of queue-based strategies. Index policies (e.g., Gittins index): Index policies compute a per-job score that balances fairness and efficiency by considering both attained service and the likelihood of short remaining work. The Gittins index is a canonical example: for an \(M/G/1\) queue, a job with attained service \(v\) receives a Gittins index  
\[\mathcal{G}(v)=\sup_{\tau>0}\frac{\Pr\{\,S_{j}\leq v+\tau\mid S_{j}>v\}}{\mathbb{ E}[\min(\tau,\,S_{j}-v)\mid S_{j}>v]},\]  
where \(S_{j}\) is the (unknown) total service time of job \(j\) and \(\mathbb{E}[\cdot]\) denotes expectation. Here, the numerator is the probability that the job will complete within the next \(\tau\) units of service given that it has already consumed \(v\); the denominator is the expected additional service it would require over that same horizon. The job with the highest index is scheduled next, yielding a policy that is provably optimal for minimizing mean slowdown when job sizes are unknown, even though exact computation is often approximated in practice [153]. Least attained service (LAS) / foreground-background (FB): A simpler offshoot of the [PERSON] family sets \(\mathcal{G}(v)=-v\), yielding the LAS/FB rule: always run the job with the smallest accumulated service. Under heavy-tailed service distributions, LAS incurs at most a 25% penalty over SRPT for mean slowdown--the information-theoretic lower bound [154]. New arrivals preempt longer-served jobs immediately, mimicking multi-level feedback. In GPU clusters, full preemption is often too costly, so systems like Tiresias use fixed-length leases: after each time slice, the job with least total GPU-time may preempt the current one. By tracking both time and GPU count (2D-LAS), Tiresias avoids starvation with minimal overhead. E-LAS further extends this by incorporating real-time epoch progress rates into the priority, improving job-completion times without runtime profiling [155]. Multi-class priority queues: Queueing theory also motivates dividing work into several priority classes, e.g., \"urgent,\" \"standard,\" and \"background.\" Strict priority in an \(M/M/1\) system guarantees minimal response for the top class, though lower classes suffer increased delays. GPU schedulers often emulate SRPT by maintaining, say, short-job and long-job queues: serve all jobs with estimated runtime \(<X\) seconds first, then switch to longer tasks. Thresholds are set based on historical job-size distributions, and user-provided estimates can refine class assignments [156]. Processor sharing (PS) approximations: Ideal processor sharing divides capacity equally among active jobs, preventing starvation and smoothing progress. GPUs cannot preempt at the granularity PS demands, but features like NVIDIA A100's MIG partitions approximate independent instances. Alternatively, coarse time slicing or round-robin dispatchers (e.g., Themis's finish-time equalization) reassign GPUs periodically to equalize job progress--capturing PS's fairness spirit while limiting I/O and checkpointing overhead [85]. It is worth noting that these policies are derived under single-server assumptions. In multi-GPU clusters, naively applying them per GPU may break global optimality. Practical extensions either decentralize the policy (one index per GPU) or coordinate across servers to generalize index and priority rules to the multi-machine setting. Practical applicability of queueing models: Queueing-based algorithms come with strong theoretical guarantees under idealized models, but real GPU clusters demand careful approximations and tuning.