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

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 \(\varDelta \) 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 \({\text{(OA)}}\) (Yao et al. in IEEE annual foundations of computer science, 1995), Average Rate \({\text{(AVR)}}\) (Yao et al. 1995), \({\text{(BKP)}}\) (Bansal in J ACM 54:1, 2007), and a Markovian Policy based on dynamic programming \({\text{(MP)}}\) (Gaujal in Technical Report hal-01615835, Inria, 2017). We prove the following results: This reinforces the interest of \({\text{(MP)}}\) that is not only optimal for energy consumption (on average) but is also optimal regarding feasibility.