Real-Time Architectures (2IN20) spring 2007

 

Last update: August 8th, 2008.

 

News: The examination of August 8th 2008 (including draft answers) and results are now available.

 

Examinations

 

The examinations (including draft answers) of previous years and of June 2008:

 

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 fourth time that the course is taught, taking into account the experiences gained and feedback received during the past three years.
For the web-sites of the past years, see RTA-2003/2004, RTA-2004/2005, and RTA-2005/2006.

There will be 12 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 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 (27-03): RTA.A1-Overview, RTA.A1-Introduction, RTA.B3-Specification concepts (through slide 14);

Week 2 (03-04): Rehearse, RTA.B3-Specification concepts (continued), RTA.B3-Reference model;

Week 3 (10-04): No RTA-course (due to illness of teacher).

Week 4 (17-04): Rehearse, RTA.D0-Water-Vessel, RTA.B4-Policies-I, RTA.B5-Analysis-I (through slide 20);

Week 5 (24-04): Rehearse, RTA.B5-Analysis-I (continued), RTA.B5-Analysis-II (through slide 24);

Week 6 (01-05): Rehearse, RTA.B5-Analysis-II-summary (continued), RTA.B5-Analysis-II-summary, RTA.B5-Analysis-IV, RTA.B5-Policies-II;

Week 7 (08-05): No RTA-course (examination week)!

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

Week 9 (22-05): No RTA-course (absence of teacher);

Week 10 (29-05): RTA.D1-QoS-for-MCTs;

Week 11 (05-06): lecture on Scalable Video Algorithms by Prof. Dr.-Ing. habil. Christian Hentschel from the Technical University of Cottbus, Germany;

Week 12 (12-06): lecture on Behavioural Analysis of Real-Time Systems with Interdependent Tasks by P.D.Eng. Alina Weffers-Albu from the Technische Universiteit Eindhoven;

Week 13 (19-06): RTA.D8-Resource-Reservation, RTA.B4-Policies-III, RTA.B5-Analysis-V;

RTA Reading guide: RTA Reading guide 2007.

RTA binder: RTA binder 2007.

Time & Location:

·         time: Tuesday, 8.45-10.30.

·         location: AUD. 16;

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

Visualization tools

·         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.

·         Realtime

Assignments: Below, you can find exercises of this year. Apart from exercise F, the exercises are the same 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 six assignments. 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.

·         Exercise F: Investigation of incorporation of cost of context switching, task scheduling, and budget scheduling in analysis.

·         Exercise G: Video Quality-of-Service for consumer terminals.

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.

Identified errors 2006/2007: no errors identified (yet).

Expected reading:

[1]  M. Jones, What really happened on Mars Rover Pathfinder, December 1997, http://www.cs.berkeley.edu/~brewer/cs262/PriorityInversion.html.

[2]  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.

[3]  C. Hentschel, R.J. Bril, Y. Chen, R. Braspenning, and T.-H. Lan, Video Quality-of-Service for consumer terminals - a novel system for programmable components, In: IEEE Transactions on Consumer Electronics, 49(4): 1367-1377, November 2003.

[4]  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.

[5]  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.

[6]  M.A. Weffers-Albu, J.J. Lukkien, E.F.M. Steffens, and P.D.V. van der Stok, On a Theory of Media Processing Systems Behavior, with Applications, In: Proc. 18th Euromicro Conference on Real-Time Systems, pp. 107 – 117, July 2006.

Further reading:

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

[8]  R.I. Davis and A. Burns, Resource sharing in Hierarchical Fixed Priority Pre-Emptive Systems, In: Proc. 27th IEEE Real-Time Systems Symposium (RTSS), pp. 257-267, December 2006.

[9]  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.

[10]       J. Goossens and R. Devillers, The non-optimality of the monotonic priority assignments for hard real-time offset free systems, Real-Time Systems, 13(2): 107-126, September 1997.

[11]       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.

[12]       C. Hentschel, Scalable Video Algorithms for Resource Constrained Platforms, Workshop on Resource Management for Media Processing in Networked Embedded Systems, Ed. R.J. Bril and R. Verhoeven, pp. 43 – 50, March 2005.

[13]       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.

[14]       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.

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

[16]       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.