Scheduling

Purpose

This section is for scheduling as a systems idea rather than as one chapter inside operating systems. The same questions keep reappearing across CPUs, routers, clusters, storage services, and model-serving systems:

• which job or flow goes next
• what objective matters most
• where the bottleneck actually is
• how fairness trades against latency and throughput
• what mechanism enforces the policy

The emphasis here should stay reference-heavy. The goal is to preserve the derivations, code sketches, and mental pathways for grokking the main policies well enough to reuse them in another domain.

Reading Path

The best route is to start with the math, then the single-resource policies, then the multi-resource and domain-specific schedulers.

1. Latency, Throughput, and Utilization
2. Queueing Theory
3. Uniprocessor Scheduling
4. Multiprocessor Scheduling
5. Load Balancing
6. Batching
7. Performance Modeling

Clusters

• Foundations:
  • Little’s Law and bottleneck analysis
  • queueing models and tail latency
  • latency, throughput, and utilization
  • tail latency and queueing under load balancing
• Runnable artifacts:
  • scheduling benchmarks and simulators
• CPU scheduling:
  • FIFO, SJF, SRPT, RR, and MLFQ
  • EDF and rate monotonic
  • uniprocessor scheduling
  • multiprocessor scheduling
  • threads and scheduler activations
• Parallel and locality-aware scheduling:
  • work stealing, affinity, and NUMA
  • NUMA-aware scheduling and locality
• Resource contention and waiting:
  • synchronization and scheduler interaction
  • locality, working sets, and thrashing
• Network and packet scheduling:
  • fair queueing, WFQ, and DRR
• Cluster and datacenter scheduling:
  • cluster scheduling and DRF
  • stragglers, speculation, and overload
  • admission control, backpressure, and overload management
• Model-serving scheduling:
  • request scheduling for LLM serving
  • batching
  • parallelism
  • performance modeling
  • speculative decoding
  • distributed training of LLMs
  • distributed ML runtime architecture
• Adjacent systems:
  • TCP congestion behavior
  • scheduled versus random access on links
  • leadership and serialized critical work

Planned Depth

The section should eventually cover at least these layers:

• queueing laws, response-time distributions, and bottleneck analysis
• single-resource policies like FIFO, SJF, SRTF, RR, MLFQ, EDF, and fair sharing
• multiprocessor policies like affinity scheduling, work stealing, gang scheduling, and NUMA-aware placement
• packet and flow schedulers like WFQ and DRR
• cluster schedulers, dominant-resource fairness, and straggler mitigation
• request scheduling, admission control, and SLO-aware scheduling for modern model-serving systems

Notes on Scope

Some notes already exist in other branches and should stay there because their home context matters. This section is meant to link them together and eventually add the missing cross-domain material, not flatten everything into one folder.