Feasibility of on-line speed policies in real-time systems
| Autor: | Alain Girault, Bruno Gaujal, Stéphan Plassart |
|---|---|
| Přispěvatelé: | Performance analysis and optimization of LARge Infrastructures and Systems (POLARIS), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), Sound Programming of Adaptive Dependable Embedded Systems (SPADES), This work has been partially supported by the LabEx PERSYVAL-Lab (ANR-11-LABX-0025-01) funded by the French program Investissement d’avenir., CASERM, ANR-11-LABX-0025,PERSYVAL-lab,Systemes et Algorithmes Pervasifs au confluent des mondes physique et numérique(2011) |
| Rok vydání: | 2020 |
| Předmět: |
010302 applied physics
Sequence Mathematical optimization Control and Optimization Feasibility condition Computer Networks and Communications Computer science Clock rate Markov process 02 engineering and technology 01 natural sciences 020202 computer hardware & architecture Computer Science Applications Dynamic programming Variable (computer science) symbols.namesake Control and Systems Engineering Modeling and Simulation Bounded function 0103 physical sciences 0202 electrical engineering electronic engineering information engineering symbols [INFO]Computer Science [cs] Markov decision process Electrical and Electronic Engineering |
| Zdroj: | Real-Time Systems Real-Time Systems, Springer Verlag, 2020, ⟨10.1007/s11241-020-09347-y⟩ Real-Time Systems, 2020, ⟨10.1007/s11241-020-09347-y⟩ |
| ISSN: | 1573-1383 0922-6443 |
| DOI: | 10.1007/s11241-020-09347-y |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink