Titre :

A pre-order relation for exact schedulability test of sporadic tasks on multiprocessor Global Fixed-Priority scheduling

Auteur(s) :

Sun, Youcheng [Auteur]
Scuola Universitaria Superiore Sant'Anna = Sant'Anna School of Advanced Studies [Pisa] [SSSUP]
Lipari, Giuseppe [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]

Titre de la revue :

Real-Time Systems

Éditeur :

Springer Verlag

Date de publication :

2015-12-09

ISSN :

0922-6443

Discipline(s) HAL :

Informatique [cs]/Systèmes embarqués
Informatique [cs]/Système d'exploitation [cs.OS]
Informatique [cs]/Théorie et langage formel [cs.FL]

Résumé en anglais : [en]

In this paper we present an exact schedulability test for sporadic real-time tasks scheduled by the Global Fixed Priority (G-FP) Fully Preemp-tive Scheduler on a multiprocessor system. The analysis consists in mod-eling ...
Lire la suite >In this paper we present an exact schedulability test for sporadic real-time tasks scheduled by the Global Fixed Priority (G-FP) Fully Preemp-tive Scheduler on a multiprocessor system. The analysis consists in mod-eling the system as a Linear Hybrid Automaton (LHA), and in performing a reachability analysis for states representing deadline miss conditions. To mitigate the problem of state space explosion, we propose a pre-order relationship over the symbolic states of the model: states that are simulated by others can be safely eliminated from the state space. We also formulate the concept of decidability interval with respect to a set of constrained-deadline sporadic tasks on multiprocessor. The decidability interval is a bounded time interval such that, if a deadline miss occurs in the schedule, then it is possible to find a configuration of arrival times for the tasks such that the deadline miss happens within the bounded interval. Vice versa, if no configuration of arrival times produces a deadline miss in the bounded interval, then no deadline miss is ever possible in the schedule. Hence we prove that the schedulability analysis problem is decidable, and we provide a formula for computing the decidability interval. To our knowledge, this is the first time such a time interval is proposed for sporadic tasks running on multiprocessor. The proposed schedulability analysis has been implemented in a software tool. For the first time we assess the pessimism of the state-of-the-art approximate schedulability test through experiments. Moreover, we show * This paper has been accepted by the Real Time Systems Journal. This is the submitted version, the final accepted version is avaliable at the journal's web site.Lire moins >

Langue :

Anglais

Vulgarisation :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL