| Autor: |
Gaujal, Bruno, Girault, Alain, Plassart, Stéphan |
| 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 ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Sound Programming of Adaptive Dependable Embedded Systems (SPADES), Inria Grenoble Rhône-Alpes, Université de Grenoble, Univ. Grenoble Alpes, LabEx PERSYVAL-Lab, ANR-11-LABX-0025,PERSYVAL-lab,Systemes et Algorithmes Pervasifs au confluent des mondes physique et numérique(2011) |
| Jazyk: |
angličtina |
| Rok vydání: |
2019 |
| Předmět: |
|
| Zdroj: |
[Research Report] RR-9301, Inria Grenoble Rhône-Alpes, Université de Grenoble; Univ. Grenoble Alpes. 2019, pp.38 |
| 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, $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. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
