Expand description
Queueing Theory Scheduler with SRPT/Smith-Rule Style Scheduling (bd-13pq.7).
This module provides a fair, work-conserving task scheduler based on queueing theory principles. It implements variants of SRPT (Shortest Remaining Processing Time) with fairness constraints to prevent starvation.
§Mathematical Model
§Scheduling Disciplines
-
SRPT (Shortest Remaining Processing Time)
- Optimal for minimizing mean response time in M/G/1 queues
- Preempts current job if a shorter job arrives
- Problem: Can starve long jobs indefinitely
-
Smith’s Rule (Weighted SRPT)
- Priority = weight / remaining_time
- Maximizes weighted throughput
- Still suffers from starvation
-
Fair SRPT (this implementation)
- Uses aging: priority increases with wait time
- Ensures bounded wait time for all jobs
- Trade-off: slightly worse mean response time for bounded starvation
§Queue Discipline
Jobs are ordered by effective priority:
priority = (weight / remaining_time) + aging_factor * wait_timeEquivalent minimization form (used for evidence logging):
loss_proxy = 1 / max(priority, w_min)This combines:
- Smith’s rule:
weight / remaining_time - Aging: linear increase with wait time
§Fairness & Waiting-Time Semantics (Simulator Preemption vs. Live FnOnce Effects)
- Priority-overtake horizon (against newly arriving jobs): A waiting job with weight $w \ge w_{\min}$ and remaining time $r \le p_{\max}$ has effective priority $\frac{w}{r} + a \cdot \text{wait}$. Once $$\text{wait} \ge \tau_{\text{overtake}} = \frac{w_{\max} / p_{\min} - w_{\min} / p_{\max}}{a}$$ its priority exceeds the initial priority $\le w_{\max} / p_{\min}$ of any newly arriving job.
- Dependence on backlog $N$:
A finite maximum job size $S_{\max}$ and aging rate $a > 0$ do not bound total
wait time independently of the queue backlog $N$. For example, if $N$ identical jobs
of size $S$ arrive at $t = 0$, all $N$ jobs age at the same rate $a \cdot t$ and the
$N$-th job waits $(N - 1) S$ before starting service. Total wait is bounded only in
combination with admission control (
max_queue_size/max_queue_depth) or subcritical arrival load $\rho = \lambda E[S] < 1$. - Simulator preemption vs. live non-preemptive
FnOnceclosures: In this discrete simulator,preemptive: trueallows a newly arrived job with higher priority to preemptrunningattick(dt)boundaries. In the live runtime (EffectQueueineffect_system.rs), each queued effect is a synchronousFnOnceclosure executed on the worker thread: once popped from the scheduler, a running closure cannot be preempted until it returns, so an arriving short high-weight task additionally waits for the residual duration $R_{\text{running}}$ of the in-flight closure ($\text{wait}(j) \le R_{\text{running}} + \sum_{k \in \text{ahead}(j)} S_k$).
§Key Invariants
- Work-conserving: Server never idles when queue is non-empty
- Priority ordering: Ready queue is ordered by effective priority (or FIFO when
force_fifois set) - Bounded priority overtake: Waiting jobs overtake new arrivals after $\tau_{\text{overtake}}$, with total backlog capped by
max_queue_size - Monotonic aging: Wait time only increases while in queue
§Failure Modes
| Condition | Behavior | Rationale |
|---|---|---|
| Zero weight | Use minimum weight | Prevent infinite priority |
| Zero remaining time | Complete immediately | Job is done |
| Queue overflow | Reject new jobs | Bounded memory |
| Clock drift | Use monotonic time | Avoid priority inversions |
Structs§
- Job
- A job in the queue.
- JobEvidence
- Evidence entry for a single job in the queue.
- Queueing
Scheduler - Queueing theory scheduler with fair SRPT.
- Scheduler
Config - Configuration for the scheduler.
- Scheduler
Stats - Scheduler statistics.
- Scheduling
Evidence - Evidence for scheduling decisions.
Enums§
- Estimate
Source - Source of a processing-time estimate.
- Scheduling
Mode - Effective scheduling discipline.
- Selection
Reason - Reason for job selection.
- TieBreak
Reason - Tie-break reason for ordering decisions.
- Weight
Source - Source of a weight/importance value.