On assessing the viability of probabilistic scheduling with dependent tasks

Despite the significant interest, in the last years, in probabilistic scheduling and probabilistic timing analysis, the interrelation between them has been scarcely addressed. Probabilistic scheduling approaches typically build on a series of assumptions on the probabilistic behavior of each task - or single jobs activations - that have not been shown to be entirely fulfilled by the distributions computed with probabilistic timing analysis. This paper aims at providing a clear understanding of probabilistic Worst-Case Execution Time distributions (pWCET) as a common concept of probabilistic timing and schedulability analysis. We focus on independence of pWCET estimates as the main concern in the application of probabilistic scheduling, with particular emphasis on measurement-based probabilistic timing analyses, for which independence across pWCET estimates may not be guaranteed. We relate pWCET (in)dependence to the platform-induced timing dependencies that occur among tasks, and even jobs of the same task. We conclude that independent pWCET distributions can be obtained, even if dependencies exist, by either controlling the measurement protocol, or by deriving distinct pWCET estimates for particular instances of a task.
This work has been partially supported by the Spanish Ministry of Economy and Competitiveness (MINECO) under grant TIN2015-65316-P, the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 772773) and the HiPEAC Network of Excellence. Jaume Abella and Enrico Mezzetti have been partially supported by MINECO under Ramon y Cajal and Juan de la Cierva-Incorporación postdoctoral fellowships number RYC-2013-14717 and IJCI-2016-27396 respectively.
Peer Reviewed
Postprint (author's final draft)