Skip to Main content Skip to Navigation
Journal articles

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

Bruno Gaujal 1, 2 Alain Girault 1, 3 Stéphan Plassart 1, 2
2 POLARIS - Performance analysis and optimization of LARge Infrastructures and Systems
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
3 SPADES - Sound Programming of Adaptive Dependable Embedded Systems
LIG - Laboratoire d'Informatique de Grenoble, Inria Grenoble - Rhône-Alpes
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, S max denotes the maximal speed of the processor. In such a real-time system, a speed selection policy dynamically chooses (i.e., on-line) he speed of the processor to execute the current, not yet finished, jobs. We saythat an on-line speed policy is feasible if it is able to execute any sequence ofjobs while meeting two constraints: the processor speed is always belowSmaxand no job misses its deadline. In this paper, we compare the feasibility regionof four on-line speed selection policies in single-processor real-time systems,namely Optimal Available (OA) (Yao, Demers, and Shenker, 1995), Aver-age Rate (AVR) (Yao, Demers, and Shenker, 1995), (BKP) (Bansal, Kimbrel,and Pruhs, 2007), and a Markovian Policy based on dynamic programming(MP) (Gaujal, Girault, and Plassart, 2017). 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 (where e= 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 con-sumption (on average) but is also optimal regarding feasibility.
Document type :
Journal articles
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download
Contributor : Stéphan Plassart <>
Submitted on : Wednesday, April 29, 2020 - 6:21:59 PM
Last modification on : Tuesday, November 24, 2020 - 4:00:17 PM


Files produced by the author(s)



Bruno Gaujal, Alain Girault, Stéphan Plassart. Feasibility of on-line speed policies in real-time systems. Real-Time Systems, Springer Verlag, 2020, ⟨10.1007/s11241-020-09347-y⟩. ⟨hal-02557148⟩



Record views


Files downloads