Real-Time Architectures (2IN25) autumn 2009 (for BIS, CSE, and ES)

 

Last update: May 10th, 2010.

 

Examinations

 

The examinations (including draft answers) of (previous years of) 2IN20 (!):

Examinations (including draft answers) of 2IN25:

 

Note: 2IN20 is a 4 ECTS credits BaMa predecessor of 2IN25.

 

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, there are 17 weeks of regular lectures, divided in 2 quartiles. Some parts of the lectures will be used for small exercises which will be given as homework assignments. The course is completed by passing the final examination and doing an obligatory assignment. The assignment involves studying one or more articles, writing a report, and giving a presentation. The assignment can be done with groups of 4 or 5 students. These groups must hand in their own, original work, reported by themselves.

On this site the current status of the course will be maintained in terms of the contents, and expected reading. Assignments and presented slides will only be available from StudyWeb.

Course program (see last year’s course for a preliminary course program)

Quartile 1 (August 31th – October 23rd):

Week 1 (01-09): RTA.A1-Overview, RTA.A1-Introduction;
           (04-09): No lectures (Recap for 2IN60)

Week 2 (08-09): RTA.A1-Introduction (cnt’d), RTA.B3-Specification Concepts, RTA.B3-Reference Model
           (11-09): No lectures (Recap for 2IN60)

Week 3 (15-09): RTA.B3-Reference Model (cnt’d), RTA.D0-Water-Vessel, RTA.B4-Policies-1 (read chapter 1 & 2)
           (18-09): Exercises-1

Week 4 (22-09): RTA.B4-Policies-1 (cnt’d), RTA.B5-Analysis-1, RTA.B5-Analysis-2
           (25-09): Exercises-2

Week 5 (29-09): RTA.B5-Analysis-2 (cnt’d), RTA.B5-Analysis-6
           (02-10): guest lectures by Dr. D. Isovic from the Mälardalen University of Västerås, Sweden.

Week 6 (06-10): RTA.B5-Analysis-6 (cnt’d), RTA.B4-Policies-2
           (09-10): Exercises-3, Exercises-5

Week 7 (13-10): RTA.B4-Policies-3
           (16-10): No lectures (study information days)

Week 8 (20-10): Exercises-6, Exercises-8
           (23-10): Additional exercise

Week 9 (27-10): No lectures (examination week)!
           (30-10): No lectures (examination week)!

Week 10 (03-11): No lectures (examination week)!
             (06-11): No lectures (examination week)!

Quartile 2 (November 9th – January 30th):

Week 11 (10-11): RTA.B5-Analysis-7, RTA.B5-Analysis-8
             (13-11): Presentation of the assignments

Week 12 (17-11): RTA.D1-QoS-for-MCTs
             (20-11): Guest lecture of Mike Holenderski, Exercises-7

Week 13 (24-11): No lectures (additional lecture on Friday, November 27th, 2009)
             (27-11): guest lectures by Prof.Dr.-Ing.habil. C. Hentschel from the Technical University of Cottbus, Germany

Week 14 (01-12): RT communication
             (04-12): RTA.C7-Platform-and-Mapping, RTA.B5-Analysis-9

Week 15 (08-12): No lectures
             (11-12): Assignment 8 (FPPS and FPDS)

Week 16 (15-12): Assignment 1 (H-FPPS for independent applications)
             (18-12): Assignment 3 (Improved analysis for FPPS), Assignment 4 (Upper bounds for WR), and Assignment 5 (Efficient feasibility test for FPPS)

Week 17 (22-12): No lectures (Christmas Holidays)!
             (25-12): No lectures (Christmas Holidays)!

Week 18 (30-12): No lectures (Christmas Holidays)!
             (01-01): No lectures (Christmas Holidays)!

Week 19 (05-01): Assignment 6 (Integrating TT tasks in mC/OS-II)
             (08-01): Assignment 7 (Server design for
mC/OS-II)

Week 20 (12-01): Assignment 2 (H-FPPS for dependent applications)
             (15-01): Assignment 9 (Analysis of tasks with mixed pre-emption relations), Assignment 10 (Swift mode changes based on FPPS and SRP)

Week 21 (19-01): No RTA-course (examination week)!
             (22-01): No RTA-course (examination week)!

Week 22 (26-01): No RTA-course (examination week)!
             (29-01): No RTA-course (examination week)!

RTA Reading guide: reading guide of RTA 2008/2009 (which is also valid for this year)!

Time & Location:

Quartine \ Day

Tuesday: 10.45 – 12.30

Friday: 10.45 – 12.30

1 & 2

AUD.7

AUD.3

Examination: There will be a final exam on Friday, January 22nd, 9.00-12.00 with a reprise on Friday, April 16th, 9.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.

Visualization tools

·         Realtime

Assignments: Not making this is failing. There will be no acceptance after the examination date. You are expected to work in teams.

·         Guidelines for RTA assignments

·         Over view of assignments

·         Assignment 1: Analysis for hierarchical fixed-priority pre-emptive scheduling (independent applications)

·         Assignment 2: Analysis for hierarchical fixed-priority pre-emptive scheduling (dependent applications)

·         Assignment 3: Improved analysis for H-FPPS

·         Assignment 4: Upper bounds for worst-case response times

·         Assignment 5: Efficient feasibility test for FPPS

·         Assignment 6: Integrating Time-Trigered tasks in mC/OS-II

·         Assignment 7: Server design for mC/OS-II

·         Assignment 8: FPPS and FPDS (investigation)

·         Assignment 9: Analysis of tasks with mixed pre-emption relations

·         Assignment 10: Swift mode changes based on FPPS & SRP

Lecturers:

R.J.Bril (main lecturer)

          HG 5.09, tel.: 5412

 

Guest lecturers:

  • Dr. D. Isovic, Mälardalen University of Västerås (S);
  • Prof. Dr.-Ing.habil C. Hentschel, TU Cottbus (D);

 

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 2008/2009: Errata.

Expected reading:

[1]  Risk Forum: What really happened on Mars Rover Pathfinder, December 1997.

[2]  L. Almeida and P. Peidreiras, Scheduling with temporal partitions: response-time analysis and server design, In: Proc. 4th ACM International Conference on Embedded Software (EMSOFT), pp. 95 - 103, September 2004.

[3]  M. Behnam, Insik Shin, T. Nolte, and M. Nolin, SIRAP: A synchronization protocol for hierarchical resource sharing in real-time open systems, In: Proc. 7th ACM  & IEEE International Conference on Embedded Software (EMSOFT), pp. 279 – 288, September 2004.

[4]  M. Bertogna, N. Fisher, and S. Baruah. Static-priority scheduling and resource hold times, In: Proc. 15th International Workshop on Parallel and Distributed Real-Time Systems, pp. 1-8, March 2007.

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

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

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

[8]  R.I. Davis, A. Burns, R.J. Bril, and J.J. Lukkien, Controller Area Network (CAN) schedulability analysis: Refuted, revisited and revised, Real-Time Systems, ISSN 1573-1383 (online), http://www.springerlink.com/content/8n32720737877071/, January 30th, 2007, ISSN 0922-6443 (print), 35(3): 239-272, April 2007.

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

[10]       D. Polock and D. Zoebel,Conformance testing of priority inheritance protocols, In: Proc. 7th IEEE International Conference on Real-Time Computing Systems and Applications (RTCSA), pp. 404-408, December 2000.

[11]       I. Shin and I. Lee, Periodic resource model for compositional real-time guarantees, In: Proc. 24th IEEE Real-Time Systems Symposium (RTSS), pp. 2-13, December 2003.

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

Further reading:

[13]       R.J. Bril, J.J. Lukkien, and W.F.J. Verhaegh, Worst-case response time analysis of real-time tasks under fixed-priority scheduling with deferred preemption, Real-Time Systems Journal, ISSN 1573-1383 (online), DOI 10.1007/s11241-009-9071-z, http://www.springerlink.com/content/f05r404j63424h27, April 28th, 2009, ISSN 0922-6443 (print), 42(1-3): 63 – 119, August 2009.

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

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

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

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

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

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

[20]       J.W.S. Liu, Real-Time Systems, Prentice Hall, 2000.

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

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

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

[24]       D. Zoebel and P. Polock and A. van Arkel, Testing for the Conformance of Real-time Protocols Implemented by Operating Systems, Electronic Notes in Theoretical Computer Science, Vol. 133, pp. 315- 332, May 2005. http://www.sciencedirect.com/science/journal/15710661