Skip to main content
Erschienen in: Real-Time Systems 1/2014

01.01.2014

Bounding and shaping the demand of generalized mixed-criticality sporadic task systems

verfasst von: Pontus Ekberg, Wang Yi

Erschienen in: Real-Time Systems | Ausgabe 1/2014

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We generalize the commonly used mixed-criticality sporadic task model to let all task parameters (execution-time, deadline and period) change between criticality modes. In addition, new tasks may be added in higher criticality modes and the modes may be arranged using any directed acyclic graph, where the nodes represent the different criticality modes and the edges the possible mode switches. We formulate demand bound functions for mixed-criticality sporadic tasks and use these to determine EDF-schedulability. Tasks have different demand bound functions for each criticality mode. We show how to shift execution demand between different criticality modes by tuning the relative deadlines. This allows us to shape the demand characteristics of each task. We propose efficient algorithms for tuning all relative deadlines of a task set in order to shape the total demand to the available supply of the computing platform. Experiments indicate that this approach is successful in practice. This new approach has the added benefit of supporting hierarchical scheduling frameworks.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
The cited works differ in the assumption of implicit, constrained or arbitrary deadlines.
 
2
One could easily find a time point where it is safe to switch back, e.g., at any time the system is idle, but it is out of scope of this paper.
 
3
A small technical issue is that the bound by Baruah et al. (1990) is dependent on the relative deadlines of tasks, which are changed by Algorithm 1. The issue is easily avoided by using the largest bound generated with any of the possible relative deadlines that may be assigned (this is simply D i (lo)=C i (lo) for all τ i hi(τ)). An even easier solution is to use an alternative bound that is independent of relative deadlines, e.g., the one described by Stigge et al. (2011).
 
4
If the behavior is not valid in any criticality mode that the system can switch to either, the system is considered erroneous.
 
5
In practice, a preprocessing step can just set D i (m)←D i (m′) if D i (m)>D i (m′) in such a case. The purpose of the non-decreasing deadline invariant is not to restrict the expressiveness of the task model, but to increase the conciseness of the schedulability analysis by removing cases that can trivially be seen to not lead to schedulability.
 
6
This is not an issue that can be avoided. Some knowledge about a system’s behavior prior to entering a new criticality mode must be assumed in order to provide any usable bound at all.
 
7
A similar evaluation performed in a preliminary version of this paper (Ekberg and Yi 2012) used the original test for EDF-VD (Baruah et al. 2011a). Here we use the improved test (Baruah et al. 2012b).
 
8
The reason we use a maximum utilization of 0.99 instead of 1 is to be able to use a pseudo-polynomial upper bound max for Algorithm 1 instead of the hyperperiod, as described in Sect. 4.1. This speeds up the run-time of the experiments significantly, which is needed as several million task sets are analyzed in total.
 
9
Note that we interpret mod as positive remainder: \(a \bmod b = a - \lfloor\frac{a}{b} \rfloor \cdot b\).
 
Literatur
Zurück zum Zitat Audsley NC (2001) On priority assignment in fixed priority scheduling. Inf Process Lett 79(1):39–44 CrossRefMATH Audsley NC (2001) On priority assignment in fixed priority scheduling. Inf Process Lett 79(1):39–44 CrossRefMATH
Zurück zum Zitat Baruah S (2012) Certification-cognizant scheduling of tasks with pessimistic frequency specification. In: SIES, pp 31–38 Baruah S (2012) Certification-cognizant scheduling of tasks with pessimistic frequency specification. In: SIES, pp 31–38
Zurück zum Zitat Baruah S, Mok A, Rosier L (1990) Preemptively scheduling hard-real-time sporadic tasks on one processor. In: RTSS, pp 182–190 Baruah S, Mok A, Rosier L (1990) Preemptively scheduling hard-real-time sporadic tasks on one processor. In: RTSS, pp 182–190
Zurück zum Zitat Baruah S, Li H, Stougie L (2010) Towards the design of certifiable mixed-criticality systems. In: RTAS, pp 13–22 Baruah S, Li H, Stougie L (2010) Towards the design of certifiable mixed-criticality systems. In: RTAS, pp 13–22
Zurück zum Zitat Baruah S, Bonifaci V, D’Angelo G, Marchetti-Spaccamela A, van der Ster S, Stougie L (2011a) Mixed-criticality scheduling of sporadic task systems. In: ESA, pp 555–566 Baruah S, Bonifaci V, D’Angelo G, Marchetti-Spaccamela A, van der Ster S, Stougie L (2011a) Mixed-criticality scheduling of sporadic task systems. In: ESA, pp 555–566
Zurück zum Zitat Baruah S, Burns A, Davis R (2011b) Response-time analysis for mixed criticality systems. In: RTSS, pp 34–43 Baruah S, Burns A, Davis R (2011b) Response-time analysis for mixed criticality systems. In: RTSS, pp 34–43
Zurück zum Zitat Baruah S, Bonifaci V, D’Angelo G, Li H, Marchetti-Spaccamela A, Megow N, Stougie L (2012a) Scheduling real-time mixed-criticality jobs. IEEE Trans Comput 61(8):1140–1152 MathSciNetCrossRef Baruah S, Bonifaci V, D’Angelo G, Li H, Marchetti-Spaccamela A, Megow N, Stougie L (2012a) Scheduling real-time mixed-criticality jobs. IEEE Trans Comput 61(8):1140–1152 MathSciNetCrossRef
Zurück zum Zitat Baruah S, Bonifaci V, D’Angelo G, Li H, Marchetti-Spaccamela A, van der Ster S, Stougie L (2012b) The preemptive uniprocessor scheduling of mixed-criticality implicit-deadline sporadic task systems. In: ECRTS, pp 145–154 Baruah S, Bonifaci V, D’Angelo G, Li H, Marchetti-Spaccamela A, van der Ster S, Stougie L (2012b) The preemptive uniprocessor scheduling of mixed-criticality implicit-deadline sporadic task systems. In: ECRTS, pp 145–154
Zurück zum Zitat Bastoni A, Brandenburg B, Anderson J (2010) Cache-related preemption and migration delays: empirical approximation and impact on schedulability. In: OSPERT, pp 33–44 Bastoni A, Brandenburg B, Anderson J (2010) Cache-related preemption and migration delays: empirical approximation and impact on schedulability. In: OSPERT, pp 33–44
Zurück zum Zitat Buttazzo GC (2005) Rate monotonic vs. EDF: judgment day. Real-Time Syst 29(1):5–26 CrossRefMATH Buttazzo GC (2005) Rate monotonic vs. EDF: judgment day. Real-Time Syst 29(1):5–26 CrossRefMATH
Zurück zum Zitat Ekberg P, Yi W (2012) Bounding and shaping the demand of mixed-criticality sporadic tasks. In: ECRTS, pp 135–144 Ekberg P, Yi W (2012) Bounding and shaping the demand of mixed-criticality sporadic tasks. In: ECRTS, pp 135–144
Zurück zum Zitat Guan N, Ekberg P, Stigge M, Yi W (2011) Effective and efficient scheduling of certifiable mixed-criticality sporadic task systems. In: RTSS, pp 13–23 Guan N, Ekberg P, Stigge M, Yi W (2011) Effective and efficient scheduling of certifiable mixed-criticality sporadic task systems. In: RTSS, pp 13–23
Zurück zum Zitat Li H, Baruah S (2010) An algorithm for scheduling certifiable mixed-criticality sporadic task systems. In: RTSS, pp 183–192 Li H, Baruah S (2010) An algorithm for scheduling certifiable mixed-criticality sporadic task systems. In: RTSS, pp 183–192
Zurück zum Zitat Li H, Baruah S (2012) Global mixed-criticality scheduling on multiprocessors. In: ECRTS, pp 166–175 Li H, Baruah S (2012) Global mixed-criticality scheduling on multiprocessors. In: ECRTS, pp 166–175
Zurück zum Zitat Mok A (1983) Fundamental design problems of distributed systems for the hard real-time environment. Technical report, Cambridge, MA, USA Mok A (1983) Fundamental design problems of distributed systems for the hard real-time environment. Technical report, Cambridge, MA, USA
Zurück zum Zitat Mok A, Feng X, Chen D (2001) Resource partition for real-time systems. In: RTAS, pp 75–84 Mok A, Feng X, Chen D (2001) Resource partition for real-time systems. In: RTAS, pp 75–84
Zurück zum Zitat Pathan R (2012) Schedulability analysis of mixed-criticality systems on multiprocessors. In: ECRTS, pp 309–320 Pathan R (2012) Schedulability analysis of mixed-criticality systems on multiprocessors. In: ECRTS, pp 309–320
Zurück zum Zitat Real J, Crespo A (2004) Mode change protocols for real-time systems: a survey and a new proposal. Real-Time Syst 26(2):161–197 CrossRefMATH Real J, Crespo A (2004) Mode change protocols for real-time systems: a survey and a new proposal. Real-Time Syst 26(2):161–197 CrossRefMATH
Zurück zum Zitat Shin I, Lee I (2003) Periodic resource model for compositional real-time guarantees. In: RTSS, pp 2–13 Shin I, Lee I (2003) Periodic resource model for compositional real-time guarantees. In: RTSS, pp 2–13
Zurück zum Zitat Stigge M, Ekberg P, Guan N, Yi W (2011) The digraph real-time task model. In: RTAS, pp 71–80 Stigge M, Ekberg P, Guan N, Yi W (2011) The digraph real-time task model. In: RTAS, pp 71–80
Zurück zum Zitat Vestal S (2007) Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In: RTSS, pp 239–243 Vestal S (2007) Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In: RTSS, pp 239–243
Metadaten
Titel
Bounding and shaping the demand of generalized mixed-criticality sporadic task systems
verfasst von
Pontus Ekberg
Wang Yi
Publikationsdatum
01.01.2014
Verlag
Springer US
Erschienen in
Real-Time Systems / Ausgabe 1/2014
Print ISSN: 0922-6443
Elektronische ISSN: 1573-1383
DOI
https://doi.org/10.1007/s11241-013-9187-z

Weitere Artikel der Ausgabe 1/2014

Real-Time Systems 1/2014 Zur Ausgabe