response_time_analysis/demand/
mod.rs

1/*! The *request-bound function* (RBF) abstraction and related definitions
2
3This module provides a trait to express request-bound functions (RBFs),
4which are an abstraction to characterize the total demand for processor
5service by one or more tasks.
6
7*/
8
9use auto_impl::auto_impl;
10
11use crate::time::{Duration, Offset, Service};
12
13/// The general interface for (arbitrarily shaped) processor demand.
14/// This can represent the demand of a single task, or the cumulative
15/// demand of multiple tasks.
16#[auto_impl(&, Box, Rc)]
17pub trait RequestBound {
18    /// Bound the total amount of service needed in an interval of length `delta`.
19    fn service_needed(&self, delta: Duration) -> Service {
20        self.job_cost_iter(delta).sum()
21    }
22
23    /// Bound the total amount of service needed by up to `max_jobs`
24    /// in an interval of length `delta`.
25    fn service_needed_by_n_jobs(&self, delta: Duration, max_jobs: usize) -> Service {
26        // take the max_jobs largest job costs
27        itertools::sorted(self.job_cost_iter(delta))
28            .rev()
29            .take(max_jobs)
30            .sum()
31    }
32
33    /// Expose the smallest WCET of any job encountered in an interval of length `delta`.
34    fn least_wcet_in_interval(&self, delta: Duration) -> Service;
35
36    /// Yield an iterator over the interval lengths (i.e., values of `delta` in
37    /// [RequestBound::service_needed]) at which the cumulative demand changes.
38    ///
39    /// More precisely, this iterator yields every value of `delta` such that:
40    ///
41    /// `self.service_needed(delta - 1) < self.service_needed(delta)`.
42    fn steps_iter<'a>(&'a self) -> Box<dyn Iterator<Item = Duration> + 'a>;
43
44    /// Expose an iterator over the individual costs that comprise the overall demand.
45    fn job_cost_iter<'a>(&'a self, delta: Duration) -> Box<dyn Iterator<Item = Service> + 'a>;
46}
47
48/// A refined interface for processor demand that represents the
49/// total demand of a collection of individual sources of demand.
50#[auto_impl(&, Box, Rc)]
51pub trait AggregateRequestBound: RequestBound {
52    /// Bound the total amount of service needed in an interval of
53    /// length `delta`, subject to the constraint that no individual
54    /// source of demand contributes more than `max_jobs` worth of
55    /// demand.
56    fn service_needed_by_n_jobs_per_component(&self, delta: Duration, max_jobs: usize) -> Service;
57}
58
59/// Yield the sequence of *offsets* at which the request bound
60/// function "steps", i.e., where the procesor demand increases.
61///
62/// More precisely, the iterator yields values of `A` such that
63///
64/// `rb.service_needed(A.since_time_zero()) < rb.service_needed(A.closed_since_time_zero())`
65///
66/// which is equivalent to
67///
68/// `rb.service_needed(Duration::from(A)) < rb.service_needed(Duration::from(A) + Duration::epsilon())`.
69///
70/// It always yields `A=0` since [RequestBound::steps_iter]
71/// necessarily yields `delta=1`, which results in `A=0` being the
72/// first element yielded by `step_offsets`.
73pub fn step_offsets(rb: &'_ (impl RequestBound + ?Sized)) -> impl Iterator<Item = Offset> + '_ {
74    rb.steps_iter().map(Offset::closed_from_time_zero)
75}
76
77mod aggregate;
78mod rbf;
79mod slice;
80
81pub use aggregate::Aggregate;
82pub use rbf::RBF;
83pub use slice::Slice;
response_time_analysis/demand/mod.rs

response_time_analysis/demand/
mod.rs
