Challenges associated with allowing preemptions and migrations are compounded in multicore systems, particularly under global scheduling policies, because of the potentially high overheads. For example, multiple levels of cache greatly increase preemption and migration related overheads as well as the difficulty involved in accurately accounting for them, leading to substantially inflated worst-case execution times (WCETs). Preemption and migration related overheads can be significantly reduced, both in number and in size, by using fixed preemption points in the tasks' code; thus dividing each task into a series of non-preemptive regions (NPRs). This leads to an additional consideration in the scheduling policy. When a high priority task is released and all of the processors are executing non-preemptive regions of lower priority tasks, then there is a choice to be made in terms of how to manage the next preemption. With an eager approach the first lower priority task to reach a preemption point is preempted even if it is not the lowest priority running task. Alternatively, with a lazy approach, preemption is delayed until the lowest priority currently running task reaches its next preemption point. In this paper, we show that under global fixed priority scheduling with eager preemptions each task suffers from at most a single priority inversion each time it resumes execution. Building on this observation, we derive a new response time based schedulability test for tasks with fixed preemption points. Experimental evaluations show that global fixed priority scheduling with eager preemptions is significantly more effective than with lazy preemption using link based scheduling in terms of task set schedulability.

Multiprocessor fixed priority scheduling with limited preemptions / Thekkilakattil, Abhilash; Davis, Robert I.; Dobrin, Radu; Punnekkat, Sasikumar; Bertogna, Marko. - (2015), pp. 13-22. ((Intervento presentato al convegno 23rd International Conference on Real-Time Networks and Systems, RTNS 2015 tenutosi a Lille France nel 4-6 Novembre 2015 [10.1145/2834848.2834855].

Multiprocessor fixed priority scheduling with limited preemptions

BERTOGNA, Marko
2015-01-01

Abstract

Challenges associated with allowing preemptions and migrations are compounded in multicore systems, particularly under global scheduling policies, because of the potentially high overheads. For example, multiple levels of cache greatly increase preemption and migration related overheads as well as the difficulty involved in accurately accounting for them, leading to substantially inflated worst-case execution times (WCETs). Preemption and migration related overheads can be significantly reduced, both in number and in size, by using fixed preemption points in the tasks' code; thus dividing each task into a series of non-preemptive regions (NPRs). This leads to an additional consideration in the scheduling policy. When a high priority task is released and all of the processors are executing non-preemptive regions of lower priority tasks, then there is a choice to be made in terms of how to manage the next preemption. With an eager approach the first lower priority task to reach a preemption point is preempted even if it is not the lowest priority running task. Alternatively, with a lazy approach, preemption is delayed until the lowest priority currently running task reaches its next preemption point. In this paper, we show that under global fixed priority scheduling with eager preemptions each task suffers from at most a single priority inversion each time it resumes execution. Building on this observation, we derive a new response time based schedulability test for tasks with fixed preemption points. Experimental evaluations show that global fixed priority scheduling with eager preemptions is significantly more effective than with lazy preemption using link based scheduling in terms of task set schedulability.
23rd International Conference on Real-Time Networks and Systems, RTNS 2015
Lille France
4-6 Novembre 2015
13
22
Thekkilakattil, Abhilash; Davis, Robert I.; Dobrin, Radu; Punnekkat, Sasikumar; Bertogna, Marko
Multiprocessor fixed priority scheduling with limited preemptions / Thekkilakattil, Abhilash; Davis, Robert I.; Dobrin, Radu; Punnekkat, Sasikumar; Bertogna, Marko. - (2015), pp. 13-22. ((Intervento presentato al convegno 23rd International Conference on Real-Time Networks and Systems, RTNS 2015 tenutosi a Lille France nel 4-6 Novembre 2015 [10.1145/2834848.2834855].
File in questo prodotto:
File Dimensione Formato  
RTNS15_2.pdf

Open access

Tipologia: Versione dell'autore revisionata e accettata per la pubblicazione
Dimensione 535.97 kB
Formato Adobe PDF
535.97 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1118715
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact