1#![forbid(unsafe_code)]
2
3use std::cmp::Ordering;
85use std::collections::BinaryHeap;
86use std::fmt::Write;
87
88const DEFAULT_AGING_FACTOR: f64 = 0.1;
90
91const MAX_QUEUE_SIZE: usize = 10_000;
93
94const DEFAULT_P_MIN_MS: f64 = 0.05;
96
97const DEFAULT_P_MAX_MS: f64 = 5_000.0;
99
100const DEFAULT_W_MIN: f64 = 1e-6;
102
103const DEFAULT_W_MAX: f64 = 100.0;
105
106const DEFAULT_WEIGHT_DEFAULT: f64 = 1.0;
108
109const DEFAULT_WEIGHT_UNKNOWN: f64 = 1.0;
111
112const DEFAULT_ESTIMATE_DEFAULT_MS: f64 = 10.0;
114
115const DEFAULT_ESTIMATE_UNKNOWN_MS: f64 = 1_000.0;
117
118const DEFAULT_WAIT_STARVE_MS: f64 = 500.0;
120
121const DEFAULT_STARVE_BOOST_RATIO: f64 = 1.5;
123
124#[derive(Debug, Clone)]
126pub struct SchedulerConfig {
127 pub aging_factor: f64,
131
132 pub p_min_ms: f64,
134
135 pub p_max_ms: f64,
137
138 pub estimate_default_ms: f64,
141
142 pub estimate_unknown_ms: f64,
145
146 pub w_min: f64,
148
149 pub w_max: f64,
151
152 pub weight_default: f64,
155
156 pub weight_unknown: f64,
159
160 pub wait_starve_ms: f64,
162
163 pub starve_boost_ratio: f64,
166
167 pub smith_enabled: bool,
169
170 pub force_fifo: bool,
173
174 pub max_queue_size: usize,
176
177 pub preemptive: bool,
179
180 pub time_quantum: f64,
183
184 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 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#[derive(Debug, Clone)]
227pub struct Job {
228 pub id: u64,
230
231 pub weight: f64,
233
234 pub remaining_time: f64,
236
237 pub total_time: f64,
239
240 pub arrival_time: f64,
242
243 pub arrival_seq: u64,
245
246 pub estimate_source: EstimateSource,
248
249 pub weight_source: WeightSource,
251
252 pub name: Option<String>,
254}
255
256impl Job {
257 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 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 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 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 pub fn is_complete(&self) -> bool {
323 self.remaining_time <= 0.0
324 }
325}
326
327#[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 self.priority
361 .total_cmp(&other.priority)
362 .then_with(|| self.base_ratio.total_cmp(&other.base_ratio))
364 .then_with(|| self.job.weight.total_cmp(&other.job.weight))
366 .then_with(|| other.job.remaining_time.total_cmp(&self.job.remaining_time))
368 .then_with(|| other.job.arrival_seq.cmp(&self.job.arrival_seq))
370 .then_with(|| other.job.id.cmp(&self.job.id))
372 }
373}
374
375#[derive(Debug, Clone)]
377pub struct SchedulingEvidence {
378 pub current_time: f64,
380
381 pub selected_job_id: Option<u64>,
383
384 pub queue_length: usize,
386
387 pub mean_wait_time: f64,
389
390 pub max_wait_time: f64,
392
393 pub reason: SelectionReason,
395
396 pub tie_break_reason: Option<TieBreakReason>,
398
399 pub jobs: Vec<JobEvidence>,
401}
402
403#[derive(Debug, Clone)]
405pub struct JobEvidence {
406 pub job_id: u64,
408 pub name: Option<String>,
410 pub estimate_ms: f64,
412 pub weight: f64,
414 pub ratio: f64,
416 pub aging_reward: f64,
418 pub starvation_floor: f64,
420 pub age_ms: f64,
422 pub effective_priority: f64,
424 pub objective_loss_proxy: f64,
426 pub estimate_source: EstimateSource,
428 pub weight_source: WeightSource,
430}
431
432#[derive(Debug, Clone, Copy, PartialEq, Eq)]
434pub enum SelectionReason {
435 QueueEmpty,
437 ShortestRemaining,
439 HighestWeightedPriority,
441 Fifo,
443 AgingBoost,
445 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#[derive(Debug, Clone, Copy, PartialEq, Eq)]
464pub enum EstimateSource {
465 Explicit,
467 Historical,
469 Default,
471 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#[derive(Debug, Clone, Copy, PartialEq, Eq)]
488pub enum WeightSource {
489 Explicit,
491 Default,
493 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#[derive(Debug, Clone, Copy, PartialEq, Eq)]
509pub enum TieBreakReason {
510 EffectivePriority,
512 BaseRatio,
514 Weight,
516 RemainingTime,
518 ArrivalSeq,
520 JobId,
522 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#[derive(Debug, Clone, Copy, PartialEq, Eq)]
542pub enum SchedulingMode {
543 Smith,
545 Srpt,
547 Fifo,
549}
550
551impl SchedulingEvidence {
552 #[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
638pub(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#[derive(Debug, Clone, Default)]
663pub struct SchedulerStats {
664 pub total_submitted: u64,
666
667 pub total_completed: u64,
669
670 pub total_rejected: u64,
672
673 pub total_preemptions: u64,
675
676 pub total_processing_time: f64,
678
679 pub total_response_time: f64,
681
682 pub max_response_time: f64,
684
685 pub queue_length: usize,
687}
688
689impl SchedulerStats {
690 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 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#[derive(Debug)]
711pub struct QueueingScheduler {
712 config: SchedulerConfig,
713
714 queue: BinaryHeap<PriorityJob>,
716
717 current_job: Option<Job>,
719
720 current_time: f64,
722
723 next_job_id: u64,
725
726 next_arrival_seq: u64,
728
729 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 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 pub fn submit(&mut self, weight: f64, estimated_time: f64) -> Option<u64> {
758 self.submit_named(weight, estimated_time, None::<&str>)
759 }
760
761 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 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 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 if self.config.preemptive {
825 self.maybe_preempt();
826 }
827
828 Some(id)
829 }
830
831 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 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; };
854
855 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 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 self.current_job = Some(job);
872 }
873 }
874
875 self.stats.total_processing_time += processed_time;
876 self.current_time = now;
877 self.refresh_priorities();
879
880 self.stats.queue_length = self.queue.len();
881 completed
882 }
883
884 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 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 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 #[must_use]
987 pub const fn max_queue_size(&self) -> usize {
988 self.config.max_queue_size
989 }
990
991 pub fn cancel(&mut self, job_id: u64) -> bool {
993 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 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 pub fn clear(&mut self) {
1017 self.queue.clear();
1018 self.current_job = None;
1019 self.stats.queue_length = 0;
1020 }
1021
1022 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 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 weight.max(self.config.w_min).min(self.config.w_max)
1051 }
1052
1053 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 estimate_ms
1067 .max(self.config.p_min_ms)
1068 .min(self.config.p_max_ms)
1069 }
1070
1071 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 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 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 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 fn compute_priority(&self, job: &Job) -> f64 {
1142 self.compute_priority_terms(job).effective_priority
1143 }
1144
1145 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 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 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(¤t_pj) == Ordering::Greater {
1190 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 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 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#[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 #[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 #[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()); 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 #[test]
1531 fn srpt_prefers_shorter_jobs() {
1532 let mut scheduler = QueueingScheduler::new(test_config());
1533
1534 scheduler.submit(1.0, 100.0); scheduler.submit(1.0, 10.0); let next = scheduler.peek_next().unwrap();
1538 assert_eq!(next.remaining_time, 10.0); }
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); scheduler.submit(10.0, 10.0); let next = scheduler.peek_next().unwrap();
1549 assert_eq!(next.weight, 10.0); }
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); scheduler.submit(1.0, 5.0); let next = scheduler.peek_next().unwrap();
1560 assert_eq!(next.remaining_time, 5.0); }
1562
1563 #[test]
1568 fn aging_increases_priority_over_time() {
1569 let mut scheduler = QueueingScheduler::new(test_config());
1570
1571 scheduler.submit(1.0, 100.0); scheduler.tick(0.0); let before_aging = scheduler.compute_priority(scheduler.peek_next().unwrap());
1575
1576 scheduler.current_time = 100.0; 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; let mut scheduler = QueueingScheduler::new(config);
1591
1592 scheduler.submit(1.0, 1000.0); scheduler.submit(1.0, 1.0); assert_eq!(scheduler.peek_next().unwrap().remaining_time, 1.0);
1597
1598 let completed = scheduler.tick(1.0);
1600 assert_eq!(completed.len(), 1);
1601
1602 assert!(scheduler.peek_next().is_some());
1603 }
1604
1605 #[test]
1610 fn preemption_when_higher_priority_arrives() {
1611 let mut scheduler = QueueingScheduler::new(test_config());
1612
1613 scheduler.submit(1.0, 100.0); scheduler.tick(10.0); let before = scheduler.peek_next().unwrap().remaining_time;
1617 assert_eq!(before, 90.0);
1618
1619 scheduler.submit(1.0, 5.0); let next = scheduler.peek_next().unwrap();
1623 assert_eq!(next.remaining_time, 5.0);
1624
1625 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); let next = scheduler.peek_next().unwrap();
1642 assert_eq!(next.remaining_time, 90.0);
1643 }
1644
1645 #[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()); 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 #[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 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 assert!((stats.throughput() - 0.1).abs() < 0.01);
1743 }
1744
1745 #[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 #[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 #[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 let id_a = scheduler.submit(1.0, 2.0).unwrap(); scheduler.current_time = 5.0;
1876 scheduler.refresh_priorities();
1877
1878 let id_b = scheduler.submit(1.0, 1.0).unwrap(); 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(); let _low_weight = scheduler.submit(1.0, 1.0).unwrap(); 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 #[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); scheduler.submit(1.0, 10.0); 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 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 #[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 #[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); }
2089
2090 #[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 #[test]
2120 fn property_work_conserving() {
2121 let mut scheduler = QueueingScheduler::new(test_config());
2122
2123 for i in 0..10 {
2125 scheduler.submit(1.0, (i as f64) + 1.0);
2126 }
2127
2128 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 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 #[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 #[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 #[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 #[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 #[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); scheduler.current_time = 60.0; scheduler.refresh_priorities();
2488
2489 let evidence = scheduler.evidence();
2490 let job_ev = &evidence.jobs[0];
2491 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 #[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); 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); let id2 = scheduler.submit(1.0, 50.0).unwrap(); scheduler.submit(1.0, 200.0); assert!(scheduler.cancel(id2));
2546 assert_eq!(scheduler.stats().queue_length, 2);
2547 }
2548
2549 #[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 let completed = scheduler.tick(9.0);
2580 assert_eq!(completed.len(), 3);
2581 }
2582
2583 #[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 #[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); 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 #[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 #[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 #[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 #[test]
2843 fn multiple_preemptions_counted() {
2844 let mut config = test_config();
2845 config.aging_factor = 0.0; config.wait_starve_ms = 0.0;
2847 let mut scheduler = QueueingScheduler::new(config);
2848
2849 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!(
2858 scheduler.stats().total_preemptions >= 2,
2859 "expected >= 2 preemptions, got {}",
2860 scheduler.stats().total_preemptions
2861 );
2862 }
2863
2864 #[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); scheduler.submit(1.0, 10.0); scheduler.submit(1.0, 10.0); assert_eq!(scheduler.stats().total_rejected, 2);
2879 }
2880
2881 #[test]
2886 fn reset_resets_job_id_sequence() {
2887 let mut scheduler = QueueingScheduler::new(test_config());
2888 scheduler.submit(1.0, 10.0); scheduler.submit(1.0, 10.0); 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); scheduler.submit(1.0, 10.0); 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 #[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 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 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 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 let long_id = scheduler.submit(1.0, 100.0).unwrap();
2988 assert!(scheduler.tick(1.0).is_empty());
2989
2990 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 assert!((short_preemptive - 2.0).abs() < 1e-9);
3013 assert!((long_preemptive - 101.0).abs() < 1e-9);
3014
3015 assert!((long_nonpreemptive - 100.0).abs() < 1e-9);
3018 assert!((short_nonpreemptive - 101.0).abs() < 1e-9);
3019 }
3020}