Abstract
Automotive electrical/electronic (E/E) architectures are evolving towards a complex software intensive distributed system. However, current technology and practice in the automotive industry do not adequately address the increasing complexity of software, which hinders accomplishing reliable, maintainable, high-quality software within time and budget constraints. Although automotive open system architecture (AUTOSAR) addresses many software issues such as system software services, application interfaces, and communication middleware, it largely focuses on the implementation aspect without sufficiently addressing the design aspect. In this paper, we present a novel approach to guaranteeing end-to-end deadlines for AUTOSAR-based automotive systems in the early design stage. Our approach, we call zero slack priority assignment (ZSPA), decomposes end-to-end deadlines into local per-task deadlines and finds a feasible scheduling solution leveraging the Audsley’s optimal priority assignment algorithm. Our simulations show that ZSPA outperforms existing methods, heuristic optimized priority assignment (HOPA) (Garcia and Harbour, 1995) and the genetic algorithm (GA) (Azketa et al., 2011). Specifically, ZSPA shows up to 20% higher success rate in finding feasible solutions than HOPA and GA. The computational complexity of ZSPA is O(n2), whereas HOPA and GA have unbounded running time.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
Abbreviations
- τ :
-
task
- S :
-
a set of tasks
- C :
-
a set of task chains
- N :
-
a set of nodes
- R :
-
release time of task chain
- E :
-
worst-case execution time of task chain
- D :
-
end-to-end deadline of task chain
- T :
-
period and minimum inter-arrvial time of task chain
- e :
-
worst-case execution time of task
- d :
-
deadline of task
- o :
-
offset of task
- p :
-
priority level of task
- r :
-
response time of task
- b :
-
longest time of certain task’s critical section
- I :
-
interference time of task
- B :
-
blocking time of task
- δ :
-
slack of task
- l :
-
size of CAN bus message
- s :
-
bit time of CAN bus
References
Asberg, M., Behnam, M., Nemati, F. and Nolte, T. (2009). Towards hierarchical scheduling in AUTOSAR. Proc. Emerging Technologies and Factory Automation, 1–8.
Audsley, N. C. (1991). Optimal Priority Assignment and Feasibility of Static Priority Tasks with Arbitrary Start Times. Dept. Computer Science, University of York. Technical Report YCS 164.
Audsley, N. C., Bruns, A., Richardson, M. F. and Wellings, A. J. (1991). Hard real-time scheduling: The deadlinemonotonic approach. Proc. IEEE Workshop on Real-Time Operating Systems and Software, 133–137.
Azketa, E., Uribe, J. P., Marcos, M., Almeida, L. and Gutierrez, J. J. (2011). Permutational genetic algorithm for the optimized assignment of priorities to tasks and messages in distributed real-time systems. Proc. IEEE 10th Trust, Security and Privacy in Computing and Communications, 958–965.
Baker, T. P. (2003). Multiprocessor EDF and deadline monotonic schedulability analysis. Proc. IEEE 24 th Real-Time Systems Symp., 120–129.
Baker, T. P. (2005). Comparison of Empirical Success Rates of Global vs. Partitioned Fixed-Priority and EDF Scheduling for Hard Real Time. Technical Report. TR-050601.
Bettati, R. and Liu, J. W. S. (1992). End-to-end scheduling to meet deadlines in distributed systems. Proc. 12 th Distributed Computing Systems, 452–459.
Davis, R. I. and Burns, A. (2011). A survey of hard realtime scheduling for multiprocessor systems. ACM Comput. Surv. 43, 4, Article No. 35.
Garcia, J. J. G. and Harbour, M. G. (1995). Optimized priority assignment for tasks and messages in distributed hard real-time systems. Proc. 3 rd Workshop on Parallel and Distributed Real-Time Systems, 124–132.
George, L., Rivierre, N. and Spuri, M. (1996). Preemptive and Non-Preemptive Real-Time Uniprocessor Scheduling. INRIA Research Report, No. 2966.
Hou, E. S. H., Ansari, N. and Hong, R. (1994). A genetic algorithm for multiprocessor scheduling. IEEE Trans. Parallel and Distributed Systems 5, 2, 113–120.
Kao, B. and Garcia-Molina, H. (1997). Deadline assignment in a distributed soft real-time system. IEEE Trans. Parallel and Distributed Systems 8, 12, 1268–1274.
Kopetz, H. and Bauer, G. (2003). The time-triggered architecture. Proc. IEEE 91, 1, 112–126.
Lee, S. K. (1994). On-line multiprocessor scheduling algorithms for real-time tasks. Proc. IEEE Region 10’s 9 th Annual Int. Conf., 607–611.
Liu, C. L. and Layland, J. W. (1973). Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM 20, 1, 46–61.
Mitra, H. and Ramanathan, P. (1993). A genetic approach for scheduling non-preemptive tasks with precedence and deadline constraints. Proc. 26 th System Sciences, 2, 556–564.
Monnier, Y., Beauvais, J. P. and Deplanche, A. M. (1998). A genetic algorithm for scheduling tasks in a real-time distributed system. Proc. 24 th Euromicro Conf., 2, 708–714.
Ryu, M., Hong, S. and Saksena, M. (1997). Streamlining real-time controller design: from performance specifications to end-to-end timing constraints. Proc. IEEE Real-Time Technology and Applications Symp., 91–99.
Samii, S., Yanfei, Y., Zebo, P., Eles, P. and Yuanping, Z. (2009). Immune genetic algorithms for optimization of task priorities and flexRay frame identifiers. Proc. IEEE 15 th Embedded and Real-Time Computing Systems and Applications, 486–493.
Shin, M. and Sunwoo, M. (2007). Optimal period and priority assignment for a networked control system scheduled by a fixed priority scheduling system. Int. J. Automotive Technology 8, 1, 39–48.
Sun, J. and Liu, J. W. S. (1996). Bounding completion times of jobs with arbitrary release times and variable execution times. Proc. IEEE 17 th Real-Time Systems Symp., 2–12.
Tindell, K. W., Burns, A. and Wellings, A. J. (1992). Allocating hard real-time tasks: An NP-hard problem made easy. J. Real-Time Systems 4, 2, 145–165.
Tindell, K. and Burns, A. (1994). Guaranteed Message Latencies for Distributed Safety-critical Hard Real-time Control Networks. Department of Computer Science. University of York. York.
Tindell, K. W. and Clark, J. (1994). Holistic schedulability analysis for distributed hard real-time systems. J. Microprocessing and Microporgramming — Parallel Processing in Embedded Real-time Systems 40, 2–3, 117–134.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Yoon, H., Ryu, M. Guaranteeing end-to-end deadlines for AUTOSAR-based automotive software. Int.J Automot. Technol. 16, 635–644 (2015). https://doi.org/10.1007/s12239-015-0065-7
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12239-015-0065-7