Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Controller Area Network (CAN) schedulability analysis: Refuted, revisited and revised
| |
 |
Controller Area Network (CAN) schedulability analysis: Refuted, revisited and revised
Robert I. Davis1  , Alan Burns1 , Reinder J. Bril2 and Johan J. Lukkien2
| (1) |
Real-Time Systems Research Group, Department of Computer Science, University of York, YO10 5DD York, UK |
| (2) |
Technische Universiteit Eindhoven (TU/e), Den Dolech 2, 5600 AZ Eindhoven, The Netherlands |
Received: 5 September 2006 Accepted: 2 January 2007 Published online: 30 January 2007
Abstract Controller Area Network (CAN) is used extensively in automotive applications, with in excess of 400 million CAN enabled microcontrollers
manufactured each year. In 1994 schedulability analysis was developed for CAN, showing how worst-case response times of CAN
messages could be calculated and hence guarantees provided that message response times would not exceed their deadlines. This
seminal research has been cited in over 200 subsequent papers and transferred to industry in the form of commercial CAN schedulability
analysis tools. These tools have been used by a large number of major automotive manufacturers in the design of in-vehicle
networks for a wide range of cars, millions of which have been manufactured during the last decade.
This paper shows that the original schedulability analysis given for CAN messages is flawed. It may provide guarantees for
messages that will in fact miss their deadlines in the worst-case. This paper provides revised analysis resolving the problems
with the original approach. Further, it highlights that the priority assignment policy, previously claimed to be optimal for
CAN, is not in fact optimal and cites a method of obtaining an optimal priority ordering that is applicable to CAN. The paper
discusses the possible impact on commercial CAN systems designed and developed using flawed schedulability analysis and makes
recommendations for the revision of CAN schedulability analysis tools.
Keywords Controller Area Network (CAN) - Fixed priority scheduling - Non-pre-emptive scheduling - Schedulability analysis - Response time analysis - Priority assignment policies
Robert I. Davis received a DPhil in Computer Science from the University of York in 1995. Since then he has founded three start-up companies,
all of which have succeeded in transferring real-time systems research into commercial product. At Northern Real-Time Technologies
Ltd. (1995–1997) he was responsible for development of the Volcano CAN software library. At LiveDevices Ltd. (1997–2001) he
was responsible for development of the Real-Time Architect suite of products, including an OSEK RTOS and schedulability analysis
tools. In 2002, Robert returned to the University of York, and in 2004 he was involved in setting up a spin out company, Rapita
Systems Ltd., aimed at transferring worst-case execution time analysis technology into industry. Robert is a member of the
Real-Time Systems Research Group at the University of York, and a director of Rapita Systems Ltd. His research interests include
scheduling algorithms and schedulability analysis for real-time systems.
Alan Burns is head of the Real-Time Systems Research Group at the University of York. His research interests cover a number of aspects
of real-time systems including the assessment of languages for use in the real-time domain, distributed operating systems,
the formal specification of scheduling algorithms and implementation strategies, and the design of dependable user interfaces
to real-time applications. He has authored/co-authored over 370 papers and 10 books, with a large proportion of them concentrating
on real-time systems and the Ada programming language. Professor Burns has been actively involved in the creation of the Ravenscar
Profile, a subset of Ada”s tasking model, designed to enable the analysis of real-time programs and their timing properties.
Reinder J. Bril received a B.Sc. and an M.Sc. (both with honours) from the University of Twente, and a Ph.D. from the Technische Universiteit
Eindhoven, the Netherlands. He started his professional career in January 1984 at the Delft University of Technology. From
May 1985 until August 2004, he was with Philips, and worked in both Philips Research as well as Philips’ Business Units. He
worked on various topics, including fault tolerance, formal specifications, software architecture analysis, and dynamic resource
management, and in different application domains, e.g. high-volume electronics consumer products and (low volume) professional
systems. In September 2004, he made a transfer back to the academic world, to the System Architecture and Networking (SAN)
group of the Mathematics and Computer Science department of the Technische Universiteit Eindhoven. His main research interests
are currently in the area of reservation-based resource management for networked embedded systems with real-time constraints.
Johan J. Lukkien has been head of the System Architecture and Networking Research group at Eindhoven University of Technology since 2002.
He received an M.Sc. and a Ph.D. from Groningen University in the Netherlands. In 1991, he joined Eindhoven University, after
two years leave at the California Institute of Technology. His research interests include the design and performance analysis
of parallel and distributed systems. Until 2000 he was involved in large-scale simulations in physics and chemistry. Since
2000, his research focus has shifted to the application domain of networked resource-constrained embedded systems. Contributions
of the SAN group are in the area of component-based middleware for resource-constrained devices, distributed co-ordination,
Quality of Service in networked systems and schedulability analysis in real-time systems.
+schedulability+analysis%3a+Refuted%2c+revisited+and+revised;msizes=468x60;bso=listed)
References
| Audsley NC (1991) Optimal priority assignment and feasibility of static priority tasks with arbitrary start times. Technical
Report YCS 164, Dept. Computer Science, University of York, UK
|
| |
| Bosch (1991) CAN Specification version 2.0. Robert Bosch GmbH, Postfach 30 02 40, D-70442 Stuttgart
|
| |
| Bril RJ (2006) Existing worst-case response time analysis of real-time tasks under fixed-priority scheduling with deferred
pre-emption is too optimistic. CS-Report 06-05, Technische Universiteit Eindhoven (TU/e), The Netherlands
|
| |
| Bril RJ (2006) Existing worst-case response time analysis of real-time tasks under fixed-priority scheduling with deferred
pre-emption is too optimistic. CS-Report 06-05, Technische Universiteit Eindhoven (TU/e), The Netherlands
|
| |
| Bril RJ, Lukkien JJ, Davis RI, and Burns A (2006a) Message response time analysis for ideal Controller Area Network (CAN)
refuted. CS-Report 06-19, Technische Universiteit Eindhoven (TU/e), The Netherlands.
|
| |
| Bril RJ, Lukkien JJ, Davis RI, Burns A (2006b) Message response time analysis for ideal Controller Area Network (CAN) refuted.
In: Proceedings of the 5th International Workshop on Real-Time Networks (RTN’06)
|
| |
| Bril RJ, Lukkien JJ, Verhaegh WFJ (2006c) Worst-case response time analysis of real-time tasks under fixed priority scheduling
with deferred preemption revisited. CS Report 06-34, Technische Universiteit Eindhoven (TU/e), The Netherlands
|
| |
| Broster I (2003) Flexibility in dependable communication. PhD Thesis, Department of Computer Science, University of York,
UK
|
| |
| Broster I, Burns A, Rodríguez-Navas G (2002) Probabilistic analysis of CAN with Faults. In: Proceedings of the 23rd IEEE real-time
systems symposium (RTSS’02), pp 269–278
|
| |
| Broster I, Burns A (2003) An analysable bus-guardian for event-triggered communication. In: Proceedings of the 24th real-time
systems symposium. IEEE Computer Society Press, pp 410–419
|
| |
Broster I, Burns A, Rodriguez-Navas G (2005) Timing analysis of real-time communication under electromagnetic interference.
Real-Time Systems 30(1–2):55–81
|
| |
| Burns A (1994) Pre-emptive priority based scheduling: An appropriate engineering approach. In: S. Son (ed), Advances in Real-Time
Systems, Prentice-Hall, pp 225–248
|
| |
| Casparsson L, Rajnak A, Tindell K, Malmberg P (1998/1) Volcano—a revolution in on-board communications. Volvo Technology Report
|
| |
| DeMeis R (2005) Cars sag under weighty wiring. Electronic Times, 10/24/2005
|
| |
| Ferreira J, Oliveira A, Fonseca P, Fonseca JA (2004) An experiment to assess bit error rate in CAN. In: Proceedings of 3rd
international workshop of real-time networks (RTN2004). Cantania, Italy, pp 15–18
|
| |
| Frischkorn H-G (2005) Automotive architecture requirements. In: Proceedings of the summer school on architectural paradigms
for dependable embedded systems. Vienna, Austria,. Vienna University of Technology, pp 45–74
|
| |
| George L, Rivierre N, Spuri M (1996) Pre-emptive and non-pre-emptive real-time uni-processor scheduling. Technical Report
2966, Institut National de Recherche et Informatique et en Automatique (INRIA), France
|
| |
| Hansson H, Nolte T, Norstrom C, Punnekkat S (2002) Integrating reliability and timing analysis of CAN-based Systems. IEEE
Transactions on Industrial Electronics 49(6):1240–1250
|
| |
| Harbour MG, Klein MH, Lehoczky JP (1991) Fixed priority scheduling of periodic tasks with varying execution priority. In:
Proceedings 12th IEEE real-time systems symposium. IEEE Computer Society Press, pp 116–128
|
| |
| Horvath I (2006) Private communication with the authors
|
| |
| ISO 11898-1 (1993) Road Vehicles—interchange of digital information—controller area network (CAN) for high-speed communication.
ISO Standard-11898, International Standards Organisation (ISO)
|
| |
| Lehoczky J (1990) Fixed priority scheduling of periodic task sets with arbitrary deadlines. In: Proceedings 11th IEEE real-time
systems symposium. IEEE Computer Society Press, pp 201–209
|
| |
| Leohold J (2004) Communication requirements for automotive systems. Keynote speech 5th IEEE international workshop on factory
communication systems, Vienna, Austria, Vienna University of Technology
|
| |
| Leohold J (2005) Automotive system architecture. In: Proceedings of the summer school on architectural paradigms for dependable
embedded systems. Vienna, Austria, Vienna University of Technology, pp 545–591
|
| |
Leung JY-T, Whitehead J (1982) On the complexity of fixed-priority scheduling of periodic real-time tasks. Performance Evaluation
2(4):237–250
|
| |
| LIN Consortium (2003) LIN Protocol Specification, Revision 2.0. September. www.lin-subbus.org
|
| |
Liu CL, Layland JW (1973) Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM 20(1):46–61
|
| |
| Motorola Inc (1998) MSCAN Block Guide V03.01 Document No. SV12MSCANV3/D. FreeScale Semiconductor Inc. (Revised July 2004)
|
| |
| Nolte T, Hansson H, Norstrom C (2002) Minimizing CAN response-time analysis jitter by message manipulation. In: Proceedings
8th IEEE real-time and embedded technology and applications symposium (RTAS’02), pp 197–206
|
| |
| Nolte T, Hansson H, Norstrom C (2003) Probabilistic worst-case response-time analysis for the Controller Area Network. In:
Proceedings of the 9th IEEE real-time and embedded technology and applications symposium (RTAS’03), pp 200–207
|
| |
| Nolte T (2006) Share-driven scheduling of embedded networks. PhD Thesis, Malardalen University Press
|
| |
| Oswald M (2004) Efficient automotive electronics. Automotive Engineer
|
| |
| Punnekkat S, Hansson H, Norstrom C (2000) Response time analysis under errors for CAN. In: Proceedings 6th real-time technology
and applications symposium. IEEE Computer Society Press, pp 258–265
|
| |
| Regehr J (2002) Scheduling tasks with mixed pre-emption relations for robustness to timing faults. In: Proceedings 23rd real-time
systems symposium. IEEE Computer Society Press, pp 315–326
|
| |
| Rufino J, Verissimo P, Arroz G, Almeida C Rodrigues L (1998) Fault-tolerant broadcasts in CAN. In Digest of Papers, The 28th
IEEE international symposium on fault-tolerant computing (FTCS’98), pp 150–159
|
| |
| Rufino J (2002) Computational system for real-time distributed control. PhD-Thesis, Technical University of Lisbon, Instituto
Superior
|
| |
| Society of Automotive Engineers (1993) Class C application requirement considerations, recommended practice, SAE Technical
Report J2056/1
|
| |
| Tindell KW, Burns A (1994) Guaranteeing message latencies on Controller Area Network (CAN). In: Proceedings of 1st international
CAN conference, pp 1–11
|
| |
| Tindell KW, Burns A, Wellings AJ (1994a) An extendible approach for analysing fixed priority hard real-time systems. Journal
of Real-Time Systems 6(2):133–152
|
| |
| Tindell KW, Hansson H, Wellings AJ (1994b) Analysing real-time communications: Controller area network (CAN). In: Proceedings
15th real-time systems symposium (RTSS’94). IEEE Computer Society Press, pp 259–263
|
| |
Tindell KW, Burns A, Wellings AJ (1995) Calculating Controller area network (CAN) message response times. Control Engineering
Practice 3(8):1163–1169
|
| |
| Wang Y, Saksena M (1999) Scheduling fixed priority tasks with pre-emption threshold. In: Proceedings of the 6th international
workshop on real-time computing systems and applications (RTCSA’99), pp 328–335
|
| |
| Zuhily A (2006) Optimality of (D-J)-monotonic priority assignment. Technical Report YCS404. Dept. of Computer Science, University
of York, UK
|
| |
|
|
|
|
|
|