An Analytical Solution for Probabilistic Guarantees of Reservation Based Soft Real-Time Systems

Luigi Palopoli, Daniele Fontanelli, Luca Abeni, Bernardo Villalba Frias

TL;DR

This paper presents a novel analytical method to compute the probability of meeting deadlines for soft real-time systems using resource reservation scheduling. The core contribution is a closed-form, conservative bound for this probability, offering a significant speedup over existing numerical methods and enabling efficient Quality of Service (QoS) optimization.

What Problem Does This Paper Address?

Soft real-time systems, common in multimedia, computer vision, and control, can tolerate occasional timing faults. Expressing their timing requirements often involves probabilistic deadlines – ensuring a deadline is met with a certain probability. Resource Reservation (RR) scheduling, like the Constant Bandwidth Server (CBS), provides temporal isolation, allowing individual task analysis. However, precisely calculating the probability of meeting these probabilistic deadlines, especially for periodic tasks with stochastic computation times, is computationally challenging. Existing methods often rely on complex numerical solutions of infinite-state Markov chains, which can be slow, or provide overly conservative bounds. This paper aims to bridge this gap by offering an efficient analytical solution and a tight, yet conservative, bound.

Methods

The authors model a periodic real-time task scheduled by a resource reservation as a Quasi-Birth-Death Process (QBDP), an infinite-state Markov chain with a specific block structure. They introduce a "granularity parameter" (Δ) to create a conservative approximation of the QBDP, allowing for trade-offs between accuracy and computation time. The key innovation lies in deriving an analytical closed-form solution for the steady-state probability of meeting the deadline from this QBDP model. This analytical solution is then used to derive a conservative bound, which is computationally much cheaper than numerical methods. The paper also details the mathematical framework, including theorems and propositions, to support the derivation of these analytical results.

Datasets

The paper does not introduce new datasets. Instead, it uses:

  • Synthetic distributions: Specifically, a beta distribution for task computation times, chosen for its unimodal nature and finite support, making it a good approximation for real-world scenarios.
  • Real-world application data: Data from a robotic vision program that identifies lane boundaries and estimates robot position. This data was used to evaluate the model's performance when its underlying assumptions (like i.i.d. computation times) are not strictly met.

Key Insights and Ideas

  • QBDP as a powerful model: The paper demonstrates that a resource-reserved periodic real-time task can be effectively modeled as a Quasi-Birth-Death Process, a structure amenable to analytical solutions.
  • Granularity for trade-offs: The introduction of a scaling factor (Δ) allows for a tunable approximation of the system, enabling a direct trade-off between computational cost and the accuracy of the probabilistic guarantee.
  • Analytical bound's efficiency: The derived closed-form analytical bound is significantly faster to compute than numerical solutions, making it practical for real-time optimization problems.
  • Conservative but useful: While the analytical bound is conservative (meaning it might overestimate the deadline miss probability), it is shown to be reasonably tight in practice and sufficient for QoS optimization.
  • Temporal isolation is key: The paper leverages the temporal isolation property of resource reservation scheduling to analyze each task independently, simplifying the problem significantly compared to analyzing task sets as a whole.

Key Results

  • Analytical Solution: The paper provides a method to compute the steady-state probability of meeting a deadline for a periodic task under resource reservation scheduling.
  • Closed-Form Conservative Bound: A key result is a closed-form analytical bound for the probability of meeting the deadline. This bound is computationally efficient, requiring orders of magnitude less time than numerical methods like Cyclic Reduction.
  • Experimental Validation:
    • Experiments with synthetic data showed that the analytical bound is reasonably close to numerical results, with accuracy improving as the bandwidth increases.
  • The bound's performance was evaluated on a real robotic vision application, demonstrating its practical applicability even when strict i.i.d. assumptions are violated. The approximation error was found to be acceptable for most cases.
  • The analytical method was shown to be significantly faster than numerical methods, enabling efficient QoS optimization. For example, in a QoS optimization scenario, the analytical approach achieved a computation time four orders of magnitude lower than cyclic reduction.

Limitations and Future Work

  • Assumptions: The model relies on assumptions such as independent and identically distributed (i.i.d.) computation times and periodic task arrivals. The paper acknowledges that real-world systems often violate these assumptions (e.g., due to OS overhead, correlations).
  • Conservatism: The analytical bound is conservative, meaning it provides a lower bound on the probability of meeting the deadline. While this is often desirable for safety, it might lead to suboptimal resource allocation if too pessimistic.
  • Future Work:
    • Investigate the connection between QoS and probabilistic deadlines in more application domains.
  • Extend the analysis to applications with multiple tasks.
  • Address computation times that are not i.i.d. (e.g., by exploring techniques like Extreme Value Theory for estimating distributions or incorporating correlation models).

Summary updated

Abstract

We show a methodology for the computation of the probability of deadline miss for a periodic real-time task scheduled by a resource reservation algorithm. We propose a modelling technique for the system that reduces the computation of such a probability to that of the steady state probability of an infinite state Discrete Time Markov Chain with a periodic structure. This structure is exploited to develop an efficient numeric solution where different accuracy/computation time trade-offs can be obtained by operating on the granularity of the model. More importantly we offer a closed form conservative bound for the probability of a deadline miss. Our experiments reveal that the bound remains reasonably close to the experimental probability in one real-time application of practical interest. When this bound is used for the optimisation of the overall Quality of Service for a set of tasks sharing the CPU, it produces a good sub-optimal solution in a small amount of time.
BibTeX
@article{palopoli2016analytical,
  author = {Luigi Palopoli and Daniele Fontanelli and Luca Abeni and Bernardo Villalba Frias},
  title = {{An Analytical Solution for Probabilistic Guarantees of Reservation Based Soft Real-Time Systems}},
  journal = {IEEE Trans. Parallel Distributed Syst.},
  year = {2016},
  url = {https://openreview.net/forum?id=CUsW6DdBbX},
}
Figure