This content is not included in your SAE MOBILUS subscription, or you are not logged in.
Taxonomy of Automotive Real-Time Scheduling
ISSN: 0148-7191, e-ISSN: 2688-3627
Published April 05, 2016 by SAE International in United States
Annotation ability available
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.
|Technical Paper||Utilizing Value Engineering as a Problem-Solving Management Tool|
|Aerospace Standard||Safety Assessment of Transport Airplanes in Commercial Service|
CitationRanadive, 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.
- Grimm K., "Software Technology in an Automotive Company - Major Challenges," in 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., mcafee.
- Monot A., Navet N., Bavoux B. and Simonot-Lion F., "Multisource Software on Multicore Automotive ECUs-Combining Runnable Sequencing With Task Scheduling," vol. 59, no. 10, pp. 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, vol. 28, pp. 979--992, 2011.
- Davis R. I. and Burns A., "A Survey of Hard Real-time Scheduling for Multiprocessor Systems," vol. 43, no. 4, pp. 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," pp. 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," vol. 1, no. 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," in 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," in 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," vol. 20, no. 3, pp. 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," vol. 2, no. 1, pp. 533-535, 2014.
- Tindell K. and Hansson H., "Real time systems and fixed priority scheduling," vol. 95, 1995.
- Lehoczky J., Sha L. and Ding Y., "The rate monotonic scheduling algorithm: Exact characterization and average case behavior," in Real Time Systems Symposium, 1989., Proceedings., 1989.
- Liu C. L. and Layland J. W., "Scheduling algorithms for multiprogramming in a hard-real-time environment," vol. 20, no. 1, pp. 46-61, 1973.
- Buttazzo G. C., "Rate monotonic vs. EDF: judgment day," vol. 29, no. 1, pp. 5-26, 2005.
- Devi U. C. and Anderson J. H., "Tardiness bounds under global EDF scheduling on a multiprocessor," vol. 38, no. 2, pp. 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," pp. 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," vol. 15, no. 12, pp. 1497-1506, 1989.
- Cho H., Ravindran B. and Jensen E. D., "An optimal real-time scheduling algorithm for multiprocessors," in 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," vol. 3, no. 4, 2014.
- Nahas M. and others, "Employing two sandwich delay mechanisms to enhance predictability of embedded systems which use time-triggered co-operative architectures," vol. 4, no. 07, p. 417, 2011.
- Anbarasi E., Karthik N. and Prabakaran R., "Analysis of time triggered schedulers in embedded system," in 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," vol. 30, no. 5, pp. 427-450, 2008.
- Davis R. I. and Kato S., "FPSL, FPCL and FPZL schedulability analysis," vol. 48, no. 6, pp. 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," vol. 15, no. 6, pp. 600-625, 1996.
- Baruah S. K., Gehrke J. E. and Plaxton C. G., "Fast scheduling of periodic tasks on multiple resources," in Parallel Processing Symposium, 1995. Proceedings., 9th International , Santa Barbara, CA , 1995.
- Anderson J. H. and Srinivasan A., "Early-release fair scheduling," in 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," pp. 31-1, 2004.
- Srinivasan A., Holman P., Anderson J. H. and Baruah S., "The case for fair multiprocessor scheduling," in 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," in 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," vol. 47, no. 4, pp. 356-377, 2011.
- Anderson J. H., Block A. and Srinivasan A., "Quick-release fair scheduling," in Real-Time Systems Symposium, 2003. RTSS 2003. 24th IEEE, 2003.
- Block A., Anderson J. H. and Bishop G., "Fine-grained task reweighting on multiprocessors," pp. 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," vol. 15, no. 6, pp. 13778-13804, 2015.
- Anderson J. H. and Baruah S. K., "Energy-aware Implementation of Hard-real-time Systems upon Multiprocessor Platforms.," pp. 430-435, 2003.
- Dudani A., Mueller F. and Zhu Y., "Energy-conserving feedback EDF scheduling for embedded systems with real-time constraints," vol. 37, no. 7, pp. 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," pp. 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.