Optimal Priority Assignment Algorithms for Probabilistic Real-Time Systems
D. Maxim, O. Buffet, L. Santinelli, L. Cucu-Grosjean and R. I. Davis
In this paper we investigate the problem of optimal priority assignment in fixed priority pre-emptive single processor systems where tasks have probabilistic execution times. We identify three sub-problems which optimise different metrics related to the probability of deadline failures. For each sub-problem we propose an algorithm that is proved optimal. The first two algorithms are inspired by Audsley's algorithm which is a greedy (lowest priority first) approach that is optimal in the case of tasks with deterministic execution times. Since we prove that such a greedy approach is not optimal for the third sub-problem, we propose a tree search algorithm in this case.
BibTex Entry
@inproceedings{Maxim2011,
author = {D. Maxim and O. Buffet and L. Santinelli and L. Cucu-Grosjean and R. I. Davis},
booktitle = {Proceedings 19th International Conference on Real-Time and Network Systems (RTNS'11)},
title = {Optimal Priority Assignment Algorithms for Probabilistic Real-Time Systems},
year = {2011}
}