Online and offline scheduling with cache-related preemption delays

Guillaume Phavorin 1 Pascal Richard 1 Joël Goossens 2 Claire Maiza 3 Laurent George 4 Thomas Chapeaux 2
1 LIAS - Laboratoire d'Informatique et d'Automatique pour les Systèmes
2 ULB - Département d'Informatique [Bruxelles]
3 VERIMAG - IMAG - VERIMAG
4 LIGM - Laboratoire d'Informatique Gaspard-Monge
Abstract : In this paper, we consider the problem of scheduling hard real-time tasks subjected to preemption delays on a uniprocessor system. While most of the existing work focus on either reducing these additional delays or improving the system predictability by bounding them, we focus in this work on the problem of taking scheduling decisions while considering preemption delays. We first study the behavior of existing online scheduling policies such as rm and edf when accounting for preemption delays. Then we prove that there exists no optimal online algorithm for the problem of scheduling sporadic tasks with preemption delays. Eventually, we propose an optimal offline solution to the problem of scheduling tasks subjected to preemption delays using mathematical programming.
Keywords : Offline scheduling Online scheduling rm edf Preemption delays CRPD Sustainability Mathematical programming
Document type :
Journal articles
Complete list of metadatas
https://hal-upec-upem.archives-ouvertes.fr/hal-01779467
Contributor : Admin Upem <>
Submitted on : Thursday, April 26, 2018 - 3:53:26 PM
Last modification on : Wednesday, September 5, 2018 - 1:30:09 PM

Links full text

openaccess

Identifiers

Collections

UPEC-UPEM | IMAG | UNIV-POITIERS | UGA | ENPC | PARISTECH | LIGM | LIGM_LRT | ESIEE-PARIS | VERIMAG

Citation

Guillaume Phavorin, Pascal Richard, Joël Goossens, Claire Maiza, Laurent George, et al.. Online and offline scheduling with cache-related preemption delays. Real-Time Systems, Springer Verlag, 2017, pp.1-38. ⟨10.1007/s11241-017-9275-6⟩. ⟨hal-01779467⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

246

Contact

CCSD