Abstract
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.
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 language | English |
---|---|
Title of host publication | International conference on Real-Time and Network Systems |
Publication status | Published - Sept 2011 |
Event | 19th International Conference on Real-Time and Network Systems (RTNS 2011) - Nantes, France Duration: 29 Sept 2011 → 30 Sept 2011 |
Conference
Conference | 19th International Conference on Real-Time and Network Systems (RTNS 2011) |
---|---|
Country/Territory | France |
City | Nantes |
Period | 29/09/11 → 30/09/11 |