Towards optimal priority assignment for probabilistic real-time systems with variable execution times
Abstract
In this paper we deal with fixed-priority scheduling of synchronous periodic task systems with variable execution times. The tasks have variable execution times given by independent discrete random variables (that we consider known) and we study the existence of an optimal priority assignment algorithm for such tasks. We provide a first result indicating that Rate Monotonic is not optimal and we prove that optimal priority assignment al- gorithms do exist. Moreover a first intuitive algorithm, that orders the tasks according to their probability of meeting the deadlines, is proved not optimal.