Real-Time Architectures (2IN20) spring 2005

 

Examinations

 

The examination of

  • August 23rd, 2005 with (draft) answers may be found here.
  • June 23rd, 2005 with (draft) answers may be found here.

 

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 second time that the course is taught, taking into account the experiences gained and feedback received during last year’s course. The web-site of last year’s course may be found here.

There will be 10 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 start of the new term in September 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 (25-03): holiday

Week 2 (01-04): A1-Overview, A1-Introduction (Dr. Johan J. Lukkien), B3-Specification concepts (Dr. Johan J. Lukkien), B3-Reference Model

Week 3 (08-04): Rehearse, B4-Scheduling-Policies-I, B5-Scheduling-Analysis-I

Week 4 (15-04): Rehearse, D2-Example: real-time data bases (Dr. Peter D.V. van der Stok)

Week 5 (22-04): Rehearse, B5-Scheduling-Analysis-II, B5-Scheduling-Analysis-III

Week 6 (29-04): no lectures (week of exams)

Week 7 (06-05): holiday

Week 8 (13-05): B6-Design of real-time systems (Prof.dr. Gerhard Fohler

)

Week 9 (20-05): D9-Example: Video streaming over network (Dr. Peter D.V. van der Stok) and D10-Example of a distributed real-time algorithm: Clock synchronization (Dr. Peter D.V. van der Stok)

Week 10 (27-05): Rehearse, B5-Scheduling-Analysis-IV, B4-Scheduling-Policies-II, B4-Scheduling-Policies-III

Week 11 (03-06): C7-Mapping & C7-Real-time operating systems (Dr. Johan J. Lukkien)

Week 12 (10-06): Rehearse, D8-Reservations

RTA binder: A single PDF-file with all presentations (apart from three presentations, 4 slides are printed on one side of a page) may be found here.

Time & Location: Friday, 13.30-15.30, AUD 15.

Examination: There will be a final exam on Thursday, June 23, 9.00-12.00 with a reprise on Tuesday, August 23, 14.00-17.00. You are allowed to take copies of slides and papers to the exam. However, you are not allowed to take books with you! Next to the exam, there will be an assignment.

Assignments: We propose to you a choice of five assignments. Note that assignments A, C, and D are the same as, i.e. re-used from, 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. Note: we have to review these exercises internally so there may be small adaptations later.

·         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 assignment is due the first day of the next term (September 1st, 2005, hand it in to Bril). Not making this is failing. There will be no acceptance after this date. You are expected to work in couples.

Lecturers:

J.J. Lukkien

HG 5.07, tel.: 5147

P.D.V.v.d.Stok

          HG 5.08, tel.: 8209 (secr.)

R.J.Bril

          HG 5.09, tel.: 5412

 

Book (you’re free to chose):

·         G.C. Buttazzo, “Hard real-time computing systems, predictable scheduling – algorithms and applications”, Kluwer Academic Publishers, 1997, ISBN 0-7923-9994-3 (1st edition).

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

 

Reading guide (preliminary)

Expected reading:

[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, 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.

Further reading:

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

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

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

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

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

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

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

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