Response time central-limit and failure rate estimation for stationary periodic rate monotonic real-time systems
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.
Rosa: We're looking at the paper: "Response time central-limit and failure rate estimation for stationary periodic rate monotonic real-time systems".
Dev: Here's the gist of the paper. Response times must be bounded to ensure safe failure rates in real-time systems The paper focuses on using the central limit of response times and an approximation with an inverse Gaussian mixture distribution to estimate failure rates This method provides a practical and simple implementation of backlog estimation using an adapted Expectation-Maximization algorithm to estimate failure rates System Modeling and Definitions The paper considers periodic tasks on a single core system where priorities are ordered decreasingly, meaning the most critical tasks are completed first A task is characterized by its execution time, period, and arrival rate of jobs Key performance metrics include utilization levels like the k-level mean utilization and maximum utilization, as well as deviation measures The system's stationarity is assumed to ensure that the estimation is independent on the arrival time of jobs Response times are defined based on a fixed-priority discarding scheduling policy, where a job is discarded if it misses its deadline Failure Rate Estimation via Mixture Models The failure rate of a task is defined as the limit of the probability that its response time exceeds its period The paper proposes an approximation for this failure rate using a mixture of Inverse Gaussian (IG) distributions This approximation is derived by relating the response time distribution to the central limit theorem built in
1: The estimated failure rate, denoted as ∆IGi, is found by approximating the integral of the response time probability density function using a finite sum based on an IG mixture model Parameter Estimation via EM Algorithm The estimation of the parameters for this IG mixture model—specifically the backlog distribution and its components—is achieved through an adapted Expectation-Maximization (EM) algorithm The E-step involves computing the conditional expectation of a latent variable indicating which component a response time belongs to, and the M-step maximizes this likelihood by computing the best suited parameters, such as the backlog in our case The algorithm is adapted to a reparametrization of the IG distribution that reduces the number of parameters and increases convergence speed Validation and Goodness-of-Fit The quality of the estimation is assessed using goodness-of-fit tests, such as checking if normalized response times are Chi-squared distributed The paper uses the Bayesian Information Criteria (BIC) to choose the number of mixture components (degrees of freedom), favoring more parsimonious models A key test involves checking if normalized response times are Chi-squared distributed as shown in Proposition 3 Simulations and hardware-in-the-loop (HITL) data demonstrate that the estimation is accurate, especially for large quantiles, when mean utilization approaches 1 Future Directions and Applications The work suggests using this statistical learning method to improve scheduling algorithms by incorporating estimated parameters into scheduling decisions Future research can adapt this framework to Earliest Deadline First (EDF) scheduling, extending the central limit derivation from
1: to that paradigm Furthermore, incorporating estimated failure rates into load-balancing processes for multicore partitioned scheduling is proposed as a next step The method can also be used to build an independence test adapted to real-time systems by leveraging the Chi-squared property of IG distributions In this work, we both provide a theoretical and approximated bound on the failure rates of stationary rate-monotonic real-time systems More than bounds, we provide a method that one could potentially improve scheduling algorithms by estimating parameters with inference The estimation is built through an EM algorithm, but this method is not unique and hopefully some more techniques will improve the proposed method The paper concludes that the proposed method can also be useful in the case of dependent execution times References
Paper summary: Rosa: So, looking at "Response time central-limit and failure rate estimation for stationary periodic rate monotonic real-time systems", what we've seen is that the authors provide both a theoretical bound on failure rates and an estimation method using an EM algorithm based on inverse Gaussian mixtures.
Dev: The paper tackles the problem of bounding response times in rate monotonic systems by relating them to the central limit theorem and approximating their distribution with an inverse Gaussian mixture >
Rosa: The implication is that we get a way to estimate failure rates practically, rather than just relying on theoretical bounds which only tell you if a system is safe or not >
Taro: It’s about moving from just knowing the rules of the game to actually estimating how likely things are to go wrong in specific operational scenarios, especially when utilization gets high >
Dev: The method is built through an EM algorithm, but they caution that this specific approach isn't unique and that other techniques could improve on it, so it’s a starting point for more research >
Rosa: Overall, the paper gives us a practical tool to estimate failure rates in these stationary rate monotonic systems using statistical modeling of response times >
Conclusion: Rosa: So we're wrapping up this look at "Response time central-limit and failure rate estimation for stationary periodic rate monotonic real-time systems."
Dev: Basically, they’ve put together a way to get an estimate of how likely a task is to fail because its response time goes over its period.
Rosa: It moves beyond just saying a system might be safe or not and gives you a statistical handle on the actual failure rates.
Dev: They use this central limit idea, which they connect to their response time distribution, and then they approximate it using an inverse Gaussian mixture model.
Rosa: That approximation is done through an expectation maximization algorithm that’s been tweaked to make the math work faster.
Dev: The authors test this out with simulations and even some hardware in the loop data, showing it actually works well for things like large response times when the system utilization gets close to one hundred percent.
Rosa: It gives us a practical way to get a number that tells us about reliability without having to run every single possible scenario.
Dev: The core idea is taking those estimated parameters, like the backlog distribution in this case, and plugging them back into scheduling decisions.
Rosa: If we can use these failure rate estimates to actually change how the scheduler makes its choices, that could lead to systems that are much more robust under real-world stress.
Dev: But they also flag some things, like the method being dependent on assumptions about stationarity and the choice of those mixture components.
Rosa: Exactly. It’s a tool for inference, not a perfect crystal ball for every single system configuration out there right now.
Dev: So it's a solid step forward for building better real-time systems, but there’s still plenty of work to do to make this method even more general and applicable across different scheduling policies.
Kevin Zagalo, Avner Bar-Hen
inria · Cnam Paris
eess.SY, cs.SY, math.ST, stat.TH
Submitted: 2022-11-03
Updated: 2026-10-27
Comments: Accepted to IEEE Transactions on Computers
Code: https://github.com/kevinzagalo/rInverseGaussian
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Importance score: 78/100
The gist: Response times must be bounded to ensure safe failure rates (also known as deadline miss probabilities) in real-time systems <ref:2211.01720#pg6> The paper focuses on using the central limit of…
Key concepts
- Response Time
- The time it takes for a task to complete its execution, considering the arrival of jobs. In this paper, response times are analyzed under fixed-priority discarding scheduling policies where tasks miss deadlines if their response time exceeds their period.
- Failure Rate
- The probability that a task's response time exceeds its period. This is defined as the limit of this probability for stationary systems and is crucial for determining system reliability and schedulability.
- Inverse Gaussian (IG) Mixture Distribution
- An approximation used to model the distribution of response times. The paper uses a mixture of IG distributions to approximate the true response time distribution, simplifying complex calculations by using a finite sum instead of integrating the full probability density function.
Terminology
Summary
Response times must be bounded to ensure safe failure rates (also known as deadline miss probabilities) in real-time systems <ref:2211. p. 0 Many everyday embedded systems, within devices such as airplanes, cars, trains, and spatial probes, operate as
real-time systems. To ensure safe failure rates (also known as deadline miss probabilities), response times must be bounded. Rate
Monotonic real-time systems prioritize tasks according to their arrival rate. This paper focuses on the use of the central limit of
response times built in [1] and an approximation of their distribution with an inverse Gaussian mixture distribution. The distribution
parameters and their associated failure rates are estimated through a suitable re-parameterization of the inverse Gaussian distribution
and an adapted Expectation-Maximization algorithm. Extensive simulations demonstrate that the method is well-suited for the
approximation of failure rates.Where the paper says it
Where the paper says it
Where the paper says it
System Modeling and Definitions
The paper considers periodic tasks on a single core system where task prioritization ensures that the most critical and time-sensitive tasks are completed first to meet deadlines <ref:2211.01720#pg5> A task is characterized by its execution time Ci, with a p. p. 1 Task prioritization ensures that the most
critical and time-sensitive tasks are completed first to meet
deadlines. A task γi
is characterized by:
1) its execution time Ci
, with a p. fi of non-negative
and finite support [c
min
i
, cmax
i
]. 2) its period pi > 0. Let us first introduce some concepts that will be used
throughout this paper. 1 Utilization
Let us define
P
k-level mean utilization of Γ as uk =
k
i=1 λiE[Ci
]. 4 Stationarity
We assume the stationarity of Γ, that we define as the
stationarity of all demand processes Wi(t) = PNi(t)
j=1 Ci,j ,
where Ni(t) = P∞
j=1 1[0,t](Ai,j ) is the process counting
the jobs of the task γi arrived before instant t ≥ 0. This
means that we assume that the distribution of the number
of jobs arrived in an interval [s, t] is the same as the
one over any time interval [u, u + t − s] of size t − s,
i. Hence, it depends on the scheduling
policy. For a fixed-prioity discarding scheduling policy, the
response time Ri,j can be written as
Ri,j = inf{t > 0 : βi(Ai,j + t) = 0}.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Failure Rate Estimation Methodology
The paper proposes a method to estimate failure rates by approximating the response time distributions using an inverse Gaussian mixture model <ref:2211.01720#pg4> The key steps involve:
- Theoretical evidence, and extensive simulations, showing that inverse Gaussian mixtures are a suited prior distribution for response times, hence for failure rate estimation <ref:2211.01720#pg4>
- A practical and simple implementation of backlog estimation using an adapted EM algorithm accounting for the statistics of execution times, in order to estimate failure rates <ref:2211.01720#pg4>
The failure rate is estimated through the parameterization provided in Section 3.1, leading to the approximated failure rate ∆IGi = Z ∞ pi h(r;πi, βi)dr <ref:2211. p. 2 of the execution time of the task of index i ui mean utilization of level i of Γ
umax
i maximum utilization of level i of Γ vi standard deviation of level i of Γ
vmax
i maximum deviation of level i of Γ Ri,j response time of the j-th job of the task of index i
Ri response time of the mixture of all jobs of the task of
index i
hi p. of the response time of the mixture of all jobs of the task
of index i
Ai,j arrival time of the j-th job of the task of index i Ni counting process of the task of index i
Oi offset -arrival time of the first job- of the task of index i pi time separating two consecutive jobs of the task of index i
λi rate of arrival of the jobs of the task of index i βi,j backlog of jobs of index strictly lower than i at time Ai,j
βˆ
i,j approximation of βi,j mi,j distribution of the backlog of jobs of index strictly lower than
i at time Ai,j
πi distribution of the backlog of index strictly lower than
i
πi,k weight of the k-th component of the mixture of the response
time of the task of index i
πˆi,k approximation of πi,k Ki degree of freedom of the approximated failure rate for the
task of index i
ψ(r; ξ, δ) p.Where the paper says it
Parameter Estimation via EM Algorithm
An adapted Expectation-Maximization algorithm is used to estimate the parameters of the mixture of IG probability density functions (p.d.f.) <ref:2211. p. 0 We outline
how to build such adaptive algorithms using the proposed
approach in Section 5. The starting point of the failure rate estimation provided
in this work is the central limit of response times built in [1],
pushing the inverse Gaussian (IG) distribution as a natural
arXiv:2211. The degree of freedom Ki
is estimated
in the following section. 1 E-step
For the (s + 1)th step of the EM algorithm, z
(s)
i
the conditional expectation of Zi given (πi
, βi
) =
π
(s)
i
, β
(s)
i
is
given by
z
(s)
i,j,k =
π
(s)
i,kψi
rj ; β
(s)
i,k
h
rj ;π
(s)
i
, β
(s)
i
. , Ki
, (12)
and maximizing ℓc2 with respect to β is maximizing each of
the Ki expressions
Xn
j=1
z
(s)
i,j,k log ψi(rj ; βi,k), k = 1, . , Ki
,
using Newton-like algorithms (c. The impact of the k-means initialization is
extensively studied in [27] in the case of Gaussian mixtures,
and shown to outperform standard initialization methods
(random, agglomerative hierarchical clustering and sumscore). 4 Degrees of freedom of the mixture of IG
The Bayesian Information Criteria (BIC, [28]) is used to
chose the degrees of freedom (d.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Validation and Goodness-of-Fit
The quality of the MLE is checked by using the link of IG distributions of the jobs of a given task with the χ2 1 distribution <ref:2211.01720#pg5> Proposition 3 states that the failure rate of the IG estimation is equal to ∆IGi = X Ki k=1 πi,k " 1/pi > βi,k 1 − ui−Φ (pi − βi,k 1 − ui)2/νipi! <ref:2211.01720#pg5> Simulations show that when the mean utilization goes to 1, the empirical response time data converges to the inverse Gaussian model <ref:2211. p. 7 5: Mean Squared Error (MSE) between the empirical
distribution of the simulations and the MLE distribution,
of 1 000 instances of the schedule, for the task set shown
in Table 2. This figure shows how the empirical response
time data converges to the inverse Gaussian model when
the mean utilization goes to 1, when assuming both the
D/G/1/FP and D/M/1/FP models.Where the paper says it
Future Directions
Future work can adapt these mechanisms to Earliest Deadline First (EDF) scheduling by extending the central-limit derived from [1] to EDF scheduling <ref:2211.01720#pg5> Incorporating estimated failure rates in the load-balancing process for multicore partitioned scheduling is suggested as a first step towards multicore partitioning <ref:2211. p. 8 We claim that incorporating estimated failure rates in the load-balancing process allows to infer the actual latent state of the system into
the scheduling decisions. We thus focused on estimating
the parameters of failure rates for fixed priority single core
scheduling using prior knowledge on the response times
distributions, as a first step towards multicore partitioned
scheduling. However,
we have shown how to use it to also detect if execution
time are indeed independent. We do not investigate in this
paper the reliability of such method, but rather suggest that
our method can also be useful in the case of dependent
execution times.Where the paper says it
Where the paper says it
Appendix A Proof of Proposition 1
The proof for Proposition 1 shows that with Ci,j = x and i−1 k=1 βk(Ai,j) = y, Ri,j converges to an inverse Gaussian variable of mean x+y 1−ui and variance (x+y)2v 2i when ui gets close to 1 <ref:2211.01720#pg5>
Appendix B Proof of Proposition 2
The proof for Proposition 2 uses Hoeffding’s inequality to derive an upper-bound on the conditional probability in (19) <ref:2211.01720#pg5>
Appendix C Proof of Proposition 3
The proof for Proposition 3 uses (15) with (11) and θ = β 1−ui and x = g(r; θ) to show the relationship between normalized response time and the Chi-squared distribution <ref:2211.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
How to improve response time estimation in real-time systems by using an adapted Expectation-Maximization algorithm to estimate parameters of a mixture of Inverse Gaussian distributions, which is a
practical and simple implementation of backlog estimation using an adapted EM algorithm accounting for the statistics of execution times.
-
The improved AI system can perform adaptive scheduling by estimating during run-time the distribution and/or the component where response times belong, as outlined in Section 1.1. This allows for an
adaptive scheduling method taking failure rates into account
to be incorporated directly into the scheduling process itself. -
The system can utilize a re-parameterized Inverse Gaussian distribution, denoted as rIG, which
reduces the number of parameters of the mixture model
and increases thespeed of convergence [of] the estimation algorithm as well as the stability of the estimates.
-
Failure rates for stationary rate monotonic real-time systems can be estimated using a formula derived from Equation 11, specifically
the approximated failure rate is DeltaIG i = X Ki k=1 (1 - Psi pi; beta i,k 1 - ui, beta i2 v squared i !).
-
The improved system can use the Bayesian Information Criteria to choose the number of components in the mixture model by calculating Ki as
argmax k 2 l n(pi, beta i) - (2k - 1) log n,
leading to more parsimonious models suitable forestimating during the scheduling process, hence with a small sample size.
-
The system can perform a goodness-of-fit test on the estimated parameters by checking if "Pn j=1 P delta i(Ri,j - xi hat i) squared / xi squared i Ri,j > Phi-1(1 - alpha) <= n alpha for all alpha in (0, 1)," as shown in Section 4.2.
Abstract
Real-time systems consist of a set of tasks, a scheduling policy, and a system architecture, all constrained by timing requirements. Many everyday embedded systems, within devices such as airplanes, cars, trains, and spatial probes, operate as real-time systems. To ensure safe failure rates, response times-the time required for the exection of a task-must be bounded. Rate Monotonic real-time systems prioritize tasks according to their arrival rate. This paper focuses on the use of the central limit of response times built in and an approximation of their distribution with an inverse Gaussian mixture distribution. The distribution parameters and their associated failure rates are estimated through a suitable re-parameterization of the inverse Gaussian distribution and an adapted Expectation-Maximization algorithm. Extensive simulations demonstrate that the method is well-suited for the approximation of failure rates. We discuss the extension of such method to a chi-squared independence test adapted to real-time systems.
Related papers
- Industrial Load Modeling and Optimization for Market-Based Interaction with Power Systems
- Exact and Approximate Convex Reformulation of Linear Stochastic Optimal Control with Chance Constraints
- Certified Set Convergence for Piecewise Affine Systems
- Symbolic Control for Stochastic Systems via Finite Parity Games
- Multiobjective optimization-based design and dispatch of islanded, hybrid microgrids for remote, off-grid communities in sub-Saharan Africa
- Physiology-informed layered sensing for intelligent human-exoskeleton interaction