Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Real-Time Systems
Published in: Real-Time Systems 5/2015

01-09-2015

Graph-based models for real-time workload: a survey

Authors: Martin Stigge, Wang Yi

Published in: Real-Time Systems | Issue 5/2015

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This paper provides a survey on task models to characterize real-time workloads at different levels of abstraction for the design and analysis of real-time systems. It covers the classic periodic and sporadic models by Liu and Layland et al., their extensions to describe recurring and branching structures as well as general graph- and automata-based models to allow modeling of complex structures such as mode switches, local loops and also global timing constraints. The focus is on the precise semantics of the various models and on the solutions and complexity results of the respective feasibilty and schedulability analysis problems for preemptable uniprocessors.
previous article Exact comparison of fixed priority and EDF scheduling based on speedup factors for both pre-emptive and non-pre-emptive paradigms

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
Footnotes
1
The exclusion window of a job is the time interval between its release time and the earliest possible release time of the next job from the same task. In the GMF model, this window has length \(P^T_i\) for jobs released by frame i of task T.
 
2
A cycle graph is a graph consisting of one single cycle, i.e., one closed chain.
 
3
The name “non-cyclic RRT” can be a bit misleading. The behavior of a non-cyclic RRT task is cyclic, in the sense that the source vertex is visited repeatedly. However, in comparison to the RRT model, the behavior is non-periodic, in the sense that revisits of the source vertex may happen in different time intervals.
 
Literature
Amnell T, Fersman E, Mokrushin L, Pettersson P, Yi W (2002) TIMES—A tool for modelling and implementation of embedded systems. In: Proceedings of TACAS. Springer, pp 460–464
Anand M, Easwaran A, Fischmeister S, Lee I (2008) Compositional feasibility analysis of conditional real-time task models. In: Proceedings of ISORC, pp 391–398
Audsley NC, Burns A, Davis RI, Tindell KW, Wellings AJ (1995) Fixed priority pre-emptive scheduling: an historical perspective. Real Time Syst 8(2):173–198CrossRef
Audsley NC, Burns A, Richardson MF, Wellings AJ (1991) Hard real-time scheduling: the deadline-monotonic approach. In: Proceedings of RTOSS, pp 133–137
Baker TP (1991) Stack-based scheduling for realtime processes. Real-Time Syst 3(1):67–99CrossRef
Baruah S, Goossens J (2004) Scheduling real-time tasks: algorithms and complexity. Handbook of scheduling: models, and performance analysis, p 3
Baruah SK, Mok AK, Rosier LE (1990) Preemptively scheduling hard-real-time sporadic tasks on one processor. In: Proceedings of RTSS, pp 182–190
Baruah SK (1998a) A general model for recurring real-time tasks. In: Proceedings of RTSS, pp 114–122
Baruah SK (1998b) Feasibility analysis of recurring branching tasks. In: Proceedings of EWRTS, pp 138–145
Baruah SK (2003) Dynamic- and static-priority scheduling of recurring real-time tasks. Real Time Syst 24(1):93–128CrossRefMATH
Baruah SK (2010) Preemptive uniprocessor scheduling of non-cyclic GMF task systems. In: Proceedings of RTCSA, pp 195–202
Baruah SK (2010b) The non-cyclic recurring real-time task model. In: Proceedings of RTSS, pp 173–182
Baruah SK (2014) Improved multiprocessor global schedulability analysis of sporadic DAG task systems. In: Proceedings of ECRTS, pp 97–105
Baruah SK, Bonifaci V, D’Angelo G, Li H, Marchetti-Spaccamela A, Megow N (2012a) Scheduling real-time mixed-criticality jobs. IEEE Trans Comput 61(8):1140–1152
Baruah SK, Bonifaci V, Marchet alei-Spaccamela A, Stougie L, Wiese A (2012b). A generalized parallel task model for recurrent real-time processes. In: Proceedings of RTSS, pp 63–72
Baruah SK, Burns A, Davis RI (2011) Response-time analysis for mixed criticality systems. In: Proceedings of RTSS, pp 34–43
Baruah SK, Chen D, Gorinsky S, Mok A (1999a) Generalized multiframe tasks. Real Time Syst 17(1):5–22CrossRef
Baruah SK, Chen D, Mok AK (1999b) Static-priority scheduling of multiframe tasks. In: Proceedings of ECRTS, pp 38–45
Bengtsson J, Yi W (2003) Timed automata: semantics, algorithms and tools. In: Lectures on concurrency and petri nets, pp 87–124
Berten V, Goossens J (2011) Sufficient FTP schedulability test for the non-cyclic generalized multiframe task model. CoRR, abs/1110.5793
Biondi A, Melani A, Marinoni M, Natale MD, Buttazz G (2014) Exact interference of adaptive variable-rate tasks under fixed-priority scheduling. In: Proceedings of ECRTS, pp 165–174
Bonifaci V, Marchetti-Spaccamela A, Stiller S, Wiese A (2013) Feasibility analysis in the sporadic DAG task model. In: Proceedings of ECRTS, pp 225–233
Boudec J, Thiran P (2001) Network Calculus: a theory of Deterministic Queuing Systems for the Internet. Lecture notes in computer science. Springer
Buttazzo G (2011) Hard real-time computing systems: predictable scheduling algorithms and applications. Realtime systems. Springer
Buttazzo GC, Bini E, Buttle D (2014) Rate-adaptive tasks: model, analysis, and design issues. In: Proceedings of DATE, pp 1–6
Chakraborty S, Erlebach T, Thiele L (2001) On the complexity of scheduling conditional real-time code. In: Proceedings of WADS, pp 38–49
Davis RI, Burns A (2011) A survey of hard real-time scheduling for multiprocessor systems. ACM Comput Surv 43(4):35:1–35:44
Davis RI, Feld T, Pollex V, Slomka F (2014) Schedulability tests for tasks with variable rate-dependent behaviour under fixed priority scheduling. In: Proceedings of RTAS, pp 51–62
Eisenbrand F, Rothvoß T (2008) Static-priority real-time scheduling: response time computation is NP-hard. In: Proceedings of RTSS, pp 397–406
Eisenbrand F, Rothvoß T (2010) EDF-schedulability of synchronous periodic task systems is coNP-hard. In: Proceedings of SODA, pp 1029–1034
Ekberg P, Guan N, Stigge M (2014) An optimal resource sharing protocol for generalized multiframe tasks. J Log Algebr Methods Program 84(1):92–105MathSciNetCrossRef
Ekberg P, Stigge M, Guan N, Yi W (2013) State-based mode switching with applications to mixed-criticality systems. In: Proceedings of WMC, pp 61–66
Ekberg P, Yi W (2012) Outstanding paper award: bounding and shaping the demand of mixed-criticality sporadic tasks. In: Proceedings of ECRTS, pp 135–144
Ekberg P, Yi W (2014) Bounding and shaping the demand of generalized mixed-criticality sporadic task systems. Real Time Syst 50(1):48–86CrossRefMATH
Ekberg P, Yi W (2015) Uniprocessor feasibility of sporadic tasks with constrained deadlines is strongly conp-complete. In: Proceedings of ECRTS. to appear
Fersman E, Krcal P, Pettersson P, Yi W, (2007) Task automata: schedulability, decidability and undecidability. Inf Comput 205(8):1149–1172
Fersman E, Mokrushin L, Pettersson P, Yi W, (2006) Schedulability analysis of fixed-priority systems using timed automata. Theor Comput Sci 354(2):301–317
Fersman E, Pettersson P, Yi W (2002) Timed automata with asynchronous processes: schedulability and decidability. In: Proceedings of TACAS 2002. Springer, pp 67–82
Guan N, Ekberg P, Stigge M, Yi W (2011) Resource sharing protocols for real-time task graph systems. In: Proceedings of ECRTS, pp 272–281
Han, C.-C. J. (1998). A Better Polynomial-Time Schedulability Test for Real-Time Multiframe Tasks. In: Proceedings of RTSS. IEEE Computer Society, Washington, DC, USA , pp 104–113
Kuo T, Chang L, Liu Y, Lin K (2003) Efficient online schedulability tests for real-time systems. IEEE Trans Softw Eng 29:734–751CrossRef
Lehoczky JP, Sha L, Strosnider JK (1987). Enhanced aperiodic responsiveness in hard real-time environments. In: Proceedings of the RTSS, pp 261–270
Leung JY-T, Whitehead J (1982) On the complexity of fixed-priority scheduling of periodic, real-time tasks. Perform Eval 2(4):237–250MathSciNetCrossRefMATH
Li H, Baruah SK (2012) Outstanding paper award: global mixed-criticality scheduling on multiprocessors. In: ECRTS, pp 166–175
Li J, Chen J-J, Agrawal K, Lu C, Gill C, Saifullah A (2014) Analysis of federated and global scheduling for parallel real-time tasks. In: Proceedings of ECRTS, pp 85–96
Lu W-C, Lin K-J, Wei H-W, Shih W-K (2007) New schedulability conditions for real-time multiframe tasks. In: Proceedings of the ECRTS, pp 39–50
Mok AK (1983) Fundamental design problems of distributed systems for the hard-real-time environment. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA
Mok AK, Chen D (1996) A general model for real-time tasks. Technical report
Mok AK, Chen D (1997) A multiframe model for real-time tasks. IEEE Trans Softw Eng 23(10):635–645CrossRef
Moyo NT, Nicollet ale E, Lafaye F, Moy C (2010) On schedulability analysis of non-cyclic generalized multiframe tasks. In: ECRTS, pp 271–278
Sha L, Abdelzaher T, Årzén K-E, Cervin A, Baker T, Burns A, Buttazzo G, Caccamo M, Lehoczky J, Mok AK (2004) Real time scheduling theory: a historical perspective. Real Time Syst 28(2–3):101–155CrossRefMATH
Sha L, Rajkumar R, Lehoczky J (1990) Priority inheritance protocols: an approach to real-time synchronization. IEEE Trans Comput 39(9):1175–1185MathSciNetCrossRef
Stigge M (2014) Real-time workload models: expressiveness vs. analysis efficiency. PhD thesis, Uppsala University, Sweden
Stigge M, Ekberg P, Guan N, Yi W (2011a). On the tractability of digraph-based task models. In: Proceedings of ECRTS, pp 162–171
Stigge M, Ekberg P, Guan N, Yi W (2011) The digraph real-time task model. In: Proceedings of RTAS, pp 71–80
Stigge M, Ekberg P, Yi W (2013) The fork-join real-time task model. Proc ACM SIGBED Rev 10(2):20CrossRef
Stigge M, Yi W (2012) Hardness results for static priority real-time scheduling. In: Proceedings of the ECRTS, pp 189–198
Stigge M, Yi W (2013) Combinatorial abstraction refinement for feasibility analysis. In: Proceedings of the RTSS, pp 340–349
Stigge M, Yi W (2014) Refinement-based exact response-time analysis. In: Proceedings of the ECRTS, pp 143–152
Takada H, Sakamura K (1997) Schedulability of generalized multiframe task sets under static priority assignment. In: Proceedings of the RTCSA, pp 80–86
Thiele L, Chakraborty S, Naedele M (2000) Real-time calculus for scheduling hard real-time systems. In: ISCAS, vol 4
Zeng H, Di Natale M (2014) Computing periodic request functions to speed-up the analysis of non-cyclic task models. Real Time Syst 1–35
Zhuo Y (2014) Static priority schedulability analysis of graph-based real-time task models with resource sharing. Uppsala University, Sweden, Term paper
Zuhily A, Burns A (2009) Exact scheduling analysis of non-accumulatively monotonic multiframe tasks. Real Time Syst J 43:119–146CrossRefMATH
Metadata
Title
Graph-based models for real-time workload: a survey
Authors
Martin Stigge
Wang Yi
Publication date
01-09-2015
Publisher
Springer US
Published in
Real-Time Systems / Issue 5/2015
Print ISSN: 0922-6443
Electronic ISSN: 1573-1383
DOI
https://doi.org/10.1007/s11241-015-9234-z

Premium Partner

    Image Credits