This content is not included in
your SAE MOBILUS subscription, or you are not logged in.
Taxonomy of Automotive Real-Time Scheduling
Technical Paper
2016-01-0038
ISSN: 0148-7191, e-ISSN: 2688-3627
Annotation ability available
Sector:
Language:
English
Abstract
Automobiles are getting more and more sophisticated with increased demand for more comfort and safety by customers. Due to this, the automotive Electronic Control Units (ECU) and the software applications running on these ECUs have become more complex and computationally more intensive. This has resulted in Original Equipment Manufacturers (OEMs) migrating to multicore platforms. Optimal usage of multicore platform necessitates the design of new scheduling algorithms. In the past decade, different approaches to implement hard real time scheduling in automotive domain have been proposed for single core as well as multicore architectures. We explore different scheduling techniques proposed so far which are relevant to automotive domain and also, provide a taxonomy of these scheduling algorithms, which will help the automotive design engineer to make an informed decision. Through this study it is realized that, automotive standards such as AUTOSAR use manual scheduling, which consume lot of time to develop a schedule table and are inflexible. To address this issue, a new mathematical scheduling approach has been discussed as a case study. This systematic approach will not only reduce the time taken to develop a schedule table, it will also predict schedulability of a given set of tasks. The schedulability will be in terms of task overlaps and deadline misses which can be analyzed at design phase and is also more flexible by providing the users with multiple options based on earliest start time, least utilization and least task overlap criteria, along with the possibility of producing optimal results.
Recommended Content
Authors
Citation
Ranadive, P., Sengupta, S., Kumar, N., Boggarapu, N. et al., "Taxonomy of Automotive Real-Time Scheduling," SAE Technical Paper 2016-01-0038, 2016, https://doi.org/10.4271/2016-01-0038.Also In
References
- Grimm K. Software Technology in an Automotive Company - Major Challenges ICSE '03 Proceedings of the 25th International Conference on Software Engineering Portland, Oregon 2003
- Brown D. A. , Cooper G. , Gilvarry I. , Rajan A. , Tatourian A. , Venugopalan R. , Wheeler D. and Zhao M.
- Monot A. , Navet N. , Bavoux B. and Simonot-Lion F. Multisource Software on Multicore Automotive ECUs-Combining Runnable Sequencing With Task Scheduling 59 10 3934 3942 Oct 2012
- Gliwa P. , Harnish J. , Kelling U. and Ficek C. From Single-Core to Multi-Core Platforms-Systematic Migration of Hard Real-Time Software in AUTOSAR Embedded World 28 979 992 2011
- Davis R. I. and Burns A. A Survey of Hard Real-time Scheduling for Multiprocessor Systems 43 4 35 1 oct 2011
- Carpenter J. , Funk S. , Holman P. , Srinivasan A. , Anderson J. and Baruah S. A categorization of real-time multiprocessor scheduling problems and algorithms 30 1 2004
- Asberg M. , Behnam M. , Nemati F. and Nolte T. Towards Hierarchical Scheduling in AUTOSAR IEEE Press Piscataway, NJ, USA 2009
- Hanti T. , Ernst M. and Frey A. Higher Utilization of Multi-Core Processors in Dynamic Real-Time Software Systems 1 4 2013
- Grösbrink S. Adaptive virtual machine scheduling and migration for embedded real-time systems 2015
- Holenderski M. , Lukkien J. J. and Bril R. J. An efficient hierarchical scheduling framework for the automotive domain INTECH Open Access Publisher 2012
- Behnam M. , Shin I. , Nolte T. and Nolin M. SIRAP: a synchronization protocol for hierarchical resource sharingin real-time open systems Proceedings of the 7th ACM & IEEE international conference on Embedded software 2007
- Shin I. , Easwaran A. and Lee I. Hierarchical Scheduling Framework for Virtual Clustering of Multiprocessors Real-Time Systems, 2008. ECRTS '08. Euromicro Conference on 2008
- Ahmad I. , Ghafoor A. and Fox G. C. Hierarchical scheduling of dynamic parallel computations on hypercube multicomputers 20 3 317 329 1994
- Mishra G. , RamPrasad M. , Itagi A. and K.S G. An Efficient Hybrid Scheduler Using Dynamic Slack for Real-Time Critical Task Scheduling in Multicore Automotive ECUs
- Sere K. , Pop P. and Mäkitalo J. Reduced Certification Costs for Trusted Multi-core Platforms (RECOMP)
- Suresh B. , Subiramaniyam N. P. and Balamurugan A. A Study on Fixed Priority Scheduling Based RTOS in Automotive Domain 2 1 533 535 2014
- Tindell K. and Hansson H. Real time systems and fixed priority scheduling 95 1995
- Lehoczky J. , Sha L. and Ding Y. The rate monotonic scheduling algorithm: Exact characterization and average case behavior Real Time Systems Symposium, 1989., Proceedings 1989
- Liu C. L. and Layland J. W. Scheduling algorithms for multiprogramming in a hard-real-time environment 20 1 46 61 1973
- Buttazzo G. C. Rate monotonic vs. EDF: judgment day 29 1 5 26 2005
- Devi U. C. and Anderson J. H. Tardiness bounds under global EDF scheduling on a multiprocessor 38 2 133 189 2008
- Dertouzos M. L. Control Robotics: the Procedural Control of Physical Processes Information Processing 74 North-Holland Publishing Company 1974
- Pahwa J. Efficient Scheduling Algorithms based on Computational Grid
- Cervin A. Analyzing the effects of missed deadlines in control systems 17 26 2001
- Bertogna M. Real-time scheduling analysis for multiprocessor platforms 2008
- Dertouzos M. L. and Mok A. Ka-Lau Multiprocessor online scheduling of hard-real-time tasks 15 12 1497 1506 1989
- Cho H. , Ravindran B. and Jensen E. D. An optimal real-time scheduling algorithm for multiprocessors Real-Time Systems Symposium, 2006. RTSS’06. 27th IEEE International 2006
- Baid P. , Prashanth S. and Raveendran B. LLFRP: An Energy Efficient Variant of LLF with Reduced Pre-emptions for Real-Time Systems 3 4 2014
- Nahas M. Employing two sandwich delay mechanisms to enhance predictability of embedded systems which use time-triggered co-operative architectures 4 07 417 2011
- Anbarasi E. , Karthik N. and Prabakaran R. Analysis of time triggered schedulers in embedded system Electronics Computer Technology (ICECT), 2011 3rd International Conference on 2011
- Hughes Z. M. and Pont M. J. Reducing the impact of task overruns in resource-constrained embedded systems in which a time-triggered software architecture is employed 30 5 427 450 2008
- Davis R. I. and Kato S. FPSL, FPCL and FPZL schedulability analysis 48 6 750 788 2012
- Baruah S. K. , Cohen N. K. , Plaxton C. G. and Varvel D. A. Proportionate progress: A notion of fairness in resource allocation 15 6 600 625 1996
- Baruah S. K. , Gehrke J. E. and Plaxton C. G. Fast scheduling of periodic tasks on multiple resources Parallel Processing Symposium, 1995. Proceedings., 9th International Santa Barbara, CA 1995
- Anderson J. H. and Srinivasan A. Early-release fair scheduling Real-Time Systems 2000 Euromicro RTS 2000. 12th Euromicro Conference on Stockholm 2000
- Anderson J. and Srinivasan A. Pfair scheduling of sporadic tasks
- Anderson J. , Holman P. and Srinivasan A. Fair scheduling of real time tasks on multiprocessors 31 1 2004
- Srinivasan A. , Holman P. , Anderson J. H. and Baruah S. The case for fair multiprocessor scheduling Parallel and Distributed Processing Symposium, 2003. Proceedings. International 2003
- Aoun D. , Déplanche A.-M. and Trinquet Y. Pfair scheduling improvement to reduce interprocessor migrations 16th International Conference on Real-Time and Network Systems (RTNS 2008) 2008
- Deubzer M. , Mottok J. , Margull U. , Niemetz M. and Wirrer G. Efficient Scheduling of Reliable Automotive Multi-core Systems with PD2 by Weakening ERfair Task System Requirements 2010
- Sarkar A. , Ghose S. and Chakrabarti P. P. Sticky-ERfair: a task-processor affinity aware proportional fair scheduler 47 4 356 377 2011
- Anderson J. H. , Block A. and Srinivasan A. Quick-release fair scheduling Real-Time Systems Symposium, 2003. RTSS 2003. 24th IEEE 2003
- Block A. , Anderson J. H. and Bishop G. Fine-grained task reweighting on multiprocessors 429 435 2005
- Zhang W. , Bai E. , He H. and Cheng A. M. Solving Energy-Aware Real-Time Tasks Scheduling Problem with Shuffled Frog Leaping Algorithm on Heterogeneous Platforms 15 6 13778 13804 2015
- Anderson J. H. and Baruah S. K. Energy-aware Implementation of Hard-real-time Systems upon Multiprocessor Platforms 430 435 2003
- Dudani A. , Mueller F. and Zhu Y. Energy-conserving feedback EDF scheduling for embedded systems with real-time constraints 37 7 213 222 2002
- D. Li and Wu J. Energy-aware scheduling on multiprocessor platforms Springer Science & Business Media 2012
- Yang C.-Y. , Chen J.-J. , Kuo T.-W. and Thiele L. Energy reduction techniques for systems with non-dvs components 1 8 2009
- Zakarya M. and Uzma A. Power aware scheduling algorithm for real-time tasks over multi-processor 2013
- Ferguson R. O. and Sargent L. F. Linear programming McGraw-Hill 1958