Schedulability analysis of multiprocessor real-time applications with stochastic task execution times

This paper presents an approach to the analysis of task sets implemented on multiprocessor systems, when the task execution times are specified as generalized probability distributions. Because of the extreme complexity of the problem, an exact solution is practically impossible to obtain even for simple examples. Therefore, our methodology is based on approximating the generalized probability distributions of execution times by Coxian distributions of exponentials. Thus, we transform the generalized semi-Markov process, corresponding to the initial problem, into a continuous Markov chain (CTMC) which, however, is extremely large and, hence, most often is impossible to store in memory. We have elaborated a solution which allows us to generate and analyze the CTMC in an efficient way, such that only a small part has to be stored at a given time. Several experiments investigate the impact of various parameters on complexity, in terms of time and memory, as well as the trade-offs regarding the accuracy of generated results.