response_time_analysis/ros2/
ecrts19.rs

1use crate::demand::RequestBound;
2use crate::fixed_point::{self, max_response_time, SearchResult};
3use crate::supply::SupplyBound;
4use crate::time::{Duration, Offset, Service};
5
6/// Bound the response time of an event source for a given supply and
7/// demand model, using the analysis proposed by
8/// [Casini et al. (2019)](https://people.mpi-sws.org/~bbb/papers/pdf/ecrts19-rev1.pdf).
9///
10/// If no fixed point is found below the divergence limit given by
11/// `limit`, return a [SearchFailure][fixed_point::SearchFailure]
12/// instead.
13///
14/// The bound is based on Lemma 1 of Casini et al. (2019).
15pub fn rta_event_source<SBF, RBF>(
16    supply: &SBF,
17    demand: &RBF,
18    limit: Duration,
19) -> fixed_point::SearchResult
20where
21    SBF: SupplyBound + ?Sized,
22    RBF: RequestBound + ?Sized,
23{
24    // right-hand side of Lemma 6 --- used to bound the max. busy-window length
25    let rhs_busy_window = |delta| demand.service_needed(delta);
26    // right-hand side of Lemma 1 --- used to bound the demand for a given offset
27    let rhs = |offset: Offset, _response| demand.service_needed(offset.closed_since_time_zero());
28
29    // solve the fixed point for all steps of the demand curve up to
30    // the maximum busy-window length and return the maximum (or divergence)
31    bound_response_time(supply, demand, rhs_busy_window, rhs, limit)
32}
33
34/// Bound the response time of a timer callback using
35/// Lemma 3 of
36/// [Casini et al. (2019)](https://people.mpi-sws.org/~bbb/papers/pdf/ecrts19-rev1.pdf).
37///
38/// # Parameters
39///
40/// - `supply`: the supply model of the shared executor
41/// - `own_demand`: model of the processor demand of the timer under analysis
42/// - `interfering_demand`: model of the processor demand of higher-priority timers
43/// - `blocking_bound`: a bound on the maximum delay due to lower-priority callbacks
44/// - `limit`: the divergence threshold at which the search for a fixed point is aborted
45///
46/// If no fixed point is found below the divergence limit given by
47/// `limit`, return a [SearchFailure][fixed_point::SearchFailure]
48/// instead.
49pub fn rta_timer<SBF, RBF1, RBF2>(
50    supply: &SBF,
51    own_demand: &RBF1,
52    interfering_demand: &RBF2,
53    blocking_bound: Service,
54    limit: Duration,
55) -> fixed_point::SearchResult
56where
57    SBF: SupplyBound + ?Sized,
58    RBF1: RequestBound + ?Sized,
59    RBF2: RequestBound + ?Sized,
60{
61    // right-hand side of Lemma 6
62    let rhs_bw = |delta| {
63        own_demand.service_needed(delta) + blocking_bound + interfering_demand.service_needed(delta)
64    };
65    // right-hand side of Lemma 3
66    let rhs = |offset: Offset, response: Duration| {
67        // length of the prefix interval before the offset
68        let prefix = offset.since_time_zero();
69        // cost of timer callback
70        let own_wcet = Duration::from(own_demand.least_wcet_in_interval(prefix + response));
71        // determine timeframe during which other callbacks can delay us
72        let interference_interval = if response > own_wcet {
73            prefix + response - own_wcet + Duration::epsilon()
74        } else {
75            prefix + Duration::epsilon()
76        };
77        own_demand.service_needed(prefix + Duration::epsilon())
78            + interfering_demand.service_needed(interference_interval)
79            + blocking_bound
80    };
81    bound_response_time(supply, own_demand, rhs_bw, rhs, limit)
82}
83
84/// Bound the response time of a polling-point-based callback using
85/// Lemmas 4 and 5 of
86/// [Casini et al. (2019)](https://people.mpi-sws.org/~bbb/papers/pdf/ecrts19-rev1.pdf).
87///
88/// # Parameters
89///
90/// - `supply`: the supply model of the shared executor
91/// - `own_demand`: model of the processor demand of the callback under analysis
92/// - `interfering_demand`: model of the processor demand of all higher-priority callbacks
93/// - `limit`: the divergence threshold at which the search for a fixed point is aborted
94///
95/// If no fixed point is found below the divergence limit given by
96/// `limit`, return a [SearchFailure][fixed_point::SearchFailure]
97/// instead.
98pub fn rta_polling_point_callback<SBF, RBF1, RBF2>(
99    supply: &SBF,
100    own_demand: &RBF1,
101    interfering_demand: &RBF2,
102    limit: Duration,
103) -> fixed_point::SearchResult
104where
105    SBF: SupplyBound + ?Sized,
106    RBF1: RequestBound + ?Sized,
107    RBF2: RequestBound + ?Sized,
108{
109    // right-hand side of Lemma 6
110    let rhs_bw =
111        |delta| own_demand.service_needed(delta) + interfering_demand.service_needed(delta);
112    // right-hand side of Eq (6), based on Lemmas 4 and 5
113    let rhs = |offset: Offset, response: Duration| {
114        // length of the prefix interval before the offset
115        let prefix = offset.since_time_zero();
116        // cost of pp-based callback under analysis
117        let own_wcet = Duration::from(own_demand.least_wcet_in_interval(prefix + response));
118        // determine timeframe during which other callbacks can delay us
119        let interference_interval = if response > own_wcet {
120            prefix + response - own_wcet + Duration::epsilon()
121        } else {
122            prefix + Duration::epsilon()
123        };
124        own_demand.service_needed(prefix + Duration::epsilon())
125            + interfering_demand.service_needed(interference_interval)
126    };
127    bound_response_time(supply, own_demand, rhs_bw, rhs, limit)
128}
129
130/// Bound the response time of a chain of callbacks using
131/// Lemma 8 of
132/// [Casini et al. (2019)](https://people.mpi-sws.org/~bbb/papers/pdf/ecrts19-rev1.pdf).
133///
134/// # Parameters
135///
136/// - `supply`: the supply model of the shared executor
137/// - `chain_last_callback`: model of the processor demand of the last
138///   callback of the chain under analysis
139/// - `chain_prefix`: model of the processor demand of the callbacks
140///   in the chain under analysis preceding the last callback
141/// - `full_chain`: model of the processor demand of the chain under analysis --- obviously, this must be consistent with the two prior parameters
142/// - `other_chains`: model of the processor demand of other callback
143///   chains allocated to the same executor
144/// - `limit`: the divergence threshold at which the search for a fixed point is aborted
145///
146/// If no fixed point is found below the divergence limit given by
147/// `limit`, return a [SearchFailure][fixed_point::SearchFailure]
148/// instead.
149pub fn rta_processing_chain<SBF, RBF1, RBF2, RBF3, RBF4>(
150    supply: &SBF,
151    chain_last_callback: &RBF1,
152    chain_prefix: &RBF2,
153    full_chain: &RBF3,
154    other_chains: &RBF4,
155    limit: Duration,
156) -> fixed_point::SearchResult
157where
158    SBF: SupplyBound + ?Sized,
159    RBF1: RequestBound + ?Sized,
160    RBF2: RequestBound + ?Sized,
161    RBF3: RequestBound + ?Sized,
162    RBF4: RequestBound + ?Sized,
163{
164    // for bounding the max. busy-window length
165    let rhs_bw = |delta| {
166        debug_assert_eq!(
167            full_chain.service_needed(delta),
168            chain_prefix.service_needed(delta) + chain_last_callback.service_needed(delta)
169        );
170        full_chain.service_needed(delta) + other_chains.service_needed(delta)
171    };
172
173    // right-hand side of Lemma 8
174    let rhs = |offset: Offset, response: Duration| {
175        let prefix = offset.since_time_zero();
176        let own_demand = chain_last_callback.service_needed(prefix + Duration::epsilon());
177        let own_wcet =
178            Duration::from(chain_last_callback.least_wcet_in_interval(prefix + response));
179        // determine timeframe during which other callbacks can delay us
180        let interference_interval = if response > own_wcet {
181            prefix + response - own_wcet + Duration::epsilon()
182        } else {
183            prefix + Duration::epsilon()
184        };
185        let other_demand = other_chains.service_needed(interference_interval);
186        let self_interference = chain_prefix.service_needed(interference_interval);
187        own_demand + self_interference + other_demand
188    };
189
190    bound_response_time(supply, full_chain, rhs_bw, rhs, limit)
191}
192
193/// Try to find a response-time bound for a given processor supply
194/// model and a given processor demand model.
195///
196/// The search for a fixed point will be aborted if the given
197/// divergence threshold indicated by `limit` is reached.
198///
199/// The fixed-point search relies on three relevant characterizations
200/// of processor demand:
201/// - `demand` is demand model of the callback under analysis from
202///    which all points are inferred at which the demand curve
203///    exhibits "steps".
204/// - `bw_demand_bound` is the right-hand side of the fixed-point
205///   equation describing the maximum busy-window length, i.e., the
206///   demand of "everything".
207/// - `offset_demand_bound` is the right-hand side of the fixed-point
208///   equation describing the response time for a given offset.
209fn bound_response_time<SBF, RBF, F, G>(
210    supply: &SBF,
211    demand: &RBF,
212    bw_demand_bound: F,
213    offset_demand_bound: G,
214    limit: Duration,
215) -> SearchResult
216where
217    SBF: SupplyBound + ?Sized,
218    RBF: RequestBound + ?Sized,
219    F: Fn(Duration) -> Service,
220    G: Fn(Offset, Duration) -> Service,
221{
222    // find a bound on the maximum busy-window
223    let max_bw = fixed_point::search(supply, limit, bw_demand_bound)?;
224    // Consider the search space of relevant offsets based on Lemma 7.
225    // That is, we have to look at all points where the demand curve "steps".
226    let offsets = demand
227        .steps_iter()
228        // Note that steps_iter() yields interval lengths, but we are interested in
229        // offsets. Since the length of an interval [0, A] is A+1, we need to subtract one
230        // to obtain the offset.
231        .map(Offset::closed_from_time_zero)
232        .take_while(|x| *x <= Offset::from_time_zero(max_bw));
233    // for each relevant offset in the search space,
234    let rta_bounds = offsets.map(|offset| {
235        let rhs = |delta| offset_demand_bound(offset, delta);
236        fixed_point::search_with_offset(supply, offset, limit, &rhs)
237    });
238    max_response_time(rta_bounds)
239}
response_time_analysis/ros2/ecrts19.rs

response_time_analysis/ros2/
ecrts19.rs
