Fundamentals of Real-time Systems (3 ECTS)

Line of teaching

The purpose of this course is to provide a large overview of fundamental aspects of real-time system architectures and development. This covers scheduling techniques, scheduling analysis including WCET evaluation, design principles of distributed real-time embedded systems, programming distributed real-time applications. Fault tolerance aspects are also addressed, in particular regarding timing faults handling. Examples of real time executive layers are also presented.

The Introduction addresses basic concepts concerning real-time applications, real-time environment, and basic notions for real-time task scheduling. Although we assume that students have some basic knowledge and practice in operating systems, a reminder of operating system features should be done, leading the students to acquire basic notions of real-time kernels and microkernels, basic services such as tasks scheduling, resource management, synchronisation, etc.

The Scheduling in real-time systems is the first major chapter of the course. Several very good textbooks are available and cover all aspects of real-time scheduling, like Giorgio Buttazzo’s book [Buttazzo 2005], but also [Cottet et al. 2002]. The sections of this chapter address the principles and the algorithms for aperiodic and periodic task scheduling, fixed-priority and dynamic priority approaches. This section includes the scheduling of independent tasks but also dependent tasks. Problems related to synchronisation and scheduling, i.e. tasks precedence relationship and tasks sharing critical resources, are part of this section together with solutions (e.g. PIP, PCP).

The WCET analysis (Worst Case Execution Time analysis) is a major issue to set up an important parameter of schedulability tests. Material can be found in particular in a Special Issue on worst-case execution-time analysis of the Real-Time System journal (May 2000) [RTS 2000]. Beyond the introduction and the objective of WCET evaluation, the chapter must cover both dynamic WCET analysis (including measures, explicit test cases, symbolic state space exploration) but also static WCET analysis (notion of basic blocks, control-flow graphs and call graphs, program flow analysis) [Colin et al. 2003]. Due to the complexity of today’s processor, low-level analysis must be addressed, i.e. caching effects, branch prediction [Colin & Puaut 2000], etc. Examples of measures and tools have to be presented.

The Design Principles for real-time application, in particular distributed embedded applications are discussed in this chapter and based on Kopetz’s book [Kopetz 1997]. Clearly real-time systems are distributed (notion of real-time distributed environment). The notion of global time is thus a major issue to be addressed before all in this course. The subsection of this chapter should include modelling of real-time systems and then address fault tolerance issues. Another important part of this chapter concerns real-time communication and networks. Among other examples, the time-triggered protocols and architecture can be presented.

Programming distributed real-time systems is clearly a major part of the course that certainly leads to practical classes and student projects. This chapter can usefully be based on several books from Alan Burns and Andy Wellings, e.g.[Burns & Wellings 2001, Wellings 2004]. Beyond, the requirements for programming real-time systems, the chapter addresses first of all concurrent programming. It also covers real-time facilities and deadline scheduling, facilities for interacting with special purpose hardware. Last but not least, it also addresses error-handling facilities in programming languages, and more generally reliability of real-time systems, including fault-tolerance, atomic actions, etc. In practice, illustration can be provided with Real-Time POSIX systems and Real-Time Java.

Finally, Real time executive layers must be presented and to some extent used for practical classes and exercises. The students will discover major examples of real-time operating systems and kernels (like RT-LINUX, VxWorks, LynxOS, QNX, etc.), but also real-time middleware (like RT Java, RT-CORBA). Some short overview of open adaptive real-time executives should be addressed, i.e. ExoKernel, Think, 2K, etc.

Text books:

[Silberschatz 2008] A. Silberschatz, P. Baer Galvin, G. Gagne: Operating Systems Concepts, John Wiley & Sons, 2008, ISBN 0-470-12872-0.

[Buttazzo 2005] G. Buttazzo: Measuring the Performance of Schedulability Tests, Journal of Real-Time Systems, Springer Netherlands, Volume 30, N° 1-2, May, 2005 Pages 129-154.

[Kopetz 1997] H. Kopetz: Real-Time Systems: Design Principles for Distributed Embedded Applications, Series: The Springer International Series in Engineering and Computer Science, Vol. 395, 1997, 356 p., ISBN: 978-0-7923-9894-3.

[Burns & Wellings 2001] Alan Burns and Andy Wellings: Real-Time Systems and Programming Languages (Third Edition): Ada 95, Real-Time Java and Real-Time POSIX, Addison Wesley, March 2001, 611 p., ISBN: 0201729881.

[Wellings 2004] Andrew Wellings: Concurrent and Real-Time Programming in Java, John Wiley & Sons Inc., October 2004, 431 p., ISBN-13: 9780470844373.

Papers:

[Colin & Puaut 2000] A. Colin, I. Puaut. Worst Case Execution Time Analysis for a Processor with Branch Prediction. Real-Time Systems, Special issue on worst-case execution time analysis, 18(2): 249-274, April 2000.

[Colin et al 2003] A. Colin, I. Puaut, C. Rochange, P. Sainrat. Calcul de majorants de pire temps d'exécution: état de l'art. Techniques et Sciences Informatiques (TSI), 22(5): 651-677, 2003.

[RTS 2000] Special issue on worst-case execution-time analysis, Real-Time Systems, Volume 18, Issue 2-3 (May 2000), ISSN:0922-6443, Editors John A. Stankovic (Univ. of Virginia, Charlottesville, USA), Wolfgang A. Halang (FernUniv. Hagen, Germany), Kim-Fung Man (City Univ. of Hong Kong, Hong Kong), Peter Puschner (Technische Univ. Wien, Vienna, Austria) and Alan Burns (Univ. of York, York, U.K.)

Links:

Links to places where parts of this course are taught:


Exercises (right click and select "Save as" to download)


Back to course content.