Real-Time Systems (#41475)
University of Aveiro
Optional course of the 5th year of:
- Integrated Masters in Electronics and Telecommunications Engineering;
- Integrated Masters in Computer Engineering and Telematics;
- Masters in Industrial Automation Engineering.
Table of contents
- Motivation, objectives and structure
- Topics, planning and slides of the theoretical component
- Lab component grading
- Research topics to discuss in the classes
- Lab component support materials
- Rules and guidelines for the report and presentation
- STR in previous years (2015/2016)
- Classes: Mondays, 16h-19h, room 4.3.20
- Support: Wednesdays, 17H00-18H00, IT-Bulding 1
Motivation, objectives and structure
Real-time systems play a crucial role in modern societies, supporting application areas such as control of nuclear facilities, chemistry industries, avionic systems, automotive systems (engine control ABS, ESP, ...), air, sea and railway traffic control, telecommunication systems, industrial automation, robotics, military and space exploration systems, consumer electronics and countless others.
Although the range of applications is vast and many of them have safety-critical constraints, the approaches typically used in the development of real-time systems are based on empirical techniques and low-level programming, without the support of a scientifically strong methodology. The consequence of this fact is a lower reliability, which in critical applications can cause serious damage to equipment, environment and even jeopardize human lives.
On the other hand, the recent diffusion of interactive applications such as virtual reality systems or multimedia systems, extend substantially the range of applicability of real-time systems. Tough these applications are not critical in terms of safety, compliance with their temporal constraints has a direct impact on their performance.
This proliferation of applications with time constraints has significantly increased interest in operating systems for real-time. For example, today it is common to find references to systems such as Real-Time Linux or to real-time services of general-purpose Operative Systems, like Linux and Windows.
This course focuses on four key aspects:
- the origin and characterization of the restrictions imposed by the environment on the temporal behavior of the computer system;
- how the computational system maintain knowledge of the state of the environment that surrounds it;
- scheduling theory of real-time tasks/processes;
- and the study of the internal structure of real-time operating/executive systems.
The course is structured in two components, theoretical and practical. The first is essentially expository, but using practical examples and discussions. The second makes use of various real-time operating and/or executive systems (e.g. Xenomai, FreeRTOS, Shark, VxWorks, ReTMiK) and a set of platforms for embedded systems (based on PIC18, PIC32 and ARM microprocessors), consisting first of a series of essentially tutorial work, followed by the development of a small project.
Topics, planning and slides of the theoretical component
- Class 0: Course overview. General rules. (slides/pdf)
Class 1: Temporal restrictions: source and characterization
- 1.1- The concept of real-time and the source of the real-time constraints
- 1.2- Characterization of the real-time constraints
- 1.3- Constraints of real-time systems
Class 2: Computational models
- 2.1- Task models with explicit temporal constraints
- 2.2- Implementation issues
- 2.3- Logic vs temporal control
- 2.4- Characterization of the Event Triggered (ET) and Time Triggered (TT) paradigms
Class 3: Real-time executives
- 3.1- Task states
- 3.2- Generic architecture of a real-time kernel
- 3.3- Common structures and functions found in real-time kernels
Class 4: Scheduling basics
- 4.1- Task scheduling - basic taxonomy
- 4.2- Some basic scheduling methods
- 4.3- Static Cyclic Scheduling
Class 5: Periodic task scheduling I
- 5.1- Fixed priority scheduling (RM, DM, etc.)
- 5.2- Utilization and response-time based schedulability analysis
Class 6: Periodic task scheduling II
- 6.1- Dynamic priority scheduling (EDF, LSF, etc.)
- 6.2- Utilization and processor-demand schedulibility analysis
- 6.3- Comparison between fixed and dynamic scheduling algorithms
Class 7: Shared resources
- 7.1- The priority inversion issue
- 7.2- Priority Inheritance Protocol
- 7.3- Priority-Ceiling Protocol
- 7.4- Stack Resource Protocol
Class 8: Aperiodic tasks
- 8.1- Fixed priority servers
- 8.2- Dynamic priority servers
Class 9: Other aspects of real-time scheduling
- 9.1- Non-preemptive scheduling
- 9.2- Implementation issues
Class 10: Optimizations
(Sample code (sample.c))
- 10.1 - Code optimization techniques
- 10.1 - Profiling
- 10.1 - Tools
- Discrete grading
- Normal period
- Written exam (theoretical component): 40%
- Research work: 10% (5% teacher, 5% by pears)
- Lab project: 40% (project+report: 25%; log book: 5%; oral presentation: 10%)
- Tutorial's complementary works: 10%
- Sample exams:
- Theoretical component (exam): 40%
- Lab component: inherited from the normal period or practical exam
- Written report
- Shall be delivered no latter than one week before the exam
- Its format must conform to the following: cover sheet with the identification of the course, teacher, school year, work and authors; Text body up to ten pages; text in a single column, single-spaced, font size 11 or 12 TimesNewRoman, lateral margins of 2.5 cm; indication of the page number in the footer.
- Technical annexes may be added when required (e.g. schematics, installation issues, etc.)
- Materials to deliver: together with the printed version of the report, students shall deliver a zip file containing: presentation slides and report (pdf format); source code (executable project with instructions); annexes (schematics, etc.). This file is sent by email, and will be named "STR-1617-##.zip", where "##" should be replaced by the group number. The subject of the message should also mention "STR" and the group number.
Giorgio Buttazzo (2011).
HARD REAL-TIME COMPUTING SYSTEMS: Predictable Scheduling Algorithms and Applications
Third Edition, Springer, 2011.
Kopetz, H. (2011).
Real-Time Systems: Design Principles for Distributed Embedded Applications (Real-Time Systems Series), 2nd Edition
Springer, 2011 (ISBN 978-1-4419-8236-0).
Xiaocong Fan (2015).
Real-Time Embedded Systems: Design Principles and Engineering Practices, 1st Edition
Springer, 2015 (ISBN-13: 978-0128015070).
Richard Barry (2011).
Using the FreeRTOS Real-Time Kernel – A practical guide
Real-Time Engineers, Ltd., 2011.
Doug Abbott (2006).
Linux for Embedded and Real-time Applications
Second Edition. Newnes, 2006;
- Veríssimo, P. and L. Rodrigues (2001). Distributed Systems for System Architects. Kluwer Academic Publishers.
- Liu, J.W.S. (2000). Real-Time Systems. Prentice Hall.
- Stankovic, J. et al. (1998). Deadline Scheduling for Real-Time Systems: EDF and Related Algorithms. Kluwer Academic Publishers.
- Laplante, P.A. (1997). Real-Time Systems Design and Analysis - An Engineer’s Handbook (2nd ed.). IEEE Press.
- Nissanke, N. (1997). Real-Time Systems. Prentice Hall.
- Welling, A. and A. Burns (1996). Real-Time Systems and Their Programming Languages (2nd ed.). Int. Computer Science Series, Addison-Wesley.
Topics/themes for oral presentation:
- Misconceptions About Real-Time Computing: A Serious Problem for Next-Generation Systems
- Scheduling anomalies
(paper analysis + bibliographic research)
- Priority Scheduling versus Pre-run-time Scheduling
(paper analysis + bibliographic research)
- PikeOS e ElinOS
- Contiki RTOS
- RIOT - RTOS
(Real-Time network presentation)
- EtherCAT and EthernetPowerlink
(Real-Time network presentation)
- Real-Time services on Linux
- Xenomai Tutorial
- Class guide
- Sample code (xenomai 2.6)
- Short Introduction to Xenomai (slides)
- Install guide - Xenomai 2.6 on Ubunto 12.04
- Install guide - Xenomai 2.6 on Linux Mint 15 (by Gonçalo Pardal)
- Install log - Xenomai 2.6 on Fedora 20 / VirtualBox
- Install Xenomai 2.6.4 on Mint 17.2 (by Cláudio Patrício)
- FreeRTOS Tutorial
- Electrostatic sensor for medical applications
- Mini Segway based on a "microrato" platform
- Ball in the plane with touch panel (x2)
- Inverted pendulum based on a "microrato" platform
- Interactive games and/or simulators with Xenomai (e.g. Brick, ...)
- Inercial sensor (ADXL335) interface demo
Support materials for the lab component
Additional resources for the projects
Reminder: don't forget the log book
The presentations of the lab project will take place in the last lecture, and will be organized in blocks of 15 min per group. During this time, each group will make a brief presentation (about 10 min), followed by a demonstration. A reference presentation is composed by 5-7 slides addressing the following topics: 1-goal/problem, 2-specific aspects (e.g. dynamics of the process, technical control), 3-approach (e.g. organization, task types, periods), 4-results, 5-status.
The report shall be delivered until one week before the exam and is limited to 10 pages, excluding any technical annexes. Its format must conform to the following: cover sheet with the identification of the course, the teacher, school year, work and authors. Text mus be formatted in a single column, single-spaced, font size 11 or 12 TimesNewRoman, margins side 2.5cm and the page number at the footer. The report structure shall follow the presentation one, presented above. The purpose of the report is to explain the approach used in the proposed resolution of the problem and the results obtained. It will also be the place for highlighting the details considered relevant and that might have been overlooked in the presentation.
In case the work was not completed on the date of the presentation, this should be mentioned in the current status. A new presentation may be delivered closer to the filing date of the report.
As promised (see grading rules), there will be an evaluation of the log book!