Template Schedule Construction For Global Real-Time Scheduling on Unrelated Multiprocessor Platforms
Antoine Bertout1, Joël Goossens3,a, Emmanuel Grolleau2 and Xavier Poczekajlo3,b
1LIAS, Université de Poitiers, ISAE-ENSMA, Poitiers, France,
antoine.bertout@univ-poitiers.fr
2LIAS, ISAE-ENSMA, Université de Poitiers, Chasseneuil-Futuroscope, France,
grolleau@ensma.fr
3Université libre de Bruxelles, Brussels, Belgium,
aJoël.Goossens@ulb.ac.be
bXavier.Poczekajlo@ulb.ac.be
ABSTRACT
The seminal work on the global real-time scheduling of periodic tasks on unrelated multiprocessor platforms is based on a two-step method. First, the workload of each task is distributed over the processors and it is proved that this first step success ensures the existence of a feasible schedule. Then, using this workload assignment as an input, a template schedule construction method is presented. In this work, we review the seminal work and show by using a counter-example that this second step is incomplete. Thus, we propose and prove correct a novel and efficient algorithm to build the template schedule.
Keywords: Real-time Scheduling, Unrelated Multiprocessor platforms, Heterogeneous Multiprocessors, Graph Theory.
