Optimal Priority Assignment Algorithms for Probabilistic Real-Time Systems

D. Maxim, O. Buffet, L. Santinelli, L. Cucu-Grosjean, R. I. Davis

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.
Original languageEnglish
Title of host publicationInternational conference on Real-Time and Network Systems
Publication statusPublished - Sept 2011
Event19th International Conference on Real-Time and Network Systems (RTNS 2011) - Nantes, France
Duration: 29 Sept 201130 Sept 2011


Conference19th International Conference on Real-Time and Network Systems (RTNS 2011)

Cite this