Skip to main content

ftui_runtime/
queueing_scheduler.rs

1#![forbid(unsafe_code)]
2
3//! Queueing Theory Scheduler with SRPT/Smith-Rule Style Scheduling (bd-13pq.7).
4//!
5//! This module provides a fair, work-conserving task scheduler based on queueing theory
6//! principles. It implements variants of SRPT (Shortest Remaining Processing Time) with
7//! fairness constraints to prevent starvation.
8//!
9//! # Mathematical Model
10//!
11//! ## Scheduling Disciplines
12//!
13//! 1. **SRPT (Shortest Remaining Processing Time)**
14//!    - Optimal for minimizing mean response time in M/G/1 queues
15//!    - Preempts current job if a shorter job arrives
16//!    - Problem: Can starve long jobs indefinitely
17//!
18//! 2. **Smith's Rule (Weighted SRPT)**
19//!    - Priority = weight / remaining_time
20//!    - Maximizes weighted throughput
21//!    - Still suffers from starvation
22//!
23//! 3. **Fair SRPT (this implementation)**
24//!    - Uses aging: priority increases with wait time
25//!    - Ensures bounded wait time for all jobs
26//!    - Trade-off: slightly worse mean response time for bounded starvation
27//!
28//! ## Queue Discipline
29//!
30//! Jobs are ordered by effective priority:
31//! ```text
32//! priority = (weight / remaining_time) + aging_factor * wait_time
33//! ```
34//!
35//! Equivalent minimization form (used for evidence logging):
36//! ```text
37//! loss_proxy = 1 / max(priority, w_min)
38//! ```
39//!
40//! This combines:
41//! - Smith's rule: `weight / remaining_time`
42//! - Aging: linear increase with wait time
43//!
44//! ## Fairness & Waiting-Time Semantics (Simulator Preemption vs. Live `FnOnce` Effects)
45//!
46//! 1. **Priority-overtake horizon (against newly arriving jobs)**:
47//!    A waiting job with weight $w \ge w_{\min}$ and remaining time $r \le p_{\max}$ has
48//!    effective priority $\frac{w}{r} + a \cdot \text{wait}$. Once
49//!    $$\text{wait} \ge \tau_{\text{overtake}} = \frac{w_{\max} / p_{\min} - w_{\min} / p_{\max}}{a}$$
50//!    its priority exceeds the initial priority $\le w_{\max} / p_{\min}$ of any newly
51//!    arriving job.
52//! 2. **Dependence on backlog $N$**:
53//!    A finite maximum job size $S_{\max}$ and aging rate $a > 0$ do **not** bound total
54//!    wait time independently of the queue backlog $N$. For example, if $N$ identical jobs
55//!    of size $S$ arrive at $t = 0$, all $N$ jobs age at the same rate $a \cdot t$ and the
56//!    $N$-th job waits $(N - 1) S$ before starting service. Total wait is bounded only in
57//!    combination with admission control (`max_queue_size` / `max_queue_depth`) or
58//!    subcritical arrival load $\rho = \lambda E\[S\] < 1$.
59//! 3. **Simulator preemption vs. live non-preemptive `FnOnce` closures**:
60//!    In this discrete simulator, `preemptive: true` allows a newly arrived job with higher
61//!    priority to preempt `running` at `tick(dt)` boundaries. In the live runtime
62//!    (`EffectQueue` in `effect_system.rs`), each queued effect is a synchronous `FnOnce`
63//!    closure executed on the worker thread: once popped from the scheduler, a running
64//!    closure **cannot be preempted** until it returns, so an arriving short high-weight
65//!    task additionally waits for the residual duration $R_{\text{running}}$ of the
66//!    in-flight closure ($\text{wait}(j) \le R_{\text{running}} + \sum_{k \in \text{ahead}(j)} S_k$).
67//!
68//! # Key Invariants
69//!
70//! 1. **Work-conserving**: Server never idles when queue is non-empty
71//! 2. **Priority ordering**: Ready queue is ordered by effective priority (or FIFO when `force_fifo` is set)
72//! 3. **Bounded priority overtake**: Waiting jobs overtake new arrivals after $\tau_{\text{overtake}}$, with total backlog capped by `max_queue_size`
73//! 4. **Monotonic aging**: Wait time only increases while in queue
74//!
75//! # Failure Modes
76//!
77//! | Condition | Behavior | Rationale |
78//! |-----------|----------|-----------|
79//! | Zero weight | Use minimum weight | Prevent infinite priority |
80//! | Zero remaining time | Complete immediately | Job is done |
81//! | Queue overflow | Reject new jobs | Bounded memory |
82//! | Clock drift | Use monotonic time | Avoid priority inversions |
83
84use std::cmp::Ordering;
85use std::collections::BinaryHeap;
86use std::fmt::Write;
87
88/// Default aging factor (0.1 = job gains priority of 1 unit after 10 time units).
89const DEFAULT_AGING_FACTOR: f64 = 0.1;
90
91/// Maximum queue size.
92const MAX_QUEUE_SIZE: usize = 10_000;
93
94/// Default minimum processing-time estimate (ms).
95const DEFAULT_P_MIN_MS: f64 = 0.05;
96
97/// Default maximum processing-time estimate (ms).
98const DEFAULT_P_MAX_MS: f64 = 5_000.0;
99
100/// Default minimum weight to prevent division issues.
101const DEFAULT_W_MIN: f64 = 1e-6;
102
103/// Default maximum weight cap.
104const DEFAULT_W_MAX: f64 = 100.0;
105
106/// Default weight when the source is `Default`.
107const DEFAULT_WEIGHT_DEFAULT: f64 = 1.0;
108
109/// Default weight when the source is `Unknown`.
110const DEFAULT_WEIGHT_UNKNOWN: f64 = 1.0;
111
112/// Default estimate (ms) when the source is `Default`.
113const DEFAULT_ESTIMATE_DEFAULT_MS: f64 = 10.0;
114
115/// Default estimate (ms) when the source is `Unknown`.
116const DEFAULT_ESTIMATE_UNKNOWN_MS: f64 = 1_000.0;
117
118/// Default starvation guard threshold (ms). 0 disables the guard.
119const DEFAULT_WAIT_STARVE_MS: f64 = 500.0;
120
121/// Default multiplier applied when starvation guard triggers.
122const DEFAULT_STARVE_BOOST_RATIO: f64 = 1.5;
123
124/// Configuration for the scheduler.
125#[derive(Debug, Clone)]
126pub struct SchedulerConfig {
127    /// Aging factor: how fast priority increases with wait time.
128    /// Higher = faster aging = more fairness, less optimality.
129    /// Default: 0.1.
130    pub aging_factor: f64,
131
132    /// Minimum processing-time estimate (ms). Default: 0.05.
133    pub p_min_ms: f64,
134
135    /// Maximum processing-time estimate (ms). Default: 5000.
136    pub p_max_ms: f64,
137
138    /// Default estimate (ms) when estimate source is `Default`.
139    /// Default: 10.0.
140    pub estimate_default_ms: f64,
141
142    /// Default estimate (ms) when estimate source is `Unknown`.
143    /// Default: 1000.0.
144    pub estimate_unknown_ms: f64,
145
146    /// Minimum weight clamp. Default: 1e-6.
147    pub w_min: f64,
148
149    /// Maximum weight clamp. Default: 100.
150    pub w_max: f64,
151
152    /// Default weight when weight source is `Default`.
153    /// Default: 1.0.
154    pub weight_default: f64,
155
156    /// Default weight when weight source is `Unknown`.
157    /// Default: 1.0.
158    pub weight_unknown: f64,
159
160    /// Starvation guard threshold (ms). 0 disables the guard. Default: 500.
161    pub wait_starve_ms: f64,
162
163    /// Multiplier applied to base ratio when starvation guard triggers.
164    /// Default: 1.5.
165    pub starve_boost_ratio: f64,
166
167    /// Enable Smith-rule weighting. If false, behaves like SRPT.
168    pub smith_enabled: bool,
169
170    /// Force FIFO ordering (arrival sequence) regardless of other settings.
171    /// Useful for safety overrides and debugging.
172    pub force_fifo: bool,
173
174    /// Maximum queue size. Default: 10_000.
175    pub max_queue_size: usize,
176
177    /// Enable preemption. Default: true.
178    pub preemptive: bool,
179
180    /// Time quantum for round-robin fallback (when priorities are equal).
181    /// Default: 10.0.
182    pub time_quantum: f64,
183
184    /// Enable logging. Default: false.
185    pub enable_logging: bool,
186}
187
188impl Default for SchedulerConfig {
189    fn default() -> Self {
190        Self {
191            aging_factor: DEFAULT_AGING_FACTOR,
192            p_min_ms: DEFAULT_P_MIN_MS,
193            p_max_ms: DEFAULT_P_MAX_MS,
194            estimate_default_ms: DEFAULT_ESTIMATE_DEFAULT_MS,
195            estimate_unknown_ms: DEFAULT_ESTIMATE_UNKNOWN_MS,
196            w_min: DEFAULT_W_MIN,
197            w_max: DEFAULT_W_MAX,
198            weight_default: DEFAULT_WEIGHT_DEFAULT,
199            weight_unknown: DEFAULT_WEIGHT_UNKNOWN,
200            wait_starve_ms: DEFAULT_WAIT_STARVE_MS,
201            starve_boost_ratio: DEFAULT_STARVE_BOOST_RATIO,
202            smith_enabled: true,
203            force_fifo: false,
204            max_queue_size: MAX_QUEUE_SIZE,
205            preemptive: true,
206            time_quantum: 10.0,
207            enable_logging: false,
208        }
209    }
210}
211
212impl SchedulerConfig {
213    /// Effective scheduling mode with FIFO override.
214    pub fn mode(&self) -> SchedulingMode {
215        if self.force_fifo {
216            SchedulingMode::Fifo
217        } else if self.smith_enabled {
218            SchedulingMode::Smith
219        } else {
220            SchedulingMode::Srpt
221        }
222    }
223}
224
225/// A job in the queue.
226#[derive(Debug, Clone)]
227pub struct Job {
228    /// Unique job identifier.
229    pub id: u64,
230
231    /// Job weight (importance). Higher = more priority.
232    pub weight: f64,
233
234    /// Estimated remaining processing time.
235    pub remaining_time: f64,
236
237    /// Original estimated total time.
238    pub total_time: f64,
239
240    /// Time when job was submitted.
241    pub arrival_time: f64,
242
243    /// Monotonic arrival sequence (tie-breaker).
244    pub arrival_seq: u64,
245
246    /// Source of processing-time estimate.
247    pub estimate_source: EstimateSource,
248
249    /// Source of weight/importance.
250    pub weight_source: WeightSource,
251
252    /// Optional job name for debugging.
253    pub name: Option<String>,
254}
255
256impl Job {
257    /// Create a new job with given ID, weight, and estimated time.
258    pub fn new(id: u64, weight: f64, estimated_time: f64) -> Self {
259        let weight = if weight.is_nan() {
260            DEFAULT_W_MIN
261        } else if weight.is_infinite() {
262            if weight.is_sign_positive() {
263                DEFAULT_W_MAX
264            } else {
265                DEFAULT_W_MIN
266            }
267        } else {
268            weight.clamp(DEFAULT_W_MIN, DEFAULT_W_MAX)
269        };
270        let estimated_time = if estimated_time.is_nan() {
271            DEFAULT_P_MAX_MS
272        } else if estimated_time.is_infinite() {
273            if estimated_time.is_sign_positive() {
274                DEFAULT_P_MAX_MS
275            } else {
276                DEFAULT_P_MIN_MS
277            }
278        } else {
279            estimated_time.clamp(DEFAULT_P_MIN_MS, DEFAULT_P_MAX_MS)
280        };
281        Self {
282            id,
283            weight,
284            remaining_time: estimated_time,
285            total_time: estimated_time,
286            arrival_time: 0.0,
287            arrival_seq: 0,
288            estimate_source: EstimateSource::Explicit,
289            weight_source: WeightSource::Explicit,
290            name: None,
291        }
292    }
293
294    /// Create a job with a name.
295    pub fn with_name(id: u64, weight: f64, estimated_time: f64, name: impl Into<String>) -> Self {
296        let mut job = Self::new(id, weight, estimated_time);
297        job.name = Some(name.into());
298        job
299    }
300
301    /// Set estimate and weight sources.
302    pub fn with_sources(
303        mut self,
304        weight_source: WeightSource,
305        estimate_source: EstimateSource,
306    ) -> Self {
307        self.weight_source = weight_source;
308        self.estimate_source = estimate_source;
309        self
310    }
311
312    /// Fraction of job completed.
313    pub fn progress(&self) -> f64 {
314        if self.total_time <= 0.0 {
315            1.0
316        } else {
317            1.0 - (self.remaining_time / self.total_time).clamp(0.0, 1.0)
318        }
319    }
320
321    /// Is the job complete?
322    pub fn is_complete(&self) -> bool {
323        self.remaining_time <= 0.0
324    }
325}
326
327/// Priority wrapper for the binary heap (max-heap, so we negate priority).
328#[derive(Debug, Clone)]
329struct PriorityJob {
330    priority: f64,
331    base_ratio: f64,
332    job: Job,
333    mode: SchedulingMode,
334}
335
336impl PartialEq for PriorityJob {
337    fn eq(&self, other: &Self) -> bool {
338        self.job.id == other.job.id
339    }
340}
341
342impl Eq for PriorityJob {}
343
344impl PartialOrd for PriorityJob {
345    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
346        Some(self.cmp(other))
347    }
348}
349
350impl Ord for PriorityJob {
351    fn cmp(&self, other: &Self) -> Ordering {
352        if self.mode == SchedulingMode::Fifo || other.mode == SchedulingMode::Fifo {
353            return other
354                .job
355                .arrival_seq
356                .cmp(&self.job.arrival_seq)
357                .then_with(|| other.job.id.cmp(&self.job.id));
358        }
359        // Higher priority comes first (max-heap)
360        self.priority
361            .total_cmp(&other.priority)
362            // Tie-break 1: base ratio (w/p)
363            .then_with(|| self.base_ratio.total_cmp(&other.base_ratio))
364            // Tie-break 2: higher weight
365            .then_with(|| self.job.weight.total_cmp(&other.job.weight))
366            // Tie-break 3: shorter remaining time
367            .then_with(|| other.job.remaining_time.total_cmp(&self.job.remaining_time))
368            // Tie-break 4: earlier arrival sequence
369            .then_with(|| other.job.arrival_seq.cmp(&self.job.arrival_seq))
370            // Tie-break 5: lower job id
371            .then_with(|| other.job.id.cmp(&self.job.id))
372    }
373}
374
375/// Evidence for scheduling decisions.
376#[derive(Debug, Clone)]
377pub struct SchedulingEvidence {
378    /// Current time.
379    pub current_time: f64,
380
381    /// Selected job ID (if any).
382    pub selected_job_id: Option<u64>,
383
384    /// Queue length.
385    pub queue_length: usize,
386
387    /// Mean wait time in queue.
388    pub mean_wait_time: f64,
389
390    /// Max wait time in queue.
391    pub max_wait_time: f64,
392
393    /// Reason for selection.
394    pub reason: SelectionReason,
395
396    /// Tie-break reason for the selected job (if applicable).
397    pub tie_break_reason: Option<TieBreakReason>,
398
399    /// Per-job evidence entries (ordered by scheduler priority).
400    pub jobs: Vec<JobEvidence>,
401}
402
403/// Evidence entry for a single job in the queue.
404#[derive(Debug, Clone)]
405pub struct JobEvidence {
406    /// Job id.
407    pub job_id: u64,
408    /// Optional name.
409    pub name: Option<String>,
410    /// Processing-time estimate (ms).
411    pub estimate_ms: f64,
412    /// Weight (importance).
413    pub weight: f64,
414    /// Base ratio (w/p).
415    pub ratio: f64,
416    /// Aging contribution (`aging_factor * age_ms`).
417    pub aging_reward: f64,
418    /// Starvation floor (`ratio * starve_boost_ratio`) when guard applies, else 0.
419    pub starvation_floor: f64,
420    /// Age in queue (ms).
421    pub age_ms: f64,
422    /// Effective priority (ratio + aging, with starvation guard).
423    pub effective_priority: f64,
424    /// Monotone loss proxy minimized by policy (lower is better).
425    pub objective_loss_proxy: f64,
426    /// Estimate source.
427    pub estimate_source: EstimateSource,
428    /// Weight source.
429    pub weight_source: WeightSource,
430}
431
432/// Reason for job selection.
433#[derive(Debug, Clone, Copy, PartialEq, Eq)]
434pub enum SelectionReason {
435    /// No jobs in queue.
436    QueueEmpty,
437    /// Selected by SRPT (shortest remaining time).
438    ShortestRemaining,
439    /// Selected by Smith's rule (weight/time).
440    HighestWeightedPriority,
441    /// Selected by FIFO override.
442    Fifo,
443    /// Selected due to aging (waited too long).
444    AgingBoost,
445    /// Continued from preemption.
446    Continuation,
447}
448
449impl SelectionReason {
450    fn as_str(self) -> &'static str {
451        match self {
452            Self::QueueEmpty => "queue_empty",
453            Self::ShortestRemaining => "shortest_remaining",
454            Self::HighestWeightedPriority => "highest_weighted_priority",
455            Self::Fifo => "fifo",
456            Self::AgingBoost => "aging_boost",
457            Self::Continuation => "continuation",
458        }
459    }
460}
461
462/// Source of a processing-time estimate.
463#[derive(Debug, Clone, Copy, PartialEq, Eq)]
464pub enum EstimateSource {
465    /// Explicit estimate provided by caller.
466    Explicit,
467    /// Historical estimate derived from prior runs.
468    Historical,
469    /// Default estimate (fallback).
470    Default,
471    /// Unknown estimate (no data).
472    Unknown,
473}
474
475impl EstimateSource {
476    fn as_str(self) -> &'static str {
477        match self {
478            Self::Explicit => "explicit",
479            Self::Historical => "historical",
480            Self::Default => "default",
481            Self::Unknown => "unknown",
482        }
483    }
484}
485
486/// Source of a weight/importance value.
487#[derive(Debug, Clone, Copy, PartialEq, Eq)]
488pub enum WeightSource {
489    /// Explicit weight provided by caller.
490    Explicit,
491    /// Default weight (fallback).
492    Default,
493    /// Unknown weight (no data).
494    Unknown,
495}
496
497impl WeightSource {
498    fn as_str(self) -> &'static str {
499        match self {
500            Self::Explicit => "explicit",
501            Self::Default => "default",
502            Self::Unknown => "unknown",
503        }
504    }
505}
506
507/// Tie-break reason for ordering decisions.
508#[derive(Debug, Clone, Copy, PartialEq, Eq)]
509pub enum TieBreakReason {
510    /// Effective priority (base ratio + aging) decided.
511    EffectivePriority,
512    /// Base ratio (w/p) decided.
513    BaseRatio,
514    /// Weight decided.
515    Weight,
516    /// Remaining time decided.
517    RemainingTime,
518    /// Arrival sequence decided.
519    ArrivalSeq,
520    /// Job id decided.
521    JobId,
522    /// Continued current job without comparison.
523    Continuation,
524}
525
526impl TieBreakReason {
527    fn as_str(self) -> &'static str {
528        match self {
529            Self::EffectivePriority => "effective_priority",
530            Self::BaseRatio => "base_ratio",
531            Self::Weight => "weight",
532            Self::RemainingTime => "remaining_time",
533            Self::ArrivalSeq => "arrival_seq",
534            Self::JobId => "job_id",
535            Self::Continuation => "continuation",
536        }
537    }
538}
539
540/// Effective scheduling discipline.
541#[derive(Debug, Clone, Copy, PartialEq, Eq)]
542pub enum SchedulingMode {
543    /// Smith's rule (weight / remaining time).
544    Smith,
545    /// SRPT (shortest remaining processing time).
546    Srpt,
547    /// FIFO (arrival order).
548    Fifo,
549}
550
551impl SchedulingEvidence {
552    /// Serialize scheduling evidence to JSONL with the supplied event tag.
553    #[must_use]
554    pub fn to_jsonl(&self, event: &str) -> String {
555        let mut out = String::with_capacity(256 + (self.jobs.len() * 64));
556        out.push_str("{\"event\":\"");
557        out.push_str(&escape_json(event));
558        out.push_str("\",\"current_time\":");
559        let _ = write!(out, "{:.6}", self.current_time);
560        out.push_str(",\"selected_job_id\":");
561        match self.selected_job_id {
562            Some(id) => {
563                let _ = write!(out, "{id}");
564            }
565            None => out.push_str("null"),
566        }
567        out.push_str(",\"queue_length\":");
568        let _ = write!(out, "{}", self.queue_length);
569        out.push_str(",\"mean_wait_time\":");
570        let _ = write!(out, "{:.6}", self.mean_wait_time);
571        out.push_str(",\"max_wait_time\":");
572        let _ = write!(out, "{:.6}", self.max_wait_time);
573        out.push_str(",\"reason\":\"");
574        out.push_str(self.reason.as_str());
575        out.push('"');
576        out.push_str(",\"tie_break_reason\":");
577        match self.tie_break_reason {
578            Some(reason) => {
579                out.push('"');
580                out.push_str(reason.as_str());
581                out.push('"');
582            }
583            None => out.push_str("null"),
584        }
585        out.push_str(",\"jobs\":[");
586        for (idx, job) in self.jobs.iter().enumerate() {
587            if idx > 0 {
588                out.push(',');
589            }
590            out.push_str(&job.to_json());
591        }
592        out.push_str("]}");
593        out
594    }
595}
596
597impl JobEvidence {
598    fn to_json(&self) -> String {
599        let mut out = String::with_capacity(128);
600        out.push_str("{\"job_id\":");
601        let _ = write!(out, "{}", self.job_id);
602        out.push_str(",\"name\":");
603        match &self.name {
604            Some(name) => {
605                out.push('"');
606                out.push_str(&escape_json(name));
607                out.push('"');
608            }
609            None => out.push_str("null"),
610        }
611        out.push_str(",\"estimate_ms\":");
612        let _ = write!(out, "{:.6}", self.estimate_ms);
613        out.push_str(",\"weight\":");
614        let _ = write!(out, "{:.6}", self.weight);
615        out.push_str(",\"ratio\":");
616        let _ = write!(out, "{:.6}", self.ratio);
617        out.push_str(",\"aging_reward\":");
618        let _ = write!(out, "{:.6}", self.aging_reward);
619        out.push_str(",\"starvation_floor\":");
620        let _ = write!(out, "{:.6}", self.starvation_floor);
621        out.push_str(",\"age_ms\":");
622        let _ = write!(out, "{:.6}", self.age_ms);
623        out.push_str(",\"effective_priority\":");
624        let _ = write!(out, "{:.6}", self.effective_priority);
625        out.push_str(",\"objective_loss_proxy\":");
626        let _ = write!(out, "{:.6}", self.objective_loss_proxy);
627        out.push_str(",\"estimate_source\":\"");
628        out.push_str(self.estimate_source.as_str());
629        out.push('"');
630        out.push_str(",\"weight_source\":\"");
631        out.push_str(self.weight_source.as_str());
632        out.push('"');
633        out.push('}');
634        out
635    }
636}
637
638// TODO(#32): Consolidate with the shared `escape_json` in
639// `ftui-demo-showcase/src/test_logging.rs` once the shared logger can be a
640// dependency of ftui-runtime (or is extracted to a lower-level crate).
641pub(crate) fn escape_json(input: &str) -> String {
642    let mut out = String::with_capacity(input.len() + 8);
643    for ch in input.chars() {
644        match ch {
645            '"' => out.push_str("\\\""),
646            '\\' => out.push_str("\\\\"),
647            '\n' => out.push_str("\\n"),
648            '\r' => out.push_str("\\r"),
649            '\t' => out.push_str("\\t"),
650            '\u{08}' => out.push_str("\\b"),
651            '\u{0C}' => out.push_str("\\f"),
652            c if c < ' ' => {
653                let _ = write!(out, "\\u{:04x}", c as u32);
654            }
655            _ => out.push(ch),
656        }
657    }
658    out
659}
660
661/// Scheduler statistics.
662#[derive(Debug, Clone, Default)]
663pub struct SchedulerStats {
664    /// Total jobs submitted.
665    pub total_submitted: u64,
666
667    /// Total jobs completed.
668    pub total_completed: u64,
669
670    /// Total jobs rejected (queue full).
671    pub total_rejected: u64,
672
673    /// Total preemptions.
674    pub total_preemptions: u64,
675
676    /// Total time processing.
677    pub total_processing_time: f64,
678
679    /// Sum of response times (for mean calculation).
680    pub total_response_time: f64,
681
682    /// Max response time observed.
683    pub max_response_time: f64,
684
685    /// Current queue length.
686    pub queue_length: usize,
687}
688
689impl SchedulerStats {
690    /// Mean response time.
691    pub fn mean_response_time(&self) -> f64 {
692        if self.total_completed > 0 {
693            self.total_response_time / self.total_completed as f64
694        } else {
695            0.0
696        }
697    }
698
699    /// Throughput (jobs per time unit).
700    pub fn throughput(&self) -> f64 {
701        if self.total_processing_time > 0.0 {
702            self.total_completed as f64 / self.total_processing_time
703        } else {
704            0.0
705        }
706    }
707}
708
709/// Queueing theory scheduler with fair SRPT.
710#[derive(Debug)]
711pub struct QueueingScheduler {
712    config: SchedulerConfig,
713
714    /// Priority queue of jobs.
715    queue: BinaryHeap<PriorityJob>,
716
717    /// Currently running job (if preemptive and processing).
718    current_job: Option<Job>,
719
720    /// Current simulation time.
721    current_time: f64,
722
723    /// Next job ID.
724    next_job_id: u64,
725
726    /// Next arrival sequence number.
727    next_arrival_seq: u64,
728
729    /// Statistics.
730    stats: SchedulerStats,
731}
732
733#[derive(Debug, Clone, Copy)]
734struct PriorityTerms {
735    aging_reward: f64,
736    starvation_floor: f64,
737    effective_priority: f64,
738}
739
740impl QueueingScheduler {
741    /// Create a new scheduler with given configuration.
742    pub fn new(config: SchedulerConfig) -> Self {
743        Self {
744            config,
745            queue: BinaryHeap::new(),
746            current_job: None,
747            current_time: 0.0,
748            next_job_id: 1,
749            next_arrival_seq: 1,
750            stats: SchedulerStats::default(),
751        }
752    }
753
754    /// Submit a new job to the scheduler.
755    ///
756    /// Returns the job ID if accepted, None if rejected (queue full).
757    pub fn submit(&mut self, weight: f64, estimated_time: f64) -> Option<u64> {
758        self.submit_named(weight, estimated_time, None::<&str>)
759    }
760
761    /// Submit a named job.
762    pub fn submit_named(
763        &mut self,
764        weight: f64,
765        estimated_time: f64,
766        name: Option<impl Into<String>>,
767    ) -> Option<u64> {
768        self.submit_with_sources(
769            weight,
770            estimated_time,
771            WeightSource::Explicit,
772            EstimateSource::Explicit,
773            name,
774        )
775    }
776
777    /// Submit a job with explicit estimate/weight sources for evidence logging.
778    pub fn submit_with_sources(
779        &mut self,
780        weight: f64,
781        estimated_time: f64,
782        weight_source: WeightSource,
783        estimate_source: EstimateSource,
784        name: Option<impl Into<String>>,
785    ) -> Option<u64> {
786        if self.queue.len() >= self.config.max_queue_size {
787            self.stats.total_rejected += 1;
788            return None;
789        }
790
791        let id = self.next_job_id;
792        self.next_job_id += 1;
793
794        // Build from raw caller values, then normalize against this scheduler's config.
795        let mut job = Job {
796            id,
797            weight,
798            remaining_time: estimated_time,
799            total_time: estimated_time,
800            arrival_time: 0.0,
801            arrival_seq: 0,
802            estimate_source,
803            weight_source,
804            name: None,
805        };
806        job.weight = self.normalize_weight_with_source(job.weight, job.weight_source);
807        job.remaining_time =
808            self.normalize_time_with_source(job.remaining_time, job.estimate_source);
809        job.total_time = job.remaining_time;
810        job.arrival_time = self.current_time;
811        job.arrival_seq = self.next_arrival_seq;
812        self.next_arrival_seq += 1;
813        if let Some(n) = name {
814            job.name = Some(n.into());
815        }
816
817        let priority_job = self.make_priority_job(job);
818        self.queue.push(priority_job);
819
820        self.stats.total_submitted += 1;
821        self.stats.queue_length = self.queue.len();
822
823        // Check for preemption
824        if self.config.preemptive {
825            self.maybe_preempt();
826        }
827
828        Some(id)
829    }
830
831    /// Advance time by the given amount and process jobs.
832    ///
833    /// Returns a list of completed job IDs.
834    pub fn tick(&mut self, delta_time: f64) -> Vec<u64> {
835        let mut completed = Vec::new();
836        if !delta_time.is_finite() || delta_time <= 0.0 {
837            return completed;
838        }
839
840        let mut remaining_time = delta_time;
841        let mut now = self.current_time;
842        let mut processed_time = 0.0;
843
844        while remaining_time > 0.0 {
845            // Get or select next job
846            let Some(mut job) = (if let Some(j) = self.current_job.take() {
847                Some(j)
848            } else {
849                self.queue.pop().map(|pj| pj.job)
850            }) else {
851                now += remaining_time;
852                break; // Queue empty
853            };
854
855            // Process job
856            let process_time = remaining_time.min(job.remaining_time);
857            job.remaining_time -= process_time;
858            remaining_time -= process_time;
859            now += process_time;
860            processed_time += process_time;
861
862            if job.is_complete() {
863                // Job completed
864                let response_time = now - job.arrival_time;
865                self.stats.total_response_time += response_time;
866                self.stats.max_response_time = self.stats.max_response_time.max(response_time);
867                self.stats.total_completed += 1;
868                completed.push(job.id);
869            } else {
870                // Job not complete, save for next tick
871                self.current_job = Some(job);
872            }
873        }
874
875        self.stats.total_processing_time += processed_time;
876        self.current_time = now;
877        // Recompute priorities for aged jobs
878        self.refresh_priorities();
879
880        self.stats.queue_length = self.queue.len();
881        completed
882    }
883
884    /// Select the next job to run without advancing time.
885    pub fn peek_next(&self) -> Option<&Job> {
886        self.current_job
887            .as_ref()
888            .or_else(|| self.queue.peek().map(|pj| &pj.job))
889    }
890
891    /// Get scheduling evidence for the current state.
892    pub fn evidence(&self) -> SchedulingEvidence {
893        let (mean_wait, max_wait) = self.compute_wait_stats();
894
895        let mut candidates: Vec<PriorityJob> = self
896            .queue
897            .iter()
898            .map(|pj| self.make_priority_job(pj.job.clone()))
899            .collect();
900
901        if let Some(ref current) = self.current_job {
902            candidates.push(self.make_priority_job(current.clone()));
903        }
904
905        candidates.sort_by(|a, b| b.cmp(a));
906
907        let selected_job_id = if let Some(ref current) = self.current_job {
908            Some(current.id)
909        } else {
910            candidates.first().map(|pj| pj.job.id)
911        };
912
913        let tie_break_reason = if self.current_job.is_some() {
914            Some(TieBreakReason::Continuation)
915        } else if candidates.len() > 1 {
916            Some(self.tie_break_reason(&candidates[0], &candidates[1]))
917        } else {
918            None
919        };
920
921        let reason = if self.queue.is_empty() && self.current_job.is_none() {
922            SelectionReason::QueueEmpty
923        } else if self.current_job.is_some() {
924            SelectionReason::Continuation
925        } else if self.config.mode() == SchedulingMode::Fifo {
926            SelectionReason::Fifo
927        } else if let Some(pj) = candidates.first() {
928            let wait_time = (self.current_time - pj.job.arrival_time).max(0.0);
929            let aging_contribution = self.config.aging_factor * wait_time;
930            let aging_boost = (self.config.wait_starve_ms > 0.0
931                && wait_time >= self.config.wait_starve_ms)
932                || aging_contribution > pj.base_ratio * 0.5;
933            if aging_boost {
934                SelectionReason::AgingBoost
935            } else if self.config.smith_enabled && pj.job.weight > 1.0 {
936                SelectionReason::HighestWeightedPriority
937            } else {
938                SelectionReason::ShortestRemaining
939            }
940        } else {
941            SelectionReason::QueueEmpty
942        };
943
944        let jobs = candidates
945            .iter()
946            .map(|pj| {
947                let age_ms = (self.current_time - pj.job.arrival_time).max(0.0);
948                let terms = self.compute_priority_terms(&pj.job);
949                JobEvidence {
950                    job_id: pj.job.id,
951                    name: pj.job.name.clone(),
952                    estimate_ms: pj.job.remaining_time,
953                    weight: pj.job.weight,
954                    ratio: pj.base_ratio,
955                    aging_reward: terms.aging_reward,
956                    starvation_floor: terms.starvation_floor,
957                    age_ms,
958                    effective_priority: pj.priority,
959                    objective_loss_proxy: 1.0 / pj.priority.max(self.config.w_min),
960                    estimate_source: pj.job.estimate_source,
961                    weight_source: pj.job.weight_source,
962                }
963            })
964            .collect();
965
966        SchedulingEvidence {
967            current_time: self.current_time,
968            selected_job_id,
969            queue_length: self.queue.len() + if self.current_job.is_some() { 1 } else { 0 },
970            mean_wait_time: mean_wait,
971            max_wait_time: max_wait,
972            reason,
973            tie_break_reason,
974            jobs,
975        }
976    }
977
978    /// Get current statistics.
979    pub fn stats(&self) -> SchedulerStats {
980        let mut stats = self.stats.clone();
981        stats.queue_length = self.queue.len() + if self.current_job.is_some() { 1 } else { 0 };
982        stats
983    }
984
985    /// Configured queue capacity used for backpressure decisions.
986    #[must_use]
987    pub const fn max_queue_size(&self) -> usize {
988        self.config.max_queue_size
989    }
990
991    /// Cancel a job by ID.
992    pub fn cancel(&mut self, job_id: u64) -> bool {
993        // Check current job
994        if let Some(ref j) = self.current_job
995            && j.id == job_id
996        {
997            self.current_job = None;
998            self.stats.queue_length = self.queue.len();
999            return true;
1000        }
1001
1002        // Remove from queue (rebuild without the job)
1003        let old_len = self.queue.len();
1004        let jobs: Vec<_> = self
1005            .queue
1006            .drain()
1007            .filter(|pj| pj.job.id != job_id)
1008            .collect();
1009        self.queue = jobs.into_iter().collect();
1010
1011        self.stats.queue_length = self.queue.len();
1012        old_len != self.queue.len()
1013    }
1014
1015    /// Clear all jobs.
1016    pub fn clear(&mut self) {
1017        self.queue.clear();
1018        self.current_job = None;
1019        self.stats.queue_length = 0;
1020    }
1021
1022    /// Reset scheduler state.
1023    pub fn reset(&mut self) {
1024        self.queue.clear();
1025        self.current_job = None;
1026        self.current_time = 0.0;
1027        self.next_job_id = 1;
1028        self.next_arrival_seq = 1;
1029        self.stats = SchedulerStats::default();
1030    }
1031
1032    // --- Internal Methods ---
1033
1034    /// Normalize a weight into the configured clamp range.
1035    fn normalize_weight(&self, weight: f64) -> f64 {
1036        if weight.is_nan() {
1037            return self.config.w_min;
1038        }
1039        if weight.is_infinite() {
1040            return if weight.is_sign_positive() {
1041                self.config.w_max
1042            } else {
1043                self.config.w_min
1044            };
1045        }
1046        // Not `f64::clamp`, which panics when the bounds are inverted or NaN:
1047        // `SchedulerConfig`'s fields are public and unchecked, so a
1048        // `w_min > w_max` made every submit panic. Here the upper bound wins
1049        // and a NaN bound is ignored.
1050        weight.max(self.config.w_min).min(self.config.w_max)
1051    }
1052
1053    /// Normalize a processing-time estimate into the configured clamp range.
1054    fn normalize_time(&self, estimate_ms: f64) -> f64 {
1055        if estimate_ms.is_nan() {
1056            return self.config.p_max_ms;
1057        }
1058        if estimate_ms.is_infinite() {
1059            return if estimate_ms.is_sign_positive() {
1060                self.config.p_max_ms
1061            } else {
1062                self.config.p_min_ms
1063            };
1064        }
1065        // As in `normalize_weight`: `clamp` panics on inverted or NaN bounds.
1066        estimate_ms
1067            .max(self.config.p_min_ms)
1068            .min(self.config.p_max_ms)
1069    }
1070
1071    /// Resolve a weight based on its declared source, then clamp to config limits.
1072    fn normalize_weight_with_source(&self, weight: f64, source: WeightSource) -> f64 {
1073        let resolved = match source {
1074            WeightSource::Explicit => weight,
1075            WeightSource::Default => self.config.weight_default,
1076            WeightSource::Unknown => self.config.weight_unknown,
1077        };
1078        self.normalize_weight(resolved)
1079    }
1080
1081    /// Resolve an estimate based on its declared source, then clamp to config limits.
1082    fn normalize_time_with_source(&self, estimate_ms: f64, source: EstimateSource) -> f64 {
1083        let resolved = match source {
1084            EstimateSource::Explicit | EstimateSource::Historical => estimate_ms,
1085            EstimateSource::Default => self.config.estimate_default_ms,
1086            EstimateSource::Unknown => self.config.estimate_unknown_ms,
1087        };
1088        self.normalize_time(resolved)
1089    }
1090
1091    /// Compute base ratio (w/p) for Smith's rule.
1092    fn compute_base_ratio(&self, job: &Job) -> f64 {
1093        if self.config.mode() == SchedulingMode::Fifo {
1094            return 0.0;
1095        }
1096        let remaining = job.remaining_time.max(self.config.p_min_ms);
1097        let weight = match self.config.mode() {
1098            SchedulingMode::Smith => job.weight,
1099            SchedulingMode::Srpt => 1.0,
1100            SchedulingMode::Fifo => 0.0,
1101        };
1102        weight / remaining
1103    }
1104
1105    /// Compute the scheduling objective terms.
1106    ///
1107    /// We maximize:
1108    /// `priority = base_ratio + aging_reward`, then apply starvation floor.
1109    ///
1110    /// The equivalent minimized quantity is:
1111    /// `loss_proxy = 1 / max(priority, w_min)`.
1112    fn compute_priority_terms(&self, job: &Job) -> PriorityTerms {
1113        if self.config.mode() == SchedulingMode::Fifo {
1114            return PriorityTerms {
1115                aging_reward: 0.0,
1116                starvation_floor: 0.0,
1117                effective_priority: 0.0,
1118            };
1119        }
1120
1121        let base_ratio = self.compute_base_ratio(job);
1122        let wait_time = (self.current_time - job.arrival_time).max(0.0);
1123        let aging_reward = self.config.aging_factor * wait_time;
1124        let starvation_floor =
1125            if self.config.wait_starve_ms > 0.0 && wait_time >= self.config.wait_starve_ms {
1126                base_ratio * self.config.starve_boost_ratio
1127            } else {
1128                0.0
1129            };
1130
1131        let effective_priority = (base_ratio + aging_reward).max(starvation_floor);
1132
1133        PriorityTerms {
1134            aging_reward,
1135            starvation_floor,
1136            effective_priority,
1137        }
1138    }
1139
1140    /// Compute effective priority (base ratio + aging, with starvation guard).
1141    fn compute_priority(&self, job: &Job) -> f64 {
1142        self.compute_priority_terms(job).effective_priority
1143    }
1144
1145    /// Build a priority-queue entry for a job.
1146    fn make_priority_job(&self, job: Job) -> PriorityJob {
1147        let base_ratio = self.compute_base_ratio(&job);
1148        let priority = self.compute_priority(&job);
1149        PriorityJob {
1150            priority,
1151            base_ratio,
1152            job,
1153            mode: self.config.mode(),
1154        }
1155    }
1156
1157    /// Determine the tie-break reason between two candidates.
1158    fn tie_break_reason(&self, a: &PriorityJob, b: &PriorityJob) -> TieBreakReason {
1159        if self.config.mode() == SchedulingMode::Fifo {
1160            if a.job.arrival_seq != b.job.arrival_seq {
1161                return TieBreakReason::ArrivalSeq;
1162            }
1163            return TieBreakReason::JobId;
1164        }
1165        if a.priority.total_cmp(&b.priority) != Ordering::Equal {
1166            TieBreakReason::EffectivePriority
1167        } else if a.base_ratio.total_cmp(&b.base_ratio) != Ordering::Equal {
1168            TieBreakReason::BaseRatio
1169        } else if a.job.weight.total_cmp(&b.job.weight) != Ordering::Equal {
1170            TieBreakReason::Weight
1171        } else if a.job.remaining_time.total_cmp(&b.job.remaining_time) != Ordering::Equal {
1172            TieBreakReason::RemainingTime
1173        } else if a.job.arrival_seq != b.job.arrival_seq {
1174            TieBreakReason::ArrivalSeq
1175        } else {
1176            TieBreakReason::JobId
1177        }
1178    }
1179
1180    /// Check if current job should be preempted.
1181    fn maybe_preempt(&mut self) {
1182        if self.config.mode() == SchedulingMode::Fifo {
1183            return;
1184        }
1185        if let Some(ref current) = self.current_job
1186            && let Some(pj) = self.queue.peek()
1187        {
1188            let current_pj = self.make_priority_job(current.clone());
1189            if pj.cmp(&current_pj) == Ordering::Greater {
1190                // Preempt
1191                let old = self
1192                    .current_job
1193                    .take()
1194                    .expect("current_job guaranteed by if-let guard");
1195                let priority_job = self.make_priority_job(old);
1196                self.queue.push(priority_job);
1197                self.stats.total_preemptions += 1;
1198            }
1199        }
1200    }
1201
1202    /// Refresh priorities for all queued jobs (aging effect).
1203    fn refresh_priorities(&mut self) {
1204        let jobs: Vec<_> = self.queue.drain().map(|pj| pj.job).collect();
1205        for job in jobs {
1206            let priority_job = self.make_priority_job(job);
1207            self.queue.push(priority_job);
1208        }
1209    }
1210
1211    /// Compute wait time statistics.
1212    fn compute_wait_stats(&self) -> (f64, f64) {
1213        let mut total_wait = 0.0;
1214        let mut max_wait = 0.0f64;
1215        let mut count = 0;
1216
1217        for pj in self.queue.iter() {
1218            let wait = (self.current_time - pj.job.arrival_time).max(0.0);
1219            total_wait += wait;
1220            max_wait = max_wait.max(wait);
1221            count += 1;
1222        }
1223
1224        if let Some(ref j) = self.current_job {
1225            let wait = (self.current_time - j.arrival_time).max(0.0);
1226            total_wait += wait;
1227            max_wait = max_wait.max(wait);
1228            count += 1;
1229        }
1230
1231        let mean = if count > 0 {
1232            total_wait / count as f64
1233        } else {
1234            0.0
1235        };
1236        (mean, max_wait)
1237    }
1238}
1239
1240// =============================================================================
1241// Unit Tests (bd-13pq.7)
1242// =============================================================================
1243
1244#[cfg(test)]
1245mod tests {
1246    use super::*;
1247    use std::collections::HashMap;
1248
1249    fn test_config() -> SchedulerConfig {
1250        SchedulerConfig {
1251            aging_factor: 0.001,
1252            p_min_ms: DEFAULT_P_MIN_MS,
1253            p_max_ms: DEFAULT_P_MAX_MS,
1254            estimate_default_ms: DEFAULT_ESTIMATE_DEFAULT_MS,
1255            estimate_unknown_ms: DEFAULT_ESTIMATE_UNKNOWN_MS,
1256            w_min: DEFAULT_W_MIN,
1257            w_max: DEFAULT_W_MAX,
1258            weight_default: DEFAULT_WEIGHT_DEFAULT,
1259            weight_unknown: DEFAULT_WEIGHT_UNKNOWN,
1260            wait_starve_ms: DEFAULT_WAIT_STARVE_MS,
1261            starve_boost_ratio: DEFAULT_STARVE_BOOST_RATIO,
1262            smith_enabled: true,
1263            force_fifo: false,
1264            max_queue_size: 100,
1265            preemptive: true,
1266            time_quantum: 10.0,
1267            enable_logging: false,
1268        }
1269    }
1270
1271    #[derive(Clone, Copy, Debug)]
1272    struct WorkloadJob {
1273        arrival: u64,
1274        weight: f64,
1275        duration: f64,
1276    }
1277
1278    #[derive(Clone, Copy, Debug, Eq, PartialEq)]
1279    enum SimPolicy {
1280        Smith,
1281        Fifo,
1282    }
1283
1284    #[derive(Debug)]
1285    struct SimulationMetrics {
1286        mean: f64,
1287        p95: f64,
1288        p99: f64,
1289        max: f64,
1290        job_count: usize,
1291        completion_order: Vec<u64>,
1292    }
1293
1294    fn mixed_workload() -> Vec<WorkloadJob> {
1295        let mut jobs = Vec::new();
1296        jobs.push(WorkloadJob {
1297            arrival: 0,
1298            weight: 1.0,
1299            duration: 100.0,
1300        });
1301        for t in 1..=200u64 {
1302            jobs.push(WorkloadJob {
1303                arrival: t,
1304                weight: 1.0,
1305                duration: 1.0,
1306            });
1307        }
1308        jobs
1309    }
1310
1311    fn percentile(sorted: &[f64], p: f64) -> f64 {
1312        if sorted.is_empty() {
1313            return 0.0;
1314        }
1315        let idx = ((sorted.len() as f64 - 1.0) * p).ceil() as usize;
1316        sorted[idx.min(sorted.len() - 1)]
1317    }
1318
1319    fn summary_json(policy: SimPolicy, metrics: &SimulationMetrics) -> String {
1320        let policy = match policy {
1321            SimPolicy::Smith => "Smith",
1322            SimPolicy::Fifo => "Fifo",
1323        };
1324        let head: Vec<String> = metrics
1325            .completion_order
1326            .iter()
1327            .take(8)
1328            .map(|id| id.to_string())
1329            .collect();
1330        let tail: Vec<String> = metrics
1331            .completion_order
1332            .iter()
1333            .rev()
1334            .take(3)
1335            .collect::<Vec<_>>()
1336            .into_iter()
1337            .rev()
1338            .map(|id| id.to_string())
1339            .collect();
1340        format!(
1341            "{{\"policy\":\"{policy}\",\"jobs\":{jobs},\"mean\":{mean:.3},\"p95\":{p95:.3},\"p99\":{p99:.3},\"max\":{max:.3},\"order_head\":[{head}],\"order_tail\":[{tail}]}}",
1342            policy = policy,
1343            jobs = metrics.job_count,
1344            mean = metrics.mean,
1345            p95 = metrics.p95,
1346            p99 = metrics.p99,
1347            max = metrics.max,
1348            head = head.join(","),
1349            tail = tail.join(",")
1350        )
1351    }
1352
1353    fn workload_summary_json(workload: &[WorkloadJob]) -> String {
1354        if workload.is_empty() {
1355            return "{\"workload\":\"empty\"}".to_string();
1356        }
1357        let mut min_arrival = u64::MAX;
1358        let mut max_arrival = 0u64;
1359        let mut min_duration = f64::INFINITY;
1360        let mut max_duration: f64 = 0.0;
1361        let mut total_work: f64 = 0.0;
1362        let mut long_jobs = 0usize;
1363        let long_threshold = 10.0;
1364
1365        for job in workload {
1366            min_arrival = min_arrival.min(job.arrival);
1367            max_arrival = max_arrival.max(job.arrival);
1368            min_duration = min_duration.min(job.duration);
1369            max_duration = max_duration.max(job.duration);
1370            total_work += job.duration;
1371            if job.duration >= long_threshold {
1372                long_jobs += 1;
1373            }
1374        }
1375
1376        format!(
1377            "{{\"workload\":\"mixed\",\"jobs\":{jobs},\"arrival_min\":{arrival_min},\"arrival_max\":{arrival_max},\"duration_min\":{duration_min:.3},\"duration_max\":{duration_max:.3},\"total_work\":{total_work:.3},\"long_jobs\":{long_jobs},\"long_threshold\":{long_threshold:.1}}}",
1378            jobs = workload.len(),
1379            arrival_min = min_arrival,
1380            arrival_max = max_arrival,
1381            duration_min = min_duration,
1382            duration_max = max_duration,
1383            total_work = total_work,
1384            long_jobs = long_jobs,
1385            long_threshold = long_threshold
1386        )
1387    }
1388
1389    fn simulate_policy(policy: SimPolicy, workload: &[WorkloadJob]) -> SimulationMetrics {
1390        let mut config = test_config();
1391        config.aging_factor = 0.0;
1392        config.wait_starve_ms = 0.0;
1393        config.starve_boost_ratio = 1.0;
1394        config.smith_enabled = policy == SimPolicy::Smith;
1395        config.force_fifo = policy == SimPolicy::Fifo;
1396        config.preemptive = true;
1397
1398        let mut scheduler = QueueingScheduler::new(config);
1399        let mut arrivals = workload.to_vec();
1400        arrivals.sort_by_key(|job| job.arrival);
1401
1402        let mut arrival_times: HashMap<u64, f64> = HashMap::new();
1403        let mut response_times = Vec::with_capacity(arrivals.len());
1404        let mut completion_order = Vec::with_capacity(arrivals.len());
1405
1406        let mut idx = 0usize;
1407        let mut safety = 0usize;
1408
1409        while (idx < arrivals.len() || scheduler.peek_next().is_some()) && safety < 10_000 {
1410            let now = scheduler.current_time;
1411
1412            while idx < arrivals.len() && (arrivals[idx].arrival as f64) <= now + f64::EPSILON {
1413                let job = arrivals[idx];
1414                let id = scheduler
1415                    .submit(job.weight, job.duration)
1416                    .expect("queue capacity should not be exceeded");
1417                arrival_times.insert(id, scheduler.current_time);
1418                idx += 1;
1419            }
1420
1421            if scheduler.peek_next().is_none() {
1422                if idx < arrivals.len() {
1423                    let next_time = arrivals[idx].arrival as f64;
1424                    let delta = (next_time - scheduler.current_time).max(0.0);
1425                    let completed = scheduler.tick(delta);
1426                    for id in completed {
1427                        let arrival = arrival_times.get(&id).copied().unwrap_or(0.0);
1428                        response_times.push(scheduler.current_time - arrival);
1429                        completion_order.push(id);
1430                    }
1431                }
1432                safety += 1;
1433                continue;
1434            }
1435
1436            let completed = scheduler.tick(1.0);
1437            for id in completed {
1438                let arrival = arrival_times.get(&id).copied().unwrap_or(0.0);
1439                response_times.push(scheduler.current_time - arrival);
1440                completion_order.push(id);
1441            }
1442            safety += 1;
1443        }
1444
1445        assert_eq!(
1446            response_times.len(),
1447            arrivals.len(),
1448            "simulation did not complete all jobs"
1449        );
1450
1451        let mut sorted = response_times.clone();
1452        sorted.sort_by(|a, b| a.partial_cmp(b).unwrap());
1453
1454        let mean = response_times.iter().sum::<f64>() / response_times.len() as f64;
1455        let p95 = percentile(&sorted, 0.95);
1456        let p99 = percentile(&sorted, 0.99);
1457        let max = *sorted.last().unwrap_or(&0.0);
1458
1459        SimulationMetrics {
1460            mean,
1461            p95,
1462            p99,
1463            max,
1464            job_count: response_times.len(),
1465            completion_order,
1466        }
1467    }
1468
1469    // =========================================================================
1470    // Initialization tests
1471    // =========================================================================
1472
1473    #[test]
1474    fn new_creates_empty_scheduler() {
1475        let scheduler = QueueingScheduler::new(test_config());
1476        assert_eq!(scheduler.stats().queue_length, 0);
1477        assert!(scheduler.peek_next().is_none());
1478    }
1479
1480    #[test]
1481    fn default_config_valid() {
1482        let config = SchedulerConfig::default();
1483        let scheduler = QueueingScheduler::new(config);
1484        assert_eq!(scheduler.stats().queue_length, 0);
1485    }
1486
1487    // =========================================================================
1488    // Job submission tests
1489    // =========================================================================
1490
1491    #[test]
1492    fn submit_returns_job_id() {
1493        let mut scheduler = QueueingScheduler::new(test_config());
1494        let id = scheduler.submit(1.0, 10.0);
1495        assert_eq!(id, Some(1));
1496    }
1497
1498    #[test]
1499    fn submit_increments_job_id() {
1500        let mut scheduler = QueueingScheduler::new(test_config());
1501        let id1 = scheduler.submit(1.0, 10.0);
1502        let id2 = scheduler.submit(1.0, 10.0);
1503        assert_eq!(id1, Some(1));
1504        assert_eq!(id2, Some(2));
1505    }
1506
1507    #[test]
1508    fn submit_rejects_when_queue_full() {
1509        let mut config = test_config();
1510        config.max_queue_size = 2;
1511        let mut scheduler = QueueingScheduler::new(config);
1512
1513        assert!(scheduler.submit(1.0, 10.0).is_some());
1514        assert!(scheduler.submit(1.0, 10.0).is_some());
1515        assert!(scheduler.submit(1.0, 10.0).is_none()); // Rejected
1516        assert_eq!(scheduler.stats().total_rejected, 1);
1517    }
1518
1519    #[test]
1520    fn submit_named_job() {
1521        let mut scheduler = QueueingScheduler::new(test_config());
1522        let id = scheduler.submit_named(1.0, 10.0, Some("test-job"));
1523        assert!(id.is_some());
1524    }
1525
1526    // =========================================================================
1527    // SRPT ordering tests
1528    // =========================================================================
1529
1530    #[test]
1531    fn srpt_prefers_shorter_jobs() {
1532        let mut scheduler = QueueingScheduler::new(test_config());
1533
1534        scheduler.submit(1.0, 100.0); // Long job
1535        scheduler.submit(1.0, 10.0); // Short job
1536
1537        let next = scheduler.peek_next().unwrap();
1538        assert_eq!(next.remaining_time, 10.0); // Short job selected
1539    }
1540
1541    #[test]
1542    fn smith_rule_prefers_high_weight() {
1543        let mut scheduler = QueueingScheduler::new(test_config());
1544
1545        scheduler.submit(1.0, 10.0); // Low weight
1546        scheduler.submit(10.0, 10.0); // High weight
1547
1548        let next = scheduler.peek_next().unwrap();
1549        assert_eq!(next.weight, 10.0); // High weight selected
1550    }
1551
1552    #[test]
1553    fn smith_rule_balances_weight_and_time() {
1554        let mut scheduler = QueueingScheduler::new(test_config());
1555
1556        scheduler.submit(2.0, 20.0); // priority = 2/20 = 0.1
1557        scheduler.submit(1.0, 5.0); // priority = 1/5 = 0.2
1558
1559        let next = scheduler.peek_next().unwrap();
1560        assert_eq!(next.remaining_time, 5.0); // Higher priority
1561    }
1562
1563    // =========================================================================
1564    // Aging tests
1565    // =========================================================================
1566
1567    #[test]
1568    fn aging_increases_priority_over_time() {
1569        let mut scheduler = QueueingScheduler::new(test_config());
1570
1571        scheduler.submit(1.0, 100.0); // Long job
1572        scheduler.tick(0.0); // Process nothing, just advance
1573
1574        let before_aging = scheduler.compute_priority(scheduler.peek_next().unwrap());
1575
1576        scheduler.current_time = 100.0; // Advance time significantly
1577        scheduler.refresh_priorities();
1578
1579        let after_aging = scheduler.compute_priority(scheduler.peek_next().unwrap());
1580        assert!(
1581            after_aging > before_aging,
1582            "Priority should increase with wait time"
1583        );
1584    }
1585
1586    #[test]
1587    fn aging_prevents_starvation() {
1588        let mut config = test_config();
1589        config.aging_factor = 1.0; // High aging
1590        let mut scheduler = QueueingScheduler::new(config);
1591
1592        scheduler.submit(1.0, 1000.0); // Very long job
1593        scheduler.submit(1.0, 1.0); // Short job
1594
1595        // Initially, short job should be preferred
1596        assert_eq!(scheduler.peek_next().unwrap().remaining_time, 1.0);
1597
1598        // After the short job completes, long job should eventually run
1599        let completed = scheduler.tick(1.0);
1600        assert_eq!(completed.len(), 1);
1601
1602        assert!(scheduler.peek_next().is_some());
1603    }
1604
1605    // =========================================================================
1606    // Preemption tests
1607    // =========================================================================
1608
1609    #[test]
1610    fn preemption_when_higher_priority_arrives() {
1611        let mut scheduler = QueueingScheduler::new(test_config());
1612
1613        scheduler.submit(1.0, 100.0); // Start processing long job
1614        scheduler.tick(10.0); // Process 10 units
1615
1616        let before = scheduler.peek_next().unwrap().remaining_time;
1617        assert_eq!(before, 90.0);
1618
1619        scheduler.submit(1.0, 5.0); // Higher priority arrives
1620
1621        // Should now be processing the short job
1622        let next = scheduler.peek_next().unwrap();
1623        assert_eq!(next.remaining_time, 5.0);
1624
1625        // Stats should show preemption
1626        assert_eq!(scheduler.stats().total_preemptions, 1);
1627    }
1628
1629    #[test]
1630    fn no_preemption_when_disabled() {
1631        let mut config = test_config();
1632        config.preemptive = false;
1633        let mut scheduler = QueueingScheduler::new(config);
1634
1635        scheduler.submit(1.0, 100.0);
1636        scheduler.tick(10.0);
1637
1638        scheduler.submit(1.0, 5.0); // Would preempt if enabled
1639
1640        // Should still be processing the first job
1641        let next = scheduler.peek_next().unwrap();
1642        assert_eq!(next.remaining_time, 90.0);
1643    }
1644
1645    // =========================================================================
1646    // Processing tests
1647    // =========================================================================
1648
1649    #[test]
1650    fn tick_processes_jobs() {
1651        let mut scheduler = QueueingScheduler::new(test_config());
1652
1653        scheduler.submit(1.0, 10.0);
1654        let completed = scheduler.tick(5.0);
1655
1656        assert!(completed.is_empty()); // Not complete yet
1657        assert_eq!(scheduler.peek_next().unwrap().remaining_time, 5.0);
1658    }
1659
1660    #[test]
1661    fn tick_completes_jobs() {
1662        let mut scheduler = QueueingScheduler::new(test_config());
1663
1664        scheduler.submit(1.0, 10.0);
1665        let completed = scheduler.tick(10.0);
1666
1667        assert_eq!(completed.len(), 1);
1668        assert_eq!(completed[0], 1);
1669        assert!(scheduler.peek_next().is_none());
1670    }
1671
1672    #[test]
1673    fn tick_completes_multiple_jobs() {
1674        let mut scheduler = QueueingScheduler::new(test_config());
1675
1676        scheduler.submit(1.0, 5.0);
1677        scheduler.submit(1.0, 5.0);
1678        let completed = scheduler.tick(10.0);
1679
1680        assert_eq!(completed.len(), 2);
1681    }
1682
1683    #[test]
1684    fn tick_handles_zero_delta() {
1685        let mut scheduler = QueueingScheduler::new(test_config());
1686        scheduler.submit(1.0, 10.0);
1687        let completed = scheduler.tick(0.0);
1688        assert!(completed.is_empty());
1689    }
1690
1691    // =========================================================================
1692    // Statistics tests
1693    // =========================================================================
1694
1695    #[test]
1696    fn stats_track_submissions() {
1697        let mut scheduler = QueueingScheduler::new(test_config());
1698
1699        scheduler.submit(1.0, 10.0);
1700        scheduler.submit(1.0, 10.0);
1701
1702        let stats = scheduler.stats();
1703        assert_eq!(stats.total_submitted, 2);
1704        assert_eq!(stats.queue_length, 2);
1705    }
1706
1707    #[test]
1708    fn stats_track_completions() {
1709        let mut scheduler = QueueingScheduler::new(test_config());
1710
1711        scheduler.submit(1.0, 10.0);
1712        scheduler.tick(10.0);
1713
1714        let stats = scheduler.stats();
1715        assert_eq!(stats.total_completed, 1);
1716    }
1717
1718    #[test]
1719    fn stats_compute_mean_response_time() {
1720        let mut scheduler = QueueingScheduler::new(test_config());
1721
1722        scheduler.submit(1.0, 10.0);
1723        scheduler.submit(1.0, 10.0);
1724        scheduler.tick(20.0);
1725
1726        let stats = scheduler.stats();
1727        // First job: 10 time units, Second job: 20 time units
1728        // Mean: (10 + 20) / 2 = 15
1729        assert_eq!(stats.total_completed, 2);
1730        assert!(stats.mean_response_time() > 0.0);
1731    }
1732
1733    #[test]
1734    fn stats_compute_throughput() {
1735        let mut scheduler = QueueingScheduler::new(test_config());
1736
1737        scheduler.submit(1.0, 10.0);
1738        scheduler.tick(10.0);
1739
1740        let stats = scheduler.stats();
1741        // 1 job in 10 time units
1742        assert!((stats.throughput() - 0.1).abs() < 0.01);
1743    }
1744
1745    // =========================================================================
1746    // Evidence tests
1747    // =========================================================================
1748
1749    #[test]
1750    fn evidence_reports_queue_empty() {
1751        let scheduler = QueueingScheduler::new(test_config());
1752        let evidence = scheduler.evidence();
1753        assert_eq!(evidence.reason, SelectionReason::QueueEmpty);
1754        assert!(evidence.selected_job_id.is_none());
1755        assert!(evidence.tie_break_reason.is_none());
1756        assert!(evidence.jobs.is_empty());
1757    }
1758
1759    #[test]
1760    fn evidence_reports_selected_job() {
1761        let mut scheduler = QueueingScheduler::new(test_config());
1762        scheduler.submit(1.0, 10.0);
1763        let evidence = scheduler.evidence();
1764        assert_eq!(evidence.selected_job_id, Some(1));
1765        assert_eq!(evidence.jobs.len(), 1);
1766    }
1767
1768    #[test]
1769    fn evidence_reports_wait_stats() {
1770        let mut scheduler = QueueingScheduler::new(test_config());
1771        scheduler.submit(1.0, 100.0);
1772        scheduler.submit(1.0, 100.0);
1773        scheduler.current_time = 50.0;
1774        scheduler.refresh_priorities();
1775
1776        let evidence = scheduler.evidence();
1777        assert!(evidence.mean_wait_time > 0.0);
1778        assert!(evidence.max_wait_time > 0.0);
1779    }
1780
1781    #[test]
1782    fn evidence_reports_priority_objective_terms() {
1783        let mut config = test_config();
1784        config.aging_factor = 0.5;
1785        config.wait_starve_ms = 10.0;
1786        config.starve_boost_ratio = 2.0;
1787        let mut scheduler = QueueingScheduler::new(config);
1788
1789        scheduler.submit(1.0, 20.0);
1790        scheduler.current_time = 20.0;
1791        scheduler.refresh_priorities();
1792
1793        let evidence = scheduler.evidence();
1794        let job = evidence.jobs.first().expect("job evidence");
1795        assert!(job.aging_reward > 0.0);
1796        assert!(job.starvation_floor > 0.0);
1797        assert!(job.effective_priority >= job.ratio + job.aging_reward);
1798        assert!(
1799            (job.objective_loss_proxy - (1.0 / job.effective_priority.max(DEFAULT_W_MIN))).abs()
1800                < 1e-9
1801        );
1802    }
1803
1804    // =========================================================================
1805    // Config override tests
1806    // =========================================================================
1807
1808    #[test]
1809    fn force_fifo_overrides_priority() {
1810        let mut config = test_config();
1811        config.force_fifo = true;
1812        let mut scheduler = QueueingScheduler::new(config);
1813
1814        let first = scheduler.submit(1.0, 100.0).unwrap();
1815        let second = scheduler.submit(10.0, 1.0).unwrap();
1816
1817        let next = scheduler.peek_next().unwrap();
1818        assert_eq!(next.id, first);
1819        assert_ne!(next.id, second);
1820        assert_eq!(scheduler.evidence().reason, SelectionReason::Fifo);
1821    }
1822
1823    #[test]
1824    fn default_sources_use_config_values() {
1825        let mut config = test_config();
1826        config.weight_default = 7.0;
1827        config.estimate_default_ms = 12.0;
1828        let mut scheduler = QueueingScheduler::new(config);
1829
1830        scheduler.submit_with_sources(
1831            999.0,
1832            999.0,
1833            WeightSource::Default,
1834            EstimateSource::Default,
1835            None::<&str>,
1836        );
1837
1838        let next = scheduler.peek_next().unwrap();
1839        assert!((next.weight - 7.0).abs() < f64::EPSILON);
1840        assert!((next.remaining_time - 12.0).abs() < f64::EPSILON);
1841    }
1842
1843    #[test]
1844    fn unknown_sources_use_config_values() {
1845        let mut config = test_config();
1846        config.weight_unknown = 2.5;
1847        config.estimate_unknown_ms = 250.0;
1848        let mut scheduler = QueueingScheduler::new(config);
1849
1850        scheduler.submit_with_sources(
1851            0.0,
1852            0.0,
1853            WeightSource::Unknown,
1854            EstimateSource::Unknown,
1855            None::<&str>,
1856        );
1857
1858        let next = scheduler.peek_next().unwrap();
1859        assert!((next.weight - 2.5).abs() < f64::EPSILON);
1860        assert!((next.remaining_time - 250.0).abs() < f64::EPSILON);
1861    }
1862
1863    // =========================================================================
1864    // Tie-break tests
1865    // =========================================================================
1866
1867    #[test]
1868    fn tie_break_prefers_base_ratio_when_effective_equal() {
1869        let mut config = test_config();
1870        config.aging_factor = 0.1;
1871        let mut scheduler = QueueingScheduler::new(config);
1872
1873        // Job A: lower base ratio but older (aging brings it up).
1874        let id_a = scheduler.submit(1.0, 2.0).unwrap(); // ratio 0.5
1875        scheduler.current_time = 5.0;
1876        scheduler.refresh_priorities();
1877
1878        // Job B: higher base ratio, newer.
1879        let id_b = scheduler.submit(1.0, 1.0).unwrap(); // ratio 1.0
1880        scheduler.refresh_priorities();
1881
1882        let next = scheduler.peek_next().unwrap();
1883        assert_eq!(next.id, id_b);
1884
1885        let evidence = scheduler.evidence();
1886        assert_eq!(evidence.selected_job_id, Some(id_b));
1887        assert_eq!(evidence.tie_break_reason, Some(TieBreakReason::BaseRatio));
1888        assert_ne!(id_a, id_b);
1889    }
1890
1891    #[test]
1892    fn tie_break_prefers_weight_over_arrival() {
1893        let mut scheduler = QueueingScheduler::new(test_config());
1894
1895        let high_weight = scheduler.submit(2.0, 2.0).unwrap(); // ratio 1.0
1896        let _low_weight = scheduler.submit(1.0, 1.0).unwrap(); // ratio 1.0
1897
1898        let evidence = scheduler.evidence();
1899        assert_eq!(evidence.selected_job_id, Some(high_weight));
1900        assert_eq!(evidence.tie_break_reason, Some(TieBreakReason::Weight));
1901    }
1902
1903    #[test]
1904    fn tie_break_prefers_arrival_seq_when_all_equal() {
1905        let mut config = test_config();
1906        config.aging_factor = 0.0;
1907        let mut scheduler = QueueingScheduler::new(config);
1908
1909        let first = scheduler.submit(1.0, 10.0).unwrap();
1910        let second = scheduler.submit(1.0, 10.0).unwrap();
1911
1912        let evidence = scheduler.evidence();
1913        assert_eq!(evidence.selected_job_id, Some(first));
1914        assert_eq!(evidence.tie_break_reason, Some(TieBreakReason::ArrivalSeq));
1915        assert_ne!(first, second);
1916    }
1917
1918    // =========================================================================
1919    // Ordering + safety edge cases (bd-3e1t.10.4)
1920    // =========================================================================
1921
1922    #[test]
1923    fn srpt_mode_ignores_weights() {
1924        let mut config = test_config();
1925        config.smith_enabled = false;
1926        let mut scheduler = QueueingScheduler::new(config);
1927
1928        scheduler.submit(10.0, 100.0); // High weight, long
1929        scheduler.submit(1.0, 10.0); // Low weight, short
1930
1931        let next = scheduler.peek_next().unwrap();
1932        assert_eq!(next.remaining_time, 10.0);
1933        assert_eq!(
1934            scheduler.evidence().reason,
1935            SelectionReason::ShortestRemaining
1936        );
1937    }
1938
1939    #[test]
1940    fn fifo_mode_disables_preemption() {
1941        let mut config = test_config();
1942        config.force_fifo = true;
1943        config.preemptive = true;
1944        let mut scheduler = QueueingScheduler::new(config);
1945
1946        let first = scheduler.submit(1.0, 100.0).unwrap();
1947        scheduler.tick(10.0);
1948
1949        let _later = scheduler.submit(10.0, 1.0).unwrap();
1950        let next = scheduler.peek_next().unwrap();
1951        assert_eq!(next.id, first);
1952    }
1953
1954    #[test]
1955    fn explicit_zero_weight_clamps_to_min() {
1956        let mut config = test_config();
1957        config.w_min = 0.5;
1958        let mut scheduler = QueueingScheduler::new(config);
1959
1960        scheduler.submit_with_sources(
1961            0.0,
1962            1.0,
1963            WeightSource::Explicit,
1964            EstimateSource::Explicit,
1965            None::<&str>,
1966        );
1967
1968        let next = scheduler.peek_next().unwrap();
1969        assert!((next.weight - 0.5).abs() < f64::EPSILON);
1970    }
1971
1972    #[test]
1973    fn explicit_zero_estimate_clamps_to_min() {
1974        let mut config = test_config();
1975        config.p_min_ms = 2.0;
1976        let mut scheduler = QueueingScheduler::new(config);
1977
1978        scheduler.submit_with_sources(
1979            1.0,
1980            0.0,
1981            WeightSource::Explicit,
1982            EstimateSource::Explicit,
1983            None::<&str>,
1984        );
1985
1986        let next = scheduler.peek_next().unwrap();
1987        assert!((next.remaining_time - 2.0).abs() < f64::EPSILON);
1988    }
1989
1990    #[test]
1991    fn explicit_weight_honors_config_w_max_above_defaults() {
1992        let mut config = test_config();
1993        config.w_max = 50.0;
1994        let mut scheduler = QueueingScheduler::new(config);
1995
1996        scheduler.submit_with_sources(
1997            20.0,
1998            1.0,
1999            WeightSource::Explicit,
2000            EstimateSource::Explicit,
2001            None::<&str>,
2002        );
2003
2004        let next = scheduler.peek_next().unwrap();
2005        assert!((next.weight - 20.0).abs() < f64::EPSILON);
2006    }
2007
2008    #[test]
2009    fn explicit_estimate_honors_config_p_max_above_defaults() {
2010        let mut config = test_config();
2011        config.p_max_ms = 100_000.0;
2012        let mut scheduler = QueueingScheduler::new(config);
2013
2014        scheduler.submit_with_sources(
2015            1.0,
2016            50_000.0,
2017            WeightSource::Explicit,
2018            EstimateSource::Explicit,
2019            None::<&str>,
2020        );
2021
2022        let next = scheduler.peek_next().unwrap();
2023        assert!((next.remaining_time - 50_000.0).abs() < f64::EPSILON);
2024    }
2025
2026    #[test]
2027    fn inverted_or_nan_config_bounds_do_not_panic_on_submit() {
2028        // Normalization used `f64::clamp`, which panics on min > max or a
2029        // NaN bound, so a config like this made every submit panic.
2030        let mut config = test_config();
2031        config.w_min = 10.0;
2032        config.w_max = 1.0;
2033        config.p_min_ms = f64::NAN;
2034        config.p_max_ms = 2.0;
2035        let mut scheduler = QueueingScheduler::new(config);
2036        assert!(scheduler.submit(5.0, 50.0).is_some());
2037        let next = scheduler.peek_next().unwrap();
2038        assert!((next.weight - 1.0).abs() < f64::EPSILON);
2039        assert!((next.remaining_time - 2.0).abs() < f64::EPSILON);
2040    }
2041
2042    // =========================================================================
2043    // Cancel tests
2044    // =========================================================================
2045
2046    #[test]
2047    fn cancel_removes_job() {
2048        let mut scheduler = QueueingScheduler::new(test_config());
2049        let id = scheduler.submit(1.0, 10.0).unwrap();
2050
2051        assert!(scheduler.cancel(id));
2052        assert!(scheduler.peek_next().is_none());
2053    }
2054
2055    #[test]
2056    fn cancel_returns_false_for_nonexistent() {
2057        let mut scheduler = QueueingScheduler::new(test_config());
2058        assert!(!scheduler.cancel(999));
2059    }
2060
2061    // =========================================================================
2062    // Reset tests
2063    // =========================================================================
2064
2065    #[test]
2066    fn reset_clears_all_state() {
2067        let mut scheduler = QueueingScheduler::new(test_config());
2068
2069        scheduler.submit(1.0, 10.0);
2070        scheduler.tick(5.0);
2071
2072        scheduler.reset();
2073
2074        assert!(scheduler.peek_next().is_none());
2075        assert_eq!(scheduler.stats().total_submitted, 0);
2076        assert_eq!(scheduler.stats().total_completed, 0);
2077    }
2078
2079    #[test]
2080    fn clear_removes_jobs_but_keeps_stats() {
2081        let mut scheduler = QueueingScheduler::new(test_config());
2082
2083        scheduler.submit(1.0, 10.0);
2084        scheduler.clear();
2085
2086        assert!(scheduler.peek_next().is_none());
2087        assert_eq!(scheduler.stats().total_submitted, 1); // Stats preserved
2088    }
2089
2090    // =========================================================================
2091    // Job tests
2092    // =========================================================================
2093
2094    #[test]
2095    fn job_progress_increases() {
2096        let mut job = Job::new(1, 1.0, 100.0);
2097        assert_eq!(job.progress(), 0.0);
2098
2099        job.remaining_time = 50.0;
2100        assert!((job.progress() - 0.5).abs() < 0.01);
2101
2102        job.remaining_time = 0.0;
2103        assert_eq!(job.progress(), 1.0);
2104    }
2105
2106    #[test]
2107    fn job_is_complete() {
2108        let mut job = Job::new(1, 1.0, 10.0);
2109        assert!(!job.is_complete());
2110
2111        job.remaining_time = 0.0;
2112        assert!(job.is_complete());
2113    }
2114
2115    // =========================================================================
2116    // Property tests
2117    // =========================================================================
2118
2119    #[test]
2120    fn property_work_conserving() {
2121        let mut scheduler = QueueingScheduler::new(test_config());
2122
2123        // Submit jobs
2124        for i in 0..10 {
2125            scheduler.submit(1.0, (i as f64) + 1.0);
2126        }
2127
2128        // Process - should never be idle while jobs remain
2129        let mut total_processed = 0;
2130        while scheduler.peek_next().is_some() {
2131            let completed = scheduler.tick(1.0);
2132            total_processed += completed.len();
2133        }
2134
2135        assert_eq!(total_processed, 10);
2136    }
2137
2138    #[test]
2139    fn property_bounded_memory() {
2140        let mut config = test_config();
2141        config.max_queue_size = 100;
2142        let mut scheduler = QueueingScheduler::new(config);
2143
2144        // Submit many jobs
2145        for _ in 0..1000 {
2146            scheduler.submit(1.0, 10.0);
2147        }
2148
2149        assert!(scheduler.stats().queue_length <= 100);
2150    }
2151
2152    #[test]
2153    fn property_deterministic() {
2154        let run = || {
2155            let mut scheduler = QueueingScheduler::new(test_config());
2156            let mut completions = Vec::new();
2157
2158            for i in 0..20 {
2159                scheduler.submit(((i % 3) + 1) as f64, ((i % 5) + 1) as f64);
2160            }
2161
2162            for _ in 0..50 {
2163                completions.extend(scheduler.tick(1.0));
2164            }
2165
2166            completions
2167        };
2168
2169        let run1 = run();
2170        let run2 = run();
2171
2172        assert_eq!(run1, run2, "Scheduling should be deterministic");
2173    }
2174
2175    #[test]
2176    fn smith_beats_fifo_on_mixed_workload() {
2177        let workload = mixed_workload();
2178        let smith = simulate_policy(SimPolicy::Smith, &workload);
2179        let fifo = simulate_policy(SimPolicy::Fifo, &workload);
2180
2181        eprintln!("{}", workload_summary_json(&workload));
2182        eprintln!("{}", summary_json(SimPolicy::Smith, &smith));
2183        eprintln!("{}", summary_json(SimPolicy::Fifo, &fifo));
2184
2185        assert!(
2186            smith.mean < fifo.mean,
2187            "mean should improve: smith={} fifo={}",
2188            summary_json(SimPolicy::Smith, &smith),
2189            summary_json(SimPolicy::Fifo, &fifo)
2190        );
2191        assert!(
2192            smith.p95 < fifo.p95,
2193            "p95 should improve: smith={} fifo={}",
2194            summary_json(SimPolicy::Smith, &smith),
2195            summary_json(SimPolicy::Fifo, &fifo)
2196        );
2197        assert!(
2198            smith.p99 < fifo.p99,
2199            "p99 should improve: smith={} fifo={}",
2200            summary_json(SimPolicy::Smith, &smith),
2201            summary_json(SimPolicy::Fifo, &fifo)
2202        );
2203    }
2204
2205    #[test]
2206    fn simulation_is_deterministic_per_policy() {
2207        let workload = mixed_workload();
2208        let smith1 = simulate_policy(SimPolicy::Smith, &workload);
2209        let smith2 = simulate_policy(SimPolicy::Smith, &workload);
2210        let fifo1 = simulate_policy(SimPolicy::Fifo, &workload);
2211        let fifo2 = simulate_policy(SimPolicy::Fifo, &workload);
2212
2213        assert_eq!(smith1.completion_order, smith2.completion_order);
2214        assert_eq!(fifo1.completion_order, fifo2.completion_order);
2215        assert!((smith1.mean - smith2.mean).abs() < 1e-9);
2216        assert!((fifo1.mean - fifo2.mean).abs() < 1e-9);
2217    }
2218
2219    #[test]
2220    fn effect_queue_trace_is_deterministic() {
2221        let mut config = test_config();
2222        config.preemptive = false;
2223        config.aging_factor = 0.0;
2224        config.wait_starve_ms = 0.0;
2225        config.force_fifo = false;
2226        config.smith_enabled = true;
2227
2228        let mut scheduler = QueueingScheduler::new(config);
2229        let id_alpha = scheduler
2230            .submit_with_sources(
2231                1.0,
2232                8.0,
2233                WeightSource::Explicit,
2234                EstimateSource::Explicit,
2235                Some("alpha"),
2236            )
2237            .expect("alpha accepted");
2238        let id_beta = scheduler
2239            .submit_with_sources(
2240                4.0,
2241                2.0,
2242                WeightSource::Explicit,
2243                EstimateSource::Explicit,
2244                Some("beta"),
2245            )
2246            .expect("beta accepted");
2247        let id_gamma = scheduler
2248            .submit_with_sources(
2249                2.0,
2250                10.0,
2251                WeightSource::Explicit,
2252                EstimateSource::Explicit,
2253                Some("gamma"),
2254            )
2255            .expect("gamma accepted");
2256        let id_delta = scheduler
2257            .submit_with_sources(
2258                3.0,
2259                3.0,
2260                WeightSource::Explicit,
2261                EstimateSource::Explicit,
2262                Some("delta"),
2263            )
2264            .expect("delta accepted");
2265
2266        scheduler.refresh_priorities();
2267
2268        let mut selected = Vec::new();
2269        while let Some(job) = scheduler.peek_next().cloned() {
2270            let evidence = scheduler.evidence();
2271            if let Some(id) = evidence.selected_job_id {
2272                selected.push(id);
2273            }
2274            println!("{}", evidence.to_jsonl("effect_queue_select"));
2275
2276            let completed = scheduler.tick(job.remaining_time);
2277            assert!(
2278                !completed.is_empty(),
2279                "expected completion per tick in non-preemptive mode"
2280            );
2281        }
2282
2283        assert_eq!(selected, vec![id_beta, id_delta, id_gamma, id_alpha]);
2284    }
2285
2286    // =========================================================================
2287    // Edge case tests
2288    // =========================================================================
2289
2290    #[test]
2291    fn zero_weight_handled() {
2292        let mut scheduler = QueueingScheduler::new(test_config());
2293        scheduler.submit(0.0, 10.0);
2294        assert!(scheduler.peek_next().is_some());
2295    }
2296
2297    #[test]
2298    fn zero_time_completes_immediately() {
2299        let mut scheduler = QueueingScheduler::new(test_config());
2300        scheduler.submit(1.0, 0.0);
2301        let completed = scheduler.tick(1.0);
2302        assert_eq!(completed.len(), 1);
2303    }
2304
2305    #[test]
2306    fn negative_time_handled() {
2307        let mut scheduler = QueueingScheduler::new(test_config());
2308        scheduler.submit(1.0, -10.0);
2309        let completed = scheduler.tick(1.0);
2310        assert_eq!(completed.len(), 1);
2311    }
2312
2313    #[test]
2314    fn tick_non_finite_delta_noops() {
2315        let mut scheduler = QueueingScheduler::new(test_config());
2316        scheduler.submit(1.0, 5.0);
2317
2318        let before = scheduler.stats();
2319        assert!(scheduler.tick(f64::NAN).is_empty());
2320        assert!(scheduler.tick(f64::INFINITY).is_empty());
2321        assert!(scheduler.tick(f64::NEG_INFINITY).is_empty());
2322        let after = scheduler.stats();
2323
2324        assert_eq!(before.total_processing_time, after.total_processing_time);
2325        assert_eq!(before.total_completed, after.total_completed);
2326        assert!(scheduler.peek_next().is_some());
2327    }
2328
2329    // =========================================================================
2330    // Job builder edge cases (bd-2x2ys)
2331    // =========================================================================
2332
2333    #[test]
2334    fn job_new_nan_weight_clamps_to_min() {
2335        let job = Job::new(1, f64::NAN, 10.0);
2336        assert_eq!(job.weight, DEFAULT_W_MIN);
2337    }
2338
2339    #[test]
2340    fn job_new_pos_inf_weight_clamps_to_max() {
2341        let job = Job::new(1, f64::INFINITY, 10.0);
2342        assert_eq!(job.weight, DEFAULT_W_MAX);
2343    }
2344
2345    #[test]
2346    fn job_new_neg_inf_weight_clamps_to_min() {
2347        let job = Job::new(1, f64::NEG_INFINITY, 10.0);
2348        assert_eq!(job.weight, DEFAULT_W_MIN);
2349    }
2350
2351    #[test]
2352    fn job_new_nan_estimate_clamps_to_max() {
2353        let job = Job::new(1, 1.0, f64::NAN);
2354        assert_eq!(job.remaining_time, DEFAULT_P_MAX_MS);
2355        assert_eq!(job.total_time, DEFAULT_P_MAX_MS);
2356    }
2357
2358    #[test]
2359    fn job_new_pos_inf_estimate_clamps_to_max() {
2360        let job = Job::new(1, 1.0, f64::INFINITY);
2361        assert_eq!(job.remaining_time, DEFAULT_P_MAX_MS);
2362    }
2363
2364    #[test]
2365    fn job_new_neg_inf_estimate_clamps_to_min() {
2366        let job = Job::new(1, 1.0, f64::NEG_INFINITY);
2367        assert_eq!(job.remaining_time, DEFAULT_P_MIN_MS);
2368    }
2369
2370    #[test]
2371    fn job_with_name_sets_name() {
2372        let job = Job::with_name(1, 1.0, 10.0, "alpha");
2373        assert_eq!(job.name.as_deref(), Some("alpha"));
2374        assert_eq!(job.id, 1);
2375    }
2376
2377    #[test]
2378    fn job_with_sources_sets_both() {
2379        let job =
2380            Job::new(1, 1.0, 10.0).with_sources(WeightSource::Unknown, EstimateSource::Historical);
2381        assert_eq!(job.weight_source, WeightSource::Unknown);
2382        assert_eq!(job.estimate_source, EstimateSource::Historical);
2383    }
2384
2385    #[test]
2386    fn job_progress_zero_total_time() {
2387        let mut job = Job::new(1, 1.0, 10.0);
2388        job.total_time = 0.0;
2389        assert_eq!(job.progress(), 1.0);
2390    }
2391
2392    #[test]
2393    fn job_is_complete_negative_remaining() {
2394        let mut job = Job::new(1, 1.0, 10.0);
2395        job.remaining_time = -5.0;
2396        assert!(job.is_complete());
2397    }
2398
2399    // =========================================================================
2400    // Scheduler normalization edge cases (bd-2x2ys)
2401    // =========================================================================
2402
2403    #[test]
2404    fn submit_nan_weight_normalized() {
2405        let mut scheduler = QueueingScheduler::new(test_config());
2406        scheduler.submit(f64::NAN, 10.0);
2407        let next = scheduler.peek_next().unwrap();
2408        assert!(next.weight >= DEFAULT_W_MIN);
2409        assert!(next.weight.is_finite());
2410    }
2411
2412    #[test]
2413    fn submit_inf_weight_normalized() {
2414        let mut scheduler = QueueingScheduler::new(test_config());
2415        scheduler.submit(f64::INFINITY, 10.0);
2416        let next = scheduler.peek_next().unwrap();
2417        assert!(next.weight <= DEFAULT_W_MAX);
2418        assert!(next.weight.is_finite());
2419    }
2420
2421    #[test]
2422    fn submit_nan_estimate_normalized() {
2423        let mut scheduler = QueueingScheduler::new(test_config());
2424        scheduler.submit(1.0, f64::NAN);
2425        let next = scheduler.peek_next().unwrap();
2426        assert!(next.remaining_time <= DEFAULT_P_MAX_MS);
2427        assert!(next.remaining_time.is_finite());
2428    }
2429
2430    #[test]
2431    fn submit_inf_estimate_normalized() {
2432        let mut scheduler = QueueingScheduler::new(test_config());
2433        scheduler.submit(1.0, f64::INFINITY);
2434        let next = scheduler.peek_next().unwrap();
2435        assert!(next.remaining_time <= DEFAULT_P_MAX_MS);
2436        assert!(next.remaining_time.is_finite());
2437    }
2438
2439    // =========================================================================
2440    // Config mode tests (bd-2x2ys)
2441    // =========================================================================
2442
2443    #[test]
2444    fn config_mode_smith() {
2445        let config = SchedulerConfig {
2446            smith_enabled: true,
2447            force_fifo: false,
2448            ..Default::default()
2449        };
2450        assert_eq!(config.mode(), SchedulingMode::Smith);
2451    }
2452
2453    #[test]
2454    fn config_mode_srpt() {
2455        let config = SchedulerConfig {
2456            smith_enabled: false,
2457            force_fifo: false,
2458            ..Default::default()
2459        };
2460        assert_eq!(config.mode(), SchedulingMode::Srpt);
2461    }
2462
2463    #[test]
2464    fn config_mode_fifo_overrides_smith() {
2465        let config = SchedulerConfig {
2466            smith_enabled: true,
2467            force_fifo: true,
2468            ..Default::default()
2469        };
2470        assert_eq!(config.mode(), SchedulingMode::Fifo);
2471    }
2472
2473    // =========================================================================
2474    // Starvation guard (bd-2x2ys)
2475    // =========================================================================
2476
2477    #[test]
2478    fn starvation_guard_triggers_after_threshold() {
2479        let mut config = test_config();
2480        config.aging_factor = 0.0;
2481        config.wait_starve_ms = 50.0;
2482        config.starve_boost_ratio = 5.0;
2483        let mut scheduler = QueueingScheduler::new(config);
2484
2485        scheduler.submit(1.0, 100.0); // ratio = 1/100 = 0.01
2486        scheduler.current_time = 60.0; // Beyond 50ms threshold
2487        scheduler.refresh_priorities();
2488
2489        let evidence = scheduler.evidence();
2490        let job_ev = &evidence.jobs[0];
2491        // starvation_floor = 0.01 * 5.0 = 0.05
2492        assert!(
2493            job_ev.starvation_floor > 0.0,
2494            "starvation floor should be active: {}",
2495            job_ev.starvation_floor
2496        );
2497        assert!(
2498            job_ev.effective_priority >= job_ev.starvation_floor,
2499            "effective priority {} should be >= starvation floor {}",
2500            job_ev.effective_priority,
2501            job_ev.starvation_floor
2502        );
2503    }
2504
2505    #[test]
2506    fn starvation_guard_disabled_when_zero() {
2507        let mut config = test_config();
2508        config.aging_factor = 0.0;
2509        config.wait_starve_ms = 0.0;
2510        let mut scheduler = QueueingScheduler::new(config);
2511
2512        scheduler.submit(1.0, 100.0);
2513        scheduler.current_time = 1000.0;
2514        scheduler.refresh_priorities();
2515
2516        let evidence = scheduler.evidence();
2517        let job_ev = &evidence.jobs[0];
2518        assert!(
2519            (job_ev.starvation_floor - 0.0).abs() < f64::EPSILON,
2520            "starvation floor should be 0 when disabled"
2521        );
2522    }
2523
2524    // =========================================================================
2525    // Cancel edge cases (bd-2x2ys)
2526    // =========================================================================
2527
2528    #[test]
2529    fn cancel_current_job() {
2530        let mut scheduler = QueueingScheduler::new(test_config());
2531        let id = scheduler.submit(1.0, 100.0).unwrap();
2532        scheduler.tick(10.0); // Start processing (moves job to current_job)
2533
2534        assert!(scheduler.cancel(id));
2535        assert!(scheduler.peek_next().is_none());
2536    }
2537
2538    #[test]
2539    fn cancel_from_middle_of_queue() {
2540        let mut scheduler = QueueingScheduler::new(test_config());
2541        scheduler.submit(1.0, 100.0); // id=1
2542        let id2 = scheduler.submit(1.0, 50.0).unwrap(); // id=2
2543        scheduler.submit(1.0, 200.0); // id=3
2544
2545        assert!(scheduler.cancel(id2));
2546        assert_eq!(scheduler.stats().queue_length, 2);
2547    }
2548
2549    // =========================================================================
2550    // Tick edge cases (bd-2x2ys)
2551    // =========================================================================
2552
2553    #[test]
2554    fn tick_negative_delta_returns_empty() {
2555        let mut scheduler = QueueingScheduler::new(test_config());
2556        scheduler.submit(1.0, 10.0);
2557        let completed = scheduler.tick(-5.0);
2558        assert!(completed.is_empty());
2559    }
2560
2561    #[test]
2562    fn tick_empty_queue_advances_time() {
2563        let mut scheduler = QueueingScheduler::new(test_config());
2564        let completed = scheduler.tick(100.0);
2565        assert!(completed.is_empty());
2566    }
2567
2568    #[test]
2569    fn tick_processes_across_multiple_jobs_in_single_delta() {
2570        let mut config = test_config();
2571        config.aging_factor = 0.0;
2572        let mut scheduler = QueueingScheduler::new(config);
2573
2574        scheduler.submit(1.0, 3.0);
2575        scheduler.submit(1.0, 3.0);
2576        scheduler.submit(1.0, 3.0);
2577
2578        // 9 units of work should complete all 3
2579        let completed = scheduler.tick(9.0);
2580        assert_eq!(completed.len(), 3);
2581    }
2582
2583    // =========================================================================
2584    // Stats edge cases (bd-2x2ys)
2585    // =========================================================================
2586
2587    #[test]
2588    fn stats_default_values() {
2589        let stats = SchedulerStats::default();
2590        assert_eq!(stats.total_submitted, 0);
2591        assert_eq!(stats.total_completed, 0);
2592        assert_eq!(stats.total_rejected, 0);
2593        assert_eq!(stats.total_preemptions, 0);
2594        assert_eq!(stats.queue_length, 0);
2595    }
2596
2597    #[test]
2598    fn stats_mean_response_time_zero_completions() {
2599        let stats = SchedulerStats::default();
2600        assert_eq!(stats.mean_response_time(), 0.0);
2601    }
2602
2603    #[test]
2604    fn stats_throughput_zero_processing_time() {
2605        let stats = SchedulerStats::default();
2606        assert_eq!(stats.throughput(), 0.0);
2607    }
2608
2609    #[test]
2610    fn stats_max_response_time_tracked() {
2611        let mut scheduler = QueueingScheduler::new(test_config());
2612        scheduler.submit(1.0, 5.0);
2613        scheduler.submit(1.0, 10.0);
2614        scheduler.tick(15.0);
2615
2616        let stats = scheduler.stats();
2617        assert!(
2618            stats.max_response_time >= 10.0,
2619            "max response time {} should be >= 10",
2620            stats.max_response_time
2621        );
2622    }
2623
2624    // =========================================================================
2625    // Evidence / JSONL edge cases (bd-2x2ys)
2626    // =========================================================================
2627
2628    #[test]
2629    fn evidence_continuation_reason() {
2630        let mut scheduler = QueueingScheduler::new(test_config());
2631        scheduler.submit(1.0, 100.0);
2632        scheduler.tick(10.0); // Partially process, sets current_job
2633
2634        let evidence = scheduler.evidence();
2635        assert_eq!(evidence.reason, SelectionReason::Continuation);
2636    }
2637
2638    #[test]
2639    fn evidence_single_job_no_tie_break() {
2640        let mut scheduler = QueueingScheduler::new(test_config());
2641        scheduler.submit(1.0, 10.0);
2642
2643        let evidence = scheduler.evidence();
2644        assert!(
2645            evidence.tie_break_reason.is_none(),
2646            "single job should have no tie break"
2647        );
2648    }
2649
2650    #[test]
2651    fn evidence_to_jsonl_contains_required_fields() {
2652        let mut scheduler = QueueingScheduler::new(test_config());
2653        scheduler.submit(1.0, 10.0);
2654        scheduler.submit(2.0, 5.0);
2655
2656        let evidence = scheduler.evidence();
2657        let json = evidence.to_jsonl("test_event");
2658
2659        assert!(json.contains("\"event\":\"test_event\""));
2660        assert!(json.contains("\"current_time\":"));
2661        assert!(json.contains("\"selected_job_id\":"));
2662        assert!(json.contains("\"queue_length\":"));
2663        assert!(json.contains("\"mean_wait_time\":"));
2664        assert!(json.contains("\"max_wait_time\":"));
2665        assert!(json.contains("\"reason\":"));
2666        assert!(json.contains("\"tie_break_reason\":"));
2667        assert!(json.contains("\"jobs\":["));
2668    }
2669
2670    #[test]
2671    fn evidence_to_jsonl_empty_queue() {
2672        let scheduler = QueueingScheduler::new(test_config());
2673        let evidence = scheduler.evidence();
2674        let json = evidence.to_jsonl("empty");
2675
2676        assert!(json.contains("\"selected_job_id\":null"));
2677        assert!(json.contains("\"tie_break_reason\":null"));
2678        assert!(json.contains("\"jobs\":[]"));
2679    }
2680
2681    #[test]
2682    fn job_evidence_to_json_contains_all_fields() {
2683        let mut config = test_config();
2684        config.aging_factor = 0.5;
2685        config.wait_starve_ms = 5.0;
2686        let mut scheduler = QueueingScheduler::new(config);
2687
2688        scheduler.submit_with_sources(
2689            2.0,
2690            10.0,
2691            WeightSource::Explicit,
2692            EstimateSource::Default,
2693            Some("test-job"),
2694        );
2695        scheduler.current_time = 10.0;
2696        scheduler.refresh_priorities();
2697
2698        let evidence = scheduler.evidence();
2699        let json = evidence.to_jsonl("detail");
2700
2701        assert!(json.contains("\"job_id\":"));
2702        assert!(json.contains("\"name\":\"test-job\""));
2703        assert!(json.contains("\"estimate_ms\":"));
2704        assert!(json.contains("\"weight\":"));
2705        assert!(json.contains("\"ratio\":"));
2706        assert!(json.contains("\"aging_reward\":"));
2707        assert!(json.contains("\"starvation_floor\":"));
2708        assert!(json.contains("\"age_ms\":"));
2709        assert!(json.contains("\"effective_priority\":"));
2710        assert!(json.contains("\"objective_loss_proxy\":"));
2711        assert!(json.contains("\"estimate_source\":"));
2712        assert!(json.contains("\"weight_source\":"));
2713    }
2714
2715    #[test]
2716    fn evidence_jsonl_escapes_special_chars_in_name() {
2717        let mut scheduler = QueueingScheduler::new(test_config());
2718        scheduler.submit_named(1.0, 10.0, Some("job\"with\\special\nchars"));
2719
2720        let evidence = scheduler.evidence();
2721        let json = evidence.to_jsonl("escape_test");
2722
2723        assert!(json.contains("\\\""));
2724        assert!(json.contains("\\\\"));
2725        assert!(json.contains("\\n"));
2726    }
2727
2728    // =========================================================================
2729    // as_str coverage (bd-2x2ys)
2730    // =========================================================================
2731
2732    #[test]
2733    fn selection_reason_as_str_coverage() {
2734        assert_eq!(SelectionReason::QueueEmpty.as_str(), "queue_empty");
2735        assert_eq!(
2736            SelectionReason::ShortestRemaining.as_str(),
2737            "shortest_remaining"
2738        );
2739        assert_eq!(
2740            SelectionReason::HighestWeightedPriority.as_str(),
2741            "highest_weighted_priority"
2742        );
2743        assert_eq!(SelectionReason::Fifo.as_str(), "fifo");
2744        assert_eq!(SelectionReason::AgingBoost.as_str(), "aging_boost");
2745        assert_eq!(SelectionReason::Continuation.as_str(), "continuation");
2746    }
2747
2748    #[test]
2749    fn estimate_source_as_str_coverage() {
2750        assert_eq!(EstimateSource::Explicit.as_str(), "explicit");
2751        assert_eq!(EstimateSource::Historical.as_str(), "historical");
2752        assert_eq!(EstimateSource::Default.as_str(), "default");
2753        assert_eq!(EstimateSource::Unknown.as_str(), "unknown");
2754    }
2755
2756    #[test]
2757    fn weight_source_as_str_coverage() {
2758        assert_eq!(WeightSource::Explicit.as_str(), "explicit");
2759        assert_eq!(WeightSource::Default.as_str(), "default");
2760        assert_eq!(WeightSource::Unknown.as_str(), "unknown");
2761    }
2762
2763    #[test]
2764    fn tie_break_reason_as_str_coverage() {
2765        assert_eq!(
2766            TieBreakReason::EffectivePriority.as_str(),
2767            "effective_priority"
2768        );
2769        assert_eq!(TieBreakReason::BaseRatio.as_str(), "base_ratio");
2770        assert_eq!(TieBreakReason::Weight.as_str(), "weight");
2771        assert_eq!(TieBreakReason::RemainingTime.as_str(), "remaining_time");
2772        assert_eq!(TieBreakReason::ArrivalSeq.as_str(), "arrival_seq");
2773        assert_eq!(TieBreakReason::JobId.as_str(), "job_id");
2774        assert_eq!(TieBreakReason::Continuation.as_str(), "continuation");
2775    }
2776
2777    // =========================================================================
2778    // Debug formatting (bd-2x2ys)
2779    // =========================================================================
2780
2781    #[test]
2782    fn debug_job() {
2783        let job = Job::with_name(1, 2.0, 50.0, "render");
2784        let dbg = format!("{job:?}");
2785        assert!(dbg.contains("Job"));
2786        assert!(dbg.contains("render"));
2787    }
2788
2789    #[test]
2790    fn debug_scheduler_config() {
2791        let config = SchedulerConfig::default();
2792        let dbg = format!("{config:?}");
2793        assert!(dbg.contains("SchedulerConfig"));
2794        assert!(dbg.contains("aging_factor"));
2795    }
2796
2797    #[test]
2798    fn debug_scheduler_stats() {
2799        let stats = SchedulerStats::default();
2800        let dbg = format!("{stats:?}");
2801        assert!(dbg.contains("SchedulerStats"));
2802    }
2803
2804    #[test]
2805    fn debug_scheduling_evidence() {
2806        let scheduler = QueueingScheduler::new(test_config());
2807        let evidence = scheduler.evidence();
2808        let dbg = format!("{evidence:?}");
2809        assert!(dbg.contains("SchedulingEvidence"));
2810    }
2811
2812    #[test]
2813    fn debug_scheduling_mode() {
2814        assert!(format!("{:?}", SchedulingMode::Smith).contains("Smith"));
2815        assert!(format!("{:?}", SchedulingMode::Srpt).contains("Srpt"));
2816        assert!(format!("{:?}", SchedulingMode::Fifo).contains("Fifo"));
2817    }
2818
2819    // =========================================================================
2820    // Historical estimate source passthrough (bd-2x2ys)
2821    // =========================================================================
2822
2823    #[test]
2824    fn historical_estimate_passes_through() {
2825        let mut scheduler = QueueingScheduler::new(test_config());
2826        scheduler.submit_with_sources(
2827            1.0,
2828            42.0,
2829            WeightSource::Explicit,
2830            EstimateSource::Historical,
2831            None::<&str>,
2832        );
2833
2834        let next = scheduler.peek_next().unwrap();
2835        assert!((next.remaining_time - 42.0).abs() < f64::EPSILON);
2836    }
2837
2838    // =========================================================================
2839    // Preemption count tracking (bd-2x2ys)
2840    // =========================================================================
2841
2842    #[test]
2843    fn multiple_preemptions_counted() {
2844        let mut config = test_config();
2845        config.aging_factor = 0.0; // Disable aging for deterministic preemption
2846        config.wait_starve_ms = 0.0;
2847        let mut scheduler = QueueingScheduler::new(config);
2848
2849        scheduler.submit(1.0, 100.0); // Long job (priority=0.01)
2850        scheduler.tick(1.0); // Start processing, remaining=99
2851
2852        scheduler.submit(1.0, 50.0); // Preempt 1 (priority=0.02 > 0.01)
2853        scheduler.tick(1.0); // Start processing job2, remaining=49
2854
2855        scheduler.submit(1.0, 10.0); // Preempt 2 (priority=0.1 > 0.02)
2856
2857        assert!(
2858            scheduler.stats().total_preemptions >= 2,
2859            "expected >= 2 preemptions, got {}",
2860            scheduler.stats().total_preemptions
2861        );
2862    }
2863
2864    // =========================================================================
2865    // Queue rejection count (bd-2x2ys)
2866    // =========================================================================
2867
2868    #[test]
2869    fn multiple_rejections_counted() {
2870        let mut config = test_config();
2871        config.max_queue_size = 1;
2872        let mut scheduler = QueueingScheduler::new(config);
2873
2874        scheduler.submit(1.0, 10.0); // Accepted
2875        scheduler.submit(1.0, 10.0); // Rejected
2876        scheduler.submit(1.0, 10.0); // Rejected
2877
2878        assert_eq!(scheduler.stats().total_rejected, 2);
2879    }
2880
2881    // =========================================================================
2882    // Reset vs clear distinction (bd-2x2ys)
2883    // =========================================================================
2884
2885    #[test]
2886    fn reset_resets_job_id_sequence() {
2887        let mut scheduler = QueueingScheduler::new(test_config());
2888        scheduler.submit(1.0, 10.0); // id=1
2889        scheduler.submit(1.0, 10.0); // id=2
2890
2891        scheduler.reset();
2892
2893        let id = scheduler.submit(1.0, 10.0).unwrap();
2894        assert_eq!(id, 1, "job id should restart from 1 after reset");
2895    }
2896
2897    #[test]
2898    fn clear_preserves_job_id_sequence() {
2899        let mut scheduler = QueueingScheduler::new(test_config());
2900        scheduler.submit(1.0, 10.0); // id=1
2901        scheduler.submit(1.0, 10.0); // id=2
2902
2903        scheduler.clear();
2904
2905        let id = scheduler.submit(1.0, 10.0).unwrap();
2906        assert_eq!(id, 3, "job id should continue after clear");
2907    }
2908
2909    // =========================================================================
2910    // Evidence aging_boost selection reason (bd-2x2ys)
2911    // =========================================================================
2912
2913    #[test]
2914    fn evidence_aging_boost_reason() {
2915        let mut config = test_config();
2916        config.aging_factor = 1.0;
2917        config.wait_starve_ms = 10.0;
2918        let mut scheduler = QueueingScheduler::new(config);
2919
2920        scheduler.submit(1.0, 100.0);
2921        scheduler.current_time = 100.0;
2922        scheduler.refresh_priorities();
2923
2924        let evidence = scheduler.evidence();
2925        assert_eq!(
2926            evidence.reason,
2927            SelectionReason::AgingBoost,
2928            "long-waiting job should show aging boost reason"
2929        );
2930    }
2931
2932    #[test]
2933    fn counterexample_many_equal_jobs_wait_scales_with_backlog() {
2934        // Counterexample showing that finite S_max and aging_factor > 0 do NOT
2935        // bound waiting time independently of queue backlog N:
2936        // Submit N = 20 identical jobs (weight = 1.0, size S = 10.0) at t = 0
2937        // with aging_factor = 1.0, w_min = 1.0.
2938        // The backlog-independent expression `S_max * (1 + 1/a) / w_min` is
2939        // 10.0 * (1 + 1) / 1.0 = 20.0, whereas all N jobs age at the exact same
2940        // rate and the N-th job waits (N - 1) * S = 190.0 before starting service.
2941        let mut config = test_config();
2942        config.aging_factor = 1.0;
2943        config.w_min = 1.0;
2944        config.p_max_ms = 10.0;
2945        config.preemptive = false;
2946        let mut scheduler = QueueingScheduler::new(config);
2947
2948        let n_jobs = 20usize;
2949        let job_size = 10.0;
2950        for _ in 0..n_jobs {
2951            scheduler.submit(1.0, job_size).unwrap();
2952        }
2953
2954        for step in 0..n_jobs {
2955            let completed = scheduler.tick(job_size);
2956            assert_eq!(completed.len(), 1);
2957            assert_eq!(completed[0], (step + 1) as u64);
2958        }
2959
2960        // The 20th job finished at t = 200.0 after waiting 190.0 in the queue.
2961        let last_wait = (n_jobs - 1) as f64 * job_size;
2962        let last_response = n_jobs as f64 * job_size;
2963        let naive_bound = 10.0 * (1.0 + 1.0 / 1.0) / 1.0;
2964        assert!((scheduler.current_time - 200.0).abs() < 1e-9);
2965        assert!(
2966            last_wait > naive_bound,
2967            "Expected backlog wait {last_wait} to exceed backlog-independent expression {naive_bound}"
2968        );
2969        assert!(
2970            scheduler.stats().max_response_time >= last_response - 1e-9,
2971            "Expected max_response_time >= {last_response}, got {}",
2972            scheduler.stats().max_response_time
2973        );
2974    }
2975
2976    #[test]
2977    fn non_preemptive_long_job_blocks_short_high_weight_arrivals() {
2978        // Contrast the simulator's `preemptive: true` mode with `preemptive: false`
2979        // (which models live `FnOnce` effect closures that cannot be preempted once
2980        // popped by the worker thread).
2981        let run_scenario = |preemptive: bool| -> (f64, f64) {
2982            let mut config = test_config();
2983            config.preemptive = preemptive;
2984            let mut scheduler = QueueingScheduler::new(config);
2985
2986            // Long low-weight job arrives at t = 0 and begins running during tick(1.0).
2987            let long_id = scheduler.submit(1.0, 100.0).unwrap();
2988            assert!(scheduler.tick(1.0).is_empty());
2989
2990            // Short high-weight job arrives at t = 1.0 (base priority = 100.0 / 1.0 = 100.0).
2991            let short_id = scheduler.submit(100.0, 1.0).unwrap();
2992
2993            let mut short_done_at = None;
2994            let mut long_done_at = None;
2995            for _ in 0..100 {
2996                for job_id in scheduler.tick(1.0) {
2997                    if job_id == short_id {
2998                        short_done_at = Some(scheduler.current_time);
2999                    }
3000                    if job_id == long_id {
3001                        long_done_at = Some(scheduler.current_time);
3002                    }
3003                }
3004            }
3005            (short_done_at.unwrap(), long_done_at.unwrap())
3006        };
3007
3008        let (short_preemptive, long_preemptive) = run_scenario(true);
3009        let (short_nonpreemptive, long_nonpreemptive) = run_scenario(false);
3010
3011        // In preemptive simulation, the short job preempts at t=1.0 and finishes at t=2.0.
3012        assert!((short_preemptive - 2.0).abs() < 1e-9);
3013        assert!((long_preemptive - 101.0).abs() < 1e-9);
3014
3015        // In non-preemptive execution (like a running FnOnce closure), the short job
3016        // must wait for the remaining 99.0ms of the in-flight long job, finishing at t=101.0.
3017        assert!((long_nonpreemptive - 100.0).abs() < 1e-9);
3018        assert!((short_nonpreemptive - 101.0).abs() < 1e-9);
3019    }
3020}