nach oben

Real-Time Systems

Erschienen in:

04.03.2019

Priority-based scheduling of mixed-critical jobs

verfasst von: Dario Socci, Peter Poplavko, Saddek Bensalem, Marius Bozga

Erschienen in: Real-Time Systems | Ausgabe 4/2019

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Modern real-time systems tend to be mixed-critical, in the sense that they integrate on the same computational platform applications at different levels of criticality (e.g., safety critical and mission critical). Scheduling of such systems is a popular topic in literature due to the complexity and importance of the problem. In this paper we propose two algorithms for job scheduling in mixed critical systems: mixed criticality earliest deadline first (MCEDF) and mixed critical priority improvement (MCPI). MCEDF is a single processor algorithm that theoretically dominates state-of-the-art fixed-priority algorithm own criticality based priority (OCBP), while having a better computational complexity. The dominance is achieved by profiting from a common extension of fixed-priority online policy to mixed criticality. MCPI is a multiprocessor algorithm that supports dependency constraints. Experiments show good schedulability results. Also we formally prove that both MCEDF and MCPI are optimal in a particular class of algorithms.

Nächster Artikel Thermal-aware task allocation and scheduling for periodic real-time applications in mesh-based heterogeneous NoCs

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Though we use this legacy name, we should admit that there are several other mixed criticality algorithms that may be considered more intimately related to EDF.

In literature the word ALAP is usually used for latest arrival.

Baruah et al. (2010) uses a more efficient procedure—makespan (see Sect. 4.4).

We do not say ‘ready’ jobs in order to also include jobs that are waiting for their predecessors to terminate.

Recall that by default we study LO-mode schedules in this section.

For equal-deadline jobs we break the ties by selecting the job with minimal \(C_j(\hbox {HI})-C_j(\hbox {LO})\). This choice is explained in Sect. 5.2.

It ignores the runtime overhead that would be incurred by fragmentation of tasks in practice.

They are also tree-children of node J, as in a P-DAG forest the edges are directed from children to parents.

In this case we would need to put precedence edges between sub-jobs.

Audsley NC (1993) Flexible scheduling in hard-real-time systems. PhD thesis, Department of Computer Science, University of York

Baruah SK (2004) Optimal utilization bounds for the fixed-priority scheduling of periodic task systems on identical multiprocessors. IEEE Trans Comput 53(6):781–784CrossRef

Baruah S (2012a) Semantics-preserving implementation of multirate mixed-criticality synchronous programs. In RTNS ’12, pp 11–19. ACM

Baruah S (2012b) Semantics-preserving implementation of multirate mixed-criticality synchronous programs. In RTNS’12, pp 11–19. ACM

Baruah SK (2013) Implementing mixed criticality synchronous reactive systems upon multiprocessor platforms. The University of North Carolina at Chapel Hill, Tech. Rep

Baruah SK, Burns A (2006) Sustainable scheduling analysis. In Real-time systems symposium (RTSS 2006), pp 159–168

Baruah S, Fisher N (2005) The partitioned multiprocessor scheduling of sporadic task systems. In 26th IEEE international real-time systems symposium, 2005. RTSS 2005, pp 9–329

Baruah S, Fohler G (2011) Certification-cognizant time-triggered scheduling of mixed-criticality systems. In IEEE real-time systems symposium, RTSS ’11, pp 3–12

Baruah SK, Li H, Stougie L (2010) Towards the design of certifiable mixed-criticality systems. In IEEE real-time and embedded technology and applications symposium, RTAS’10, pp 13–22

Baruah S, Bonifaci V, D’Angelo G, Li H, Marchetti-Spaccamela A, van der Ster S, Stougie L (2012a) The preemptive uniprocessor scheduling of mixed-criticality implicit-deadline sporadic task systems. In IEEE Euromicro conference on real-time systems, ECRTS’12, pp 145–154

Baruah S, Bonifaci V, D’Angelo G, Li H, Marchetti-Spaccamela A, Megow N, Stougie L (2012b) Scheduling real-time mixed-criticality jobs. IEEE Trans Comput 61(8):1140–1152MathSciNetCrossRef

Baruah S, Chattopadhyay B, Li H, Shin I (2014) Mixed-criticality scheduling on multiprocessors. Real-Time Syst 50(1):142–177CrossRef

Behera L, Bhaduri P (2017) Time-triggered scheduling of mixed-criticality systems. ACM Trans Des Autom Electron Syst 22(4):74:1–74:25CrossRef

Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms, 2nd edn. McGraw-Hill Higher Education, New YorkMATH

Davis RI, Burns A (2011) A survey of hard real-time scheduling for multiprocessor systems. ACM Comput Surv 43(4):35CrossRef

Dhall SK, Liu CL (1978) On a real-time scheduling problem. Oper Res 26(1):127–140MathSciNetCrossRef

Ekberg P, Yi W (2012) Bounding and shaping the demand of mixed-criticality sporadic tasks. In IEEE Euromicro conference on real-time systems, ECRTS’12, pp. 145–154

Forget J et al (2010) Scheduling dependent periodic tasks without synchronization mechanisms. In RTAS’10, pp 301–310

Guan Nan, Ekberg Pontus, Stigge Martin, Yi Wang (2011) Effective and efficient scheduling of certifiable mixed-criticality sporadic task systems. In IEEE real-time systems symposium, RTSS’11, pp 13–23

Guo Z (2016) Real-time scheduling of mixed-critical workloads upon platforms with uncertainties. PhD thesis, University of North Carolina

Ha R, Liu JWS (1994) Validating timing constraints in multiprocessor and distributed real-time systems. In Proceedings international conference distributed computing systems, pp 162–171

Herman JL, Kenna CJ, Mollison MS, Anderson JH, Johnson DM (2012) Rtos support for multicore mixed-criticality systems. In IEEE real-time and embedded technology and applications symposium (RTAS), 2012 IEEE 18th, pp 197–208

Johnson LA (1992) DO-178B: software considerations in airborne systems and equipment certification. In Radio technical commission for aeronautics, RTCA

Kahil R, Poplavko P, Socci D, Bensalem S (2018a) Predictability in mixed-criticality systems. In IEEE 24th International Conference on Embedded and real-time computing systems and applications (RTCSA), 2018

Kahil R, Poplavko P, Socci D, Bensalem S (2018b) Predictability in mixed-criticality systems. Technical Report TR-2018-8, Verimag, (Extended version of the RTCSA-18 paper)

Kahil R, Socci D, Poplavko P, Bensalem S (2018c) Algorithmic complexity of correctness testing in MC-scheduling. In RTNS ’18, pp 180–190, New York. ACM

Kwok Y-K, Ahmad I (1999) Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Comput Surv 31(4):406–471CrossRef

Li H, Baruah S (2010) Load-based schedulability analysis of certifiable mixed-criticality systems. In International conference on embedded software, EMSOFT ’10, pp 99–108. ACM

Li H, Baruah SK (2012) Outstanding paper award: global mixed-criticality scheduling on multiprocessors. In 24th Euromicro conference on real-time systems, ECRTS 2012

Liu JWS (2000) Real-time systems. Prentice-Hall, Inc., Upper Saddle River

Mollison MS, Erickson JP, Anderson JH, Baruah SK, Scoredos JA (2010) Mixed-criticality real-time scheduling for multicore systems. In IEEE international conference on computer and information technology, CIT ’10, pp 1864–1871

Pathan RM (2012) Schedulability analysis of mixed-criticality systems on multiprocessors. In IEEE 24th Euromicro conference on real-time systems (ECRTS), 2012, pp 309–320

Park T, Kim S (2011) Dynamic scheduling algorithm and its schedulability analysis for certifiable dual-criticality systems. In International conference on embedded software, EMSOFT ’11, pp 253–262. ACM

Socci D (2016) Scheduling of certifiable mixed-criticality systems. PhD thesis, VERIMAG Research Center, Université Grenoble Alpes

Socci D, Poplavko P, Bensalem S, Bozga M (2013) Mixed critical earliest deadline first. In IEEE 25th Euromicro conference on real-time systems (ECRTS), 2013, pp 93–102

Socci D, Poplavko P, Bensalem S, Bozga M (2015a) Multiprocessor scheduling of precedence-constrained mixed-critical jobs. In IEEE ISORC 2015

Socci D, Poplavko P, Bensalem S, Bozga M (2015b) Time-triggered mixed-critical scheduler on single- and multi-processor platforms (revised version). Technical Report TR-2015-8, Verimag Research Report

Socci D, Poplavko P, Bensalem S, Bozga M(2015c) Time-triggered mixed-critical scheduler on single-and multi-processor platforms. In 17th IEEE international conference on high performance computing and communications (HPCC)

Vestal Steve (2007) Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In IEEE real-time systems symposium, RTSS’07, pp 239–243

Yip E, Kuo M, Roop PS, Broman D (2014) Relaxing the synchronous approach for mixed-criticality systems. In: 12th IEEE real-time and embedded technology and applications symposium (RTAS)

Titel: Priority-based scheduling of mixed-critical jobs
verfasst von: Dario Socci
Peter Poplavko
Saddek Bensalem
Marius Bozga
Publikationsdatum: 04.03.2019
Verlag: Springer US
Erschienen in: Real-Time Systems / Ausgabe 4/2019
Print ISSN: 0922-6443
Elektronische ISSN: 1573-1383
DOI: https://doi.org/10.1007/s11241-019-09329-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 4/2019

Thermal-aware task allocation and scheduling for periodic real-time applications in mesh-based heterogeneous NoCs

Practical task allocation for software fault-tolerance and its implementation in embedded automotive systems

Correction to: A compiler framework for the reduction of worst-case execution times

A real-time scratchpad-centric OS with predictable inter/intra-core communication for multi-core embedded systems

Cache-conscious off-line real-time scheduling for multi-core platforms: algorithms and implementation