[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

Priority-based scheduling of mixed-critical jobs

  • Published:
Real-Time Systems Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20
Fig. 21
Fig. 22
Fig. 23
Fig. 24
Fig. 25
Fig. 26
Fig. 27
Fig. 28
Fig. 29

Similar content being viewed by others

Notes

  1. 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.

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

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

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

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

  6. 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.

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

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

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

References

  • 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–784

    Article  Google Scholar 

  • 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–1152

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    MATH  Google Scholar 

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

    Article  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  • 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–471

    Article  Google Scholar 

  • 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

    Google Scholar 

  • 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)

Download references

Acknowledgements

We would like to thank Prof. Sanjoy Baruah for valuable discussions, especially for a hypothesis that lead to establishing improved algorithmic complexity result for MCEDF. We would also like to thank the reviewers for providing very constructive remarks that helped us to correct some important errors and improve the quality.

Author information

Authors and Affiliations

  1. Mentor® A Siemens Business, 38334, Inovallée Montbonnot, France

    Dario Socci & Peter Poplavko

  2. Université Grenoble Alpes (UGA), VERIMAG, 38000, Grenoble, France

    Saddek Bensalem

  3. Centre National de la Recherche Scientifique (CNRS), VERIMAG, 38000, Grenoble, France

    Marius Bozga

Authors
  1. Dario Socci
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Peter Poplavko
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Saddek Bensalem
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Marius Bozga
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Peter Poplavko.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Research supported by the European ICT Project Nos. 288175 (CERTAINTY) and 332987 (ARROWHEAD).

The presented research was done when the first two authors worked at UGA/VERIMAG.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Socci, D., Poplavko, P., Bensalem, S. et al. Priority-based scheduling of mixed-critical jobs. Real-Time Syst 55, 709–773 (2019). https://doi.org/10.1007/s11241-019-09329-9

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11241-019-09329-9

Keywords