Module queueing_scheduler 

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 Guarantee (Aging-Based)

With aging factor a and maximum job size S_max:

max_wait <= S_max * (1 + 1/a) / min_weight

Key Invariants

1. Work-conserving: Server never idles when queue is non-empty
2. Priority ordering: Queue is always sorted by effective priority
3. Bounded starvation: All jobs complete within bounded time
4. 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.

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.