1#![forbid(unsafe_code)]
2
3use std::cmp::Ordering;
68use std::collections::BinaryHeap;
69use std::fmt::Write;
70
71const DEFAULT_AGING_FACTOR: f64 = 0.1;
73
74const MAX_QUEUE_SIZE: usize = 10_000;
76
77const DEFAULT_P_MIN_MS: f64 = 0.05;
79
80const DEFAULT_P_MAX_MS: f64 = 5_000.0;
82
83const DEFAULT_W_MIN: f64 = 1e-6;
85
86const DEFAULT_W_MAX: f64 = 100.0;
88
89const DEFAULT_WEIGHT_DEFAULT: f64 = 1.0;
91
92const DEFAULT_WEIGHT_UNKNOWN: f64 = 1.0;
94
95const DEFAULT_ESTIMATE_DEFAULT_MS: f64 = 10.0;
97
98const DEFAULT_ESTIMATE_UNKNOWN_MS: f64 = 1_000.0;
100
101const DEFAULT_WAIT_STARVE_MS: f64 = 500.0;
103
104const DEFAULT_STARVE_BOOST_RATIO: f64 = 1.5;
106
107#[derive(Debug, Clone)]
109pub struct SchedulerConfig {
110 pub aging_factor: f64,
114
115 pub p_min_ms: f64,
117
118 pub p_max_ms: f64,
120
121 pub estimate_default_ms: f64,
124
125 pub estimate_unknown_ms: f64,
128
129 pub w_min: f64,
131
132 pub w_max: f64,
134
135 pub weight_default: f64,
138
139 pub weight_unknown: f64,
142
143 pub wait_starve_ms: f64,
145
146 pub starve_boost_ratio: f64,
149
150 pub smith_enabled: bool,
152
153 pub force_fifo: bool,
156
157 pub max_queue_size: usize,
159
160 pub preemptive: bool,
162
163 pub time_quantum: f64,
166
167 pub enable_logging: bool,
169}
170
171impl Default for SchedulerConfig {
172 fn default() -> Self {
173 Self {
174 aging_factor: DEFAULT_AGING_FACTOR,
175 p_min_ms: DEFAULT_P_MIN_MS,
176 p_max_ms: DEFAULT_P_MAX_MS,
177 estimate_default_ms: DEFAULT_ESTIMATE_DEFAULT_MS,
178 estimate_unknown_ms: DEFAULT_ESTIMATE_UNKNOWN_MS,
179 w_min: DEFAULT_W_MIN,
180 w_max: DEFAULT_W_MAX,
181 weight_default: DEFAULT_WEIGHT_DEFAULT,
182 weight_unknown: DEFAULT_WEIGHT_UNKNOWN,
183 wait_starve_ms: DEFAULT_WAIT_STARVE_MS,
184 starve_boost_ratio: DEFAULT_STARVE_BOOST_RATIO,
185 smith_enabled: true,
186 force_fifo: false,
187 max_queue_size: MAX_QUEUE_SIZE,
188 preemptive: true,
189 time_quantum: 10.0,
190 enable_logging: false,
191 }
192 }
193}
194
195impl SchedulerConfig {
196 pub fn mode(&self) -> SchedulingMode {
198 if self.force_fifo {
199 SchedulingMode::Fifo
200 } else if self.smith_enabled {
201 SchedulingMode::Smith
202 } else {
203 SchedulingMode::Srpt
204 }
205 }
206}
207
208#[derive(Debug, Clone)]
210pub struct Job {
211 pub id: u64,
213
214 pub weight: f64,
216
217 pub remaining_time: f64,
219
220 pub total_time: f64,
222
223 pub arrival_time: f64,
225
226 pub arrival_seq: u64,
228
229 pub estimate_source: EstimateSource,
231
232 pub weight_source: WeightSource,
234
235 pub name: Option<String>,
237}
238
239impl Job {
240 pub fn new(id: u64, weight: f64, estimated_time: f64) -> Self {
242 let weight = if weight.is_nan() {
243 DEFAULT_W_MIN
244 } else if weight.is_infinite() {
245 if weight.is_sign_positive() {
246 DEFAULT_W_MAX
247 } else {
248 DEFAULT_W_MIN
249 }
250 } else {
251 weight.clamp(DEFAULT_W_MIN, DEFAULT_W_MAX)
252 };
253 let estimated_time = if estimated_time.is_nan() {
254 DEFAULT_P_MAX_MS
255 } else if estimated_time.is_infinite() {
256 if estimated_time.is_sign_positive() {
257 DEFAULT_P_MAX_MS
258 } else {
259 DEFAULT_P_MIN_MS
260 }
261 } else {
262 estimated_time.clamp(DEFAULT_P_MIN_MS, DEFAULT_P_MAX_MS)
263 };
264 Self {
265 id,
266 weight,
267 remaining_time: estimated_time,
268 total_time: estimated_time,
269 arrival_time: 0.0,
270 arrival_seq: 0,
271 estimate_source: EstimateSource::Explicit,
272 weight_source: WeightSource::Explicit,
273 name: None,
274 }
275 }
276
277 pub fn with_name(id: u64, weight: f64, estimated_time: f64, name: impl Into<String>) -> Self {
279 let mut job = Self::new(id, weight, estimated_time);
280 job.name = Some(name.into());
281 job
282 }
283
284 pub fn with_sources(
286 mut self,
287 weight_source: WeightSource,
288 estimate_source: EstimateSource,
289 ) -> Self {
290 self.weight_source = weight_source;
291 self.estimate_source = estimate_source;
292 self
293 }
294
295 pub fn progress(&self) -> f64 {
297 if self.total_time <= 0.0 {
298 1.0
299 } else {
300 1.0 - (self.remaining_time / self.total_time).clamp(0.0, 1.0)
301 }
302 }
303
304 pub fn is_complete(&self) -> bool {
306 self.remaining_time <= 0.0
307 }
308}
309
310#[derive(Debug, Clone)]
312struct PriorityJob {
313 priority: f64,
314 base_ratio: f64,
315 job: Job,
316 mode: SchedulingMode,
317}
318
319impl PartialEq for PriorityJob {
320 fn eq(&self, other: &Self) -> bool {
321 self.job.id == other.job.id
322 }
323}
324
325impl Eq for PriorityJob {}
326
327impl PartialOrd for PriorityJob {
328 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
329 Some(self.cmp(other))
330 }
331}
332
333impl Ord for PriorityJob {
334 fn cmp(&self, other: &Self) -> Ordering {
335 if self.mode == SchedulingMode::Fifo || other.mode == SchedulingMode::Fifo {
336 return other
337 .job
338 .arrival_seq
339 .cmp(&self.job.arrival_seq)
340 .then_with(|| other.job.id.cmp(&self.job.id));
341 }
342 self.priority
344 .total_cmp(&other.priority)
345 .then_with(|| self.base_ratio.total_cmp(&other.base_ratio))
347 .then_with(|| self.job.weight.total_cmp(&other.job.weight))
349 .then_with(|| other.job.remaining_time.total_cmp(&self.job.remaining_time))
351 .then_with(|| other.job.arrival_seq.cmp(&self.job.arrival_seq))
353 .then_with(|| other.job.id.cmp(&self.job.id))
355 }
356}
357
358#[derive(Debug, Clone)]
360pub struct SchedulingEvidence {
361 pub current_time: f64,
363
364 pub selected_job_id: Option<u64>,
366
367 pub queue_length: usize,
369
370 pub mean_wait_time: f64,
372
373 pub max_wait_time: f64,
375
376 pub reason: SelectionReason,
378
379 pub tie_break_reason: Option<TieBreakReason>,
381
382 pub jobs: Vec<JobEvidence>,
384}
385
386#[derive(Debug, Clone)]
388pub struct JobEvidence {
389 pub job_id: u64,
391 pub name: Option<String>,
393 pub estimate_ms: f64,
395 pub weight: f64,
397 pub ratio: f64,
399 pub aging_reward: f64,
401 pub starvation_floor: f64,
403 pub age_ms: f64,
405 pub effective_priority: f64,
407 pub objective_loss_proxy: f64,
409 pub estimate_source: EstimateSource,
411 pub weight_source: WeightSource,
413}
414
415#[derive(Debug, Clone, Copy, PartialEq, Eq)]
417pub enum SelectionReason {
418 QueueEmpty,
420 ShortestRemaining,
422 HighestWeightedPriority,
424 Fifo,
426 AgingBoost,
428 Continuation,
430}
431
432impl SelectionReason {
433 fn as_str(self) -> &'static str {
434 match self {
435 Self::QueueEmpty => "queue_empty",
436 Self::ShortestRemaining => "shortest_remaining",
437 Self::HighestWeightedPriority => "highest_weighted_priority",
438 Self::Fifo => "fifo",
439 Self::AgingBoost => "aging_boost",
440 Self::Continuation => "continuation",
441 }
442 }
443}
444
445#[derive(Debug, Clone, Copy, PartialEq, Eq)]
447pub enum EstimateSource {
448 Explicit,
450 Historical,
452 Default,
454 Unknown,
456}
457
458impl EstimateSource {
459 fn as_str(self) -> &'static str {
460 match self {
461 Self::Explicit => "explicit",
462 Self::Historical => "historical",
463 Self::Default => "default",
464 Self::Unknown => "unknown",
465 }
466 }
467}
468
469#[derive(Debug, Clone, Copy, PartialEq, Eq)]
471pub enum WeightSource {
472 Explicit,
474 Default,
476 Unknown,
478}
479
480impl WeightSource {
481 fn as_str(self) -> &'static str {
482 match self {
483 Self::Explicit => "explicit",
484 Self::Default => "default",
485 Self::Unknown => "unknown",
486 }
487 }
488}
489
490#[derive(Debug, Clone, Copy, PartialEq, Eq)]
492pub enum TieBreakReason {
493 EffectivePriority,
495 BaseRatio,
497 Weight,
499 RemainingTime,
501 ArrivalSeq,
503 JobId,
505 Continuation,
507}
508
509impl TieBreakReason {
510 fn as_str(self) -> &'static str {
511 match self {
512 Self::EffectivePriority => "effective_priority",
513 Self::BaseRatio => "base_ratio",
514 Self::Weight => "weight",
515 Self::RemainingTime => "remaining_time",
516 Self::ArrivalSeq => "arrival_seq",
517 Self::JobId => "job_id",
518 Self::Continuation => "continuation",
519 }
520 }
521}
522
523#[derive(Debug, Clone, Copy, PartialEq, Eq)]
525pub enum SchedulingMode {
526 Smith,
528 Srpt,
530 Fifo,
532}
533
534impl SchedulingEvidence {
535 #[must_use]
537 pub fn to_jsonl(&self, event: &str) -> String {
538 let mut out = String::with_capacity(256 + (self.jobs.len() * 64));
539 out.push_str("{\"event\":\"");
540 out.push_str(&escape_json(event));
541 out.push_str("\",\"current_time\":");
542 let _ = write!(out, "{:.6}", self.current_time);
543 out.push_str(",\"selected_job_id\":");
544 match self.selected_job_id {
545 Some(id) => {
546 let _ = write!(out, "{id}");
547 }
548 None => out.push_str("null"),
549 }
550 out.push_str(",\"queue_length\":");
551 let _ = write!(out, "{}", self.queue_length);
552 out.push_str(",\"mean_wait_time\":");
553 let _ = write!(out, "{:.6}", self.mean_wait_time);
554 out.push_str(",\"max_wait_time\":");
555 let _ = write!(out, "{:.6}", self.max_wait_time);
556 out.push_str(",\"reason\":\"");
557 out.push_str(self.reason.as_str());
558 out.push('"');
559 out.push_str(",\"tie_break_reason\":");
560 match self.tie_break_reason {
561 Some(reason) => {
562 out.push('"');
563 out.push_str(reason.as_str());
564 out.push('"');
565 }
566 None => out.push_str("null"),
567 }
568 out.push_str(",\"jobs\":[");
569 for (idx, job) in self.jobs.iter().enumerate() {
570 if idx > 0 {
571 out.push(',');
572 }
573 out.push_str(&job.to_json());
574 }
575 out.push_str("]}");
576 out
577 }
578}
579
580impl JobEvidence {
581 fn to_json(&self) -> String {
582 let mut out = String::with_capacity(128);
583 out.push_str("{\"job_id\":");
584 let _ = write!(out, "{}", self.job_id);
585 out.push_str(",\"name\":");
586 match &self.name {
587 Some(name) => {
588 out.push('"');
589 out.push_str(&escape_json(name));
590 out.push('"');
591 }
592 None => out.push_str("null"),
593 }
594 out.push_str(",\"estimate_ms\":");
595 let _ = write!(out, "{:.6}", self.estimate_ms);
596 out.push_str(",\"weight\":");
597 let _ = write!(out, "{:.6}", self.weight);
598 out.push_str(",\"ratio\":");
599 let _ = write!(out, "{:.6}", self.ratio);
600 out.push_str(",\"aging_reward\":");
601 let _ = write!(out, "{:.6}", self.aging_reward);
602 out.push_str(",\"starvation_floor\":");
603 let _ = write!(out, "{:.6}", self.starvation_floor);
604 out.push_str(",\"age_ms\":");
605 let _ = write!(out, "{:.6}", self.age_ms);
606 out.push_str(",\"effective_priority\":");
607 let _ = write!(out, "{:.6}", self.effective_priority);
608 out.push_str(",\"objective_loss_proxy\":");
609 let _ = write!(out, "{:.6}", self.objective_loss_proxy);
610 out.push_str(",\"estimate_source\":\"");
611 out.push_str(self.estimate_source.as_str());
612 out.push('"');
613 out.push_str(",\"weight_source\":\"");
614 out.push_str(self.weight_source.as_str());
615 out.push('"');
616 out.push('}');
617 out
618 }
619}
620
621pub(crate) fn escape_json(input: &str) -> String {
625 let mut out = String::with_capacity(input.len() + 8);
626 for ch in input.chars() {
627 match ch {
628 '"' => out.push_str("\\\""),
629 '\\' => out.push_str("\\\\"),
630 '\n' => out.push_str("\\n"),
631 '\r' => out.push_str("\\r"),
632 '\t' => out.push_str("\\t"),
633 '\u{08}' => out.push_str("\\b"),
634 '\u{0C}' => out.push_str("\\f"),
635 c if c < ' ' => {
636 let _ = write!(out, "\\u{:04x}", c as u32);
637 }
638 _ => out.push(ch),
639 }
640 }
641 out
642}
643
644#[derive(Debug, Clone, Default)]
646pub struct SchedulerStats {
647 pub total_submitted: u64,
649
650 pub total_completed: u64,
652
653 pub total_rejected: u64,
655
656 pub total_preemptions: u64,
658
659 pub total_processing_time: f64,
661
662 pub total_response_time: f64,
664
665 pub max_response_time: f64,
667
668 pub queue_length: usize,
670}
671
672impl SchedulerStats {
673 pub fn mean_response_time(&self) -> f64 {
675 if self.total_completed > 0 {
676 self.total_response_time / self.total_completed as f64
677 } else {
678 0.0
679 }
680 }
681
682 pub fn throughput(&self) -> f64 {
684 if self.total_processing_time > 0.0 {
685 self.total_completed as f64 / self.total_processing_time
686 } else {
687 0.0
688 }
689 }
690}
691
692#[derive(Debug)]
694pub struct QueueingScheduler {
695 config: SchedulerConfig,
696
697 queue: BinaryHeap<PriorityJob>,
699
700 current_job: Option<Job>,
702
703 current_time: f64,
705
706 next_job_id: u64,
708
709 next_arrival_seq: u64,
711
712 stats: SchedulerStats,
714}
715
716#[derive(Debug, Clone, Copy)]
717struct PriorityTerms {
718 aging_reward: f64,
719 starvation_floor: f64,
720 effective_priority: f64,
721}
722
723impl QueueingScheduler {
724 pub fn new(config: SchedulerConfig) -> Self {
726 Self {
727 config,
728 queue: BinaryHeap::new(),
729 current_job: None,
730 current_time: 0.0,
731 next_job_id: 1,
732 next_arrival_seq: 1,
733 stats: SchedulerStats::default(),
734 }
735 }
736
737 pub fn submit(&mut self, weight: f64, estimated_time: f64) -> Option<u64> {
741 self.submit_named(weight, estimated_time, None::<&str>)
742 }
743
744 pub fn submit_named(
746 &mut self,
747 weight: f64,
748 estimated_time: f64,
749 name: Option<impl Into<String>>,
750 ) -> Option<u64> {
751 self.submit_with_sources(
752 weight,
753 estimated_time,
754 WeightSource::Explicit,
755 EstimateSource::Explicit,
756 name,
757 )
758 }
759
760 pub fn submit_with_sources(
762 &mut self,
763 weight: f64,
764 estimated_time: f64,
765 weight_source: WeightSource,
766 estimate_source: EstimateSource,
767 name: Option<impl Into<String>>,
768 ) -> Option<u64> {
769 if self.queue.len() >= self.config.max_queue_size {
770 self.stats.total_rejected += 1;
771 return None;
772 }
773
774 let id = self.next_job_id;
775 self.next_job_id += 1;
776
777 let mut job = Job {
779 id,
780 weight,
781 remaining_time: estimated_time,
782 total_time: estimated_time,
783 arrival_time: 0.0,
784 arrival_seq: 0,
785 estimate_source,
786 weight_source,
787 name: None,
788 };
789 job.weight = self.normalize_weight_with_source(job.weight, job.weight_source);
790 job.remaining_time =
791 self.normalize_time_with_source(job.remaining_time, job.estimate_source);
792 job.total_time = job.remaining_time;
793 job.arrival_time = self.current_time;
794 job.arrival_seq = self.next_arrival_seq;
795 self.next_arrival_seq += 1;
796 if let Some(n) = name {
797 job.name = Some(n.into());
798 }
799
800 let priority_job = self.make_priority_job(job);
801 self.queue.push(priority_job);
802
803 self.stats.total_submitted += 1;
804 self.stats.queue_length = self.queue.len();
805
806 if self.config.preemptive {
808 self.maybe_preempt();
809 }
810
811 Some(id)
812 }
813
814 pub fn tick(&mut self, delta_time: f64) -> Vec<u64> {
818 let mut completed = Vec::new();
819 if !delta_time.is_finite() || delta_time <= 0.0 {
820 return completed;
821 }
822
823 let mut remaining_time = delta_time;
824 let mut now = self.current_time;
825 let mut processed_time = 0.0;
826
827 while remaining_time > 0.0 {
828 let Some(mut job) = (if let Some(j) = self.current_job.take() {
830 Some(j)
831 } else {
832 self.queue.pop().map(|pj| pj.job)
833 }) else {
834 now += remaining_time;
835 break; };
837
838 let process_time = remaining_time.min(job.remaining_time);
840 job.remaining_time -= process_time;
841 remaining_time -= process_time;
842 now += process_time;
843 processed_time += process_time;
844
845 if job.is_complete() {
846 let response_time = now - job.arrival_time;
848 self.stats.total_response_time += response_time;
849 self.stats.max_response_time = self.stats.max_response_time.max(response_time);
850 self.stats.total_completed += 1;
851 completed.push(job.id);
852 } else {
853 self.current_job = Some(job);
855 }
856 }
857
858 self.stats.total_processing_time += processed_time;
859 self.current_time = now;
860 self.refresh_priorities();
862
863 self.stats.queue_length = self.queue.len();
864 completed
865 }
866
867 pub fn peek_next(&self) -> Option<&Job> {
869 self.current_job
870 .as_ref()
871 .or_else(|| self.queue.peek().map(|pj| &pj.job))
872 }
873
874 pub fn evidence(&self) -> SchedulingEvidence {
876 let (mean_wait, max_wait) = self.compute_wait_stats();
877
878 let mut candidates: Vec<PriorityJob> = self
879 .queue
880 .iter()
881 .map(|pj| self.make_priority_job(pj.job.clone()))
882 .collect();
883
884 if let Some(ref current) = self.current_job {
885 candidates.push(self.make_priority_job(current.clone()));
886 }
887
888 candidates.sort_by(|a, b| b.cmp(a));
889
890 let selected_job_id = if let Some(ref current) = self.current_job {
891 Some(current.id)
892 } else {
893 candidates.first().map(|pj| pj.job.id)
894 };
895
896 let tie_break_reason = if self.current_job.is_some() {
897 Some(TieBreakReason::Continuation)
898 } else if candidates.len() > 1 {
899 Some(self.tie_break_reason(&candidates[0], &candidates[1]))
900 } else {
901 None
902 };
903
904 let reason = if self.queue.is_empty() && self.current_job.is_none() {
905 SelectionReason::QueueEmpty
906 } else if self.current_job.is_some() {
907 SelectionReason::Continuation
908 } else if self.config.mode() == SchedulingMode::Fifo {
909 SelectionReason::Fifo
910 } else if let Some(pj) = candidates.first() {
911 let wait_time = (self.current_time - pj.job.arrival_time).max(0.0);
912 let aging_contribution = self.config.aging_factor * wait_time;
913 let aging_boost = (self.config.wait_starve_ms > 0.0
914 && wait_time >= self.config.wait_starve_ms)
915 || aging_contribution > pj.base_ratio * 0.5;
916 if aging_boost {
917 SelectionReason::AgingBoost
918 } else if self.config.smith_enabled && pj.job.weight > 1.0 {
919 SelectionReason::HighestWeightedPriority
920 } else {
921 SelectionReason::ShortestRemaining
922 }
923 } else {
924 SelectionReason::QueueEmpty
925 };
926
927 let jobs = candidates
928 .iter()
929 .map(|pj| {
930 let age_ms = (self.current_time - pj.job.arrival_time).max(0.0);
931 let terms = self.compute_priority_terms(&pj.job);
932 JobEvidence {
933 job_id: pj.job.id,
934 name: pj.job.name.clone(),
935 estimate_ms: pj.job.remaining_time,
936 weight: pj.job.weight,
937 ratio: pj.base_ratio,
938 aging_reward: terms.aging_reward,
939 starvation_floor: terms.starvation_floor,
940 age_ms,
941 effective_priority: pj.priority,
942 objective_loss_proxy: 1.0 / pj.priority.max(self.config.w_min),
943 estimate_source: pj.job.estimate_source,
944 weight_source: pj.job.weight_source,
945 }
946 })
947 .collect();
948
949 SchedulingEvidence {
950 current_time: self.current_time,
951 selected_job_id,
952 queue_length: self.queue.len() + if self.current_job.is_some() { 1 } else { 0 },
953 mean_wait_time: mean_wait,
954 max_wait_time: max_wait,
955 reason,
956 tie_break_reason,
957 jobs,
958 }
959 }
960
961 pub fn stats(&self) -> SchedulerStats {
963 let mut stats = self.stats.clone();
964 stats.queue_length = self.queue.len() + if self.current_job.is_some() { 1 } else { 0 };
965 stats
966 }
967
968 #[must_use]
970 pub const fn max_queue_size(&self) -> usize {
971 self.config.max_queue_size
972 }
973
974 pub fn cancel(&mut self, job_id: u64) -> bool {
976 if let Some(ref j) = self.current_job
978 && j.id == job_id
979 {
980 self.current_job = None;
981 self.stats.queue_length = self.queue.len();
982 return true;
983 }
984
985 let old_len = self.queue.len();
987 let jobs: Vec<_> = self
988 .queue
989 .drain()
990 .filter(|pj| pj.job.id != job_id)
991 .collect();
992 self.queue = jobs.into_iter().collect();
993
994 self.stats.queue_length = self.queue.len();
995 old_len != self.queue.len()
996 }
997
998 pub fn clear(&mut self) {
1000 self.queue.clear();
1001 self.current_job = None;
1002 self.stats.queue_length = 0;
1003 }
1004
1005 pub fn reset(&mut self) {
1007 self.queue.clear();
1008 self.current_job = None;
1009 self.current_time = 0.0;
1010 self.next_job_id = 1;
1011 self.next_arrival_seq = 1;
1012 self.stats = SchedulerStats::default();
1013 }
1014
1015 fn normalize_weight(&self, weight: f64) -> f64 {
1019 if weight.is_nan() {
1020 return self.config.w_min;
1021 }
1022 if weight.is_infinite() {
1023 return if weight.is_sign_positive() {
1024 self.config.w_max
1025 } else {
1026 self.config.w_min
1027 };
1028 }
1029 weight.max(self.config.w_min).min(self.config.w_max)
1034 }
1035
1036 fn normalize_time(&self, estimate_ms: f64) -> f64 {
1038 if estimate_ms.is_nan() {
1039 return self.config.p_max_ms;
1040 }
1041 if estimate_ms.is_infinite() {
1042 return if estimate_ms.is_sign_positive() {
1043 self.config.p_max_ms
1044 } else {
1045 self.config.p_min_ms
1046 };
1047 }
1048 estimate_ms
1050 .max(self.config.p_min_ms)
1051 .min(self.config.p_max_ms)
1052 }
1053
1054 fn normalize_weight_with_source(&self, weight: f64, source: WeightSource) -> f64 {
1056 let resolved = match source {
1057 WeightSource::Explicit => weight,
1058 WeightSource::Default => self.config.weight_default,
1059 WeightSource::Unknown => self.config.weight_unknown,
1060 };
1061 self.normalize_weight(resolved)
1062 }
1063
1064 fn normalize_time_with_source(&self, estimate_ms: f64, source: EstimateSource) -> f64 {
1066 let resolved = match source {
1067 EstimateSource::Explicit | EstimateSource::Historical => estimate_ms,
1068 EstimateSource::Default => self.config.estimate_default_ms,
1069 EstimateSource::Unknown => self.config.estimate_unknown_ms,
1070 };
1071 self.normalize_time(resolved)
1072 }
1073
1074 fn compute_base_ratio(&self, job: &Job) -> f64 {
1076 if self.config.mode() == SchedulingMode::Fifo {
1077 return 0.0;
1078 }
1079 let remaining = job.remaining_time.max(self.config.p_min_ms);
1080 let weight = match self.config.mode() {
1081 SchedulingMode::Smith => job.weight,
1082 SchedulingMode::Srpt => 1.0,
1083 SchedulingMode::Fifo => 0.0,
1084 };
1085 weight / remaining
1086 }
1087
1088 fn compute_priority_terms(&self, job: &Job) -> PriorityTerms {
1096 if self.config.mode() == SchedulingMode::Fifo {
1097 return PriorityTerms {
1098 aging_reward: 0.0,
1099 starvation_floor: 0.0,
1100 effective_priority: 0.0,
1101 };
1102 }
1103
1104 let base_ratio = self.compute_base_ratio(job);
1105 let wait_time = (self.current_time - job.arrival_time).max(0.0);
1106 let aging_reward = self.config.aging_factor * wait_time;
1107 let starvation_floor =
1108 if self.config.wait_starve_ms > 0.0 && wait_time >= self.config.wait_starve_ms {
1109 base_ratio * self.config.starve_boost_ratio
1110 } else {
1111 0.0
1112 };
1113
1114 let effective_priority = (base_ratio + aging_reward).max(starvation_floor);
1115
1116 PriorityTerms {
1117 aging_reward,
1118 starvation_floor,
1119 effective_priority,
1120 }
1121 }
1122
1123 fn compute_priority(&self, job: &Job) -> f64 {
1125 self.compute_priority_terms(job).effective_priority
1126 }
1127
1128 fn make_priority_job(&self, job: Job) -> PriorityJob {
1130 let base_ratio = self.compute_base_ratio(&job);
1131 let priority = self.compute_priority(&job);
1132 PriorityJob {
1133 priority,
1134 base_ratio,
1135 job,
1136 mode: self.config.mode(),
1137 }
1138 }
1139
1140 fn tie_break_reason(&self, a: &PriorityJob, b: &PriorityJob) -> TieBreakReason {
1142 if self.config.mode() == SchedulingMode::Fifo {
1143 if a.job.arrival_seq != b.job.arrival_seq {
1144 return TieBreakReason::ArrivalSeq;
1145 }
1146 return TieBreakReason::JobId;
1147 }
1148 if a.priority.total_cmp(&b.priority) != Ordering::Equal {
1149 TieBreakReason::EffectivePriority
1150 } else if a.base_ratio.total_cmp(&b.base_ratio) != Ordering::Equal {
1151 TieBreakReason::BaseRatio
1152 } else if a.job.weight.total_cmp(&b.job.weight) != Ordering::Equal {
1153 TieBreakReason::Weight
1154 } else if a.job.remaining_time.total_cmp(&b.job.remaining_time) != Ordering::Equal {
1155 TieBreakReason::RemainingTime
1156 } else if a.job.arrival_seq != b.job.arrival_seq {
1157 TieBreakReason::ArrivalSeq
1158 } else {
1159 TieBreakReason::JobId
1160 }
1161 }
1162
1163 fn maybe_preempt(&mut self) {
1165 if self.config.mode() == SchedulingMode::Fifo {
1166 return;
1167 }
1168 if let Some(ref current) = self.current_job
1169 && let Some(pj) = self.queue.peek()
1170 {
1171 let current_pj = self.make_priority_job(current.clone());
1172 if pj.cmp(¤t_pj) == Ordering::Greater {
1173 let old = self
1175 .current_job
1176 .take()
1177 .expect("current_job guaranteed by if-let guard");
1178 let priority_job = self.make_priority_job(old);
1179 self.queue.push(priority_job);
1180 self.stats.total_preemptions += 1;
1181 }
1182 }
1183 }
1184
1185 fn refresh_priorities(&mut self) {
1187 let jobs: Vec<_> = self.queue.drain().map(|pj| pj.job).collect();
1188 for job in jobs {
1189 let priority_job = self.make_priority_job(job);
1190 self.queue.push(priority_job);
1191 }
1192 }
1193
1194 fn compute_wait_stats(&self) -> (f64, f64) {
1196 let mut total_wait = 0.0;
1197 let mut max_wait = 0.0f64;
1198 let mut count = 0;
1199
1200 for pj in self.queue.iter() {
1201 let wait = (self.current_time - pj.job.arrival_time).max(0.0);
1202 total_wait += wait;
1203 max_wait = max_wait.max(wait);
1204 count += 1;
1205 }
1206
1207 if let Some(ref j) = self.current_job {
1208 let wait = (self.current_time - j.arrival_time).max(0.0);
1209 total_wait += wait;
1210 max_wait = max_wait.max(wait);
1211 count += 1;
1212 }
1213
1214 let mean = if count > 0 {
1215 total_wait / count as f64
1216 } else {
1217 0.0
1218 };
1219 (mean, max_wait)
1220 }
1221}
1222
1223#[cfg(test)]
1228mod tests {
1229 use super::*;
1230 use std::collections::HashMap;
1231
1232 fn test_config() -> SchedulerConfig {
1233 SchedulerConfig {
1234 aging_factor: 0.001,
1235 p_min_ms: DEFAULT_P_MIN_MS,
1236 p_max_ms: DEFAULT_P_MAX_MS,
1237 estimate_default_ms: DEFAULT_ESTIMATE_DEFAULT_MS,
1238 estimate_unknown_ms: DEFAULT_ESTIMATE_UNKNOWN_MS,
1239 w_min: DEFAULT_W_MIN,
1240 w_max: DEFAULT_W_MAX,
1241 weight_default: DEFAULT_WEIGHT_DEFAULT,
1242 weight_unknown: DEFAULT_WEIGHT_UNKNOWN,
1243 wait_starve_ms: DEFAULT_WAIT_STARVE_MS,
1244 starve_boost_ratio: DEFAULT_STARVE_BOOST_RATIO,
1245 smith_enabled: true,
1246 force_fifo: false,
1247 max_queue_size: 100,
1248 preemptive: true,
1249 time_quantum: 10.0,
1250 enable_logging: false,
1251 }
1252 }
1253
1254 #[derive(Clone, Copy, Debug)]
1255 struct WorkloadJob {
1256 arrival: u64,
1257 weight: f64,
1258 duration: f64,
1259 }
1260
1261 #[derive(Clone, Copy, Debug, Eq, PartialEq)]
1262 enum SimPolicy {
1263 Smith,
1264 Fifo,
1265 }
1266
1267 #[derive(Debug)]
1268 struct SimulationMetrics {
1269 mean: f64,
1270 p95: f64,
1271 p99: f64,
1272 max: f64,
1273 job_count: usize,
1274 completion_order: Vec<u64>,
1275 }
1276
1277 fn mixed_workload() -> Vec<WorkloadJob> {
1278 let mut jobs = Vec::new();
1279 jobs.push(WorkloadJob {
1280 arrival: 0,
1281 weight: 1.0,
1282 duration: 100.0,
1283 });
1284 for t in 1..=200u64 {
1285 jobs.push(WorkloadJob {
1286 arrival: t,
1287 weight: 1.0,
1288 duration: 1.0,
1289 });
1290 }
1291 jobs
1292 }
1293
1294 fn percentile(sorted: &[f64], p: f64) -> f64 {
1295 if sorted.is_empty() {
1296 return 0.0;
1297 }
1298 let idx = ((sorted.len() as f64 - 1.0) * p).ceil() as usize;
1299 sorted[idx.min(sorted.len() - 1)]
1300 }
1301
1302 fn summary_json(policy: SimPolicy, metrics: &SimulationMetrics) -> String {
1303 let policy = match policy {
1304 SimPolicy::Smith => "Smith",
1305 SimPolicy::Fifo => "Fifo",
1306 };
1307 let head: Vec<String> = metrics
1308 .completion_order
1309 .iter()
1310 .take(8)
1311 .map(|id| id.to_string())
1312 .collect();
1313 let tail: Vec<String> = metrics
1314 .completion_order
1315 .iter()
1316 .rev()
1317 .take(3)
1318 .collect::<Vec<_>>()
1319 .into_iter()
1320 .rev()
1321 .map(|id| id.to_string())
1322 .collect();
1323 format!(
1324 "{{\"policy\":\"{policy}\",\"jobs\":{jobs},\"mean\":{mean:.3},\"p95\":{p95:.3},\"p99\":{p99:.3},\"max\":{max:.3},\"order_head\":[{head}],\"order_tail\":[{tail}]}}",
1325 policy = policy,
1326 jobs = metrics.job_count,
1327 mean = metrics.mean,
1328 p95 = metrics.p95,
1329 p99 = metrics.p99,
1330 max = metrics.max,
1331 head = head.join(","),
1332 tail = tail.join(",")
1333 )
1334 }
1335
1336 fn workload_summary_json(workload: &[WorkloadJob]) -> String {
1337 if workload.is_empty() {
1338 return "{\"workload\":\"empty\"}".to_string();
1339 }
1340 let mut min_arrival = u64::MAX;
1341 let mut max_arrival = 0u64;
1342 let mut min_duration = f64::INFINITY;
1343 let mut max_duration: f64 = 0.0;
1344 let mut total_work: f64 = 0.0;
1345 let mut long_jobs = 0usize;
1346 let long_threshold = 10.0;
1347
1348 for job in workload {
1349 min_arrival = min_arrival.min(job.arrival);
1350 max_arrival = max_arrival.max(job.arrival);
1351 min_duration = min_duration.min(job.duration);
1352 max_duration = max_duration.max(job.duration);
1353 total_work += job.duration;
1354 if job.duration >= long_threshold {
1355 long_jobs += 1;
1356 }
1357 }
1358
1359 format!(
1360 "{{\"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}}}",
1361 jobs = workload.len(),
1362 arrival_min = min_arrival,
1363 arrival_max = max_arrival,
1364 duration_min = min_duration,
1365 duration_max = max_duration,
1366 total_work = total_work,
1367 long_jobs = long_jobs,
1368 long_threshold = long_threshold
1369 )
1370 }
1371
1372 fn simulate_policy(policy: SimPolicy, workload: &[WorkloadJob]) -> SimulationMetrics {
1373 let mut config = test_config();
1374 config.aging_factor = 0.0;
1375 config.wait_starve_ms = 0.0;
1376 config.starve_boost_ratio = 1.0;
1377 config.smith_enabled = policy == SimPolicy::Smith;
1378 config.force_fifo = policy == SimPolicy::Fifo;
1379 config.preemptive = true;
1380
1381 let mut scheduler = QueueingScheduler::new(config);
1382 let mut arrivals = workload.to_vec();
1383 arrivals.sort_by_key(|job| job.arrival);
1384
1385 let mut arrival_times: HashMap<u64, f64> = HashMap::new();
1386 let mut response_times = Vec::with_capacity(arrivals.len());
1387 let mut completion_order = Vec::with_capacity(arrivals.len());
1388
1389 let mut idx = 0usize;
1390 let mut safety = 0usize;
1391
1392 while (idx < arrivals.len() || scheduler.peek_next().is_some()) && safety < 10_000 {
1393 let now = scheduler.current_time;
1394
1395 while idx < arrivals.len() && (arrivals[idx].arrival as f64) <= now + f64::EPSILON {
1396 let job = arrivals[idx];
1397 let id = scheduler
1398 .submit(job.weight, job.duration)
1399 .expect("queue capacity should not be exceeded");
1400 arrival_times.insert(id, scheduler.current_time);
1401 idx += 1;
1402 }
1403
1404 if scheduler.peek_next().is_none() {
1405 if idx < arrivals.len() {
1406 let next_time = arrivals[idx].arrival as f64;
1407 let delta = (next_time - scheduler.current_time).max(0.0);
1408 let completed = scheduler.tick(delta);
1409 for id in completed {
1410 let arrival = arrival_times.get(&id).copied().unwrap_or(0.0);
1411 response_times.push(scheduler.current_time - arrival);
1412 completion_order.push(id);
1413 }
1414 }
1415 safety += 1;
1416 continue;
1417 }
1418
1419 let completed = scheduler.tick(1.0);
1420 for id in completed {
1421 let arrival = arrival_times.get(&id).copied().unwrap_or(0.0);
1422 response_times.push(scheduler.current_time - arrival);
1423 completion_order.push(id);
1424 }
1425 safety += 1;
1426 }
1427
1428 assert_eq!(
1429 response_times.len(),
1430 arrivals.len(),
1431 "simulation did not complete all jobs"
1432 );
1433
1434 let mut sorted = response_times.clone();
1435 sorted.sort_by(|a, b| a.partial_cmp(b).unwrap());
1436
1437 let mean = response_times.iter().sum::<f64>() / response_times.len() as f64;
1438 let p95 = percentile(&sorted, 0.95);
1439 let p99 = percentile(&sorted, 0.99);
1440 let max = *sorted.last().unwrap_or(&0.0);
1441
1442 SimulationMetrics {
1443 mean,
1444 p95,
1445 p99,
1446 max,
1447 job_count: response_times.len(),
1448 completion_order,
1449 }
1450 }
1451
1452 #[test]
1457 fn new_creates_empty_scheduler() {
1458 let scheduler = QueueingScheduler::new(test_config());
1459 assert_eq!(scheduler.stats().queue_length, 0);
1460 assert!(scheduler.peek_next().is_none());
1461 }
1462
1463 #[test]
1464 fn default_config_valid() {
1465 let config = SchedulerConfig::default();
1466 let scheduler = QueueingScheduler::new(config);
1467 assert_eq!(scheduler.stats().queue_length, 0);
1468 }
1469
1470 #[test]
1475 fn submit_returns_job_id() {
1476 let mut scheduler = QueueingScheduler::new(test_config());
1477 let id = scheduler.submit(1.0, 10.0);
1478 assert_eq!(id, Some(1));
1479 }
1480
1481 #[test]
1482 fn submit_increments_job_id() {
1483 let mut scheduler = QueueingScheduler::new(test_config());
1484 let id1 = scheduler.submit(1.0, 10.0);
1485 let id2 = scheduler.submit(1.0, 10.0);
1486 assert_eq!(id1, Some(1));
1487 assert_eq!(id2, Some(2));
1488 }
1489
1490 #[test]
1491 fn submit_rejects_when_queue_full() {
1492 let mut config = test_config();
1493 config.max_queue_size = 2;
1494 let mut scheduler = QueueingScheduler::new(config);
1495
1496 assert!(scheduler.submit(1.0, 10.0).is_some());
1497 assert!(scheduler.submit(1.0, 10.0).is_some());
1498 assert!(scheduler.submit(1.0, 10.0).is_none()); assert_eq!(scheduler.stats().total_rejected, 1);
1500 }
1501
1502 #[test]
1503 fn submit_named_job() {
1504 let mut scheduler = QueueingScheduler::new(test_config());
1505 let id = scheduler.submit_named(1.0, 10.0, Some("test-job"));
1506 assert!(id.is_some());
1507 }
1508
1509 #[test]
1514 fn srpt_prefers_shorter_jobs() {
1515 let mut scheduler = QueueingScheduler::new(test_config());
1516
1517 scheduler.submit(1.0, 100.0); scheduler.submit(1.0, 10.0); let next = scheduler.peek_next().unwrap();
1521 assert_eq!(next.remaining_time, 10.0); }
1523
1524 #[test]
1525 fn smith_rule_prefers_high_weight() {
1526 let mut scheduler = QueueingScheduler::new(test_config());
1527
1528 scheduler.submit(1.0, 10.0); scheduler.submit(10.0, 10.0); let next = scheduler.peek_next().unwrap();
1532 assert_eq!(next.weight, 10.0); }
1534
1535 #[test]
1536 fn smith_rule_balances_weight_and_time() {
1537 let mut scheduler = QueueingScheduler::new(test_config());
1538
1539 scheduler.submit(2.0, 20.0); scheduler.submit(1.0, 5.0); let next = scheduler.peek_next().unwrap();
1543 assert_eq!(next.remaining_time, 5.0); }
1545
1546 #[test]
1551 fn aging_increases_priority_over_time() {
1552 let mut scheduler = QueueingScheduler::new(test_config());
1553
1554 scheduler.submit(1.0, 100.0); scheduler.tick(0.0); let before_aging = scheduler.compute_priority(scheduler.peek_next().unwrap());
1558
1559 scheduler.current_time = 100.0; scheduler.refresh_priorities();
1561
1562 let after_aging = scheduler.compute_priority(scheduler.peek_next().unwrap());
1563 assert!(
1564 after_aging > before_aging,
1565 "Priority should increase with wait time"
1566 );
1567 }
1568
1569 #[test]
1570 fn aging_prevents_starvation() {
1571 let mut config = test_config();
1572 config.aging_factor = 1.0; let mut scheduler = QueueingScheduler::new(config);
1574
1575 scheduler.submit(1.0, 1000.0); scheduler.submit(1.0, 1.0); assert_eq!(scheduler.peek_next().unwrap().remaining_time, 1.0);
1580
1581 let completed = scheduler.tick(1.0);
1583 assert_eq!(completed.len(), 1);
1584
1585 assert!(scheduler.peek_next().is_some());
1586 }
1587
1588 #[test]
1593 fn preemption_when_higher_priority_arrives() {
1594 let mut scheduler = QueueingScheduler::new(test_config());
1595
1596 scheduler.submit(1.0, 100.0); scheduler.tick(10.0); let before = scheduler.peek_next().unwrap().remaining_time;
1600 assert_eq!(before, 90.0);
1601
1602 scheduler.submit(1.0, 5.0); let next = scheduler.peek_next().unwrap();
1606 assert_eq!(next.remaining_time, 5.0);
1607
1608 assert_eq!(scheduler.stats().total_preemptions, 1);
1610 }
1611
1612 #[test]
1613 fn no_preemption_when_disabled() {
1614 let mut config = test_config();
1615 config.preemptive = false;
1616 let mut scheduler = QueueingScheduler::new(config);
1617
1618 scheduler.submit(1.0, 100.0);
1619 scheduler.tick(10.0);
1620
1621 scheduler.submit(1.0, 5.0); let next = scheduler.peek_next().unwrap();
1625 assert_eq!(next.remaining_time, 90.0);
1626 }
1627
1628 #[test]
1633 fn tick_processes_jobs() {
1634 let mut scheduler = QueueingScheduler::new(test_config());
1635
1636 scheduler.submit(1.0, 10.0);
1637 let completed = scheduler.tick(5.0);
1638
1639 assert!(completed.is_empty()); assert_eq!(scheduler.peek_next().unwrap().remaining_time, 5.0);
1641 }
1642
1643 #[test]
1644 fn tick_completes_jobs() {
1645 let mut scheduler = QueueingScheduler::new(test_config());
1646
1647 scheduler.submit(1.0, 10.0);
1648 let completed = scheduler.tick(10.0);
1649
1650 assert_eq!(completed.len(), 1);
1651 assert_eq!(completed[0], 1);
1652 assert!(scheduler.peek_next().is_none());
1653 }
1654
1655 #[test]
1656 fn tick_completes_multiple_jobs() {
1657 let mut scheduler = QueueingScheduler::new(test_config());
1658
1659 scheduler.submit(1.0, 5.0);
1660 scheduler.submit(1.0, 5.0);
1661 let completed = scheduler.tick(10.0);
1662
1663 assert_eq!(completed.len(), 2);
1664 }
1665
1666 #[test]
1667 fn tick_handles_zero_delta() {
1668 let mut scheduler = QueueingScheduler::new(test_config());
1669 scheduler.submit(1.0, 10.0);
1670 let completed = scheduler.tick(0.0);
1671 assert!(completed.is_empty());
1672 }
1673
1674 #[test]
1679 fn stats_track_submissions() {
1680 let mut scheduler = QueueingScheduler::new(test_config());
1681
1682 scheduler.submit(1.0, 10.0);
1683 scheduler.submit(1.0, 10.0);
1684
1685 let stats = scheduler.stats();
1686 assert_eq!(stats.total_submitted, 2);
1687 assert_eq!(stats.queue_length, 2);
1688 }
1689
1690 #[test]
1691 fn stats_track_completions() {
1692 let mut scheduler = QueueingScheduler::new(test_config());
1693
1694 scheduler.submit(1.0, 10.0);
1695 scheduler.tick(10.0);
1696
1697 let stats = scheduler.stats();
1698 assert_eq!(stats.total_completed, 1);
1699 }
1700
1701 #[test]
1702 fn stats_compute_mean_response_time() {
1703 let mut scheduler = QueueingScheduler::new(test_config());
1704
1705 scheduler.submit(1.0, 10.0);
1706 scheduler.submit(1.0, 10.0);
1707 scheduler.tick(20.0);
1708
1709 let stats = scheduler.stats();
1710 assert_eq!(stats.total_completed, 2);
1713 assert!(stats.mean_response_time() > 0.0);
1714 }
1715
1716 #[test]
1717 fn stats_compute_throughput() {
1718 let mut scheduler = QueueingScheduler::new(test_config());
1719
1720 scheduler.submit(1.0, 10.0);
1721 scheduler.tick(10.0);
1722
1723 let stats = scheduler.stats();
1724 assert!((stats.throughput() - 0.1).abs() < 0.01);
1726 }
1727
1728 #[test]
1733 fn evidence_reports_queue_empty() {
1734 let scheduler = QueueingScheduler::new(test_config());
1735 let evidence = scheduler.evidence();
1736 assert_eq!(evidence.reason, SelectionReason::QueueEmpty);
1737 assert!(evidence.selected_job_id.is_none());
1738 assert!(evidence.tie_break_reason.is_none());
1739 assert!(evidence.jobs.is_empty());
1740 }
1741
1742 #[test]
1743 fn evidence_reports_selected_job() {
1744 let mut scheduler = QueueingScheduler::new(test_config());
1745 scheduler.submit(1.0, 10.0);
1746 let evidence = scheduler.evidence();
1747 assert_eq!(evidence.selected_job_id, Some(1));
1748 assert_eq!(evidence.jobs.len(), 1);
1749 }
1750
1751 #[test]
1752 fn evidence_reports_wait_stats() {
1753 let mut scheduler = QueueingScheduler::new(test_config());
1754 scheduler.submit(1.0, 100.0);
1755 scheduler.submit(1.0, 100.0);
1756 scheduler.current_time = 50.0;
1757 scheduler.refresh_priorities();
1758
1759 let evidence = scheduler.evidence();
1760 assert!(evidence.mean_wait_time > 0.0);
1761 assert!(evidence.max_wait_time > 0.0);
1762 }
1763
1764 #[test]
1765 fn evidence_reports_priority_objective_terms() {
1766 let mut config = test_config();
1767 config.aging_factor = 0.5;
1768 config.wait_starve_ms = 10.0;
1769 config.starve_boost_ratio = 2.0;
1770 let mut scheduler = QueueingScheduler::new(config);
1771
1772 scheduler.submit(1.0, 20.0);
1773 scheduler.current_time = 20.0;
1774 scheduler.refresh_priorities();
1775
1776 let evidence = scheduler.evidence();
1777 let job = evidence.jobs.first().expect("job evidence");
1778 assert!(job.aging_reward > 0.0);
1779 assert!(job.starvation_floor > 0.0);
1780 assert!(job.effective_priority >= job.ratio + job.aging_reward);
1781 assert!(
1782 (job.objective_loss_proxy - (1.0 / job.effective_priority.max(DEFAULT_W_MIN))).abs()
1783 < 1e-9
1784 );
1785 }
1786
1787 #[test]
1792 fn force_fifo_overrides_priority() {
1793 let mut config = test_config();
1794 config.force_fifo = true;
1795 let mut scheduler = QueueingScheduler::new(config);
1796
1797 let first = scheduler.submit(1.0, 100.0).unwrap();
1798 let second = scheduler.submit(10.0, 1.0).unwrap();
1799
1800 let next = scheduler.peek_next().unwrap();
1801 assert_eq!(next.id, first);
1802 assert_ne!(next.id, second);
1803 assert_eq!(scheduler.evidence().reason, SelectionReason::Fifo);
1804 }
1805
1806 #[test]
1807 fn default_sources_use_config_values() {
1808 let mut config = test_config();
1809 config.weight_default = 7.0;
1810 config.estimate_default_ms = 12.0;
1811 let mut scheduler = QueueingScheduler::new(config);
1812
1813 scheduler.submit_with_sources(
1814 999.0,
1815 999.0,
1816 WeightSource::Default,
1817 EstimateSource::Default,
1818 None::<&str>,
1819 );
1820
1821 let next = scheduler.peek_next().unwrap();
1822 assert!((next.weight - 7.0).abs() < f64::EPSILON);
1823 assert!((next.remaining_time - 12.0).abs() < f64::EPSILON);
1824 }
1825
1826 #[test]
1827 fn unknown_sources_use_config_values() {
1828 let mut config = test_config();
1829 config.weight_unknown = 2.5;
1830 config.estimate_unknown_ms = 250.0;
1831 let mut scheduler = QueueingScheduler::new(config);
1832
1833 scheduler.submit_with_sources(
1834 0.0,
1835 0.0,
1836 WeightSource::Unknown,
1837 EstimateSource::Unknown,
1838 None::<&str>,
1839 );
1840
1841 let next = scheduler.peek_next().unwrap();
1842 assert!((next.weight - 2.5).abs() < f64::EPSILON);
1843 assert!((next.remaining_time - 250.0).abs() < f64::EPSILON);
1844 }
1845
1846 #[test]
1851 fn tie_break_prefers_base_ratio_when_effective_equal() {
1852 let mut config = test_config();
1853 config.aging_factor = 0.1;
1854 let mut scheduler = QueueingScheduler::new(config);
1855
1856 let id_a = scheduler.submit(1.0, 2.0).unwrap(); scheduler.current_time = 5.0;
1859 scheduler.refresh_priorities();
1860
1861 let id_b = scheduler.submit(1.0, 1.0).unwrap(); scheduler.refresh_priorities();
1864
1865 let next = scheduler.peek_next().unwrap();
1866 assert_eq!(next.id, id_b);
1867
1868 let evidence = scheduler.evidence();
1869 assert_eq!(evidence.selected_job_id, Some(id_b));
1870 assert_eq!(evidence.tie_break_reason, Some(TieBreakReason::BaseRatio));
1871 assert_ne!(id_a, id_b);
1872 }
1873
1874 #[test]
1875 fn tie_break_prefers_weight_over_arrival() {
1876 let mut scheduler = QueueingScheduler::new(test_config());
1877
1878 let high_weight = scheduler.submit(2.0, 2.0).unwrap(); let _low_weight = scheduler.submit(1.0, 1.0).unwrap(); let evidence = scheduler.evidence();
1882 assert_eq!(evidence.selected_job_id, Some(high_weight));
1883 assert_eq!(evidence.tie_break_reason, Some(TieBreakReason::Weight));
1884 }
1885
1886 #[test]
1887 fn tie_break_prefers_arrival_seq_when_all_equal() {
1888 let mut config = test_config();
1889 config.aging_factor = 0.0;
1890 let mut scheduler = QueueingScheduler::new(config);
1891
1892 let first = scheduler.submit(1.0, 10.0).unwrap();
1893 let second = scheduler.submit(1.0, 10.0).unwrap();
1894
1895 let evidence = scheduler.evidence();
1896 assert_eq!(evidence.selected_job_id, Some(first));
1897 assert_eq!(evidence.tie_break_reason, Some(TieBreakReason::ArrivalSeq));
1898 assert_ne!(first, second);
1899 }
1900
1901 #[test]
1906 fn srpt_mode_ignores_weights() {
1907 let mut config = test_config();
1908 config.smith_enabled = false;
1909 let mut scheduler = QueueingScheduler::new(config);
1910
1911 scheduler.submit(10.0, 100.0); scheduler.submit(1.0, 10.0); let next = scheduler.peek_next().unwrap();
1915 assert_eq!(next.remaining_time, 10.0);
1916 assert_eq!(
1917 scheduler.evidence().reason,
1918 SelectionReason::ShortestRemaining
1919 );
1920 }
1921
1922 #[test]
1923 fn fifo_mode_disables_preemption() {
1924 let mut config = test_config();
1925 config.force_fifo = true;
1926 config.preemptive = true;
1927 let mut scheduler = QueueingScheduler::new(config);
1928
1929 let first = scheduler.submit(1.0, 100.0).unwrap();
1930 scheduler.tick(10.0);
1931
1932 let _later = scheduler.submit(10.0, 1.0).unwrap();
1933 let next = scheduler.peek_next().unwrap();
1934 assert_eq!(next.id, first);
1935 }
1936
1937 #[test]
1938 fn explicit_zero_weight_clamps_to_min() {
1939 let mut config = test_config();
1940 config.w_min = 0.5;
1941 let mut scheduler = QueueingScheduler::new(config);
1942
1943 scheduler.submit_with_sources(
1944 0.0,
1945 1.0,
1946 WeightSource::Explicit,
1947 EstimateSource::Explicit,
1948 None::<&str>,
1949 );
1950
1951 let next = scheduler.peek_next().unwrap();
1952 assert!((next.weight - 0.5).abs() < f64::EPSILON);
1953 }
1954
1955 #[test]
1956 fn explicit_zero_estimate_clamps_to_min() {
1957 let mut config = test_config();
1958 config.p_min_ms = 2.0;
1959 let mut scheduler = QueueingScheduler::new(config);
1960
1961 scheduler.submit_with_sources(
1962 1.0,
1963 0.0,
1964 WeightSource::Explicit,
1965 EstimateSource::Explicit,
1966 None::<&str>,
1967 );
1968
1969 let next = scheduler.peek_next().unwrap();
1970 assert!((next.remaining_time - 2.0).abs() < f64::EPSILON);
1971 }
1972
1973 #[test]
1974 fn explicit_weight_honors_config_w_max_above_defaults() {
1975 let mut config = test_config();
1976 config.w_max = 50.0;
1977 let mut scheduler = QueueingScheduler::new(config);
1978
1979 scheduler.submit_with_sources(
1980 20.0,
1981 1.0,
1982 WeightSource::Explicit,
1983 EstimateSource::Explicit,
1984 None::<&str>,
1985 );
1986
1987 let next = scheduler.peek_next().unwrap();
1988 assert!((next.weight - 20.0).abs() < f64::EPSILON);
1989 }
1990
1991 #[test]
1992 fn explicit_estimate_honors_config_p_max_above_defaults() {
1993 let mut config = test_config();
1994 config.p_max_ms = 100_000.0;
1995 let mut scheduler = QueueingScheduler::new(config);
1996
1997 scheduler.submit_with_sources(
1998 1.0,
1999 50_000.0,
2000 WeightSource::Explicit,
2001 EstimateSource::Explicit,
2002 None::<&str>,
2003 );
2004
2005 let next = scheduler.peek_next().unwrap();
2006 assert!((next.remaining_time - 50_000.0).abs() < f64::EPSILON);
2007 }
2008
2009 #[test]
2010 fn inverted_or_nan_config_bounds_do_not_panic_on_submit() {
2011 let mut config = test_config();
2014 config.w_min = 10.0;
2015 config.w_max = 1.0;
2016 config.p_min_ms = f64::NAN;
2017 config.p_max_ms = 2.0;
2018 let mut scheduler = QueueingScheduler::new(config);
2019 assert!(scheduler.submit(5.0, 50.0).is_some());
2020 let next = scheduler.peek_next().unwrap();
2021 assert!((next.weight - 1.0).abs() < f64::EPSILON);
2022 assert!((next.remaining_time - 2.0).abs() < f64::EPSILON);
2023 }
2024
2025 #[test]
2030 fn cancel_removes_job() {
2031 let mut scheduler = QueueingScheduler::new(test_config());
2032 let id = scheduler.submit(1.0, 10.0).unwrap();
2033
2034 assert!(scheduler.cancel(id));
2035 assert!(scheduler.peek_next().is_none());
2036 }
2037
2038 #[test]
2039 fn cancel_returns_false_for_nonexistent() {
2040 let mut scheduler = QueueingScheduler::new(test_config());
2041 assert!(!scheduler.cancel(999));
2042 }
2043
2044 #[test]
2049 fn reset_clears_all_state() {
2050 let mut scheduler = QueueingScheduler::new(test_config());
2051
2052 scheduler.submit(1.0, 10.0);
2053 scheduler.tick(5.0);
2054
2055 scheduler.reset();
2056
2057 assert!(scheduler.peek_next().is_none());
2058 assert_eq!(scheduler.stats().total_submitted, 0);
2059 assert_eq!(scheduler.stats().total_completed, 0);
2060 }
2061
2062 #[test]
2063 fn clear_removes_jobs_but_keeps_stats() {
2064 let mut scheduler = QueueingScheduler::new(test_config());
2065
2066 scheduler.submit(1.0, 10.0);
2067 scheduler.clear();
2068
2069 assert!(scheduler.peek_next().is_none());
2070 assert_eq!(scheduler.stats().total_submitted, 1); }
2072
2073 #[test]
2078 fn job_progress_increases() {
2079 let mut job = Job::new(1, 1.0, 100.0);
2080 assert_eq!(job.progress(), 0.0);
2081
2082 job.remaining_time = 50.0;
2083 assert!((job.progress() - 0.5).abs() < 0.01);
2084
2085 job.remaining_time = 0.0;
2086 assert_eq!(job.progress(), 1.0);
2087 }
2088
2089 #[test]
2090 fn job_is_complete() {
2091 let mut job = Job::new(1, 1.0, 10.0);
2092 assert!(!job.is_complete());
2093
2094 job.remaining_time = 0.0;
2095 assert!(job.is_complete());
2096 }
2097
2098 #[test]
2103 fn property_work_conserving() {
2104 let mut scheduler = QueueingScheduler::new(test_config());
2105
2106 for i in 0..10 {
2108 scheduler.submit(1.0, (i as f64) + 1.0);
2109 }
2110
2111 let mut total_processed = 0;
2113 while scheduler.peek_next().is_some() {
2114 let completed = scheduler.tick(1.0);
2115 total_processed += completed.len();
2116 }
2117
2118 assert_eq!(total_processed, 10);
2119 }
2120
2121 #[test]
2122 fn property_bounded_memory() {
2123 let mut config = test_config();
2124 config.max_queue_size = 100;
2125 let mut scheduler = QueueingScheduler::new(config);
2126
2127 for _ in 0..1000 {
2129 scheduler.submit(1.0, 10.0);
2130 }
2131
2132 assert!(scheduler.stats().queue_length <= 100);
2133 }
2134
2135 #[test]
2136 fn property_deterministic() {
2137 let run = || {
2138 let mut scheduler = QueueingScheduler::new(test_config());
2139 let mut completions = Vec::new();
2140
2141 for i in 0..20 {
2142 scheduler.submit(((i % 3) + 1) as f64, ((i % 5) + 1) as f64);
2143 }
2144
2145 for _ in 0..50 {
2146 completions.extend(scheduler.tick(1.0));
2147 }
2148
2149 completions
2150 };
2151
2152 let run1 = run();
2153 let run2 = run();
2154
2155 assert_eq!(run1, run2, "Scheduling should be deterministic");
2156 }
2157
2158 #[test]
2159 fn smith_beats_fifo_on_mixed_workload() {
2160 let workload = mixed_workload();
2161 let smith = simulate_policy(SimPolicy::Smith, &workload);
2162 let fifo = simulate_policy(SimPolicy::Fifo, &workload);
2163
2164 eprintln!("{}", workload_summary_json(&workload));
2165 eprintln!("{}", summary_json(SimPolicy::Smith, &smith));
2166 eprintln!("{}", summary_json(SimPolicy::Fifo, &fifo));
2167
2168 assert!(
2169 smith.mean < fifo.mean,
2170 "mean should improve: smith={} fifo={}",
2171 summary_json(SimPolicy::Smith, &smith),
2172 summary_json(SimPolicy::Fifo, &fifo)
2173 );
2174 assert!(
2175 smith.p95 < fifo.p95,
2176 "p95 should improve: smith={} fifo={}",
2177 summary_json(SimPolicy::Smith, &smith),
2178 summary_json(SimPolicy::Fifo, &fifo)
2179 );
2180 assert!(
2181 smith.p99 < fifo.p99,
2182 "p99 should improve: smith={} fifo={}",
2183 summary_json(SimPolicy::Smith, &smith),
2184 summary_json(SimPolicy::Fifo, &fifo)
2185 );
2186 }
2187
2188 #[test]
2189 fn simulation_is_deterministic_per_policy() {
2190 let workload = mixed_workload();
2191 let smith1 = simulate_policy(SimPolicy::Smith, &workload);
2192 let smith2 = simulate_policy(SimPolicy::Smith, &workload);
2193 let fifo1 = simulate_policy(SimPolicy::Fifo, &workload);
2194 let fifo2 = simulate_policy(SimPolicy::Fifo, &workload);
2195
2196 assert_eq!(smith1.completion_order, smith2.completion_order);
2197 assert_eq!(fifo1.completion_order, fifo2.completion_order);
2198 assert!((smith1.mean - smith2.mean).abs() < 1e-9);
2199 assert!((fifo1.mean - fifo2.mean).abs() < 1e-9);
2200 }
2201
2202 #[test]
2203 fn effect_queue_trace_is_deterministic() {
2204 let mut config = test_config();
2205 config.preemptive = false;
2206 config.aging_factor = 0.0;
2207 config.wait_starve_ms = 0.0;
2208 config.force_fifo = false;
2209 config.smith_enabled = true;
2210
2211 let mut scheduler = QueueingScheduler::new(config);
2212 let id_alpha = scheduler
2213 .submit_with_sources(
2214 1.0,
2215 8.0,
2216 WeightSource::Explicit,
2217 EstimateSource::Explicit,
2218 Some("alpha"),
2219 )
2220 .expect("alpha accepted");
2221 let id_beta = scheduler
2222 .submit_with_sources(
2223 4.0,
2224 2.0,
2225 WeightSource::Explicit,
2226 EstimateSource::Explicit,
2227 Some("beta"),
2228 )
2229 .expect("beta accepted");
2230 let id_gamma = scheduler
2231 .submit_with_sources(
2232 2.0,
2233 10.0,
2234 WeightSource::Explicit,
2235 EstimateSource::Explicit,
2236 Some("gamma"),
2237 )
2238 .expect("gamma accepted");
2239 let id_delta = scheduler
2240 .submit_with_sources(
2241 3.0,
2242 3.0,
2243 WeightSource::Explicit,
2244 EstimateSource::Explicit,
2245 Some("delta"),
2246 )
2247 .expect("delta accepted");
2248
2249 scheduler.refresh_priorities();
2250
2251 let mut selected = Vec::new();
2252 while let Some(job) = scheduler.peek_next().cloned() {
2253 let evidence = scheduler.evidence();
2254 if let Some(id) = evidence.selected_job_id {
2255 selected.push(id);
2256 }
2257 println!("{}", evidence.to_jsonl("effect_queue_select"));
2258
2259 let completed = scheduler.tick(job.remaining_time);
2260 assert!(
2261 !completed.is_empty(),
2262 "expected completion per tick in non-preemptive mode"
2263 );
2264 }
2265
2266 assert_eq!(selected, vec![id_beta, id_delta, id_gamma, id_alpha]);
2267 }
2268
2269 #[test]
2274 fn zero_weight_handled() {
2275 let mut scheduler = QueueingScheduler::new(test_config());
2276 scheduler.submit(0.0, 10.0);
2277 assert!(scheduler.peek_next().is_some());
2278 }
2279
2280 #[test]
2281 fn zero_time_completes_immediately() {
2282 let mut scheduler = QueueingScheduler::new(test_config());
2283 scheduler.submit(1.0, 0.0);
2284 let completed = scheduler.tick(1.0);
2285 assert_eq!(completed.len(), 1);
2286 }
2287
2288 #[test]
2289 fn negative_time_handled() {
2290 let mut scheduler = QueueingScheduler::new(test_config());
2291 scheduler.submit(1.0, -10.0);
2292 let completed = scheduler.tick(1.0);
2293 assert_eq!(completed.len(), 1);
2294 }
2295
2296 #[test]
2297 fn tick_non_finite_delta_noops() {
2298 let mut scheduler = QueueingScheduler::new(test_config());
2299 scheduler.submit(1.0, 5.0);
2300
2301 let before = scheduler.stats();
2302 assert!(scheduler.tick(f64::NAN).is_empty());
2303 assert!(scheduler.tick(f64::INFINITY).is_empty());
2304 assert!(scheduler.tick(f64::NEG_INFINITY).is_empty());
2305 let after = scheduler.stats();
2306
2307 assert_eq!(before.total_processing_time, after.total_processing_time);
2308 assert_eq!(before.total_completed, after.total_completed);
2309 assert!(scheduler.peek_next().is_some());
2310 }
2311
2312 #[test]
2317 fn job_new_nan_weight_clamps_to_min() {
2318 let job = Job::new(1, f64::NAN, 10.0);
2319 assert_eq!(job.weight, DEFAULT_W_MIN);
2320 }
2321
2322 #[test]
2323 fn job_new_pos_inf_weight_clamps_to_max() {
2324 let job = Job::new(1, f64::INFINITY, 10.0);
2325 assert_eq!(job.weight, DEFAULT_W_MAX);
2326 }
2327
2328 #[test]
2329 fn job_new_neg_inf_weight_clamps_to_min() {
2330 let job = Job::new(1, f64::NEG_INFINITY, 10.0);
2331 assert_eq!(job.weight, DEFAULT_W_MIN);
2332 }
2333
2334 #[test]
2335 fn job_new_nan_estimate_clamps_to_max() {
2336 let job = Job::new(1, 1.0, f64::NAN);
2337 assert_eq!(job.remaining_time, DEFAULT_P_MAX_MS);
2338 assert_eq!(job.total_time, DEFAULT_P_MAX_MS);
2339 }
2340
2341 #[test]
2342 fn job_new_pos_inf_estimate_clamps_to_max() {
2343 let job = Job::new(1, 1.0, f64::INFINITY);
2344 assert_eq!(job.remaining_time, DEFAULT_P_MAX_MS);
2345 }
2346
2347 #[test]
2348 fn job_new_neg_inf_estimate_clamps_to_min() {
2349 let job = Job::new(1, 1.0, f64::NEG_INFINITY);
2350 assert_eq!(job.remaining_time, DEFAULT_P_MIN_MS);
2351 }
2352
2353 #[test]
2354 fn job_with_name_sets_name() {
2355 let job = Job::with_name(1, 1.0, 10.0, "alpha");
2356 assert_eq!(job.name.as_deref(), Some("alpha"));
2357 assert_eq!(job.id, 1);
2358 }
2359
2360 #[test]
2361 fn job_with_sources_sets_both() {
2362 let job =
2363 Job::new(1, 1.0, 10.0).with_sources(WeightSource::Unknown, EstimateSource::Historical);
2364 assert_eq!(job.weight_source, WeightSource::Unknown);
2365 assert_eq!(job.estimate_source, EstimateSource::Historical);
2366 }
2367
2368 #[test]
2369 fn job_progress_zero_total_time() {
2370 let mut job = Job::new(1, 1.0, 10.0);
2371 job.total_time = 0.0;
2372 assert_eq!(job.progress(), 1.0);
2373 }
2374
2375 #[test]
2376 fn job_is_complete_negative_remaining() {
2377 let mut job = Job::new(1, 1.0, 10.0);
2378 job.remaining_time = -5.0;
2379 assert!(job.is_complete());
2380 }
2381
2382 #[test]
2387 fn submit_nan_weight_normalized() {
2388 let mut scheduler = QueueingScheduler::new(test_config());
2389 scheduler.submit(f64::NAN, 10.0);
2390 let next = scheduler.peek_next().unwrap();
2391 assert!(next.weight >= DEFAULT_W_MIN);
2392 assert!(next.weight.is_finite());
2393 }
2394
2395 #[test]
2396 fn submit_inf_weight_normalized() {
2397 let mut scheduler = QueueingScheduler::new(test_config());
2398 scheduler.submit(f64::INFINITY, 10.0);
2399 let next = scheduler.peek_next().unwrap();
2400 assert!(next.weight <= DEFAULT_W_MAX);
2401 assert!(next.weight.is_finite());
2402 }
2403
2404 #[test]
2405 fn submit_nan_estimate_normalized() {
2406 let mut scheduler = QueueingScheduler::new(test_config());
2407 scheduler.submit(1.0, f64::NAN);
2408 let next = scheduler.peek_next().unwrap();
2409 assert!(next.remaining_time <= DEFAULT_P_MAX_MS);
2410 assert!(next.remaining_time.is_finite());
2411 }
2412
2413 #[test]
2414 fn submit_inf_estimate_normalized() {
2415 let mut scheduler = QueueingScheduler::new(test_config());
2416 scheduler.submit(1.0, f64::INFINITY);
2417 let next = scheduler.peek_next().unwrap();
2418 assert!(next.remaining_time <= DEFAULT_P_MAX_MS);
2419 assert!(next.remaining_time.is_finite());
2420 }
2421
2422 #[test]
2427 fn config_mode_smith() {
2428 let config = SchedulerConfig {
2429 smith_enabled: true,
2430 force_fifo: false,
2431 ..Default::default()
2432 };
2433 assert_eq!(config.mode(), SchedulingMode::Smith);
2434 }
2435
2436 #[test]
2437 fn config_mode_srpt() {
2438 let config = SchedulerConfig {
2439 smith_enabled: false,
2440 force_fifo: false,
2441 ..Default::default()
2442 };
2443 assert_eq!(config.mode(), SchedulingMode::Srpt);
2444 }
2445
2446 #[test]
2447 fn config_mode_fifo_overrides_smith() {
2448 let config = SchedulerConfig {
2449 smith_enabled: true,
2450 force_fifo: true,
2451 ..Default::default()
2452 };
2453 assert_eq!(config.mode(), SchedulingMode::Fifo);
2454 }
2455
2456 #[test]
2461 fn starvation_guard_triggers_after_threshold() {
2462 let mut config = test_config();
2463 config.aging_factor = 0.0;
2464 config.wait_starve_ms = 50.0;
2465 config.starve_boost_ratio = 5.0;
2466 let mut scheduler = QueueingScheduler::new(config);
2467
2468 scheduler.submit(1.0, 100.0); scheduler.current_time = 60.0; scheduler.refresh_priorities();
2471
2472 let evidence = scheduler.evidence();
2473 let job_ev = &evidence.jobs[0];
2474 assert!(
2476 job_ev.starvation_floor > 0.0,
2477 "starvation floor should be active: {}",
2478 job_ev.starvation_floor
2479 );
2480 assert!(
2481 job_ev.effective_priority >= job_ev.starvation_floor,
2482 "effective priority {} should be >= starvation floor {}",
2483 job_ev.effective_priority,
2484 job_ev.starvation_floor
2485 );
2486 }
2487
2488 #[test]
2489 fn starvation_guard_disabled_when_zero() {
2490 let mut config = test_config();
2491 config.aging_factor = 0.0;
2492 config.wait_starve_ms = 0.0;
2493 let mut scheduler = QueueingScheduler::new(config);
2494
2495 scheduler.submit(1.0, 100.0);
2496 scheduler.current_time = 1000.0;
2497 scheduler.refresh_priorities();
2498
2499 let evidence = scheduler.evidence();
2500 let job_ev = &evidence.jobs[0];
2501 assert!(
2502 (job_ev.starvation_floor - 0.0).abs() < f64::EPSILON,
2503 "starvation floor should be 0 when disabled"
2504 );
2505 }
2506
2507 #[test]
2512 fn cancel_current_job() {
2513 let mut scheduler = QueueingScheduler::new(test_config());
2514 let id = scheduler.submit(1.0, 100.0).unwrap();
2515 scheduler.tick(10.0); assert!(scheduler.cancel(id));
2518 assert!(scheduler.peek_next().is_none());
2519 }
2520
2521 #[test]
2522 fn cancel_from_middle_of_queue() {
2523 let mut scheduler = QueueingScheduler::new(test_config());
2524 scheduler.submit(1.0, 100.0); let id2 = scheduler.submit(1.0, 50.0).unwrap(); scheduler.submit(1.0, 200.0); assert!(scheduler.cancel(id2));
2529 assert_eq!(scheduler.stats().queue_length, 2);
2530 }
2531
2532 #[test]
2537 fn tick_negative_delta_returns_empty() {
2538 let mut scheduler = QueueingScheduler::new(test_config());
2539 scheduler.submit(1.0, 10.0);
2540 let completed = scheduler.tick(-5.0);
2541 assert!(completed.is_empty());
2542 }
2543
2544 #[test]
2545 fn tick_empty_queue_advances_time() {
2546 let mut scheduler = QueueingScheduler::new(test_config());
2547 let completed = scheduler.tick(100.0);
2548 assert!(completed.is_empty());
2549 }
2550
2551 #[test]
2552 fn tick_processes_across_multiple_jobs_in_single_delta() {
2553 let mut config = test_config();
2554 config.aging_factor = 0.0;
2555 let mut scheduler = QueueingScheduler::new(config);
2556
2557 scheduler.submit(1.0, 3.0);
2558 scheduler.submit(1.0, 3.0);
2559 scheduler.submit(1.0, 3.0);
2560
2561 let completed = scheduler.tick(9.0);
2563 assert_eq!(completed.len(), 3);
2564 }
2565
2566 #[test]
2571 fn stats_default_values() {
2572 let stats = SchedulerStats::default();
2573 assert_eq!(stats.total_submitted, 0);
2574 assert_eq!(stats.total_completed, 0);
2575 assert_eq!(stats.total_rejected, 0);
2576 assert_eq!(stats.total_preemptions, 0);
2577 assert_eq!(stats.queue_length, 0);
2578 }
2579
2580 #[test]
2581 fn stats_mean_response_time_zero_completions() {
2582 let stats = SchedulerStats::default();
2583 assert_eq!(stats.mean_response_time(), 0.0);
2584 }
2585
2586 #[test]
2587 fn stats_throughput_zero_processing_time() {
2588 let stats = SchedulerStats::default();
2589 assert_eq!(stats.throughput(), 0.0);
2590 }
2591
2592 #[test]
2593 fn stats_max_response_time_tracked() {
2594 let mut scheduler = QueueingScheduler::new(test_config());
2595 scheduler.submit(1.0, 5.0);
2596 scheduler.submit(1.0, 10.0);
2597 scheduler.tick(15.0);
2598
2599 let stats = scheduler.stats();
2600 assert!(
2601 stats.max_response_time >= 10.0,
2602 "max response time {} should be >= 10",
2603 stats.max_response_time
2604 );
2605 }
2606
2607 #[test]
2612 fn evidence_continuation_reason() {
2613 let mut scheduler = QueueingScheduler::new(test_config());
2614 scheduler.submit(1.0, 100.0);
2615 scheduler.tick(10.0); let evidence = scheduler.evidence();
2618 assert_eq!(evidence.reason, SelectionReason::Continuation);
2619 }
2620
2621 #[test]
2622 fn evidence_single_job_no_tie_break() {
2623 let mut scheduler = QueueingScheduler::new(test_config());
2624 scheduler.submit(1.0, 10.0);
2625
2626 let evidence = scheduler.evidence();
2627 assert!(
2628 evidence.tie_break_reason.is_none(),
2629 "single job should have no tie break"
2630 );
2631 }
2632
2633 #[test]
2634 fn evidence_to_jsonl_contains_required_fields() {
2635 let mut scheduler = QueueingScheduler::new(test_config());
2636 scheduler.submit(1.0, 10.0);
2637 scheduler.submit(2.0, 5.0);
2638
2639 let evidence = scheduler.evidence();
2640 let json = evidence.to_jsonl("test_event");
2641
2642 assert!(json.contains("\"event\":\"test_event\""));
2643 assert!(json.contains("\"current_time\":"));
2644 assert!(json.contains("\"selected_job_id\":"));
2645 assert!(json.contains("\"queue_length\":"));
2646 assert!(json.contains("\"mean_wait_time\":"));
2647 assert!(json.contains("\"max_wait_time\":"));
2648 assert!(json.contains("\"reason\":"));
2649 assert!(json.contains("\"tie_break_reason\":"));
2650 assert!(json.contains("\"jobs\":["));
2651 }
2652
2653 #[test]
2654 fn evidence_to_jsonl_empty_queue() {
2655 let scheduler = QueueingScheduler::new(test_config());
2656 let evidence = scheduler.evidence();
2657 let json = evidence.to_jsonl("empty");
2658
2659 assert!(json.contains("\"selected_job_id\":null"));
2660 assert!(json.contains("\"tie_break_reason\":null"));
2661 assert!(json.contains("\"jobs\":[]"));
2662 }
2663
2664 #[test]
2665 fn job_evidence_to_json_contains_all_fields() {
2666 let mut config = test_config();
2667 config.aging_factor = 0.5;
2668 config.wait_starve_ms = 5.0;
2669 let mut scheduler = QueueingScheduler::new(config);
2670
2671 scheduler.submit_with_sources(
2672 2.0,
2673 10.0,
2674 WeightSource::Explicit,
2675 EstimateSource::Default,
2676 Some("test-job"),
2677 );
2678 scheduler.current_time = 10.0;
2679 scheduler.refresh_priorities();
2680
2681 let evidence = scheduler.evidence();
2682 let json = evidence.to_jsonl("detail");
2683
2684 assert!(json.contains("\"job_id\":"));
2685 assert!(json.contains("\"name\":\"test-job\""));
2686 assert!(json.contains("\"estimate_ms\":"));
2687 assert!(json.contains("\"weight\":"));
2688 assert!(json.contains("\"ratio\":"));
2689 assert!(json.contains("\"aging_reward\":"));
2690 assert!(json.contains("\"starvation_floor\":"));
2691 assert!(json.contains("\"age_ms\":"));
2692 assert!(json.contains("\"effective_priority\":"));
2693 assert!(json.contains("\"objective_loss_proxy\":"));
2694 assert!(json.contains("\"estimate_source\":"));
2695 assert!(json.contains("\"weight_source\":"));
2696 }
2697
2698 #[test]
2699 fn evidence_jsonl_escapes_special_chars_in_name() {
2700 let mut scheduler = QueueingScheduler::new(test_config());
2701 scheduler.submit_named(1.0, 10.0, Some("job\"with\\special\nchars"));
2702
2703 let evidence = scheduler.evidence();
2704 let json = evidence.to_jsonl("escape_test");
2705
2706 assert!(json.contains("\\\""));
2707 assert!(json.contains("\\\\"));
2708 assert!(json.contains("\\n"));
2709 }
2710
2711 #[test]
2716 fn selection_reason_as_str_coverage() {
2717 assert_eq!(SelectionReason::QueueEmpty.as_str(), "queue_empty");
2718 assert_eq!(
2719 SelectionReason::ShortestRemaining.as_str(),
2720 "shortest_remaining"
2721 );
2722 assert_eq!(
2723 SelectionReason::HighestWeightedPriority.as_str(),
2724 "highest_weighted_priority"
2725 );
2726 assert_eq!(SelectionReason::Fifo.as_str(), "fifo");
2727 assert_eq!(SelectionReason::AgingBoost.as_str(), "aging_boost");
2728 assert_eq!(SelectionReason::Continuation.as_str(), "continuation");
2729 }
2730
2731 #[test]
2732 fn estimate_source_as_str_coverage() {
2733 assert_eq!(EstimateSource::Explicit.as_str(), "explicit");
2734 assert_eq!(EstimateSource::Historical.as_str(), "historical");
2735 assert_eq!(EstimateSource::Default.as_str(), "default");
2736 assert_eq!(EstimateSource::Unknown.as_str(), "unknown");
2737 }
2738
2739 #[test]
2740 fn weight_source_as_str_coverage() {
2741 assert_eq!(WeightSource::Explicit.as_str(), "explicit");
2742 assert_eq!(WeightSource::Default.as_str(), "default");
2743 assert_eq!(WeightSource::Unknown.as_str(), "unknown");
2744 }
2745
2746 #[test]
2747 fn tie_break_reason_as_str_coverage() {
2748 assert_eq!(
2749 TieBreakReason::EffectivePriority.as_str(),
2750 "effective_priority"
2751 );
2752 assert_eq!(TieBreakReason::BaseRatio.as_str(), "base_ratio");
2753 assert_eq!(TieBreakReason::Weight.as_str(), "weight");
2754 assert_eq!(TieBreakReason::RemainingTime.as_str(), "remaining_time");
2755 assert_eq!(TieBreakReason::ArrivalSeq.as_str(), "arrival_seq");
2756 assert_eq!(TieBreakReason::JobId.as_str(), "job_id");
2757 assert_eq!(TieBreakReason::Continuation.as_str(), "continuation");
2758 }
2759
2760 #[test]
2765 fn debug_job() {
2766 let job = Job::with_name(1, 2.0, 50.0, "render");
2767 let dbg = format!("{job:?}");
2768 assert!(dbg.contains("Job"));
2769 assert!(dbg.contains("render"));
2770 }
2771
2772 #[test]
2773 fn debug_scheduler_config() {
2774 let config = SchedulerConfig::default();
2775 let dbg = format!("{config:?}");
2776 assert!(dbg.contains("SchedulerConfig"));
2777 assert!(dbg.contains("aging_factor"));
2778 }
2779
2780 #[test]
2781 fn debug_scheduler_stats() {
2782 let stats = SchedulerStats::default();
2783 let dbg = format!("{stats:?}");
2784 assert!(dbg.contains("SchedulerStats"));
2785 }
2786
2787 #[test]
2788 fn debug_scheduling_evidence() {
2789 let scheduler = QueueingScheduler::new(test_config());
2790 let evidence = scheduler.evidence();
2791 let dbg = format!("{evidence:?}");
2792 assert!(dbg.contains("SchedulingEvidence"));
2793 }
2794
2795 #[test]
2796 fn debug_scheduling_mode() {
2797 assert!(format!("{:?}", SchedulingMode::Smith).contains("Smith"));
2798 assert!(format!("{:?}", SchedulingMode::Srpt).contains("Srpt"));
2799 assert!(format!("{:?}", SchedulingMode::Fifo).contains("Fifo"));
2800 }
2801
2802 #[test]
2807 fn historical_estimate_passes_through() {
2808 let mut scheduler = QueueingScheduler::new(test_config());
2809 scheduler.submit_with_sources(
2810 1.0,
2811 42.0,
2812 WeightSource::Explicit,
2813 EstimateSource::Historical,
2814 None::<&str>,
2815 );
2816
2817 let next = scheduler.peek_next().unwrap();
2818 assert!((next.remaining_time - 42.0).abs() < f64::EPSILON);
2819 }
2820
2821 #[test]
2826 fn multiple_preemptions_counted() {
2827 let mut config = test_config();
2828 config.aging_factor = 0.0; config.wait_starve_ms = 0.0;
2830 let mut scheduler = QueueingScheduler::new(config);
2831
2832 scheduler.submit(1.0, 100.0); scheduler.tick(1.0); scheduler.submit(1.0, 50.0); scheduler.tick(1.0); scheduler.submit(1.0, 10.0); assert!(
2841 scheduler.stats().total_preemptions >= 2,
2842 "expected >= 2 preemptions, got {}",
2843 scheduler.stats().total_preemptions
2844 );
2845 }
2846
2847 #[test]
2852 fn multiple_rejections_counted() {
2853 let mut config = test_config();
2854 config.max_queue_size = 1;
2855 let mut scheduler = QueueingScheduler::new(config);
2856
2857 scheduler.submit(1.0, 10.0); scheduler.submit(1.0, 10.0); scheduler.submit(1.0, 10.0); assert_eq!(scheduler.stats().total_rejected, 2);
2862 }
2863
2864 #[test]
2869 fn reset_resets_job_id_sequence() {
2870 let mut scheduler = QueueingScheduler::new(test_config());
2871 scheduler.submit(1.0, 10.0); scheduler.submit(1.0, 10.0); scheduler.reset();
2875
2876 let id = scheduler.submit(1.0, 10.0).unwrap();
2877 assert_eq!(id, 1, "job id should restart from 1 after reset");
2878 }
2879
2880 #[test]
2881 fn clear_preserves_job_id_sequence() {
2882 let mut scheduler = QueueingScheduler::new(test_config());
2883 scheduler.submit(1.0, 10.0); scheduler.submit(1.0, 10.0); scheduler.clear();
2887
2888 let id = scheduler.submit(1.0, 10.0).unwrap();
2889 assert_eq!(id, 3, "job id should continue after clear");
2890 }
2891
2892 #[test]
2897 fn evidence_aging_boost_reason() {
2898 let mut config = test_config();
2899 config.aging_factor = 1.0;
2900 config.wait_starve_ms = 10.0;
2901 let mut scheduler = QueueingScheduler::new(config);
2902
2903 scheduler.submit(1.0, 100.0);
2904 scheduler.current_time = 100.0;
2905 scheduler.refresh_priorities();
2906
2907 let evidence = scheduler.evidence();
2908 assert_eq!(
2909 evidence.reason,
2910 SelectionReason::AgingBoost,
2911 "long-waiting job should show aging boost reason"
2912 );
2913 }
2914}