Skip to Main content Skip to Navigation

Feasibility of on-line speed policies in real-time systems

Bruno Gaujal 1 Alain Girault 2 Stéphan Plassart 1, 2
1 POLARIS - Performance analysis and optimization of LARge Infrastructures and Systems
LIG - Laboratoire d'Informatique de Grenoble, Inria Grenoble - Rhône-Alpes
2 SPADES - Sound Programming of Adaptive Dependable Embedded Systems
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : We consider a real-time system where a single processor with variable speed executes an infinite sequence of sporadic and independent jobs. We assume that job sizes and relative deadlines are bounded by $C$ and $∆$ respectively. Furthermore, $Smax$ denotes the maximal speed of the processor. In such a real-time system, a speed selection policy dynamically chooses (i.e.,on-line) the speed of the processor to execute the current, not yet finished, jobs. We say that an on-line speed policy is feasible if it is able to execute any sequence of jobs while meeting two constraints: the processor speed is always below $Smax$ and no job misses its deadline. In this paper, we compare the feasibility region of four on-line speed selection policies in single-processor real-time systems, namely Optimal Available(OA)[1], Average Rate(AVR)[1],(BKP)[2], and aMarkovian Policy based on dynamic programming(MP)[3]. We prove the following results: • (OA)is feasible if and only if $Smax≥C(h∆−1+ 1)$, where $hn$ is the $n-th$ harmonic number $(hn=∑ni=11/i≈logn)$. • (AVR) is feasible if and only if $Smax≥Ch∆$. • (BKP) is feasible if and only if $Smax≥eC(wheree= exp(1))$. • (MP) is feasible if and only if $Smax≥C$. This is an optimal feasibility condition because when $Smax< C$ no policy can be feasible. This reinforces the interest of (MP) that is not only optimal for energy consumption (on average) but is also optimal regarding feasibility.
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download
Contributor : Stéphan Plassart <>
Submitted on : Wednesday, November 20, 2019 - 10:56:57 AM
Last modification on : Monday, April 20, 2020 - 11:44:05 AM


Files produced by the author(s)


  • HAL Id : hal-02371996, version 1


Bruno Gaujal, Alain Girault, Stéphan Plassart. Feasibility of on-line speed policies in real-time systems. [Research Report] RR-9301, Inria Grenoble Rhône-Alpes, Université de Grenoble; Univ. Grenoble Alpes. 2019, pp.38. ⟨hal-02371996⟩



Record views


Files downloads