5th International ICST Conference on Performance Evaluation Methodologies and Tools

Research Article

A symbolic approach to quantitative analysis of preemptive real-time systems with non-Markovian temporal parameters

Download142 downloads
  • @INPROCEEDINGS{10.4108/icst.valuetools.2011.245728,
        author={Laura Carnevali and Enrico Vicario and Johnny Giuntini},
        title={A symbolic approach to quantitative analysis of preemptive real-time systems with non-Markovian temporal parameters},
        proceedings={5th International ICST Conference on Performance Evaluation Methodologies and Tools},
        publisher={ICST},
        proceedings_a={VALUETOOLS},
        year={2012},
        month={6},
        keywords={Quantitative evaluation non-Markovian Stochastic Petri Nets Generalized Semi-Markov Processes \% preemptive real-time systems approximate state space representation Difference Bounds Matrix Bernstein Polynomials},
        doi={10.4108/icst.valuetools.2011.245728}
    }
    
  • Laura Carnevali
    Enrico Vicario
    Johnny Giuntini
    Year: 2012
    A symbolic approach to quantitative analysis of preemptive real-time systems with non-Markovian temporal parameters
    VALUETOOLS
    ICST
    DOI: 10.4108/icst.valuetools.2011.245728
Laura Carnevali1,*, Enrico Vicario2, Johnny Giuntini2
  • 1: Dip. Sistemi e Informatica
  • 2: Dipartimento di Sistemi e Informatica - Università di Firenze
*Contact email: laura.carnevali@unifi.it

Abstract

The method of stochastic state classes provides a means for quantitative analysis of a rather wide class of non-Markovian models. As a major and structural limitation, the approach cannot be applied to models encompassing a preemptive policy, which in the practice rules out the mechanism of suspension and resume usually applied in many real-time systems.

We overcome here the limitation by proposing an approach that faces the complexity issues introduced by the suspension/resume mechanism in the structure of supports and distributions of remaining times. In particular, these are distributed over a polyhedral support according to a multivariate joint density function with analytic piecewise form over a partition into polyhedral subdomains. The approach resorts to an imprecise analysis that extends distributions over the tightest DBM zones enclosing polyhedral domains, and approximates them with Bernstein Polynomials to obtain a global (non-piecewise) analytic representation. Computational experience is reported to show the different impact of errors due to the approximation of supports and distributions.