Real-Time Systems (2IN26) winter 2015 (for BIS, CSE, and ES)

 

Last update: July 7th, 2015.

 

News:

·         2015-07-07: Exam of July 3rd, 2015 including draft answers added.

·         2015-04-23: Exam of April 16th, 2015 including draft answers added.

·         2015-03-16: Presentation on FPTS removed from the schedule.

·         2015-03-06: No classes on Friday, March 20th, 2015 (due to so-called “Open Days”).

·         2015-03-02: Presentation of RTS.B5-Analysis-5-FPPS-extension moved to March 3rd, 2015.

·         2015-02-25: Link to assignments activated.

·         2015-02-13: Link to Practical training included.

 

Examinations

 

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

Examinations (including draft answers) of 2IN25 (!):

Examinations (including draft answers) of 2IN26:

·         2010/2011: November 3rd, 2010 (2XN26), January 20th, 2011 (reprise 2XN26), January 20th, 2011 (2YN26), April 11th, 2011 (reprise 2YN26).

·         2011/2012: November 1st, 2011 (2XN26), January 23rd, 2012 (reprise 2XN26), January 23rd, 2012 (2YN26), April 16th, 2012 (reprise 2YN26).

·         2012/2013: October 29th, 2012, January 23rd, 2013.

·         2013/2014: November 4th, 2013 (2XN26), January 27th, 2014 (reprise 2XN26).

·         2014/2015: April 16th, 2015 (2XN26), July 3rd, 2015 (reprise 2XN26).

 

Notes:

·         2IN20 is a 4 ECTS credits BaMa predecessor of 2IN26.

·         2IN25 is a 5 ECTS credits BaMa predecessor of 2IN26.

 

Introduction

 

The course addresses basic concepts of real-time systems, presents examples of real-time systems, covers real-time systems analysis and design, and gives an in-depth treatment of timing analysis and scheduling. The course is organized around the issue of real-time requirements and their impact on the architecture of a system. The considered system domain will be networked embedded systems. Applications are drawn from automotive domain (e.g. real-time control) and multi-media applications, such as video streaming.

The course is completed by passing an examination and doing either an assignment or a practical training. The assignment involves studying one or more articles and writing a report. The assignment can be done with groups of 4 or 5 students. These groups must hand in their own, original work, reported by themselves. The practical training involves performing weekly experiments with a set of simple real-time kernels using a simple application.

This year, there are 8 weeks of regular lectures. There will be two regular lectures per week and a tutorial session. The tutorial session consists of two hours. The first hour will be used to discuss exercises. Students are expected to make those assignments prior to the lecture. Answers to the exercises will be made available via OASE. The second hour will be used to discuss the practical training.

On this site the current status of the course will be maintained in terms of the contents, and expected reading. Slides and other material will mostly be available from OASE only.

Course objectives (high-level):

The objective of this course is to bring students into the position to analyze and (partially) design real-time systems, and conduct research in the area of real-time systems.

Course objectives (lower-level):

The student can:

(i)                   explain and apply the fundamental concepts and terminology of real-time systems;

(ii)                 explain and address the fundamental problems of real-time systems;

(iii)                analyze real-time systems designs;

(iv)                design a real-time system (at least partially); and

(v)                 identify and assess the relevant literature and research trends of real-time systems.

Preliminary course program

Classes Quartile 3 (February 2nd, 2015 – April 2nd, 2015):

Week 1 (02-02): slides: RTS.A1-Overview, RTS.A1-Introduction;
                       book: chapter 1.
           (03-02): slides: RTS.B3-Specification-concepts, RTS.D0-Water-Vessel, RTS.B3-Reference Model;
                       book: chapter 2.
           (06-02): discussion (exercises & practical training).

Week 2 (09-02): slides: RTS.B3-Reference Model (cnt’d), RTS.B4-Policies-1;
                       book: chapter 2;
                       expected reading: [4].
           (10-02): slides: RTS.B3-Cyclic Executives, RTS.B5-Analysis-1;
                       book: section 3.3, chapter 4, sections 4.1 till 4.4;
                       expected reading: “A Note on Cyclic Executives”.
           (13-09): discussion (exercises & practical training).

Week 3 (16-02): No classes (Carnaval)
           (17-02):
No classes (Carnaval)
             
(20-02): No classes (Carnaval)

Week 4 (23-02): slides: RTS.B5-Analysis-2-FPPS;
                       book: section 4.5 (excluding 4.5.3);
                       expected reading: [2].
           (24-02): slides: RTS.B5-Analysis-2-FPPS (cnt’d), RTS.C7-Periodic Tasks, RTS.B4-Policies-2-FP-servers;
                       book: chapter 5 (except for sections 5.3.1, 5.3.2, 5.3.3, 5.4.1, 5.4.3, 5.5, 5.6, and 5.7), section 10.5.4;
                       expected reading: [5].

           (27-02):
discussion (exercises & practical training).

Week 5 (02-03): slides: RTS.B4-Policies-2-FP-servers (cnt’d), RTS.B5-Policies-3-RAP;
                       book: chapter 7 (except for implementation considerations of all protocols and multi-unit aspects of SRP);
                       expected reading: [1, 3].
           (03-03): slides: RTS.B5-Analysis-5-FPPS-extensions, RTA.C6-Resource reservation;
                       book: section 4.5 (excluding 4.5.3);
           (06-03): discussion (exercises & practical training).

Week 6 (09-03): Guest lecture by Prof.Dr.-Ing.habil. C. Hentschel from the Brandenburg University of Technology of Cottbus-Senftenberg, Germany;
                       expected reading: [7].
           (10-03): Guest lecture by Prof.Dr.-Ing.habil. C. Hentschel from the Brandenburg University of Technology of Cottbus-Senftenberg, Germany.
           (13-03): discussion (exercises & practical training).

Week 7 (16-03): slides: RTS.B5-Analysis-6-FPPS-arbitrary deadlines;
           (17-03): slides: RTS.B5-Analysis-7-FPDS;
           (20-03):
No classes (Auditorium closed due to so-called “Open Days”).

Week 8 (23-03): discussion (exercises & practical training)
           (24-03): slides: RTS.B5-Analysis-8-FPDS-pessimistic, RTS.B5-Analysis-9-practical factors;
                       book: section 8.1, 8.2, 8.4 (up to and including 8.4.1).
           (27-03): discussion (exercises & practical training).

Week 9 (30-03): Guest lecture by Dr. M. Behnam from the Mälardalen University of Västerås, Sweden;
                       expected reading: [6].
           (31-03): Guest lecture by Dr. M. Behnam from the Mälardalen University of Västerås, Sweden.
           (03-04):
No classes (Good Friday)!

Week 10 (06-04): No classes (Easter Monday)!
            (07-04):
No classes (examination week)!
            (10-04):
No classes (examination week)!

Week 11 (13-04): No classes (examination week)!
             (14-04):
No classes (examination week)!
             (17-04):
No classes (examination week)!

RTA Reading guides:

·         2013/2014 (Last year!): 2IN26-reading-guide-2013/2014.

·         2014/2015: <t.b.s.>.

Examination: There will be an exam at the end of the 3rd quartile and a reprise after the 4th quartile. 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:

·         2013/2014 (Last year!): 2IN26-assignments-2013/2014.

·         2014/2015: 2IN26-assignment-2014/2015 (only available within TU/e domain or via VPN).

Guidelines for the report can be found here.

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

Practical training: information can be found here.

Lecturers:

R.J.Bril (main lecturer)

          MF 6.068, tel.: 5412

E.J. Luit (practical)

          MF 6.118, tel.: 4338

 

Guest lecturers:

  • Prof. Dr.-Ing.habil C. Hentschel, TU Cottbus (D).
  • Dr. M. Behnam, MDH Västerås (S).

 

Book: G.C. Buttazzo, “Hard real-time computing systems, predictable scheduling – algorithms and applications”, Springer, 2011, ISBN 978-1-4614-0676-1 (3nd edition).

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

Expected reading (preliminary):

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

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

[4]  J.A. Stankovic, Real-Time Computing, Byte, pp. 155 – 160, August 1992.

[5]  M. Stanovich, T.P. Baker, A.I. Wang, and M. González Harbour, Defects of the POSIX Sporadic Server and How to Correct Them, In: Proc. 16th IEEE RTAS, pp. 35 – 45, April 2010.

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

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

Further reading (preliminary):

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

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

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

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

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

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

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

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

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

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