response_time_analysis/arrival/
mod.rs

1/*! Models of arrival processes (periodic, sporadic, etc.)
2
3This module provides a central trait, [ArrivalBound], which represents
4an upper-bounding arrival curve. Furthermore, it provides
5implementations of the trait for several types of arrival processes
6commonly studied in the literature on the analysis of real-time systems
7(e.g, [Periodic] and [Sporadic] tasks).
8*/
9
10use auto_impl::auto_impl;
11use itertools::Itertools;
12
13use crate::time::Duration;
14
15/// The main interface for models describing arrival processes.
16#[auto_impl(&, Box, Rc)]
17pub trait ArrivalBound {
18    /// Bound the number of jobs released in any interval of length `delta`.
19    fn number_arrivals(&self, delta: Duration) -> usize;
20
21    /// Yield the sequence of interval lengths (i.e., values of `delta` in
22    /// [ArrivalBound::number_arrivals]) for which the arrival bound
23    /// "steps", i.e., where it shows an increase in the number of
24    /// released jobs.
25    ///
26    /// More precisely, the iterator yields values of `delta` such that:
27    ///
28    /// `self.number_arrivals(delta - 1) < self.number_arrivals(delta)`.
29    ///
30    /// Defaults to using [ArrivalBound::brute_force_steps_iter],
31    /// which is very slow, so implementors should override this method.
32    fn steps_iter<'a>(&'a self) -> Box<dyn Iterator<Item = Duration> + 'a> {
33        self.brute_force_steps_iter()
34    }
35
36    /// Same semantics as [ArrivalBound::steps_iter], but provided by
37    /// a default implementation in the most naive way possible.
38    /// Avoid if performance is at all important.
39    fn brute_force_steps_iter<'a>(&'a self) -> Box<dyn Iterator<Item = Duration> + 'a> {
40        let (a1, a2) = (0..)
41            .map(move |delta| (delta, self.number_arrivals(Duration::from(delta))))
42            .tee();
43        Box::new(
44            a1.zip(a2.skip(1))
45                .filter(|((_, njobs1), (_, njobs2))| njobs1 != njobs2)
46                .map(|((_, _), (d2, _))| Duration::from(d2)),
47        )
48    }
49
50    /// Clone the arrival model while accounting for added release
51    /// jitter. Returns a boxed `dyn` object because the underlying
52    /// type may change.
53    fn clone_with_jitter(&self, jitter: Duration) -> Box<dyn ArrivalBound>;
54}
55
56mod aggregated;
57mod arrival_curve_prefix;
58mod curve;
59mod dmin;
60mod never;
61mod periodic;
62mod poisson;
63mod propagated;
64mod slice;
65mod sporadic;
66
67pub use aggregated::sum_of;
68pub use arrival_curve_prefix::ArrivalCurvePrefix;
69pub use curve::{Curve, ExtrapolatingCurve};
70pub use dmin::{delta_min_iter, nonzero_delta_min_iter};
71pub use never::Never;
72pub use periodic::Periodic;
73pub use poisson::{ApproximatedPoisson, Poisson};
74pub use propagated::Propagated;
75pub use sporadic::Sporadic;
76
77// common helper function
78fn divide_with_ceil(a: Duration, b: Duration) -> u64 {
79    a / b + (a % b > Duration::from(0)) as u64
80}
81
82#[cfg(test)]
83mod tests;
response_time_analysis/arrival/mod.rs

response_time_analysis/arrival/
mod.rs
