Skip to Main content Skip to Navigation
Reports

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
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
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.
Document type :
Reports
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/hal-02371996
Contributor : Stéphan Plassart <>
Submitted on : Wednesday, November 20, 2019 - 10:56:57 AM
Last modification on : Friday, November 20, 2020 - 9:24:05 AM

File

RR-9301.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02371996, version 1

Citation

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⟩

Share

Metrics

Record views

135

Files downloads

593