Skip to main content

Module queueing_scheduler

Module queueing_scheduler 

Source
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

  1. 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
  2. Smith’s Rule (Weighted SRPT)

    • Priority = weight / remaining_time
    • Maximizes weighted throughput
    • Still suffers from starvation
  3. 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_time

Equivalent 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)

  1. 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.
  2. 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$.
  3. Simulator preemption vs. live non-preemptive FnOnce closures: In this discrete simulator, preemptive: true allows a newly arrived job with higher priority to preempt running at tick(dt) boundaries. In the live runtime (EffectQueue in effect_system.rs), each queued effect is a synchronous FnOnce closure 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

  1. Work-conserving: Server never idles when queue is non-empty
  2. Priority ordering: Ready queue is ordered by effective priority (or FIFO when force_fifo is set)
  3. Bounded priority overtake: Waiting jobs overtake new arrivals after $\tau_{\text{overtake}}$, with total backlog capped by max_queue_size
  4. Monotonic aging: Wait time only increases while in queue

§Failure Modes

ConditionBehaviorRationale
Zero weightUse minimum weightPrevent infinite priority
Zero remaining timeComplete immediatelyJob is done
Queue overflowReject new jobsBounded memory
Clock driftUse monotonic timeAvoid priority inversions

Structs§

Job
A job in the queue.
JobEvidence
Evidence entry for a single job in the queue.
QueueingScheduler
Queueing theory scheduler with fair SRPT.
SchedulerConfig
Configuration for the scheduler.
SchedulerStats
Scheduler statistics.
SchedulingEvidence
Evidence for scheduling decisions.

Enums§

EstimateSource
Source of a processing-time estimate.
SchedulingMode
Effective scheduling discipline.
SelectionReason
Reason for job selection.
TieBreakReason
Tie-break reason for ordering decisions.
WeightSource
Source of a weight/importance value.