Real-Time Architectures (2IN20) spring 2006

 

Last update: September 13st, 2006.

 

Examinations

 

The examinations (including draft answers) of previous years:

The examination (including draft answers) of this year:

 

Introduction

 

This course is organized around the issue of real-time requirements and their impact on the hardware-software architecture of a system. This includes:

·         examples of applications with real-time requirements;

·         the techniques used to enforce real-time properties in a verifiable manner (e.g., real-time scheduling, Quality of Service management);

·         examples of particular problems and solutions.

The considered system domain will the hardware software interface of most notably, (networked) embedded systems and (multi)processing architectures. Applications are drawn from real-time control and multimedia applications such as video streaming.

This year is the third time that the course is taught, taking into account the experiences gained and feedback received during the past two years.
For the web-sites of the past years, see RTA-2003/2004 and RTA-2004/2005.

There will be 9 weeks of regular lectures. Some parts of the lectures may be used for small exercises which will be given as homework assignments. The course is completed by passing the final examination and doing a practical assignment. The assignment has to be completed before the exam in June and can be done with groups of 2 students. These groups must hand in their own, original work, programmed and reported by themselves.

On this site we will maintain the current status of the course in terms of the contents, expected reading, assignments and presented slides.

Course program

Week 1 (28-03): RTA.A1-Overview, RTA.A1-Introduction, RTA.B3-Specification concepts ;

Week 2 (04-04): Rehearse, RTA.B3-Reference model, RTA.B4-Policies-I (through slide 10);

Week 3 (11-04): Rehearse, RTA.B4-Policies-I (continued), RTA.B5-Analysis-I, RTA.B5-Analysis-II (through slide 13);

Week 4 (18-04): Rehearse, RTA.B5-Analysis-II (continued), RTA.B5-Analysis-II-summary, RTA.B5-Analysis-IV, RTA.B4-Policies-II (through slide 5);

Week 5 (25-04): Rehearse, RTA.B4-Policies-II (continued), RTA.B5-Analysis-III

Week 6 (02-05): No RTA-course!

Week 7 (09-05): No RTA-course!

Week 8 (16-05): Time Triggered and Event Triggered; Off-line Scheduling by Prof. Dr. Gerhard Fohler from the Technical University of Kaiserslautern

Week 9 (23-05): No RTA-course!

Week 10 (30-05): A QoS approach for Multimedia Consumer Terminals

Week 11 (06-06): RTA.D8-Resource Reservations, RTA.B4-Policies-III

Week 12 (13-06): Rehearse, RTA.B5-Analysis-V, RTA.C7-Mapping, RTA.C7-Mapping-example, RTA_concluding-remark

Week 13 (20-06): No RTA-course!

RTA Reading guide: The guide can be found here.

RTA binder: The binder (containing all presentations) can be found here.

Time & Location: Tuesday, 8.45-10.30, AUD-1.

Examination: There will be a final exam on Wednesday, June 28, 14.00-17.00 with a reprise on Wednesday, August 30, 09.00-12.00. You are not allowed to take any information with you to the examination! Next to the exam, there will be an assignment.

REST-tool: REST-setup.zip

Note that you need to set the language of your laptop to e.g. “English” if you want to use values for tasks that differ from Natural numbers.

Assignments: Unfortunately, we did not manage to get a practical up and running this year that would be both sufficiently challenging and not too complicated. Below, you therefore find the same exercises as last year. This has an advantage for students that have already made an exercise last year: you do not need to hand in an exercise this year again! However, please inform me by email about it, allowing me to maintain an up-to-date status.

We propose to you the same five assignments as last year. You are allowed to use any sources to support your work but you have to hand in your own original work, including relevant references (especially those that you based your work on). Any attempt of fraud will be taken very seriously. Comments on the exercises are welcome and reasonable adjustments are ok. The idea is that it takes you roughly one week and deepens your insight. So, if the amount of time required to complete an assignment becomes a problem please contact us. If useful we will make a FAQ for the exercises.

·         Exercise A: Producer/consumer with different rates;

·         Exercise B: Processor demand approach for EDF with deadlines less than periods;

·         Exercise C: Distributed clock synchronization;

·         Exercise D: Elevator system architecture;

·         Exercise E: Design of a dedicated layer supporting PCP on top of a COTS RTOS.

The due date of the assignment is the day of the examination (see above). Not making this is failing. There will be no acceptance after this date. You are expected to work in couples.

Lecturers:

R.J.Bril

          HG 5.09, tel.: 5412

 

Book: G.C. Buttazzo, “Hard real-time computing systems, predictable scheduling – algorithms and applications”, Springer, 2005, ISBN 0-387-23137-4 (2nd edition).

Related slides: http://feanor.sssup.it/~giorgio/slides/realtime/;

Errata: http://feanor.sssup.it/~giorgio/errata-HRT2.pdf and identified errors in RTA-slides and book.

Expected reading (preliminary):

[1]  R.J. Bril, E.F.M. Steffens, and W.F.J. Verhaegh, Best-case response times and jitter analysis of real-time tasks, Journal of Scheduling, 7(2): 133-147, 2004.

[2]  L. Sha, J. Lehoczky, and R. Rajkumar, Solutions for some practical problems in prioritized preemptive scheduling, In: Proc. 7th IEEE Real-Time Systems Symposium (RTSS), pp. 181 –191, 1986.

[3]  L. Steffens, G. Fohler, G. Lipari, and G. Buttazzo, Resource Reservation in Real-Time Operating Systems – a joint industrial and academic position, In: Proc. International Workshop on Advanced Real-Time Operating System Services (ARTOSS), pp. 25 – 30, July 2003.

[4]  R. Davis and A. Burns, Hierarchical Fixed Priority Pre-emptive Scheduling, In: Proc. 26th IEEE Real-Time Systems Symposium (RTSS), pp. 389 – 398, December 2005.

Further reading (preliminary):

[5]   R.J. Bril and W.F.J. Verhaegh, Towards best-case response times of real-time tasks under fixed-priority scheduling with deferred preemption, In: Proc. Work in Progress (WiP) session of the 17th Euromicro Conference on Real-Time Systems (ECRTS), Internal Report No. 1723 Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), pp. 17 - 20, July 2005.

[6]  R.J. Bril, Existing worst-case response time analysis of real-time tasks under fixed-priority scheduling with deferred preemption is too optimistic, CS-report 06-05, Technische Universiteit Eindhoven, February 2006.

[7]  G.C. Buttazzo, Rate Monotonic vs. EDF: Judgment Day, Real-Time Systems, 29(1): 5 – 26, 2005.

[8]  M. González Harbour, M.H. Klein, and J.P. Lehoczky, Fixed Priority Scheduling of Periodic Tasks with Varying Execution Priority, In: Proc. 12th IEEE Real-Time Systems Symposium (RTSS), pp. 116 – 128, 1991.

[9]  A.M. Groba, A. Alonso, J.A. Rodriques, M. Garcia Valls, Response time of streaming chains: analysis and results, In: Proc. 14th IEEE Euromicro Conference on Real-Time Systems, pp. 182 – 189, 2002.

[10]       M.H. Klein, T. Ralya, B. Pollak, R. Obenza, and M. González Harbour, A Practitioner’s Handbook for Real-Time Analysis: Guide to Rate Monotonic Analysis for Real-Time Systems, Kluwer Academic Publishers (KAP), 1993.

[11]       C.W. Mercer and S. Savage and H. Tokuda, Processor Capability Reserves: Operating System Support for Multimedia Applications, In: Proc. International Conference on Multimedia Computing and Systems (ICMCS)", pp. 90-99, May 1994.

[12]       R. Obenza, Guaranteeing real-time performance using RMA, Embedded Systems Programming, pp. 26-40, 1994.

[13]       R. Rajkumar and K. Juvva and A. Molano and S. Oikawa, Resource Kernels: A Resource-Centric Approach to Real-Time and Multimedia Systems, In: Proc. SPIE Vol. 3310, Conference on Multimedia Computing and Networking, pp. 150-164, January 1998.

[14]       M. Spuri, Analysis of Deadline Scheduled Real-Time Systems, INRIA Report 2772, January 1996.

[15]       M.A. Weffers-Albu, J.J. Lukkien, P.D.V. v.d. Stok, A Characterization of Streaming Applications Execution, In: Proc. Workshop on Resource Management for Media Processing in Networked Embedded Systems, Eindhoven, pp. 123 - 125, March 2005.