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 (2013/2014)
- Classes: Mondays, 13h-16h, 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 11: Review of current research topics addressed by the real-time community
- Discrete grading
- Normal period
- Written exam (theoretical component): 40%
- Research work: 10% (5% by faculty, 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
Lab evaluation guidelines
- Written report
- Shall be delivered until January 9, 2015
- 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 four 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-1415-##.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. (1997).
Real-Time Systems Design Principles for Distributed Embedded Applications
Kluwer Academic Publishers.
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.
- Briand, L. and D.M. Roy (1999). Meeting Deadlines in Hard Real-Time Systems: the Rate-Monotonic Approach . IEEE Computer Society Press, Los Alamitos (CA), USA.
- Stankovic, J. et al. (1998). Deadline Scheduling for Real-Time Systems: EDF and Related Algorithms. Kluwer Academic Publishers.
- Krishna, C.M. and K. Shin (1997). Real-Time Systems. McGraw-Hill.
- 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.
- Motus, L. and M.G. Rodd (1994). Timing Analysis of Real-Time Software. IEEE Press.
- Klein, M. et al. (1993). A Practitioner’s Handbook for Real-Time Analysis: Guide to Rate-Monotonic Analysis for Real-Time Systems. Kluwer Academic Publishers.
Topics/themes for oral presentation:
- Bernard Cole, "Picking-the-right-RTOS-for-your-next-gen-embedded-IoT-design", http://www.embedded.com/, 20/Jul/2014
- P. Pedreiras et al,"A Real-Time Framework for the Vision Subsystem in Autonomous Mobile Robots", INTECH, Vision Systems Applications, DOI: 10.5772/4983
- Pau Marti et al, "Real-Time Scheduling Methods Requirements in Distributed Control Systems", WRTPD 2000
- Audsley, N. Tindell, K. and Burns, A. "The End Of The Line For Static Cyclic Scheduling?", In Proc. 5th Euromicro Workshop on Real-Time Systems, 1993
- OSEK/VDX Introduction
- Priority Inversion in the Real World: Mars Pathfinder
- The Posix 1003.13 profile for real-time applications
Base text: "Early experience with an implementation of the POSIX.13 minimal real-time
operating system for embedded applications", by Mario Aldea Rivas and Michael Gonzalez Harbour,
Universidad de Cantabria, Spain
- Padmanabhan Pillai and Kang G. Shin. "Real-Time Dynamic Voltage Scaling for Low-Power Embedded Operating Systems". Proceedings of the eighteenth ACM symposium on Operating systems principles (SOSP '01 )
- Giorgio Buttazzo and Giuseppe Lipari, "Ptask: an Educational C Library for Programming Real-Time Systems on Linux", Proceedings of the 18th IEEE Conference on Emerging Technologies and Factory Automation (ETFA 2013), Cagliari, Italy, September 10-13, 2013.(link)
Support materials for the lab component
- 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
- Xenomai 2.6 on Fedora 20 / VirtualBox image (username=passwd=adminuser)
- FreeRTOS Tutorial
- St1 - Ball in the plane with touch panel (x2)
- St2 - Mini Segway based on a "microrato" platform
- St3 - Inverted pendulum based on a "microrato" platform
- St4 - Interactive games and/or simulators with Xenomai (e.g. Brick, ...)
- St5 - Nunchuck I2C Interface for interactive game/platform
- Sp1 - Contiki Open-Source RTOS
- Sp2 - Control of a 2 axis plotter with FreeRTOS
- Sp3 - Schedulability Analysis Tool for Multi-Hop Ethernet Networks
Additional resources for the projects
- Sample projects for FreeRTOS/DETPIC32
- 5 wire resistive touch pannel info
- Servo info
- Interfacing the Wii Nunchuck info
Reminder: don't forget the log book
Additional indications for the presentation of the lab project and corresponding report
The presentations of the lab project will take place in the last lecture, and will be organized in blocks of 10 min per group. During this time, each group will make a brief presentation (about 5 min), followed by a demonstration. The presentation should have no more 4-5 slides containing: 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 January 9, 2015 and is limited to 4 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. Their structure should follow the points above referred to, for to presentation. 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!