View in EDS

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

Saved in:
Bibliographic Details
Title: Feasibility of on-line speed policies in real-time systems.
Authors: Gaujal, Bruno1 (AUTHOR), Girault, Alain1 (AUTHOR) alain.girault@inria.fr, Plassart, Stéphan1 (AUTHOR)
Source: Real-Time Systems. Jul2020, Vol. 56 Issue 3, p254-292. 39p.
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) 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 S max 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) (Yao et al. in IEEE annual foundations of computer science, 1995), Average Rate (AVR) (Yao et al. 1995), (BKP) (Bansal in J ACM 54:1, 2007), and a Markovian Policy based on dynamic programming (MP) (Gaujal in Technical Report hal-01615835, Inria, 2017). We prove the following results: (OA) is feasible if and only if S max ≥ C (h Δ - 1 + 1) , where h n is the n-th harmonic number ( h n = ∑ i = 1 n 1 / i ≈ log n ). (AVR) is feasible if and only if S max ≥ C h Δ . (BKP) is feasible if and only if S max ≥ e C (where e = exp (1) ). (MP) is feasible if and only if S max ≥ C . This is an optimal feasibility condition because when S max < 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. [ABSTRACT FROM AUTHOR]
Copyright of Real-Time Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
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) 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 S max 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) (Yao et al. in IEEE annual foundations of computer science, 1995), Average Rate (AVR) (Yao et al. 1995), (BKP) (Bansal in J ACM 54:1, 2007), and a Markovian Policy based on dynamic programming (MP) (Gaujal in Technical Report hal-01615835, Inria, 2017). We prove the following results: (OA) is feasible if and only if S max ≥ C (h Δ - 1 + 1) , where h n is the n-th harmonic number ( h n = ∑ i = 1 n 1 / i ≈ log n ). (AVR) is feasible if and only if S max ≥ C h Δ . (BKP) is feasible if and only if S max ≥ e C (where e = exp (1) ). (MP) is feasible if and only if S max ≥ C . This is an optimal feasibility condition because when S max < 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. [ABSTRACT FROM AUTHOR]
ISSN:09226443
DOI:10.1007/s11241-020-09347-y