Probabilistic schedulability analysis
Résumé
The classical model of a real-time system consists of a number of tasks, each of which has an execution time which is upper bounded by a constant, referred to as the Worst-Case Execution Time (WCET). Further, jobs of each task execute periodically or sporadically, subject to some minimum inter-arrival time. Task execution is controlled by a real-time scheduler that determines, at any given time, which of the ready jobs the processor will execute. For such a model, schedulability analysis provides an a priori mathematical verification indicating whether or not all of the jobs of each task can be guaranteed to meet their deadlines under the particular scheduling policy used. This analysis is typically achieved by determining the worst-case scenario which leads to the the worst-case response time (from the release to the completion of any job of the task), calculating the worst-case response time, and comparing it with the task’s deadline. Probabilistic real-time systems differ from this classical model in two main ways. Firstly, at least one parameter of the tasks (e.g. execution time) is modeled as a random variable, i.e. described by a probability distribution. Secondly, rather than requiring an absolute guarantee that all deadlines must be met, timing constraints are specified in terms of a threshold on the acceptable probability of a deadline miss for each task. This chapter focuses on research into scheduling and specifically schedulability analysis for probabilistic real-time systems.